그리디, DFS/BFS, DP의 난이도

코딩 테스트에서는 알고리즘의 구현법을 외우는 것보다 문제를 보고 어떤 알고리즘을 적용할지 판단하는 능력이 더 중요하다.

한눈에 비교하기

알고리즘	유형 파악	구현 난이도	핵심
DFS/BFS	비교적 쉬움	보통	문제를 그래프 탐색으로 표현하기
DP	어려움	보통	상태를 정의하고 점화식 찾기
그리디	어려움	비교적 쉬움	선택 기준을 찾고 정당성 증명하기

DFS/BFS

DFS와 BFS는 비교적 유형을 알아보기 쉽다.

격자나 그래프에서 영역의 개수, 연결 여부, 이동 가능성 등을 묻는다면 탐색을 떠올릴 수 있다.

• DFS: 한 경로를 깊게 탐색하거나 모든 경우를 확인할 때 사용한다.
• BFS: 가까운 곳부터 탐색하며, 가중치가 없는 그래프의 최단 거리를 구할 때 주로 사용한다.

구현에 익숙해진 후에는 방문 처리 시점과 상태 표현이 주요 관건이 된다.

DP

DP의 핵심은 상태 정의와 점화식 발견이다.

완전탐색으로 풀었을 때 동일한 계산이 반복되고 경우의 수가 너무 많아진다면 DP를 의심해 볼 수 있다.

DP 문제를 풀 때는 다음 두 가지를 먼저 생각해야 한다.

1. dp[i]는 무엇을 의미하는가?
2. 이전 상태로부터 현재 상태를 어떻게 계산할 것인가?

특히 dp[i]의 의미를 한 문장으로 명확하게 정의하는 것이 중요하다.

그리디

그리디는 구현 자체는 간단한 경우가 많지만, 문제를 그리디로 풀 수 있다는 사실을 알아내는 과정이 어렵다.

단순히 현재 가장 좋아 보이는 선택을 하는 것이 아니라, 그 선택이 미래의 가능성을 해치지 않고 항상 최적해로 이어진다는 근거가 필요하다.

즉, 선택 기준을 찾는 것뿐만 아니라 다음 질문에 답할 수 있어야 한다.

지금의 선택이 항상 최적해로 이어지는가?

정리

알고리즘	스스로 던질 질문
DFS/BFS	정점과 간선으로 표현해서 탐색할 수 있는가?
DP	작은 문제의 답을 저장하고 재사용할 수 있는가?
그리디	지금의 최선이 전체의 최선임을 증명할 수 있는가?

결국 코딩 테스트에서 중요한 것은 알고리즘 코드를 암기하는 일이 아니다.

문제의 구조를 파악하고, 왜 이 알고리즘이 적절한지 설명할 수 있어야 한다.