다이나믹 프로그래밍이란 하나의 큰 문제를 여러개의 부분문제로 분할한뒤 , 이전값을 활용하여 문제를 해결하는 기법입니다.
1,2,3더하기 시리즈 문제를 통해서 2차원 dp 에 대해 자세히 알아봅시다.
📌 1, 2, 3 더하기 1
정수 N 을 1,2,3 의 합으로 나타내는 경우의 수를 구하는 문제입니다.
dp 를 사용하기 전에 고려해야할 점이 있습니다.
- 시간복잡도가 맞을까?
백트래킹을 사용해서 모든 경우를 살펴보는 경우 시간복잡도는 O(2^N) 입니다.
dp 를 사용하면 이를 O(N^2) 정도로 줄일 수 있습니다.
- 이전값을 활용할 수 있을까?
문제를 부분문제로 분할하기 위해서는 이전값을 활용할 수 있어야 합니다.
"4를 만들기 위해 필요한 경우를 구하기 위해서는 1~3에서 필요한 경우의 수가 활용될수있는가?" 를 생각해봅시다.
직감적으로 와닿지 않는다면 N<=5 일때까지 직접 모든 경우를 구해보면서 시뮬레이션을 해보는걸 추천합니다.
- 테이블과 점화식을 어떻게 정의할까?
테이블을 정의하기 위해서는 필요한 값을 정해야 합니다.
보통 문제에서 요구하는 경우를 잘 읽어보면 찾을 수 있습니다.
dp[i] = i 번째 수를 만들때 경우의 수
다음으로 점화식을 선언하기 위해서는 이전값을 활용해야 합니다.
N = 1
- 1
N = 2
- 1+1
- 2
N = 3
- 1+1+1
- 1+2
- 2+1
- 3
N = 4
- 1+1+1+1
- 1+1+2
- 1+2+1
- 2+1+1
- 2+2
- 1+3
- 3+1
대략 4일때까지 경우를 구해봤습니다.
규칙을 찾아보면 4라는 숫자를 만들기 위해서는
3에다가 1을 더하는경우 , 2에다가 2를 더하는 경우 , 1에다가 3을 더하는 경우
가 됩니다. 이를 점화식으로 표현하면
dp[i] = dp[i-1]+dp[i-2]+dp[i-3] 이 됩니다.
- 초기값은 무엇일까?
dp 테이블을 정의하고 점화식을 정의했다면 초기값을 정해야 합니다.
초기값이 없는 빈 배열에서는 이전값을 활용할 수 없기 때문입니다.
만약 이전에 3개의 값까지 사용해야한다면 적어도 값이 3개는 선언되어야 합니다.
dp=[1,2,4]
위 형태로 저장해줍시다.
import sys
input=sys.stdin.readline
T=int(input())
dp=[1,2,4]
for i in range(2,20):
dp.append(dp[i-2]+dp[i-1]+dp[i])
for i in range(T):
a=int(input())
print(dp[a-1])📌 1, 2, 3 더하기 4
이전문제와 비슷합니다.
정수 N 을 1,2,3의 합으로 나타내는 경우의 수를 구하면 됩니다.
다만 합을 이루는 수의 순서만 다른 경우는 제외해야합니다.
기존에 사용하던 1차원 점화식을 아무리 수정해도 해결하기 어렵습니다.
그 이유는 합을 이루는 수의 순서 에 대한 정보를 구할 수 없기 때문입니다.
N 차원 점화식을 사용할때 필요한 정보가 더 필요하다면 N+1 차원을 사용하면 됩니다.
그럼 이제 dp 테이블을 정의해봅시다.
dp[i][j] : i 번째 수를 1,2,3의 합으로 나타내는 경우
이제 j 에 대한 정의를 해야하는데 , 중복을 지우기 위해서 어떻게 하면 좋을까요?
만약 j 를 1 or 2 or 3 을 이전값에 더하는 경우로 정의해봅시다.
중복이 생기는 이유는 1+2 , 2+1 와 같은 경우 때문입니다.
그렇다면 1 을 더할때는 1 만 더하고 , 2를 더할때는 이전에 1 또는 2를 더했을때 더해주고
3을 더할때는 이전에 1 또는 2 또는 3을 더했을때 경우를 추가해주면 되지 않을까요?
따라서 dp 테이블을 정의하면 다음과 같습니다.
dp[i][j] : i 번째 수를 j 를 더해서 나타낼수 있는 경우의 수
이제 점화식을 생각해봅시다.
dp[1][i] += dp[1][i-1]
dp[2][i] += dp[2][i-2] + dp[1][i-2]
dp[3][i] += dp[3][i-3]+dp[2][i-3]+dp[1][i-3]배열인덱스를 편하게 할려고 i,j 를 반대로 했습니다.
이제 초기값을 생각해봅시다.
dp[1][1] = 1
dp[2][2] = 1
dp[3][3] = 1숫자 1을 나타내기 위해서는 숫자 1 , 숫자 2를 나타내기 위해서는 숫자 2 , 숫자 3을 나타내기 위해서는 숫자 3을 더한 경우의 수가 각각 1 입니다.
dp = [ [0]*10004 for _ in range(4)]
dp[1][3] = 1
dp[2][4] = 1
dp[3][5] = 1
for i in range(4,10004):
dp[1][i] += dp[1][i - 1]
dp[2][i] += dp[2][i-2] + dp[1][i-2]
dp[3][i] += dp[3][i-3]+dp[2][i-3]+dp[1][i-3]
for i in range(int(input())):
N=int(input())
print(dp[1][N+2]+dp[2][N+2]+dp[3][N+2])📌 1, 2, 3 더하기 5
이번에도 1,2,3 을 사용해 N 을 만드는 경우를 구하는 문제입니다.
추가된 조건은 "같은 수를 연속해서 사용하면 안된다" 입니다.
같은 수를 연속하지 않게 사용하기 위해서는 어떤 정보가 필요할까요?
바로 이전에 사용했던 수에 대한 정보 입니다.
이전에 1을 사용했다면 2 또는 3을 선택하면 되기 때문이죠.
그럼 이제 dp 테이블을 정의해보겠습니다.
dp[i][j] : i 번째 수를 j 를 더해서 나타낼수 있는 경우의 수
테이블은 이전과 동일합니다. 다만 점화식은 다릅니다.
dp[3][i] += dp[2][i - 3] + dp[1][i - 3]
dp[2][i] += dp[1][i - 2] + dp[3][i - 2]
dp[1][i] += dp[3][i - 1] + dp[2][i - 1]i 번째 수를 만들기 위해 3을 사용하기 위해서는
i-3 을 만들었던 경우에서 1과 2를 더했던 경우를 더해주면 됩니다.
이제 초기값을 설정해봅시다.
dp[1][1] = 1
dp[2][2] = 1
dp[3][3] = 1초기값도 동일합니다.
MOD = 1000000009
dp= [ [0]*100007 for _ in range(4)]
dp[1][3] = 1
dp[2][4] = 1
dp[3][5] = 1
for i in range(5,100007):
dp[3][i] += dp[2][i - 3] + dp[1][i - 3]
dp[2][i] += dp[1][i - 2] + dp[3][i - 2]
dp[1][i] += dp[3][i - 1] + dp[2][i - 1]
dp[3][i]%=MOD
dp[2][i]%=MOD
dp[1][i]%=MOD
for i in range(int(input())):
N=int(input())
print(dp[1][N+2]+dp[2][N+2]+dp[3][N+2])📌 1, 2, 3 더하기 6
이번의 조건에는 "합은 대칭을 이룬다 " 입니다.
만약 1+2+1 이라는 수식은 다음값에 사용될 수 있을까요?
1+1+2+1+12+1+2+1+23+1+2+1+3
위와같이 가능합니다.
합이 대칭을 이루는 식에서 양끝에 같은 값을 더한다면 대칭을 유지할 수 있습니다.
반대로 말하면 양끝에 같은 값을 뺀 경우에다가 양끝에 같은 값을 더함으로써 경우의 수를 구할 수 있습니다.
이제 테이블을 정의해봅시다.
dp[i][j] : i 번째 수를 만들때 j 를 더하는 경우
점화식을 세워봅시다.
dp[1][i] += dp[1][i-2]+ dp[2][i-2] + dp[3][i-2]
dp[2][i] += dp[1][i-4] + dp[2][i-4]+ dp[3][i-4]
dp[3][i] += dp[1][i-6] + dp[2][i-6] + dp[3][i-6]i 번째 수를 만들기 위해 1 이라는 숫자를 사용할 거라면
i-2 번째 수를 만든 경우에다가 양끝에 1을 2번 더해줌으로써 대칭을 유지할 수 있습니다.
초기값을 설정해봅시다.
dp[1][1] = 1
dp[1][2] = 1
dp[2][2] = 1
dp[2][4] = 1
dp[3][3] = 1
dp[3][6] = 1숫자를 한개만 썼을때 , 2개를 썼을때 경우를 넣어줍니다.
dp = [[0] * 100001 for _ in range(4)]
MOD = 1000000009
dp[1][1] = 1
dp[1][2] = 1
dp[2][2] = 1
dp[2][4] = 1
dp[3][3] = 1
dp[3][6] = 1
for i in range(2, 100001):
if i >= 2:
dp[1][i] += dp[1][i - 2] + dp[2][i - 2] + dp[3][i - 2]
if i >= 4:
dp[2][i] += dp[1][i - 4] + dp[2][i - 4] + dp[3][i - 4]
if i >= 6:
dp[3][i] += dp[1][i - 6] + dp[2][i - 6] + dp[3][i - 6]
dp[1][i] %= MOD
dp[2][i] %= MOD
dp[3][i] %= MOD
for i in range(int(input())):
N = int(input())
print((dp[1][N] + dp[2][N] + dp[3][N]) % MOD)📌 1, 2, 3 더하기 7
이번에 나온 조건은 사용한 수의 개수가 M 개 이어야 하는 조건입니다.
그렇다면 자연스럽게 dp 를 사용하기 위해서는 이전에 사용한 수의 개수 가 필요합니다.
테이블을 정의해봅시다.
dp[i][j] : i 번째 수를 j 개의 수로 사용한 경우의 수
점화식을 생각해봅시다.
이전에 i 번째수를 만들기 위해서는 i-1,i-2,i-3 의 정보가 필요했습니다.
그렇다면 i-1,i-2,i-3 은 그대로 사용하되 , 사용하는 수의 개수는 항상 한개만 증가하므로
dp[i][j] = dp[i-3][j-1] + dp[i-2][j-1] + dp[i-1][j-1]
위와 같은 점화식을 만들 수 있습니다.
이제 초기값을 설정해봅시다.
dp[1][1] = 1 # 1
dp[2][1] = 1 # 2
dp[2][2] = 1 # 1 + 1
dp[3][1] = 1 # 3
dp[3][2] = 2 # 1+2 , 2+1
dp[3][3] = 1 # 1+1+1숫자 i 를 만들기 위해 j 개를 사용한 경우를 시뮬레이션을 돌려보면 초기값을 찾아볼 수 있습니다.
dp=[ [0]*1001 for _ in range(1001)]
MOD = 1000000009
dp[1][1] = 1
dp[2][1] = 1
dp[2][2] = 1
dp[3][1] = 1
dp[3][2] = 2
dp[3][3] = 1
for i in range(4,1001):
for j in range(2,1001):
dp[i][j] = (dp[i-3][j-1] + dp[i-2][j-1] + dp[i-1][j-1])%MOD
for i in range(int(input())):
N,M=map(int,input().split())
print(dp[N][M])📌 1, 2, 3 더하기 9
이번에는 사용한 수의 개수가 M 개 이하이어야 합니다.
이전에는 M 개의 수로 만들었을때 경우를 구했는데 M 개 이하의 수를 구할려면 어떻게 해야할까요?'
1부터 M 개의 수로 만든 모든 경우를 더해주면 됩니다.
점화식과 테이블 정의는 이전과 같습니다.
다만 여러개의 테스트 케이스가 있고 매번 1부터 M 개의 수를 구한다고 가정해봅시다.
효율적으로 구하긴 위해선 테스트 케이스마다 매번 1부터 M 개의 수를 구할 필요없이
누적합을 이용한다면 1부터 M 개의 수를 O(NM) 의 전처리를 통해 쿼리마다 O(1) 에 처리할 수 있습니다.
dp=[ [0]*1004 for _ in range(1004) ]
MOD = 1000000009
dp[1][1+3] = 1
dp[2][1+3] = 1
dp[3][1+3] = 1
for i in range(1,1001):
for j in range(4,i+4):
dp[i][j] += (dp[i-1][j-1]+dp[i-2][j-1]+dp[i-3][j-1])%MOD
dp[i][j]%=MOD
for i in range(1,1001):
for j in range(4,i+4):
dp[i][j] += dp[i][j-1]
dp[i][j]%=MOD
for i in range(int(input())):
N,M=map(int,input().split())
print(dp[N][M+3])📌 1, 2, 3 더하기 8
마지막으로 볼 문제는 사용한 수의 개수가 홀수인 방법의 수 , 짝수인 방법의 수를 구하는 방법입니다.
dp 테이블은 바로 잡을 수 있습니다.
dp[i][j] : i 번째 수를 만드는데 홀수 또는 짝수를 만드는 경우의 수
이제 점화식을 생각해봅시다.
이전에 사용한 수의 개수가 홀수라면 숫자 하나를 더해줌으로써 짝수를 만들 수 있습니다.
반대로 이전에 사용한 수의 개수가 짝수라면 숫자 하나를 더해줌으로써 홀수를 만들 수 있습니다.
dp[i][1] = dp[i - 1][2] + dp[i - 2][2] + dp[i - 3][2]
dp[i][2] = dp[i - 1][1] + dp[i - 2][1] + dp[i - 3][1]이제 초기값도 설정해줍시다.
dp[1][1] = 1 # 1
dp[2][1] = 1 # 2
dp[3][1] = 2 # 1+1+1 , 3
dp[2][2] = 1 #1+1
dp[3][2] = 2 #1+2 , 2+1경우에 맞게 넣어주면 됩니다.
dp= [ [0]*3 for _ in range(100001) ]
MOD = 1000000009
dp[1][1] = 1 # 1
dp[2][1] = 1 # 2
dp[3][1] = 2 # 1+1+1 , 3
dp[2][2] = 1 #1+1
dp[3][2] = 2 #1+2 , 2+1
for i in range(4,100001):
dp[i][1] = (dp[i - 1][2] + dp[i - 2][2] + dp[i - 3][2])%MOD
dp[i][2] = (dp[i - 1][1] + dp[i - 2][1] + dp[i - 3][1])%MOD
for i in range(int(input()):
N=int(input())
print( dp[N][1] ,dp[N][2])📌 마무리
지금까지 2차원 dp 를 정의하는걸 연습했습니다.
골드이상의 문제에서는 dp 를 3차원 , 때로는 4차원까지 사용해야할 때가있습니다.
dp 를 사용해야하는데 필요한 정보의 개수가 너무 많아서 차원이 증가하고 , 시간복잡도가 너무 증가해버리면 차원을 줄일 수 있는 방법을 생각해봐야합니다.
불필요한 연산을 하지않는다거나 , 필요하지 않는 정보를 제거하는 방법 등이 있습니다.
또한 dp 에는 여러가지 심화 알고리즘이 있습니다.
- 비트필드를 이용한
dp - 트리에서의
dp - 가장 긴 증가하는 부분수열
lis - 가장 긴 공통 부분 수열
lcs - 배낭문제
knapsack problem - 커넥션 프로파일을 이용한
dp - 컨벡스 헐 트릭
Convex Hull Trick
이외에도 여러가지가 있습니다.
또한 dp 에서 몇가지 주의해야할 점을 소개하자면
MOD연산은 가능하면 매번 해줘야한다.
모든연산이 끝나고 마지막에MOD연산시 오버플로우가 나고 수의 크기가 커지면 연산시간이 오래걸린다.- 테이블의 인덱스를 주의해야한다.
i-3의 값을 필요로할때 반복문을0부터 시작하면 안된다.
또한 dp 유형의 문제에서는 보통
- 경우의 수
- 최소값 , 최대값
이 두가지에 대한 쿼리가 주로 요청되기 때문에 이런 요청이 있으면 dp 를 사용해볼 생각을 하는걸 추천합니다.
