.PNG)
72. 네트워크 선 자르기(Bottom-Up)
현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다.
예를 들어 4m의 네트워크 선이 주어진다면
1) 1m+1m+1m+1m
2) 2m+1m+1m
3) 1m+2m+1m
4) 1m+1m+2m
5) 2m+2m
의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가
다르면 다른 경우로 생각한다.
그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요?
▣ 입력설명
첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다.
▣ 출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.
▣ 입력예제 1
7
▣ 출력예제 1
21
<내 풀이>
동적계획법에 대한 설명을 들었음
<풀이>
- f(n) = f(n-2) + f(n-1)
코드를 입력하세요
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])<반성점>
<배운 점>
출처 : 링크텍스트
동적계획법
:입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
:상향식 접근법으로, 가장 최하위 해답을 구한 후 이를 저장하고 해당 결과값 이용해서 상위 문제를 출어가는 방식
=>
-
Memoization
:프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 -
문제를 잘게 쪼갤 때 부분 문제는 중복되어 재활용
(ex)피보나치 수열
분할 정복
: 문제를 나눌 수 없을 때까지 나눠서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
-
하향식 접근법으로 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식
-
일반적으로 재귀함수로 구현
-
문제 잘게 쪼갤 때 부분문제는 서로 중복되지 않음
(ex) 병합정렬, 퀵정렬 등
공통점과 차이점
(1) 공통점
- 문제를 잘게 쪼개서 가장 작은 단위로 분할
(2) 차이점
-
동적 계획법 :
부분문제는 중복되어 상위 문제 해결 시 사용
메모이제이션 기법 사용(부분 문제의 해답을 저장해서 재활용하는 최적화 기법) -
분할 정복
-
부분 문제는 서로 중복되지 않음
-
메모이제이션 사용이 안됨
