동빈나 2021 이코테 _ 6. 다이나믹 프로그래밍

• 다이나믹프로그래밍 : 메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과의 재사용 --> 한번 계산해서 해결한 문제는 다시 계산하지 않도록 한다.
• 일반적으로 두가지 방식 ( 탑다운, 보텀업)으로 구성된다.

언제 DP로 문제를 풀 수 있는가??

1. 최적 부분 구조 : 특정 번째까지의 최적의해는 앞의 최적의해를 이용해서 계산되는경우

ex) i번째까지의 최적의해는 i-1, i-2번째까지의 최적의해를 이용하는 경우

2. 중복되는 부분문제

점화식으로 표현되는 식은 재귀함수를 통해 구현할 수 있다. but 시간복잡도가 큼

메모이제이션을 사용하는 탑다운 방법은 구현시 재귀함수를 이용한다. 즉, 큰 문제를 해결하기위해서 작은문제들을 재귀적으로 호출하여 작은문제가 모두 해결되었을때 큰 문제도 해결할수있도록함

 

보텀업 방법(아래쪽에서 작은문제를 먼저 해결해나감 ) 은 구현시 반복문을 이용한다.  다이나믹형태의 전형적인 형태이며 결과저장용 리스트는 dp테이블 이라고 부른다.

 

 < DP _ 탑다운방식 >

<DP _ 하향식방식>  _ 이게더 생각하기 쉬운것같음 (내기준)

 

 

한번 분할이 이루어지고 나면 5는 더이상 다른 부분문제에 포함되지 않고 위치가 더이상 변경되지 않기때문에 부분문제가 중복되지 않는다.

 

주어진 문제가 DP임을 파악하는것이 중요!!!!! ㅇㅈㅇㅈ

처음 접했을때 어렵다고 느낄스 있지만 반복적으로 이런 유형을 접해보면 익숙해질수 있다!

 

<예제문제1 _ 개미전사 >

 

창고0번만 있다고 했을때의 최적의해 -->

창고 0, 1번만 있다고 했을떄의 최적의 해 -->

창고 0,1,2번 있다고 했을때의 최적의 해-->

창고 0,1,2,3이 모두 있다고 했을때의 최적의해 

이렇게 DP를 갱신한다

 

위 두가지 경우 하나를 선택하면 현재위치까지 얻을수있는 최댓값이 된다.

 

DP 점화식

정답코드:

<예제문제2 _ 1로 만들기 >

esoongan.tistory.com/55

백준 1463번 파이썬 _ 1로 만들기

<예제문제3 _ 효율적인 화폐 구성 >

 

화폐단위가 2,3,5라고하면 2일때 전체한바퀴돌고 3일떄 전체한바퀴돌고 이런식으로 가면서 조건확인

 

step 1

 

step 2

step 3 (2단계에 비교해 7이 더작은값으로 갱신되었음)

결과적으로 7원을 만들기위한 최소한의 화폐개수는 2개가 된다.

 

정답코드:

자꾸 이상하게 생각을하는게 있는데 (내가) 1,2,3,4,5~~m까지 배열은 필요없어 ;; 그냥 반복문에서 i가 그 역할을 하자낭

 

<예제문제4 _  금광 >

내가 생각한 코드 점화식

현재위치의 optimal solution은 현재위치까지 올수있는 3가지 경우의 optimal solution중 가장 큰 값 + 현재의 금값

따라서 최적부분 구조문제를 충족한다.

• 금광정보가 한줄에 쭉 입력되므로 입력된 1차원 배열을 슬라이싱을 통해 dp테이블에 담는다.
• 외부반복문 j = 열  / 내부반복문 i = 행
• i=0이거나 n-1일때는 위에서 오는경우와 아래서 오는경우는 뺴줘야 하므로 left_up, left_down을 이용해서 예외처리해줌

<예제문제5 _  병사 배치하기 >

나열되어있는 병사에서 몇명을 열외시켜서 조건을 만족하도록 ( 전투력 내림차순 정렬+병사최대)

내 아이디어 :

문제발생부분 (뒤에병사가 전투력이 높아지는 부분) 에서 둘중 어떤것을 빼느냐에 땨라 다음문제발생부분까지 남아있는 병사의수를 비교

15 11 4 8 // 문제발생

1) 4를 빼는경우 : 15 11 8 5 2 4 // 삐빅 문제발생 : 5,2 두명의 병사

2) 8을 빼는경우 : 15 11 4 5 // 삐빅 문제발생 : 0명의 병사

 

LIS 알고리즘 ( 최장 증가부분수열)

점화식 : i는 각각의 원소가되고 j는 i보다 앞쪽에 있는 모든 원소 // 앞쪽 원소가 현재원소보다 작다면 다음과같은 점화식을따라 갱신

나를 끝으로하는 가장긴 부분수열의 길이보다, 나보다 앞에있는 원소중, 나보다 작은 어떤 원소를 마지막으로하며 그 끝에 내가 추가된 부분수열의 길이가 더 크면 후자의것이 더 최장길이가 되므로!

 

초기상태 : 길이 1

i=2일떄, 1 vs 2 = 2

최종적으로 dp테이블이 다음과같이 설정된다. 15를 마지막원소로 갖는 최장 증가부분수열의 길이는 5이다.

최종적으로 dp테이블의 원소중 가장큰값을 찾으면 그게 최장길이가된다.

 

다만 이 문제에서는 가장 긴 감소 부분수열을 구하는문제이므로 입력받은 병사정보의 순서를 뒤집은후 LIS알고리즘을 수행하면된다

외부반복문 : i번째 원소를 마지막으로 하는 부분수열을 확인 

내부반복문 : 0부터 현재원소(i)직전까지 확인하면서 현재원소보다 작은원소일때 점화식에 의해 확인한다.