무조건 해당 유형이다라는 의미가 아니며, 높은 확률로 해당 유형일 수 있다는 가정입니다.

입력값이 작은 문제

→ 완전탐색 or 백트래킹 문제

지도가 주어지고 특정 요소 및 영역을 찾아야 하는 경우

→ BFS or DFS

그래프 그림이 있는 경우

→ 높은 확률로 세가지 유형 중 하나

• 최소 신장 트리 : “가장 저렴한 방법으로 모두 연결” → 크루스칼, 프림 알고리즘
• 위상 정렬 : “가장 빠른 길”, “최단거리” 와 비슷한 키워드가 나오거나 “X비용 내로 갈 수 있는 길을 찾아라” → 최단거리 찾기 → 다익스트라, BFS, DFS
  • “순서”, “차례” 등의 키워드가 나오면 위상정렬 문제, 위상정렬은 순서를 정해야 할 때 사용

X라는 조건을 만족하는 가장 최대/최소값을 찾아라

→ 결정 문제 → 파라메트릭 서치

실시간으로 정렬이 이루어져야 하는 경우

→ 우선순위 큐 or 힙

DP 문제

→ 보통 문제를 보고 바로 유형을 파악하기 힘든 경우 DP처럼 풀 수 있는지 확인 필요

1. 문제를 따라 먼저 초기값을 적는다.
2. 초기값을 포함해 모든 상태값을 적는다.
3. 현재상태를 통해 다음 값을 구할 수 있는지 판단한다.
4. 혹은 이전상태들을 통해 현재값을 구할 수 있는지 판단한다.