1.
문제 : 꼬인 전깃줄
2.
알고리즘 : 이분 탐색, LIS
3.
성공 여부 : 성공(5분)
4.
풀이 : 패스
5.
복기 : 대표적인 LIS 응용 문제
1.
문제 : 트리
2.
알고리즘 : 트리, 분할 정복, 재귀
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 전위 순회와 중위 순회의 결과를 통해서 바이너리 트리를 만들 수 있는지 묻는 문제. 중위 순회는 node의 왼쪽을 먼저 확인하고 난 뒤, 방문하므로 node는 범위의 중간에 위치한다는 특징을 알아야 한다.
1.
문제 : 히스토그램에서 가장 큰 직사각형
2.
알고리즘 : 자료 구조, 분할 정복, 스택
3.
성공 여부 : 성공 (50분)
4.
풀이 : 패스
5.
복기 : n개의 직사각형들로 이루어진 히스토그램에서 넓이가 가장 큰 직사각형을 구하는 문제. 인접한 직사각형들 간의 연관성을 고려해 문제를 풀어야 했고, n의 범위가 10만이라 스택을 이용해 풀면 될 것 같았다. 기존 직사각형보다 높이가 높은 직사각형은 push하고, 같으면 개수를 1 늘리고, 작으면 스택 내부에서 같거나 작은 값이 나올 때까지 pop을 하는 방식으로 풀었다. 높이가 0인 직사각형을 유의해야 함
1.
문제 : LCA 2
2.
알고리즘 : 자료 구조, 트리, LCA, 희소 배열
3.
성공 여부 : 실패
4.
풀이 : 보류
5.
복기 : LCA 문제지만, 일반적인 풀이로 풀면 O(N * M)의 시간 복잡도가 걸리므로 시간 초과가 발생한다. 부모 배열을 이차원 배열로 선언하고, 2의 제곱수만큼 건너 뛰면서 부모 배열을 완성한 뒤, 구해야 한다. 추후 블로그 포스트로 작성하면서 더 공부할 예정
1.
문제 : 사회망 서비스(SNS)
2.
알고리즘 : DP, 트리, 트리에서의 DP
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 트리 구조에서 인접한 모든 노드가 얼리어답터일 때, 해당 노드는 새로운 아이디어를 받아들인다고 한다. 모든 사람이 새로운 아이디어를 수용하기 위한 최소 얼리 어답터의 수를 찾는 문제. 정점 수가 MAX 100만이라서 처음에 그냥 dfs로 풀었더니 시간 초과가 발생했다. 그래서 dp를 사용함
1.
문제 : ABCDE
2.
알고리즘 : 그래프이론, 그래프 탐색, DFS, 백트래킹
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 인접 리스트로 친구 관계를 저장하고 각 노드를 시작점으로 DFS를 돌면서 깊이가 5이상 되는 게 있는지 확인하는 문제
1.
문제 : 중앙값 구하기
2.
알고리즘 : 자료 구조, 우선순위 큐, 집합과 맵
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 숫자를 추가할 때 홀수 개수마다 중앙값을 구하는 문제. 이러한 중앙값 문제를 maxQ와 minQ를 사용해
1.
문제 : 코드트리 투어
2.
알고리즘 : 시뮬레이션, 다익스트라, 우선순위 큐
3.
성공 여부 : 성공 (1시간 30분)
4.
풀이 : 코드트리 투어
5.
복기 : 삼성 코딩테스트 2024년 상반기 오후 2번 문제. 도시들 간의 최단 경로를 찾고, 이를 기반으로 최적의 여행 상품을 선택해 판매하는 문제. 모든 면에서 최적화를 할 수 있어야 시간 초과가 나지 않음.
1.
문제 : 여왕 개미
2.
알고리즘 : 이분 탐색, 그리디
3.
성공 여부 : 성공 (30분)
4.
풀이 : 여왕 개미
5.
복기 : 삼성 코딩테스트 2025년 상반기 오후 2번 문제. 개미집들이 x좌표 상에 정렬된 상태로 주어질 때, 정찰에 걸리는 최소 시간을 구하는 문제. x 좌표 상에 정렬된 상태라는 사실을 근거로 이분 탐색으로 풀 수 있음.
1.
문제 : 플로이드
2.
알고리즘 : 그래프 이론, 최단 경로, 플로이드-워셜
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 플로이드-워셜은 모든 노드 간의 최소 경로를 구할 수 있는 알고리즘. 그렇지만 3중 반복문을 사용해서 해결하므로 N의 크기가 큰 경우 사용할 수 없음.
1.
문제 : 공유기 설치
2.
알고리즘 : 이분 탐색, 매개 변수 탐색
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 이분탐색을 이용해 인접한 공유기 사이의 최소 거리를 가장 크게 하는 값을 찾는 문제. 인접한 공유기 사이의 최소 거리를 찾기 위해 이 값을 mid로 두고, 첫번째 집에 공유기를 설치한 뒤, 그 다음 집들을 확인하면서 (현재 집 위치) - (이전 공유기가 설치된 위치) 가 mid 이상이 되었을 때, 새롭게 공유기를 설치함. 이렇게 설치한 공유기의 개수와 문제에서 주어진 공유기 설치 개수를 비교해 설치한 공유기의 개수가 더 크면, 아직 mid를 증가시킬 수 있는 가능성이 있으므로 l = mid + 1로 설정
1.
문제 : 플로이드 2
2.
알고리즘 : 그래프 이론, 최단 경로, 플로이드-워셜, 역추적
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : ‘플로이드’ 문제의 확장판으로 경로까지 추적하는 문제. 다익스트라, 벨만-포드 등은 역방향 추적을 통해 경로를 찾아내지만, 플로이드-워셜 알고리즘은 i → j로 가는 경로를 k를 경유해서 더 짧게 만들 수 있는지를 삼중 반복문으로 업데이트해나가는 알고리즘이기 때문에, 자연스럽게 순방향 확장됨. 따라서 순방향으로 경로를 추적해야 함.
1.
문제 : 피보나치 수 6
2.
알고리즘 : 수학, 분할 정복을 이용한 거듭제곱
3.
성공 여부 : 성공 (20분)
4.
풀이 : 패스
5.
복기 : 피보나치 수는 유명한 점화식으로 이루어진 수열. 선형대수에서 배웠던 것처럼 행렬을 제곱해나가면서 풀면된다.
1.
문제 : 미생물 연구
2.
알고리즘 : 시뮬레이션, BFS
3.
성공 여부 : 성공 (2시간)
4.
풀이 : 패스
5.
복기 : 빡 구현 문제. 메서드를 하나하나 차근차근 구현하면서 풀면 된다. 조건을 하나도 빠뜨리지 않아야 한다.
1.
문제 : 궁금한 민호
2.
알고리즘 : 그래프 이론, 최단 경로, 플로이드-워셜
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : 플로이드 워셜의 결과를 통해 원래 도로가 어떻게 생겼는지 예측하고 도로의 가중치를 더해서 출력하는 문제. 플로이드 워셜의 결과에 다시 한번 플로이드 워셜 알고리즘 (cost[i][j] = cost[i][k] + cost[k][j])을 수행했을 때, 모든 k에서 cost[i][j] == cost[i][k] + cost[k][j]인 결과가 없다면 cost[i][j]인 경로는 대체될 수 없다는 것을 이용해서 풀면 된다.
1.
문제 : 네트워크 복구
2.
알고리즘 : 그래프 이론, 최단 경로, 데이크스트라
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 슈퍼컴퓨터 노드(1번)부터 모든 경로의 최소 거리를 만들 수 있는 필수 간선들의 개수를 찾고, 간선을 출력하는 문제. 데이크스트라의 구성 경로를 찾는 방법을 응용하면 된다.
1.
문제 : 화물차
2.
알고리즘 : 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 최단 경로, 데이크스트라
3.
성공 여부 : 성공 (1시간 30분)
4.
풀이 : 패스
5.
복기 : 2차원 공간에서 화물차가 A에서 B로 이동할 때, 중간에 신호등이 있다. 신호등은 주기에 따라 가로 통행, 세로 통행이 바뀌는데, 이를 감안해서 최단 경로를 구하는 문제. 다익스트라를 베이스로 하면서 신호등을 만났을 경우, 주기에 따라 가장 빠르게 신호등에 진입할 수 있는 시점을 구해서 더해주면 된다. 다만, 해당 문제에서는 입력이 기존 포맷과 다르게 주어지므로 입력을 잘 처리할 수 있도록 구성하는 것이 어려웠다.
1.
문제 : 타일 채우기 2
2.
알고리즘 : 수학, DP, 분할 정복을 이용한 거듭제곱
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : 3 x N크기의 벽을 2 x 1, 1 x 2 크기의 타일로 채우는 문제. 벽의 높이가 2가 아니라 3이라서 조금 까다로웠다. 또, N의 범위가 무지막지하게 크기 때문에 점화식을 구했다 하더라도 일반적인 DP로는 구하기 어렵고, 행렬을 구한 뒤 거듭제곱하는 형태로 결과를 구해야 했다.
1.
문제 : 전깃줄 - 2
2.
알고리즘 : LIS. 역추적
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : 대표적인 LIS 활용 문제인 전깃줄 문제. 하지만 구해야 하는 건 제거해야 할 전깃줄의 개수와 전깃줄 위치이므로, 두 개의 배열 인덱스 배열과 prev배열을 통해 역추적으로 남아있어야 할 전깃줄을 구한 뒤 거기에 포함되지 않는 전깃줄의 위치를 출력하는 형태로 문제를 풀 수 있다.
30
0
