[코독하구만 팀] 2021.01.27(수) - 6주차 개인 결과

- 목표 -

codekodo.tistory.com/42

[코독하구만 팀] 2021.01.27(수) - 6주차 개인 목표

 

1. 피보나치

재귀로 풀어도 되지만 dp를 활용하면 더욱 빠르게 정답에 접근이 가능하다.

 

 

2. 가방

점화식을 유도해야한다.

행은 가방의 최대 무게이고, 열은 주어진 물건의 무게이다.

이를 이용하여 최대한의 값어치를 구하고 표를 채우면 다음과 같이 채울 수 있다.

 

	0	1	2	3	4	5
0	0	0	0	0	0	0
2	0	0	3	3	3	3
3	0	0	3	4	4	7
4	0	0	3	4	4	7
5	0	0	3	4	5	7

 

이를 활용하여 점화식을 유도하면 아래와 같은 점화식을 유도할 수 있다.

dp[i][j] = dp[i-1][j] (weight > j)

dp[i][j] = max(dp[i-1][j], value + dp[i-1][j-weight])

 

 

3. 제재소

이 문제 역시 점화식을 유도해야한다.

행은 재료의 크기, 열은 자를 수 있는 크기이다.

이를 이용하여 최소한의 나무토막의 개수를 표로 나타내보면 다음과 같이 채울 수 있다.

 

이를 활용하여 점화식을 듀오하면 아래와 같은 점화식을 유도할 수 있다.

dp[j] = min(dp[j], dp[j-cut[i]] + 1)

 

 

4. 개구리 게임

가장 좌측 열의 경우(1열) 갈 수 있는 방향이 바로 위와 오른쪽 위 = 1열과 2열

가장 우측 열의 경우(4열) 갈 수 있는 방향이 바로 위와 왼쪽 위 = 3열과 4열

나머지 열의 경우 갈 수 있는 방향이 바로 위와 왼쪽, 오른쪽 위 = i-1열, i열, i+1열

 

이를 도착하는 지점의 시점에서 나타내면

가장 좌측 열의 경우(1열) 올 수 있는 방향이 바로 아래와 오른쪽 아래 = 1열과 2열

가장 우측 열의 경우(4열) 갈 수 있는 방향이 바로 아래와 왼쪽 아래 = 3열과 4열

나머지 열의 경우 갈 수 있는 방향이 바로 아래와 왼쪽, 오른쪽 아래 = i-1열, i열, i+1열

 

위의 식으로 dp를 채우고 첫번째 행에 저장된 값들 중에서 가장 큰 값을 출력한다.

 

 

5. 백준

 

 

이전에 풀어봤던 문제여서 쉽게 풀 수 있었다.

 

문제 해설을 첨부하였다. (codekodo.tistory.com/31)

[동적 계획법 1] [C++] 1463번. 1로 만들기

 

- 깃허브 -

github.com/k906506/2020_Winter_Assemble-And-selfcode

k906506/2020_Winter_Assemble-And-selfcode