DP 란 무엇인가
먼저 DP 의 개념을 알아보기 위해 구글링을 하면 아래와 같은 답변을 얻을 수 있다.
수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법( dynamic programming )이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.
출처 : 위키백과
빠른 이해를 위해 바로 다음 단계로 넘어가보도록 하겠다.
DP 문제 풀어보기
시작하기 전에 언어는 C/C++, Java 등을 이용해도 좋지만 원리 이해에 좀 더 집중하기 위해 비교적 문법이 쉬운 파이썬 을 사용하겠다.
DP 문제 중 하나인 백준의 1463번 문제를 풀어보자.
1로 만들기
필자도 처음 이 문제를 봤을 때는 규칙을 제대로 이해하지 못하고 풀어서 계속 틀렸던 기억이 있다.
코드가 실행되는 시나리오를 그려보자면 아래와 같다.
이 문제를 처음 접한 사람이라면 본인이 생각한 시나리오와 다를 수 있을 것이다.
이제부터 시나리오처럼 코드를 작성을 해보겠다.
먼저 N 에 입력 값을 저장해주겠다.
N = int(input())다음은 최소 값의 경로를 저장 ( 메모제이션 ) 하기 위해 dp 라는 배열을
선언 해주겠다.
dp = [0,0,1,1]왜 배열에 할당한 값이 0,0,1,1 이냐고 묻는다면 첫번째 0은 단순 인덱스를 맞춰주기 위함이고 나머지는 N이 1일 때의 출력 값, N이 2일 때의 출력 값, N이 3일 때의 출력 값을 순서대로 할당한 것이다.
이렇게 작성하면 하드코딩이나 다름이 없는거 아니냐고 생각할 수 있는데 다음 코드를 보며 설명을 하겠다.
for i in range(4,N+1):
dp.append(dp[i-1]+1)
if i%2 == 0: dp[i] = min(dp[i//2]+1, dp[i])
if i%3 == 0: dp[i] = min(dp[i//3]+1, dp[i])위의 코드처럼 최소값을 비교하기 위한 조건은 3가지가 있다.
만약 반복문을 2 또는 3 부터 실행해준다면 오류가 발생하거나 출력 값이 올바르지 않을 것이다.
ex) dp[2//3] → 오류가 발생
그렇기 때문에 dp 배열에는 필요한 최소한의 값만을 넣어두고 그 값을 기반으로 반복하여 N까지의 결과를 할당할 수 있는 것이다.
반복문이 종료되면 dp의 (N+1)번째 값을 출력해준다.
print(dp[N])전체 코드
N = int(input())
dp = [0,0,1,1]
for i in range(4,N+1):
dp.append(dp[i-1]+1)
if i%2 == 0: dp[i] = min(dp[i//2]+1, dp[i])
if i%3 == 0: dp[i] = min(dp[i//3]+1, dp[i])
print(dp[N])이 문제를 재귀를 이용해서 풀 수 있다고 하는데 필자는 굳이 이런 좋은 방법을 두고 재귀를 쓸 이유는 없다고 생각한다.
이대로 끝내면 재미가 없으니 백준의 9095번 문제도 풀어보자.
1, 2, 3 더하기
코드가 실행되는 시나리오를 그려보자면 아래와 같다.
n이 5인 경우까지의 출력 값을 적어보았는데 자세히 보면 규칙을 발견할 수 있다.
그렇다. n의 출력 값은 n-3, n-2, n-1 의 출력 값을 모두 더한 것이다.
이것은 DP 를 이용해서 풀 문제라는 증거라고 할 수 있겠다.
그 규칙을 이용한 코드를 작성하면 아래와 같다.
dp = [0,1,2,4]
for _ in range(4,14): dp.append(sum(dp[-3:]))
for _ in range(int(input())): print(dp[int(input())])규칙만 찾는다면 딱히 설명할 내용이 없을 정도로 쉬운 문제였다.
글에서 놓친 부분이나 보다 효율적인 방법을 알고있다면 댓글에 공유해주길 바란다.
