4. 동적 프로그래밍(Dynamic Programming)

1. 동적 프로그래밍(Dynamic Programming)
* 복잡한 문제를 작은 하위 문제들로 나누고 그 결과를 재사용하여 효율적으로 문제를 해결하는 알고리즘 기법
* 주어진 문제를 풀 때,같은 하위 문제를 여러 번 푸는 대신,그 결과를 저장해 두고 필요할 때 다시 사용하는 방식

1-1. 동적 프로그래밍의 접근 방식
* 메모이제이션(Bottom-Down): 큰 문제를 풀기 위해 재귀적으로 하위 문제들을 풀면서, 이미 계산된 하위 문제는 저장된 값을 재사용하는 방식
* 테이블 방식(Bottom-Up): 작은 하위 문제부터 시작해 차례대로 계산해가며, 최종적으로 큰 문제를 해결하는 방식

1-2. 동적 프로그래밍 알고리즘
* 피보나치 수열 n을 입력받아서 계산
* [피보나치](https://namu.wiki/w/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98%EC%97%B4)

```
함수 이름을 fibonacci 라고 하면
fibonacci(0): 0
fibonacci(1): 1
fibonacci(2): 1
fibonacci(3): 2
fibonacci(4): 3
fibonacci(5): 5
fibonacci(6): 8
...
```

# 재귀 함수를 활용
def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)


fibonacci(6)
-->
8


# 메모이제이션 활용
def fibonacci(num):
    cache = [0 for index in range(num + 1)]
    # print(cache)
    cache[0] = 0
    cache[1] = 1
    for index in range(2, num + 1):
        cache[index] = cache[index-1] + cache[index-2]
    return cache[num]

 

문제1

* 2 * n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
(단, 출력은 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.)
#인덱스 1~1000까지의 범위를 지정한다
# for index in range(1, 1001): 
#     print(index)
dp = [0] * 1001
dp[0], dp[1000]
-->
(0, 0)

-------------------
#답안
dp[1] = 1
dp[2] = 2
n = int(input())

for index in range(3, 1001):
    dp[index] = dp[index-1] + dp[index-2]
print(dp[n] % 10007)

 

문제 2

* 파도반 수열

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다.

그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다.

나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다.

P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력은 첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다.

(1 ≤ N ≤ 100)

 

# 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16 ...
# dp[i + 3] = dp[i] + dp[i + 1]
dp = [0] * 101
dp[1] = 1
dp[2] = 1
dp[3] = 1

for index in range(0, 98):
    dp[index+3] = dp[index] + dp[index+1]

print(dp[6])
print(dp[12])


# 테이블 방식
# 작은 하위 문제들부터 차례로 해결해가며 결과를 테이블에 저장
def fibonacci(num):
    if num <= 1:
        return num
    dp = [0] * (num + 1)
    dp[1] = 1

    for i in range(2, num + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[num]
    
    
fibonacci(4)    
fibonacci(6)
-->
3
8