1.
문제 : 뉴스 전하기
2.
알고리즘 : DP, 그리디, 정렬, 트리, 트리에서의 DP
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : DFS로 모든 트리를 순회하되, 한 노드에서 각 DFS한 결과를 정렬한 뒤 순서에 따른 시간을 추가해주면 된다.
1.
문제 : 도로포장
2.
알고리즘 : DP, 그래프 이론, 최단 경로, 데이크스트라
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : K개 이하의 도로를 포장해 1에서 N으로 갈 때 걸리는 최소 시간을 구하는 문제. K개 이하의 도로를 포장한다는 문장에 주목하면 각 DP에서 다음 상태로 진행할 때, 도로 포장 여부에 따라서 상태가 변경되므로 2차원 DP로 풀면 된다. 그리고 도시의 수 max 10,000 x 걸리는 시간 max 1,000,000 = 100억 정도 되므로 int가 아니라 long으로 풀자.
1.
문제 : K번째 수
2.
알고리즘 : 이분 탐색, 매개 변수 탐색
3.
성공 여부 : 실패
4.
풀이 : 패스
5.
복기 : A[i][j] = i x j인 이차원 배열이 있을 때, 배열의 수를 일차원 배열 B에 넣고 오름차순으로 정렬했을 때, K번째 수를 구하는 문제. i행의 숫자들은 i * 1, i * 2, i * 3, …, i * j로 이루어져 있으므로, i행의 숫자들 중 임의의 a값보다 작거나 같은 숫자의 개수는 i * j ≤ a를 만족하는 j의 개수라는 아이디어를 떠올려야 한다. 이를 이용해 left = 1, right = N * N를 베이스로 이분탐색을 진행해 lower_bound로 K가 되는 mid값을 찾으면 정답이다.
1.
문제 : 백조의 호수
2.
알고리즘 : 자료 구조, 그래프 이론, 그래프 탐색, BFS, 분리 집합, 격자 그래프
3.
성공 여부 : 성공 (1시간 30분)
4.
풀이 : 패스
5.
복기 : 단순한 버전관리 BFS문제인 줄 알았는데, R, C 범위가 1,500이라 상당히 까다로웠다. 총 map의 크기가 1,500 x 1,500 = 2백만이 넘다보니 일반적인 이중 for문으로 다음 녹을 얼음을 체크할 수 없었다. 풀이 방법으로는 녹을 얼음에 대한 큐와 백조가 다음에 이동할 좌표를 담은 큐를 사용하는 것이다. 백조가 이동하다가 얼음에 막혔다면 그 좌표는 다음 턴에 얼음이 녹을 것이므로 백조가 다음 이동할 수 있는 좌표가 된다.
1.
문제 : 사탕상자
2.
알고리즘 : 자료 구조, 세그먼트 트리, 이분 탐색
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : 대놓고 세그먼트 트리를 요구하는 문제. 맛의 좋고 나쁨의 척도가 1 - 1,000,000까지 있을 때, 사탕을 넣는 쿼리, n번째 사탕을 빼는 쿼리 두 가지를 구현하는 문제였다.
1.
문제 : GCD(n, k) = 1
2.
알고리즘 : 수학, 정수론, 오일러 피 함수
3.
성공 여부 : 실패
4.
풀이 : 패스
5.
복기 : 오일러 피 함수를 그대로 사용하는 문제. 오일러 피 함수에 대해서 알고 있어야 한다.
1.
문제 : 철로
2.
알고리즘 : 자료 구조, 정렬, 스위핑, 우선순위 큐
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : 마지막 끝나는 지점을 기준으로 정렬하는 것이 키 포인트. 이후 우선순위 큐를 이용해 하나씩 넣다가 새로 들어오는 노선의 끝나는 지점과 우선순위 큐의 첫번째 요소의 시작점의 차이가 d보다 크면 하나씩 빼면서 우선순위 큐의 size를 재면 된다.
1.
문제 : 수열과 쿼리 16
2.
알고리즘 : 자료 구조, 세그먼트 트리
3.
성공 여부 : 실패
4.
풀이 : 패스
5.
복기 : 세그먼트 트리를 이용해서 크기가 가장 작은 인덱스를 찾는 문제. 인덱스만을 리턴해서 계산해야 한다.
1.
문제 : 개미
2.
알고리즘 : 자료 구조, 그래프 이론, 그래프 탐색, DFS, 희소 배열
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : DFS + 스택 + 이분탐색을 적절히 사용하는 문제. 각 개미가 가진 에너지만큼 루트 노드를 향해 올라가야 하므로 DFS를 통해 탐색하면서 거리를 저장하고 스택에 넣은 뒤 이분탐색을 통해서 최대한 갈 수 있는 위치를 찾으면 된다. 이분탐색 시에 스택에 들어 있는 가장 큰 거리에서 mid의 거리를 뺀 값이 남아있는 에너지보다 큰 지 작은 지를 비교하는 것이 핵심
1.
문제 : 공장
2.
알고리즘 : 자료 구조, 세그먼트 트리
3.
성공 여부 : 실패
4.
풀이 : 패스
5.
복기 : 케이블 문제와 비슷해보이지만, 교차하는 점의 개수를 구해야 하는 문제이므로 접근을 다르게 해야 한다. 즉 역순쌍을 구하는 문제로, 머지 소트 혹은 세그먼트 트리로 풀 수 있다. 머지 소트로 풀면, 머지 단계에서 left 배열과 right 배열을 합칠 때, 오른쪽 배열의 값보다 왼쪽 값이 클 경우, 왼쪽 배열의 남은 개수만큼 역순쌍이 생긴다는 원리를 통해 풀어야 한다.
1.
문제 : 단절점
2.
알고리즘 : 그래프 이론, 그래프 탐색, DFS, 단절점과 단절선
3.
성공 여부 : 실패
4.
풀이 : 패스
5.
복기 : 단절점을 구하는 방법을 떠올려야 풀 수 있는 문제. 주어진 그래프에서 단절점을 구하기 위해서는 어떤 한 정점 A를 기준으로 DFS를 수행하면서 방문하는 정점에 순서대로 넘버링을 한다. 그리고 A 정점의 넘버와 비교했을 때 이후에 방문한 정점들에서 얻은 최소 넘버가 A 정점의 넘버보다 높다면, 이후에 방문한 정점들에서는 A 정점 이전의 정점을 방문할 수 없다는 뜻이므로 A 정점이 단절점이 된다. 예외 케이스로 A 정점이 시작점, 즉 루트 노드라면 이 A 정점에서 갈 수 있는 다른 정점(Child)의 개수가 2개 이상이라면 단절점이 된다.
1.
문제 : 휴대폰 자판
2.
알고리즘 : 자료 구조, 문자열, 트리, 트라이
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : 트라이 구조를 구현해 각 단어를 완성할 수 있는 버튼 입력 횟수의 평균을 구하는 문제. 임의의 노드 이하에 존재하는 단어의 개수를 별도로 저장해 만약 단어의 개수가 1이 되면 더 이상 탐색하지 않고 지금까지의 버튼 입력 횟수를 리턴시켜주는 식으로 최적화했다.
12
0
