[Dynamic Programming] - 다이나믹 프로그래밍이란? / 문제 1로 만들기

컴퓨터를 활용해도 해결하기 어려운 문제는 무엇일까?

• 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다.
• 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다.
• 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.

 

메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 대표적인 방법 => 다이나믹 프로그래밍

---

다이나믹 프로그래밍(Dynamic Programming)이란?

= 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법

 

🌟 다이나믹 프로그래밍 사용 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

대표적으로 다음 두 가지 방식이 사용된다.

Top-Down 방식(메모이제이션): 큰 문제를 해결하기 위해 작은 문제를 호출,
Bottom-Up 방식: 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출

---

문제

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

※ 책에 있는 1로 만들기와 같은 로직으로 풀 수 있는 문제를 첨부하였습니다.

 

---

풀이

아이디어

• 현재 수에서 1을 빼는 경우와, 나누어 떨어지는 경우 중 더 작은 수를 비교해 1을 만드는 연산 횟수의 최솟값을 구한다.
• 동일한 함수들이 여러 번 호출되고, 동일한 함수에서 구하는 값들은 동일해야 하므로 DP 사용조건 충족.

x = int(input())

# x의 입력값 + 1만큼의 DP 테이블 초기화
d = [0] * (x + 1)

# 다이나믹 프로그래밍 보텀업 진행
for i in range(2, x + 1):
    # 현재 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    # 현재 수가 3으로 나누어 떨어지는 경우 
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    # 현재 수가 2으로 나누어 떨어지는 경우 
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)

print(d[x])

 

참고

 

---

 

출처: 나동빈, 「이것이 취업을 위한 코딩테스트다 with 파이썬」, 한빛미디어, p.208~219