위 링크에서 동적계획법(DP) 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다.
5. 동적계획법(DP)
- 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 다시 큰 문제를 해결할 때 사용하는 것. DP가 아닌 기억하며 풀기라고 부르기도 한다. (대표적인 문제: 피보나치 수열)
- dp 값을 구하는 규칙을 찾는 것이 가장 핵심인 문제이다.
- 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.
- 이름의 의미는 없다. 벨만 리차드 씨가 멋있어보여서 그렇게 지은 것
- 일반적인 재귀 방식 또한 DP와 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용시 동일한 작은 문제들이 여러 번 반복되 비효율적인 계산이 될 수도 있다는 것이다.
- 사용조건
- 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
- 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP를 사용할 수 있게 된다.
- DP 사용 과정
- DP로 풀 수 있는 문제인지 확인
- 문제의 변수 파악
- 변수 간 관계식 만들기(점화식)
- 변수의 값에 따른 결과 저장
- 기저 상태 파악하기. 가장 작은 시작 부분 파악
- 구현하기
- 구현방법
- Bottom-Up 방식: 아래부터(dp[0]) 계산을 수행하고 누적시켜서 전체 큰 문제(dp[n])를 해결하는 방식 (반복문 사용)
- Top-Down 방식: dp[n]값을 찾기위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 재활용하는 방식 (재귀 사용)
문제
(❌ 표시는 혼자 못푼 문제)
2023. 12. 06. 2일차(5)
1. 9655번 돌 게임 (실버5) 문제링크
문제 해석
두 명이서 즐기는 재밌는 돌 게임. 상근이와 창영이가 게임을 한다.
탁자위에 돌 N개가 있다.
턴을 돌아가며 돌을 가져간다. 돌은 1개 또는 3개를 가져갈 수 있다.
마지막 돌을 가져가는 사람이 이기게 된다.
두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하자.
게임은 상근이가 먼저시작한다.
제한: 1초 128MB
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)
출력
상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.
코드
규칙을 찾는다. 첫번째시작한 사람이 홀수번째에 이기고 짝수 번째는 상대방이 이긴다.
44ms
N = int(input())
if N%2==0:
print("CY")
else:
print("SK")2023. 12. 06. 2일차(6)
2. 1463번 1로 만들기 (실버3) 문제링크
문제 해석
정수 X에 사용할 수 있는 연산 3가지.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
주어진 N을 1로 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력.
제한: 0.15초 128MB
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
코드
1 : 0회
2부터는 (-1, /2,/3 해서 나오는 값의 횟수 + 1) 중 최솟값
548ms
N = int(input())
dp = [0 for _ in range(N+1)]
dp[1] = 0
for i in range(2, N+1):
minValue = dp[i-1] + 1
if i % 2 == 0:
minValue = min(minValue, dp[i//2] + 1)
if i % 3 == 0:
minValue = min(minValue, dp[i // 3] + 1)
dp[i] = minValue
print(dp[N])
이 문제의 포인트
* 기본 dp 배열만들때 dp = [0 for _ in range(N+1)] 로 사용.
* 처음에 N+1 리스트를 만들지 않고 아래와 같이 for 문 돌때마다 append해서 추가하면 된다. (위 코드에서는 이걸 적용안했다.)
dp = [0, 1]
for i in range(2, N+1):
dp.append(dp[i-1])
print(dp[N])
2023. 12. 06. 2일차(7)
3. 2193번 이친수 (실버3) 문제링크
문제 해석
이진수 중 특별한 성질을 갖는 애를 이친수라고 정의한다.
이친수의 성질
1. 0으로 시작하지 않는다.
2. 1이 두번 연속으로 나타나지 않는다.
N이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성해보자.
제한: 2초 128MB
입력
첫째 줄에 N이 주어진다.
출력
첫째 줄에 N자리 이친수의 개수를 출력한다.
코드
규칙 dp[i-2] + dp[i-1]
40ms
N = int(input())
if N == 1 or N == 2:
print(1)
else:
dp = [0 for _ in range(N + 1)]
dp[1] = 1
dp[2] = 1
for i in range(3, N+1):
dp[i] = dp[i-2] + dp[i-1]
print(dp[N])
N+1 리스트를 시작부터 만들지 않고 append로 추가한 코드
N = int(input())
dp = [0,1,1]
for i in range(3, N+1):
dp.append(dp[i-2]+dp[i-1])
print(dp[N])2023. 12. 06. 2일차(8)
4. 1904번 01타일 (실버3) 문제링크
문제 해석
타일에 0 또는 1 쓰여있다.
0과 0 두개가 붙어서 1 과 00 타일만 존재한다.
N이 주어졌을 때 만들 수 있는 모든 가짓수를 세보자.
제한: 0.75초 256MB
입력
첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
출력
첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.
코드
문제의 규칙은 dp[i-2]+dp[i-1] 이다.
각 단계를 저장할때 15756을 나눈 나머지를 저장한다. 이때 나눈값을 저장하지 않으면 값이 커져서 메모리 초과가 난다.
336ms
N = int(input())
dp = [0, 1, 2]
for i in range(3, N+1):
dp.append((dp[i-2]+dp[i-1]) % 15746)
print(dp[N])2023. 12. 07. 3일차(1)
5. 11726번 2xn 타일링 (실버3) 문제링크
문제 해석
2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하여라.
1 <= n <= 1000
제한: 2초 256MB
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
코드
그림을 그려서 규칙을 찾았다. dp[i-1]+ dp[i-2]
N = int(input())
dp = [0, 1, 2]
for i in range(3, N+1):
dp.append(dp[i-1]+dp[i-2])
print(dp[N] % 10007)2023. 12. 07. 3일차(2)
❌ 6. 11727번 2xn 타일링 2 (실버3) 문제링크
문제 해석
2xn 크기의 직사각형을 1x2, 2x1 , 2x2 타일로 채우는 방법의 수를 구하여라.
제한: 2초 256MB
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
참고: https://velog.io/@real-bird/Python-2n-%ED%83%80%EC%9D%BC%EB%A7%81-2-%EB%B0%B1%EC%A4%80-11727
아이디어
dp[i] = dp[i-1] + 2*dp[i-2]
[i-1]의 타일 끝에 1x2 타일을 붙여서 i를 만드는 경우
[i-2]의 타일 끝에 2층짜리 2X1 와 2x2를 붙여서 i를 만드는 경우
를 더해서 i의 모든 경우를 구할 수 있다.
코드
#
이 문제의 포인트
- 그림을 그려서 하려고 하다보니 빼먹은 경우가 생겨서 규칙이 안찾아졌었다. 직접 그린것으로 개수를 파악하지말고 정확하게 i가 증가할 때의 규칙을 찾는게 중요하다!
2023. 12. 07. 3일차(3)
7. 11051번 이항 계수2 (실버3) 문제링크
문제 해석
자연수 N과 정수 K 가 있을 때 이항계수 nCk를 10007로 나눈 나머지를 구하여라.
제한: 1초 256MB
입력
첫첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)
출력
nCk를 10007로 나눈 나머지를 출력
코드
파스칼 삼각형 공식 이용
264ms
N, K = map(int, input().split())
dp = [[] for _ in range(N + 1)]
for i in range(N + 1):
for j in range(i + 1):
if j == 0 or j == i:
dp[i].append(1)
else:
dp[i].append(dp[i - 1][j - 1] + dp[i - 1][j])
print(dp[N][K]% 10007)2023. 12. 08. 4일차(1)
❌ 8. 1699번 제곱수의 합 (실버2) 문제링크
문제 해석
N 은 그보다 작거나 같은 제곱 수들의 합으로 나타낼 수 있다.
ex) 11 = 3의 제곱 + 1의 제곱 + 1의 제곱 (3개항)
11 = 2의 제곱 + 2의 제곱 + 1의 제곱 + 1의 제곱 (5개 항)
제곱수항의 최소개수를 구하는 프로그램을 작성하시오.
제한: 2초 128MB
입력
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)
출력
주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.
참고: https://jyeonnyang2.tistory.com/50
아이디어
N의 최대 제곱수를 1부터 올려가면서 N에서 최대 제곱수를 뺀 값의 dp값을 참조해서 그 값이 이전에 저장해둔 값보다 작으면 업데이트한다.
코드
N = int(input())
#최대 개수로 초기화
dp = [i for i in range(N+1)]
for i in range(1, N + 1):
for j in range(1, i+1):
if j*j > i:
break
if dp[i] > dp[i-j*j]+1:
dp[i] = dp[i-j*j]+1
print(dp[N])
이 문제의 포인트
* 무조건 이전 값의 최대 제곱수 값이 다음 값의 최대 제곱수 값이라고 잘못생각했었다.
* N의 최대 제곱값이 N-1의 최대 제곱 값보다 작아도 그 값을 뺀 부분의 dp값의 최소항의 개수가 더 작을 수 있다.
2023. 12. 08. 4일차(2)
9. 11055번 가장 큰 증가 부분 수열 (실버2) 문제링크
문제 해석
수열 A가 있다.
증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하여라.
ex) A = {1, 100, 2, 50, 60, 2, 5, 6, 7, 8}
제한: 1초 256MB
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.
코드
인덱스를 증가시켜가면수 해당 인덱스까지의 증가하는 부분수열의 합을 저장한다.
증가하는 부분 수열의 합이므로 동일한 값은 증가하는 것으로 보면안된다. 주의!
128ms
N = int(input())
arr = list(map(int, input().split()))
dp = [0] * N
for i in range(N):
maxValue = 0
for j in range(i):
if arr[j] >= arr[i]: # 동일한 값도 증가하는 것으로 보면안된다. (그래서 = 추가)
continue
if maxValue < dp[j]:
maxValue = dp[j]
dp[i] = arr[i] + maxValue
print(max(dp))2023. 12. 08. 4일차(3)
❌ 10. 9465번 스티커 (실버2) 문제링크
문제 해석
스티커가 2행 n열로 배치되어있다.
스티커 한장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다.
모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다.
상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시요.
제한: 2초 256MB
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.
출력
각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.
참고: https://beyond-common-sense.tistory.com/10
아이디어
column을 증가시키면서 해당 셀까지 왔을 때의 value를 dp에 저장한다.
해당 셀까지 오기 전에 거칠 수 있는 이전 경우 셀의 값 중 더 큰 값에 해당 셀의 값을 더한다.
코드
#
이 문제의 포인트
* 무작정 풀기보다 문제의 접근 방식을 잘생각해보자
추가문제
11. 1912번 연속합 (실버2) 문제링크
12. 1535번 안녕 (실버2) 문제링크
13. 12852번 1로 만들기 2 (실버1) 문제링크
14. 11052번 카드 구매하기 (실버1) 문제링크
15. 10844번 쉬운 계단 수 (실버1) 문제링크
16. 11057번 오르막 수 (실버1) 문제링크
17. 1149번 RGB거리 (실버1) 문제링크
18. 15989번 1,2,3 더하기 4 (실버1) 문제링크
19. 2293번 동전 1 (골드5) 문제링크
20. 2294번 동전 2 (골드5) 문제링크
21. 4811번 알약 (골드5) 문제링크
22. 2240번 자두나무 (골드5) 문제링크
23. 12865번 평범한 배낭 (골드5) 문제링크
24. 16500번 문자열 판별 (골드5) 문제링크
25. 17070번 파이프 옮기기 1 (골드5) 문제링크
26. 12865번 평범한 배낭 (골드5) 문제링크
27. 5557번 1학년 (골드5) 문제링크
28. 9252번 LCS2 (골드4) 문제링크
29. 2631번 줄세우기 (골드4) 문제링크
30. 12869번 뮤탈리스크 (골드4) 문제링크
31. 4781번 사탕 가게 (골드4) 문제링크
32. 14002번 가장 긴 증가하는 부분 수열4 (골드4) 문제링크
33. 14863번 서울에서 강산까지 (골드4) 문제링크
34. 10942번 팰린드롬? (골드4) 문제링크
35. 2533번 사회망 서비스(SNS) (골드3) 문제링크
36. 2248번 이진수 찾기 (골드3) 문제링크
37. 1943번 동전 분배 (골드3) 문제링크
38. 2342번 Dance Dance Revolution (골드3) 문제링크
39. 12201번 이진수 찾기 2 (골드2) 문제링크
40. 1256번 사전 (골드2) 문제링크
41. 2291번 Sequence (골드2) 문제링크
42. 3687번 성냥개비 (골드2) 문제링크
43. 1513번 경로 찾기 (골드2) 문제링크
44. 2213번 트리의 독립집합 (골드1) 문제링크
45. 2494번 숫자 맞추기 (골드1) 문제링크
46. 2098번 외판원 순회 (골드1) 문제링크
47. 1509번 팰린드롬 분할 (골드1) 문제링크
48. 2618번 경찰차 (플레5) 문제링크
49. 17258번 인기가 넘쳐흘러 (플레4) 문제링크
50. 1023번 우괄호 문자열체국 (플레3) 문제링크
51. 1315번 RPG (플레3) 문제링크
'알고리즘 문제풀이' 카테고리의 다른 글
| 이진탐색(Binary Search) 문제 및 풀이 (Python) (0) | 2023.12.04 |
|---|---|
| 구현 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 완전탐색(브루트포스) 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 너비 우선 탐색(BFS) 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 깊이 우선 탐색(DFS) 문제 및 풀이 (Python) (0) | 2023.12.04 |