동적계획법(DP)과 그리디, 왜 풀이가 완전히 다를까?

코딩테스트를 준비하다 보면 많은 사람이 특정 시점에서 막히기 시작한다. 구현과 자료구조 문제는 어느 정도 풀리는데, DP와 그리디 문제가 등장하는 순간 갑자기 접근 방향이 보이지 않는 경우가 많다. 특히 두 알고리즘 모두 최적의 결과를 찾는다는 설명을 듣다 보니 무엇이 어떻게 다른지 혼란스러워지는 경우가 많다.

실제로 DP와 그리디를 가장 어려워하는 이유는 문제 풀이 자체보다 사고 방식이 완전히 다르기 때문이다. 둘 다 최적화를 목표로 하지만, 선택을 누적하는 방식과 정답을 찾는 흐름은 전혀 다르다.

DP와 그리디는 둘 다 최적화를 목표로 한다

두 알고리즘 모두 최소 비용, 최대 효율, 최단 거리 같은 문제를 해결할 때 자주 사용된다. 하지만 많은 초보자가 여기서부터 두 알고리즘을 같은 방식으로 이해하기 시작한다.

DP는 이전 계산 결과를 저장하면서 여러 가능성을 비교한다. 반면 그리디는 현재 시점에서 가장 좋아 보이는 선택을 즉시 결정한다. 즉, DP는 여러 경우를 누적해서 최적해를 찾고, 그리디는 현재 선택이 미래에도 최적이라는 가정을 기반으로 움직인다.

이 차이를 이해하지 못하면 DP 문제를 그리디처럼 접근하다가 반례에서 틀리는 경우가 많다. 실제 코딩테스트에서도 초보자들이 자주 겪는 실수 중 하나다.

DP는 이전 결과를 저장하면서 문제를 해결한다

DP의 핵심은 작은 문제 결과를 저장하고 재사용하는 것이다. 이미 계산한 값을 다시 계산하지 않기 때문에 복잡도를 크게 줄일 수 있다.

대표적인 예시가 피보나치 수열이다. 단순 재귀로 풀면 같은 계산이 반복되지만, 이전 값을 저장하면 훨씬 효율적으로 해결할 수 있다.

$f(n)=f(n-1)+f(n-2)$

여기서 중요한 것은 공식을 외우는 것이 아니다. 현재 상태가 이전 상태와 어떤 관계를 가지는지를 이해해야 한다. DP는 결국 현재 문제를 더 작은 문제로 나눌 수 있는가를 판단하는 과정에 가깝다.

초보자들이 DP를 어려워하는 가장 큰 이유는 점화식을 암기하려고 하기 때문이다. 하지만 실제 코딩테스트에서는 문제마다 상태 정의가 달라진다.

메모이제이션은 필요한 순간 계산 결과를 저장하는 방식이고, 테이블 기반 DP는 작은 문제부터 차례대로 값을 채워나가는 방식이다. 구현은 다르지만 핵심은 동일하다. 이전 계산 결과를 재사용한다는 점이다.

그리디는 현재 가장 좋은 선택을 반복한다

그리디 알고리즘은 현재 시점에서 가장 좋아 보이는 선택을 반복하는 방식이다. 현재 가장 유리해 보이는 선택을 이어붙여 전체 최적해를 만든다.

대표적인 예시가 동전 문제다. 큰 단위 동전부터 사용하는 방식은 매우 직관적이다. 실제로 한국 화폐 구조처럼 특정 조건이 성립하는 경우에는 그리디 방식이 효율적으로 동작한다.

하지만 모든 문제가 그리디로 해결되는 것은 아니다. 현재 가장 좋아 보이는 선택이 미래에도 최적이어야만 그리디가 성립한다.

예를 들어 1원, 4원, 5원 동전으로 8원을 만든다고 가정해보자. 가장 큰 동전인 5원을 먼저 선택하면 총 4개 동전이 필요하다. 하지만 실제 최적해는 4원 동전 2개다.

이런 이유 때문에 그리디 문제에서는 “왜 현재 선택이 항상 정답이 되는가”를 설명하는 과정이 중요하다. 그래서 많은 개발자들이 그리디는 구현보다 증명이 더 중요하다고 이야기한다.

• 현재 선택이 이후 결과를 망치지 않는가
• 선택 기준이 항상 유지되는가
• 반례가 존재하지 않는가

실제 코딩테스트에서는 이 세 가지를 먼저 확인하는 습관이 중요하다.

DP와 그리디의 핵심 차이는 되돌릴 수 있는가에 있다

두 알고리즘의 가장 큰 차이는 선택을 되돌릴 수 있는가에 있다.

DP는 여러 선택 가능성을 비교하면서 진행한다. 이전 상태를 저장하고 필요하면 다른 선택 결과와 비교할 수 있다. 즉, 누적 계산을 통해 최적해를 찾는 구조다.

