백준 복습 - 동적 계획법 1

동적 계획법 1 - 24416번: 알고리즘 수업 1 - 피보나치 수 1

https://jh4995.tistory.com/179

동적 계획법 1 - 24416번

---

동적 계획법 1 - 9184번: 신나는 함수 실행

https://jh4995.tistory.com/180

[C] 백준 - 9184번: 신나는 함수 실행

---

동적 계획법 1 - 1904번: 01타일

https://jh4995.tistory.com/182

[C] 백준 - 1904번: 01타일

---

동적 계획법 1 - 9461번: 파도반 수열

https://jh4995.tistory.com/184

[C] 백준 - 9461번: 파도반 수열

---

동적 계획법 1 - 1912번: 연속합

1) 연속합을 구하는 과정에서 새롭게 입력되는 수가 양수/음수인지를 구분하는 방법

-> 최초 생각은 버리고 새로 수정한 방법에 대한 복습

https://jh4995.tistory.com/186

[C] 백준 - 1912번: 연속합

---

동적 계획법 1 - 1149번: RGB거리

https://jh4995.tistory.com/188

[C] 백준 - 1149번: RGB거리

---

동적 계획법 1 - 1932번: 정수 삼각형

https://jh4995.tistory.com/190

[C] 백준 - 1932번: 정수 삼각형

---

동적 계획법 1 - 2579번: 계단 오르기

https://jh4995.tistory.com/192

[C] 백준 - 2579번: 계단 오르기

---

동적 계획법 1 - 1463번: 1로 만들기

1) 최초 문제 조건 파악 관련 복습

2) 동적계획법 풀이과정중에서 MIN안에서 비교해야하는 대상의 표현에 대한 복습

https://jh4995.tistory.com/194

[C] 백준 - 1463번: 1로 만들기

---

동적 계획법 1 - 2156번: 포도주 시식

https://jh4995.tistory.com/196

[C] 백준 - 2156번: 포도주 시식

---

동적 계획법 1 - 10844번: 쉬운 계단 수

1) 2차원 dp를 설정하는 경우, 두 인덱스에 각각 어떤 의미에 해당하는 값을 할당할 것 인지 복습

2) 마지막에 엄청 큰 수로 나눈 나머지를 출력 -> 각각의 계산마다 매번 나머지 계산은 왜 해야하는지 추가공부

https://jh4995.tistory.com/198

[C] 백준 - 10844번: 쉬운 계단 수

---

동적 계획법 1 - 11053번: 가장 긴 증가하는 부분수열

1) 전체 참고 -> 처음부터 복습

https://jh4995.tistory.com/200

[C] 백준 - 11053번: 가장 긴 증가하는 부분수열

---

동적계획법의 경우

주어지는 문제의 조건과 예제의 입출력을 통해서 점화식을 만들어내는것이 가장 중요하다

 

- 점화식을 만들기 전

"1904번: 01타일" 혹은 "9461번: 파도반 수열" 문제에서는

위에서 말했던 것 처럼 문제의 조건 그리고 예제에서 점화식으로 뽑아낼 수 있는 관계성을 찾아내는 것이 중요하다

위의 문제들에서는 피보나치 수열이 숨어있었고, 이를 발견해낸 뒤, dp배열을 이용해서 동적계획법을 적용해야한다

하지만 이렇게 점화식을 만들다보면, 처음으로 입력되는 값부터 그 점화식이 바로 적용되지 않을 수 있다

1) 위의 "9461번: 파도반 수열"은 배열의 세 번째 값까지 모두 1이고 그 이후에 피보나치 수열 계산이 성립한다

2) 혹은 "1149번: RGB거리"처럼 가장 처음의 값들은 일단 입력해놓아야 이후의 점화식을 계산할 수 있기도 하다

결국 반복문안에서 dp배열을 활용한 점화식을 계산하기위한 사전작업으로, 초기값들은 임의로 선언해야할 수 있다

 

- 점화식을 만드는 과정에서

1) dp배열을 1차원 배열로 사용할 것 인지 / 2차원 배열로 사용할 것 인지를 결정해야한다

즉 주어진 조건이 몇 가지 존재하고, 이들을 어찌 활용할것인지 전체적인 풀이과정을 미리 그려보며 결정해야한다

2) 또한 dp배열의 인덱스값을 단순히 이전의 누적된 값들을 불러오는 용도로 쓸 것 인지( dp[i-1] , dp[i-2] ... )

아니면 인덱스값에 사칙연산을 해주며 활용할 것 인지 결정해야한다( dp[i/3] , dp[i/2] ... )

 

- 점화식을 만들어냈다면

1) 동적계획법에서 최종적으로 구해야하는 것은 점화식으로 계산한 최댓값 혹은 최솟값인 경우가 많다

값들을 누적해놓은 dp 값과 새로운 입력값들을 활용해서 새로운 dp[ i ]를 결정하는 과정에서, 대소비교가 요구된다

-> 이러한 과정을 거치며 dp에 누적된 최댓값 혹은 최솟값을 저장할 수 있을 것 이기 때문

결국 아래와 같이 입력되는 2개 수의 대소관계를 비교하여 원하는 값을 출력해내는 함수를 자주 사용하게된다

"2579번: 계단 오르기"와 "2156번: 포도주 시식"에서는 현재의 계단(와인잔)이 연속된 2개의 계단(와인잔)중에서

첫 번째 계단(와인잔)인 경우 /  혹은 두 번째 계단(와인잔)인 경우로 나누어서

둘 중 더 큰 값을 가지는 경우를 새로운 dp[i]에 넣는 계산을 진행해야한다

이 과정에서 아래의 함수를 사용하게된다

int MAX(int x, int y)
{
	return ((x > y) ? x : y);
}

2) 또한 점화식을 문제의 조건에따라 개별적으로 나누어서 만들어야하기도 한다

"1932번: 정수 삼각형"에서는 삼각형의 한 줄에서 왼쪽 끝에 위치한 j=1인 경우 / 오른쪽 끝에 위치한 j=i인 경우 /

둘을 제외하고 중간에 위치한 경우로 나누어서 점화식을 작성하고, dp값을 갱신한다

"10844번: 쉬운 계단 수"에서도 이전의 숫자가 1이라서 j가 0이 되는 경우 / 이전의 숫자가 8이라서 j가 9가 되는 경우 /

이들을 제외한 다른 값인 경우로 나누어서 점화식을 작성하고, dp값을 갱신한다

"1463번: 1로 만들기"에서는 반복문의 i 가 3으로 나누어떨어지는 경우 / 2로 나누어떨어지는 경우에 따라서

dp값을 갱신하는 점화식을 다르게 계산해야한다

-> 이 과정에서 dp배열의 인덱스값에 연산을 하는 풀이도 하게된다

 

 

+) dp배열의 크기를 꽤나 큰 수로 잡게된다

이럴경우 dp배열을 main함수안이 아닌 밖에서 전역으로 정의하면 heap으로 넘기라는 warning이 생기지 않는다

+) dp배열을 활용하는 경우, 첫 번째 값을 dp[0]에 넣게되면 이후 숫자가 커지며 헷갈린다

원활한 풀이와 정신건강을 위해서라도 반복문의 시작을 기존 int i = 0이 아닌 int i = 1부터 시작하는 것을 추천

+) 그리고 점화식을 만들다보면 dp[0]의 값도 필요한 경우가 생기므로, 이때는 dp[0]=0을 넣어서 해결

+) "2579번: 계단 오르기" 문제와 "2156번: 포도주 시식" 문제는 결이 매우 비슷하다