Algorithm - 네트워크선 자르기(동적 계획법)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[네트워크선 자르기(동적 계획법)]

 

현수는 네트워크선을 1m, 2m의 길이를 갖는 선으로 자르려고 한다.

예를 들어, 4m의 네트워크 선이 주어진다면 아래와 같이 5가지의 방법을 생각할 수 있다.

 

4m 네트워크선을 자르는 경우의 수

 

2)와 3)과 4)의 경우는 왼쪽을 기준으로 자르는 위치가 다르기 때문에 다른 경우의 수로 고려한다.

네트워크선의 길이가 N일 때, 1m 혹은 2m의 길이로 네트워크선을 자르는 방법을 구하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 네트워크 선의 총 길이인 자연수 N(3 ≤ N ≤ 45)이 주어진다.

 

*출력 설명

첫 번째 줄에 길이가 N인 네트워크선을 자르는 경우의 수를 출력한다.

 

 

---

 

 

풀이(Python)

답안(Bottom-Up)

import sys
sys.stdin = open('AA/input_73.txt', 'rt')

n = int(input())
dy = [0]*(n+1)

dy[1] = 1
dy[2] = 2

for i in range(3, n+1):
    dy[i] = dy[i-1] + dy[i-2]
    
print(dy[n])

# 출력 : 89

 

input_73.txt(입력)

10

 

 

중요내용

1. 위 문제풀이는 바텀업(Bottom-Up) 방식으로 접근한 것이다.
2. 바텀업(Bottom-Up) 방식은 작은 규모의 문제부터 시작해서 점차 규모를 확장시켜 결국 규모가 큰 문제를 해결하는 방식이다.
3. 즉, 길이가 1m인 네트워크선부터 접근해서 해결한 후, 2m, 3m, 4m, ... ,  Nm 와 같이 길이를 확장해나가며 문제의 접근 방식을 찾는 것이다.
4. 위의 문제에서는 바텀업 방식으로 점화식의 규칙을 찾는 것이 중요하다.
5. dy[1] = 1, dy[2] = 2는 직관적으로 바로 알 수 있기 때문에 경우의 수를 미리 선언해준 것이다.
6. 점화식을 찾는 방법은 네트워크선의 마지막 부분을 1m 혹은 2m로 자르는 경우의 수를 고려하면 된다.
7. 예를 들어, 3m 짜리의 네트워크선을 자른다고 하면 마지막 부분을 1m 로 만드는 경우와 2m로 만드는 경우 2가지가 존재한다.
8. 만약 네트워크선의 마지막 부분을 1m로 만들면 나머지 부분은 2m가 남게되고, 2m를 자르는 경우의 수는 2가지로 이미 알고 있다.
9. 만약 네트워크선의 마지막 부분을 2m로 만들면 나머지 부분은 1m가 남게되고, 1m를 자르는 경우의 수는 1가지로 이미 알고 있다.
10. 따라서 마지막 부분을 1m로 만드는 경우와 2m로 만드는 경우를 더하면 3m의 네트워크선을 자르는 경우를 모두 고려하는 것이다.
11. 결국 길이가 N인 네트워크선을 1m 혹은 2m로 자르는 점화식(규칙)은 f(n) = f(n-1) + f(n-2)이다.
12. 참고로 변수 dy는 길이가 N인 네트워크선을 자르는 경우의 수를 저장하는 리스트이다.

 

 

추가풀이(Python)

답안(Top-Down : 재귀함수 & 메모이제이션)

import sys
sys.stdin = open('AA/input_73.txt', 'rt')

def DFS(len):
    if dy[len] > 0:
        return dy[len]
    if len == 1 or len == 2:
        return len
    else:
        dy[len] = DFS(len-1) + DFS(len-2)
        return dy[len]


if __name__ == "__main__":
    n = int(input())
    dy = [0] * (n+1)
    print(DFS(n))

 

input_73.txt(입력)

10

 

 

참고내용

1. 재귀함수(DFS)를 통해 해당 문제를 접근하면, 전위순회 방식(부모노드 -> 왼쪽 자식노드 -> 오른쪽 자식노드)으로 탐색을 진행한다.
2. 단, 전위순회 방식은 탑다운(Top-Down) 방식으로 접근한다.
3. 이 때, 중복 탐색은 불필요하므로 리스트 dy에 이미 특정 값이 존재하면 중복 탐색 대신 해당 값을 리턴하는 것으로 컷엣지를 한다. (시간복잡도 개선)
4. 이러한 방식을 ' 메모이제이션 '이라고 한다. (ex. if dy[len] > 0: --> return dy[len])
5. 참고로 DFS() 함수의 인자인 len은 네트워크선의 길이를 의미한다.