🪨 🪨 🪨

https://www.acmicpc.net/problem/27210 27210번: 신을 모시는 사당 칠할 수 있는 돌상의 개수에 제한은 없으며, 반드시 연속한(인접한) 돌상들만 칠할 수 있음(띄엄띄엄 칠할 수 없음)에 유의하라. www.acmicpc.net 원티드 쇼미더코드 3회차 문제 중 풀이에는 가장 짧은 시간이 들었지만, 코드가 가장 자신 없는 문제이다. 우선, 돌상이 왼쪽을 보고 있을 때는 누적값에 1을 더해주고, 돌상이 오른쪽을 보고 있을 때는 1을 빼주는 방식으로 누적값(curr 변수)을 계산했다. 예시를 하나 만들어보자면, 누적값을 아래와 같이 계산할 수 있다. 인덱스 : 0 1 2 3 4 5 6 7 8 9 10 방 향 : 왼 오 왼 왼 오 오 오 오 오 왼 누적값 : 0 1 0 1 2 1 ..

https://www.acmicpc.net/problem/27211 27211번: 도넛 행성 준겸이는 $N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 www.acmicpc.net 문제의 그림이 어마무시했는데... 그냥 그래프 탐색 문제였다. 4963번 섬의 개수, 혹은 2667번 단지번호붙이기와 유사한 문제이다. 유일하게 추가된 조건은 0번 행과 (N-1) 번 행이 연결되어 있고, 0번 열과 (M-1) 번 열이 연결되어 있다는 점이다. 이 조건을 고려해서 인접한 칸을 탐색할 때 0

https://www.acmicpc.net/problem/27212 27212번: 미팅 오늘은 A대학의 학생 $N$명과 B대학의 학생 $M$명이 만나는 날이다. 이들이 만나는 장소에는 크고 길이가 긴 식탁이 하나 있어서, 한쪽에는 A대학 학생이, 다른 한쪽에는 B대학 학생이 앉을 예정이 www.acmicpc.net 악수 얘기만 들었을 때는 전깃줄 문제가 떠올랐는데 갑자기 만족도를 구하라고 한다. DP로 접근해서 해결했다. dp[a][b]는 A대학 a번 학생이 B대학에서 b번 이하의 학생과 악수를 할 수 있을 때 얻을 수 있는 총만족도의 최댓값으로 정했다. 말이 이상한데, 예를 들어 문제의 예제를 살짝 변형해서 아래와 같은 조건이 있다고 치자. W = | 10 1 | | 1 10 | A = [1, 2] B..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 스탠다드한 그래프 탐색 문제이다. - DFS 풀이 컴퓨터(노드) 간의 연결 정보는 graph라는 이차원 배열에 저장했다. graph[n]에는 n번 컴퓨터와 연결된 컴퓨터들을 저장한다. 예를 들어 1번 컴퓨터가 2, 4번 컴퓨터와 연결되어 있다면 graph[1] = [2, 4]가 된다. 그다음 그래프에 컴퓨터들 간의 연결관계를 input 받아서 저장한다. 1번과 2번 컴퓨터가 서로 연결되어 있다면 gra..

https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 두 원의 교점의 수를 구하는 문제이다. 중학교였나 고등학교였나 먼 과거에 배웠던 내용인데, 경우만 잘 따져주면 된다. 먼저, 두 점 사이의 거리 공식을 이용해 원의 중심 사이의 거리인 d를 구해준다. #1 원의 중심이 동일하고 반지름도 동일하다면 두 원이 서로 같고, 접점의 개수가 무한대이다. -1을 출력한다. #2 두 원의 반지름의 합(r1 + r2)이 d와 같거나 반지름의 차(abs(r1 - r2))가 d와 같다면 각각 외접, 내접하는 경우이다...

https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net set 자료형을 이용해서 데이터를 다루는 문제이다. 데이터의 수가 최대 10 ** 6이어서 빠른 입출력을 사용하지 않거나 list를 사용하면 시간 초과가 난다. at_company라는 set 자료형을 생성해 줬다. 한 줄씩 input을 받으면서 만약 출근을 했다면 at_company에 add 해주고, 퇴근을 했다면 at_company에서 remove 해준다...

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net dp와 수학 두 가지 방법으로 풀었다. - dp 풀이 dp 배열을 선언해 여기에 답을 저장해가며 풀 수 있다. dp[n]은 n kg의 설탕을 옮기는 데 필요한 최소한의 봉지의 수를 의미한다. 계산이 귀찮지 않도록 dp[3]과 dp[5]는 1로 초기화해 준다. dp의 길이가 (N+1)이 아니라 max(6, N+1)인 이유는 초기화 과정에서 index 에러가 발생하지 않도록 하기 위함이다. 6 kg부터 N kg..

2022년 하반기 코딩 테스트를 응시하며 느꼈던 점 및 공부한 방법 등을 정리해두었다. PS(문제풀이) 고수가 아닌 비전공자 취준생 현지인 시점에서 공부한 방법과 느낀 점 등을 정리해본다. 목차 1. 코딩 테스트 언어 2. 공부 방법 - 자료구조/알고리즘 - 문제 풀이 - 문제 플랫폼 - 백준 문제집 추천 3. 코딩 테스트 난이도 #순한맛 #진라면 #신라면 4. SQL 문제 하반기에는 총 18번의 코테에 응시했고, 11번을 합격했다. 서류도 함께 본 경우도 있었지만 생각보다는 타율이 낮다. 본격적인 공채 시즌 전에는 백준 솔브닷 티어 골드 2 정도였고, 시즌 막바지부터 취미로 알고리즘 문제를 열심히 풀어서 현재는 플래티넘 5 턱걸이 상태이다. 국비 최종 프로젝트 종료 거의 직후에 채용 시즌이 시작되었다...

처음 백준을 접할 때 입력, 출력 관련해서 고생을 좀 했었어서 기록을 남겨본다. 1. 입력이 한 줄에 하나씩 들어옴 input() 함수를 통해 입력을 받을 수 있다. 단, string으로 입력값이 받아지므로 숫자로 받고 싶다면 형 변환이 필요하다. N = input() # N = "3" N = int(input()) # N = 3 입력값이 여러 줄인 경우에도 마찬가지이다. N = int(input()) # N = 5 for _ in range(N): print(input()) # 이후의 입력을 한 줄씩 프린트 파이참에서 input() 함수로 입력값을 받을 때, 백준 예제 입력을 복붙해서 엔터를 치면 마지막 줄 입력값이 반영이 안 되는 경우가 자주 있다. 이런 경우에는 그냥 엔터만 한 번 더 쳐주면 정상적..

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 가장 잘 알려진 풀이는 스택을 두 개 사용하는 것이다. 커서를 기준으로 왼쪽에 위치한 스택과 오른쪽에 위치한 스택 두 개를 만든다. 오른쪽 스택은 방향을 뒤집어두었다. pop 하면 왼쪽에 있는 원소가 나오고, append도 왼쪽에 된다. 처음에는 문장의 맨 뒤에 커서가 위치하므로 왼쪽 스택에 문자를 순서대로 넣어두면 된다. 커서는 항상 left 리스트 오른쪽에 있다. 만약 "P"라는 명령어가 들어오..