반면 그리디는 현재 가장 좋은 선택을 즉시 확정한다. 한 번 선택한 결과를 다시 비교하지 않는다. 그렇기 때문에 현재 선택이 전체 최적해를 보장해야만 사용할 수 있다.

많은 초보자들이 DP와 그리디를 헷갈리는 이유도 여기에 있다. 둘 다 최적화를 목표로 하지만 실제 사고 흐름은 완전히 다르다.

실전에서는 이 차이가 매우 중요하다. 특히 반례가 존재하는 문제를 그리디로 접근하면 예제는 맞지만 제출 이후 틀리는 경우가 많다.

실제 코딩테스트에서는 어떻게 구분할까

실제 시험에서는 알고리즘 이름보다 입력 조건과 제한 시간을 먼저 보는 습관이 중요하다.

입력 크기가 매우 크고 모든 경우를 직접 계산하기 어렵다면 시간복잡도를 먼저 계산해야 한다. 이 과정에서 DP나 그리디 가능성이 보이기 시작한다.

예를 들어 경우의 수가 폭발적으로 증가하는데 동일 계산이 반복된다면 DP 가능성이 높다. 반대로 매 순간 선택 기준이 명확하고, 선택 이후에도 최적성이 유지된다면 그리디 가능성이 높다.

많은 합격자들이 실제 시험에서 가장 먼저 하는 행동도 입력 제한 확인이다. 문제 설명보다 입력 범위를 먼저 보면서 어떤 복잡도가 가능한지 판단한다.

또 하나 중요한 점은 문제 유형 암기에만 의존하지 않는 것이다. 같은 DP 문제라도 상태 정의 방식이 완전히 다를 수 있고, 그리디 문제도 증명 방식이 필요한 경우가 많다.

DP가 유리한 대표 문제와 그리디가 강한 대표 문제

DP 대표 문제로는 배낭 문제, 계단 오르기, LIS 문제가 자주 등장한다. 이런 문제들은 이전 상태 결과가 이후 계산에 직접 영향을 준다.

반면 그리디는 회의실 배정, 활동 선택, 특정 동전 문제처럼 선택 기준이 명확한 경우에 강력하다.

1. DP는 이전 상태 누적이 중요하다.
2. 그리디는 현재 선택 기준 유지가 중요하다.
3. 조건이 조금만 바뀌어도 접근 방식이 달라질 수 있다.

실제로 백준 ‘회의실 배정’ 문제는 대표적인 그리디 유형으로 자주 언급된다. 가장 빨리 끝나는 회의를 우선 선택하는 방식이 전체 최적해로 이어지기 때문이다.

반면 ‘정수 삼각형’ 문제는 이전 상태 누적 계산이 핵심이라 DP 접근이 필요하다. 같은 최적화 문제처럼 보여도 내부 구조가 완전히 다른 셈이다.

알고리즘 암기보다 중요한 것은 문제 해석 습관이다

많은 초보자들이 알고리즘 공부를 유형 암기처럼 접근한다. DP 문제 20개, 그리디 문제 20개를 외우듯 반복하는 방식이다.

물론 반복 학습 자체는 중요하다. 하지만 실력이 빠르게 늘어나는 사람들은 문제를 외우기보다 왜 이 접근이 가능한가를 계속 분석한다.

특히 코딩테스트 중상위권부터는 단순 구현보다 문제 해석 능력이 훨씬 중요해진다. 어떤 상태를 저장해야 하는지, 현재 선택이 미래 결과를 보장하는지 판단하는 과정이 핵심이 된다.

실제로 알고리즘 실력이 크게 성장하는 시점은 새로운 개념을 배울 때보다 반례를 이해하기 시작할 때라는 이야기도 많다. 왜 특정 접근이 실패했는지 분석하는 과정에서 사고력이 빠르게 확장되기 때문이다.

결국 DP와 그리디의 차이를 이해한다는 것은 알고리즘 이름을 구분하는 수준이 아니다. 문제를 바라보는 방식 자체를 바꾸는 과정에 가깝다. 이 흐름이 익숙해지기 시작하면 이전에는 보이지 않던 풀이 방향이 조금씩 눈에 들어오기 시작한다.

코딩테스트 학습 순서를 먼저 이해하면 DP와 그리디가 더 쉬워진다

DP와 그리디가 어렵게 느껴지는 가장 큰 이유는 알고리즘 자체보다 문제 해결 흐름이 아직 익숙하지 않기 때문이다.

구현, 자료구조, 탐색 과정을 어떤 순서로 익혀야 하는지 먼저 이해하고 싶다면 이전에 정리한 “알고리즘 문제 풀이” 내용을 함께 보는 것도 도움이 된다.

기본 구현부터 탐색과 최적화까지 이어지는 학습 흐름을 먼저 이해하면 DP와 그리디 문제를 바라보는 시야도 훨씬 자연스럽게 연결되기 시작한다.