입력이 100 이하인 경우
- 완전 탐색
- 백트래킹
입력이 10,000 이하인 경우
- 최대 O(n^2) 이내로 끝내야하는 문제
- 문제에 따라 O(n^2 log n)까지는 허용
- n*n 2차원 리스트를 모두 순회해야하는 문제가 많음
입력이 1,000,000 이하인 경우
- 최대 O(n log n)으로 끝내야하는 문제
- 힙, 우선순위 큐
- 정렬
- 동적 계획법
- 위상 정렬
- 다익스트라 알고리즘
입력이 100,000,000 이하인 경우
- 최대 O(n)으로 끝내야하는 문제
- 동적 계획법
- 그리디
최대 O(log n)으로 끝내야하는 문제가 많음
- 거의 안나오는 문제 유형
- 이진탐색
지도가 주어지고 채워진 영역을 찾아야하는 경우
- 높은 확률로 BFS, DFS 문제
그래프 그림이 있는 경우
- 최단 거리 찾기
문제에서 "가장 빠른 길", "최단 거리"와 비슷한 키워드가 나온다면 당연히 최단 거리 찾기 유형이고 "X 비용 내로 갈 수 있는 길을 찾아라"와 같은 키워드가 나와도 최단 거리 찾기 유형입니다. 다익스트라, BFS, DFS 등이 사용될 수 있다
- 최소 신장 트리
최소 신장 트리 문제는 보통 "가장 저렴한 방법으로 모든 경로 연결해라" 등의 키워드로 출제됩니다. 경로가 아니라 통신망, 전송 시간, 회로, 배관 등 다양한 용어로 나올 수는 있지만 핵심은 모든 경로를 "가장 싸게 연결해라"입니다. 그래프는 양방향일수도 단방향일수도 있습니다. 크루스칼, 프림 알고리즘을 사용할 수 있다.
- 위상 정렬
위상 정렬은 순서를 정해야할 때 사용됩니다. 보통 "순서", "차례" 등의 키워드가 나오면 위상 정렬 문제입니다.
X라는 조건을 만족하는 가장 최대/최소값을 찾아라
- 이 경우 높은 확률로 결정 문제입니다. 파라메트릭 서치를 이용해서 풀 수 있습니다.
실시간으로 정렬이 이루어져야 하는 경우
- 높은 확률로 우선순위 큐 혹은 힙을 사용하는 문제입니다.
DP 문제
- 보통 완전 탐색처럼 시간이 오래걸리면 안되는데 특별한 알고리즘을 사용하는 문제가 아닐거 같을 때는 높은 확률로 DP 문제
- 현재상태를 통해 다음 값을 구할 수 있는지 판단한다.
- 혹은 이전 상태들을 통해 현재 값을 구할 수 있는지 판단한다. 이런식으로 여러 번 해보고 식을 만들 수 있다면 100% DP 문제
문자열이 주어지는 경우
- 구현력 문제인 경우가 많다. 문자열을 자르거나, 붙이거나 탐색하는 문제가 대부분.
현재 상황에서 가장 최적인 선택을 해야하는 경우
- 문제에서 항상 최적의 선택을 해야하는 경우 혹은 "가장 많은 선택을 할 수 있는", "가장 작은/큰" 등의 키워드가 들어가면 그리디 문제일 가능성이 높다.
대구 사나이