✏️ 서론
오늘은 어제 배웠던 동적계획법의 예제들을 풀어보자.
✏️ 본론
📍 [ 문제 1 ] 1463 - 1로 만들기
이 문제는 잘 알려진 다이나믹 프로그래밍 문제다.
피보나치 수열 문제를 도식화했던 것처럼 문제를 풀기 전에 함수가 호출되는 과정을 직접 그림으로 그려보면 이해하는데 도움이 된다.
점화식은 다음과 같다.
a(i) = min(a(i-1), a(i-2), a(i-5)) + 1
점화식 끝에 1을 더해주는 이유는 함수의 호출 횟수를 구해야하기 때문이다.
실제 코드로 구현 할 때는 1을 빼는 연산을 제외하고는 해당 수로 나누어떨어질 때 한해서만 점화식을 적용 할 수 있다.
두 수 중 단순히 더 작은수를 구할 때는 min() 함수를 이용하자.
이 문제를 풀때 사실 답안 예시를 보고도 이해가 되지않았다. 그래서 다른 사람들은 어떻게 풀었는지 검색해봤는데
빈 리스트(values)를 선언하고 거기에 추가하는 방식이다.
# bottom_up 방식
n = int(input())
# 셋 중 편한식을 사용하자.
# 30001은 정수 X의 범위가 (1 <= x <= 30000)이기 때문에 1개를 더 추가해 작성했다.
array = [0 for _ in range(n+1)]
array = [0] * (n+1)
array = [0] * 30001
# 반복문의 범위가 2부터 시작하는 이유는 array [0], [1]이 모두 0이기 때문이다.
for i in range(2, n+1):
if i == 1:
continue
values = []
if i % 3 == 0:
values.append(array[i//3] + 1)
if i % 2 == 0:
values.append(array[i//2] + 1)
if i % 5 == 0:
values.append(array[i//5] + 1)
values.append(array[i - 1] + 1)
array[i] = min(values)
print(array[n])
👉🏽 3# bottom_up 교재 방식
n = int(input())
array = [0] * 30001
for i in range(2, n+1):
d[i] = d[i-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)
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1)
print(d[n])
👉🏽 3📍 [ 문제 2 ] 11726 - 2 x N 타일링
이 문제 또한 다이나믹 프로그래밍 기초 예제에서 빠질 수 없는 타일링 문제 유형이다. 문제를 잘 보면 마지막에 10,007로 나눈 나머지를 출력하라고 명시되어있는데,
이는 단지 결과값이 굉장히 커질 수 있기 때문에 그런 것이다.
식 마지막에 (d[x-1] + d[x-2]) % 10007을 붙여주자.
처음에 타일링 문제를 풀때 이해가 하나도 되지않았다. 왜 점화식을 사용해야하고 어떻게 작성하는지 감이 안와서 절망하며
강의를 찾아보다 나동빈 - 다이나믹프로그래밍 타일링 문제 풀어보기 편을 봤는데 어떻게 점화식을 작성해야하는지 잘 나와있어서 타일링 문제는 잘 풀 수 있을 것 같다.
나처럼 타일링 문제 이해가 잘 안되는 분들은 밑져야본전인 생각으로 한번 강의를 봤으면 좋겠다!
백준에서 타일링문제를 몇 번 풀어보니까 점화식이 대체로 큰 틀에서 벗어나지 않는다는 느낌을 받았다.
점화식을 구할 때 N=1, N=2일 때의 경우의 수를 구하고 처음에 선언해준 뒤 나중에 N-1, N-2의 경우의 수를 구하면 끝이었다.
이런식으로 혼자서 정리해봤다.(발 글씨 양해부탁드립니다.)
✏️ 결론
강의를 들으면서 나동빈님이 코딩테스트에서 자주 출제되는 문제 유형 중 하나가 지금 배운 다이나믹프로그래밍이라고 하셨다.
문제를 풀면서 삽질을 하도 많이해서 시간이 다 날라가 버렸따. 😂 😂
내일까지 동적분할법 문제를 한번 더 풀면서 감을 조금 더 익혀야겠다.
