1463_1로 만들기
⭕풀이:
X = int(input())
d = [0] * (X + 1) #d에 계산된 값을 저장해둔다. n + 1이라고 한 이유는, 1번째 수는 사실 d[1]이 아니고 d[2]이기 때문에, 계산하기 편하게 d[1]을 1번째 인 것 처럼 만들어준다.
for i in range(2, X + 1): #1) 처음 1을 빼고 시작하는 경우, 2)처음 3으로 나누고 시작하는 경우, 3)처음 2로 나누고 시작하는 경우, = 1) dp[i] = dp[i-1] + 1, 2) 첫 번째 if문 3) 두 번째 if문 으로 세 가지 경우 모두 실행해보고, 그 중 min을 통해 해당 숫자 X의 최솟값을 구해 d[i]에 저장하게 된다.
d[i] = d[i-1] + 1 #일단, 2와 3으로 나누어 떨어지지 않는 경우는 무조건 1을 빼야 하는 수밖에 없기 때문에 dp[i] = dp[i-1] + 1을 통해 횟수를 +1 추가 해준다.
if i % 3 == 0:
d[i] = min(d[i], d[i//3] + 1)
if i % 2 == 0:
d[i] = min(d[i], d[i//2] + 1)
print(d[X])
⭕풀이설명:
1) 다이나믹 프로그래밍 = 동적 계획법
- 다이나믹 프로그래밍, 동적 계획법을 이용해 풀어야 하는 문제입니다.
동적계획법은 상향식과 하향식이 있는데, 처음 두 수 을 알기 때문에 상향식으로 문제를 풀면 됩니다.
상향식은 제일 작은 인덱스의 수 부터 목표하는 값으로 향하는 것이고,
하향식은 반대로 가장 큰 값에서 재귀로 제일 작은 인덱스를 향하는 것입니다.
2) 동적 계획법 vs 그리디 알고리즘
- 이 동적계획법이 최솟값을 구하는 면에서 그리디 알고리즘이랑 다른 점은
그리디 알고리즘은 내가 생각한 처음 최적의 방법이 끝까지 반례 없이 적용되는 경우에 이용하는 것이고,
동적 계획법은 가능성을 모두 두고 그 안에 최솟값을 찾을 수 있기 때문에
느낌은 그리디와 브루트포스의 중간 정도로 느낄 수 있습니다.
3) 그리디 알고리즘의 변수
- 그렇다면, 위의 문제가 일반적인 그리디문제로 푼다면 변수가 있다는 것을 알 수 있는데,
그 예로 10의 경우엔10 - 5 - 4 - 2 - 1로 푸는 것보다
처음부터 1을 빼고,10 - 9 - 3 - 1을 만드는 방법이 최솟값이고,
무조건 3 or 2 로 나누는 방법에 변수가 생기는 것입니다.
4) 풀이과정
- 결국 이 문제는 전의 결과를 다음 결과에 이용하게 되는 점화식을 활용한 DP문제입니다.
X = 10인 경우, 10 - 9 - 3 - 1 의 과정을 거쳐 1이 되는데
X = 9의 경우에는 또, 9 - 3 - 1 의 과정을 거치며
X = 3의 경우에는 3 - 1 의 정을 거칩니다.
즉, 10의 최솟값을 구할 때는 9의 최솟값 결과를,
9의 최솟값을 구할 때는 3의 최솟값 결과를 이용하게 되는 겁니다.
앞에서 구한 결과값을 저장해뒀다가 후에 사용하는 것입니다.
📌필요지식
11726_2 * n 타일링
⭕풀이:
s = [0, 1, 2]
for i in range(3, 1001):
s.append(s[i - 2] + s[i - 1])
n = int(input())
print(s[n] % 10007)⭕풀이설명:
1) 피보나치 수
위의 그림을 보아
입력 값 n이 1 이면, 방법의 수 = 1
입력 값 n이 2 이면, 방법의 수 = 2
입력 값 n이 3 이면, 방법의 수 = 3
입력 값 n이 4 이면, 방법의 수 = 5
입력 값 n이 5 이면, 방법의 수 = 8
입력 값 n이 6 이면, 방법의 수 = 13...
으로 피보나치 수와 유사한 형태의 점화식을 세울 수 있습니다.
점화식: s[i] = s[i - 2] + s[i - 1]
❗느낀 점:
앞 선 두 문제(1463, 11726)를 통해 이번 다이나믹 프로그래밍, 동적 계획법에서는 문제에서 핵심인 규칙을 찾는 것이 매우 중요하다는 것을 알 수 있었습니다.
약간 gsat와 비슷한 느낌이고, 공식을 몇 가지 알고 있으면 코드 내용이 매우 간결해질 것 같습니다.
11727_2 * n 타일링 2
⭕풀이:
s = [0, 1, 3]
for i in range(3, 1001):
s.append((s[i - 2] * 2) + s[i - 1])
n = int(input())
print(s[n] % 10007)⭕풀이설명:
입력 값 n이 1 이면, 방법의 수 = 1
입력 값 n이 2 이면, 방법의 수 = 3
입력 값 n이 3 이면, 방법의 수 = 5
입력 값 n이 4 이면, 방법의 수 = 11
입력 값 n이 5 이면, 방법의 수 = 21..
점화식: (s[i - 2] * 2) + s[i - 1]
9095_1, 2, 3 더하기
⭕풀이:
test_case = int(input())
s = [1, 2, 4]
for i in range(3, 10):
s.append((s[i - 3] + s[i - 2] + s[i - 1]))
for i in range(test_case):
n = int(input())
print(s[n-1])⭕풀이설명:
입력 값 n이 1 이면, 방법의 수 = 1
입력 값 n이 2 이면, 방법의 수 = 2
입력 값 n이 3 이면, 방법의 수 = 4
입력 값 n이 4 이면, 방법의 수 = 7..
점화식 = s[i - 3] + s[i - 2] + s[i - 1]
11052_카드 구매하기
⭕풀이:
N = int(input())
dp = [0] * (N+1) #카드 i개 살 때, 최댓값은 dp[i]으로 변수선언해둔다.
p = [0] + list(map(int,input().split())) #카드 i개 살 때, i개 들어있는 카드팩 값을 p에 리스트로 넣어둔다.
for i in range(1,N+1):
for k in range(1,i+1):
dp[i] = max(dp[i], dp[i-k] + p[k])
print(dp[i])⭕풀이설명:
dp[N]의 배열은 N개의 최댓값을 저장하는 배열입니다.
p의 배열은 입력을 받는 각각의 가격입니다. 헷갈리지 않게 dp[0], p[0]에 0을 넣어서 dp[1], p[1] 부터 값을 받게 해둡니다.
dp[1]는 즉, 1개를 산다고 했을 때의 최댓값은 당연히 p[1]의 값일 겁니다.
이후로 dp[2]의 최댓값부터 계산해 보면,
d[2] = d[1] + p[1] or d[0] + p[2]
d[3] = d[2] + p[1] or d[1] + p[2] or d[0] + p[3]
d[4] = d[3] + p[1] or d[2] + p[2] or d[1] + p[3] or d[0] + p[4]
가 될 것입니다.
결국에는 모두 계산해 가장 큰 값을 배출하면 되는 것입니다.
이를 for문으로 처음부터 하나씩 계산해 i의 값과 i+1의 값을 max()를 통해 비교해 둘 중 큰 값만 dp[i]로 변수선언하고,(=저장해두고,) 또 다음 dp[i+1]의 값과 비교하는 반복문을 N값만큼 실행해 최댓값을 구하는 식입니다.
N = 4
p = 1, 5, 6, 7이면,
i=1, k=1일 때,
dp[1] = max(dp[1], dp[0] + p[1])
= p[1]
--------------------------------------------------------------------------------------
i=2, k=1일 때,
dp[2] = max(dp[2], dp[1] + p[1])
= dp[1] + p[1] #둘 중 큰값만 dp[i]로 변수선언!
= 1
i=2, k=2일 때,
dp[2] = max(dp[2], dp[0] + p[2])
= dp[0] + p[2]
= 5
--------------------------------------------------------------------------------------
i=3, k=1일 때,
dp[3] = max(dp[3], dp[2] + p[1])
= dp[2] + p[1]
= 6
i=3, k=1일 때,
dp[3] = max(dp[3], dp[2] + p[1])
= dp[2] + p[1]
= 6
i=3, k=2일 때,
dp[3] = max(dp[3], dp[1] + p[2])
= 6 #dp[3]과 dp[1] + p[2]이 같음.
i=3, k=3일 때,
dp[3] = max(dp[3], dp[0] + p[3])
= 6 #dp[3]과 dp[0] + p[3]이 같음.
--------------------------------------------------------------------------------------
i=4, k=1일 때,
dp[4] = max(dp[4], dp[3] + p[1])
= dp[3] + p[1]
= 7
i=4, k=2일 때,
dp[4] = max(dp[4], dp[2] + p[2])
= dp[2] + p[2]
= 10
i=4, k=3일 때,
dp[4] = max(dp[4], dp[1] + p[3])
= dp[4]
= 10
i=4, k=4일 때,
dp[4] = max(dp[4], dp[0] + p[4])
= dp[4]
= 1016194_카드 구매하기 2
⭕풀이:
N = int(input())
p = [0] + list(map(int, input().split()))
dp = [False] * (N + 1) #min을 사용해 최솟값을 구하기 위해 0을 대신해 False를 사용하면 최솟값이 0이 나오는 것을 피할 수 있다.
for i in range(1, N + 1):
for k in range(1, i + 1):
if dp[i] == False:
dp[i] = dp[i - k] + p[k]
else:
dp[i] = min(dp[i], dp[i - k] + p[k])
print(dp[i])15990_1, 2, 3 더하기 5
⭕풀이:
import sys
input = sys.stdin.readline
r = 1000000009
dp = [[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 1]]
ans = [0 for i in range(100001)]
for i in range(3, 100001):
dp.append([(dp[i][1] + dp[i][2]) % r, (dp[i - 1][0] + dp[i - 1][2]) % r, (dp[i - 2][0] + dp[i - 2][1]) % r])
for i in range(100001):
ans[i] = (dp[i][0] + dp[i][1] + dp[i][2]) % r
test_case = int(input())
for _ in range(test_case):
num = int(input())
print(ans[num])
10844_쉬운 계단 수
⭕풀이:
import sys
input = sys.stdin.readline
n = int(input())
dp = [[0] * 10 for _ in range(n + 1)]
# 1 자리수는 0을 제외하고(조거 : 0은 앞에 올 수 없음) 1로 초기화
for i in range(1,10):
dp[1][i] = 1
# dp[N 자리 수][N자리 숫자일 때 해당 Index 앞에 올 수 있는 일의 자리 수]
# 2 자리수부터 시작
for i in range(2, n+1): # n 자리 수
for j in range(10): # Index
# 뒷자리가 0일 때는 앞에 1밖에 오지 못함
if j == 0 : dp[i][j] = dp[i-1][j+1]
# 뒷자리가 9일 때는 앞에 8밖에 오지 못함
elif j == 9 : dp[i][j] = dp[i-1][j-1]
# 뒷자리가 2~8일 때는 앞에 숫자가 2개씩 올 수 있음
else : dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
print(sum(dp[n]) % 1000000000)https://ji-gwang.tistory.com/275
2193_이친수
⭕풀이:
N = int(input())
prinary_list = [0, 1, 1]
for i in range(3,91):
prinary_list.append(prinary_list[i-2] + prinary_list[i-1])
print(prinary_list[N])⭕풀이설명:
N[i] = N[i - 2] + s[i - 1]
점화식: N[i] = N[i - 2] + s[i - 1]
11053_가장 긴 증가하는 부분 수열
⭕풀이:
numbers = int(input())
numbers_list = list(map(int, input().split()))
dp = [0] * (numbers + 1)
for i in range(numbers):
for j in range(i):
if numbers_list[i] > numbers_list[j] and dp[i] < dp[j]:
dp[i] = dp[j]
dp[i] += 1
print(max(dp))
⭕풀이설명:
1) a[i] 와 a[i-1] 비교
수열 a = {10, 20, 10, 30, 20, 50}이 있을때, 4번째 숫자(30)까지의 수열의 길이의 최댓값을 구하는 과정은 다음과 같습니다.
첫번째 숫자부터 검사를 해 나간다.
자기 자신인 a[1]보다 작은 숫자들 중 가장 큰 길이를 구하고 그 길이에 +1을 하면 된다.
14002_가장 긴 증가하는 부분 수열 4
⭕풀이:
numbers = int(input())
numbers_list = list(map(int, input().split()))
dp = [0] * (numbers + 1)
arr = []
for i in range(numbers):
for j in range(i):
if numbers_list[i] > numbers_list[j] and dp[i] < dp[j]:
dp[i] = dp[j]
dp[i] += 1
answer = max(dp)
arr = []
print(max(dp))
for i in range(numbers - 1, -1, -1): #
if dp[i] == answer:
arr.append(numbers_list[i])
answer -= 1
arr.reverse()
for i in arr:
print(i, end=" ")📌필요지식
1) range(a, b, -1)
- for문을 통해 i를 큰 수에서 작은 수로 반대로 대입하며 반복하고 싶을 때, 다음과 같이 사용할 수 있습니다.
- 한 가지 주의할 점은 거꾸로 할 때에도
range(a, b, -1)는 a부터 b미만까지 반복을 의미하므로 위 풀이와 같이 a는 반복하고 싶은 해당 리스트에 길이만큼, b는 0이 아닌 -1로 설정해주어야 함.
1912_연속합
⭕풀이:
test_case = int(input())
numbers = list(map(int, input().split()))
sum_list = [numbers[0]]
for i in range(len(numbers) - 1):
sum_list.append(max(sum_list[i] + numbers[i + 1], numbers[i +1]))
print(max(sum_list))1699_제곱수의 합
⭕풀이:
N = int(input())
dp = [i for i in range(N + 1)]
for i in range(1, N + 1):
for j in range(1, i):
if j * j > i:
break
dp[i] = min(dp[i], dp[i - j * j] + 1)
# if dp[i] > dp[i - j * j] + 1:
# dp[i] = dp[i - j * j] + 1
print(dp[N])⭕풀이설명:
dp[i] = dp[i - (j * j)] + 1
- dp엔 해당 인덱스에 해당하는 제곱수 합의 최소 항의 개수를 업데이트할 것입니다.
- 그러기 위해 초기 dp의 내부 요소값은 각 인덱스와 동일한 값으로 0,1,2,.. 배열입니다.
- i로 1부터 N까지 돌면서, j는 1부터 N-1까지의 수 중 제곱한 값이 i보다 크지 않아야 합니다.
- 그렇기 위해 나온 점화식이 dp[i] > dp[i-j*j] + 1 으로
i = 제곱수의 합의 최소 항의 개수를 찾아내기 위한 해당 index
j = i보다 작은 수의 제곱수가 될 값입니다.즉,
dp[6] = dp[6 - 2*2] + 1 = dp[2] + 1
입니다. - 여기서 1을 더해주는 이유는 앞서 뺀
2*2의 경우를 더한 것이기 때문입니다.
2*2 로 더하는 경우 (=1가지) + 나머지 dp[2] 의 경우를 더한다고 볼 수 있습니다. - N 이라는 타겟 넘버의 제곱수를 바로 구하는 것이 아닌, N 보다 작은 수 (i) 의 제곱수를 먼저 구하면서 N 까지 결과를 업데이트 하는 방법입니다.
https://junior-datalist.tistory.com/229
https://jyeonnyang2.tistory.com/50
타이밀크티는 맛있습니다.