우주의 IT 소행성

https://www.acmicpc.net/problem/1309

백준 1309번 동물원 문제를 풀던 도중...

d[n][k] 배열을 선언해야 했는데 (N(1≤N≤100,000), K = 3)

d = [[1, 0, 0]] + [[0, 0, 0]] * n 을 선언해서 solution을 돌렸을 때죽어도 원하는 값이 나오질 않았다.

분명 solution은 맞게 풀이하였고, 아무리 디버깅을 해봐도 맞았다.

그래서 d2 = [[0] * 3 for _ in range(n + 1)] 로 리스트를 다시 만들고d2[0][0] = 1로 초기화 해준 뒤 solution을 돌리니 원하는 값이 나왔다.

혹시나 해서 d의 값을 변경 해보았더니 아뿔싸.

리스트 d를 선언할 때 [[0, 0, 0]] * n 이 문제였다.

리스트 속 리스트를 곱연산 하기 때문에 외부 리스트와는 별개로

내부의 [0, 0, 0]이 얕은 복사가 이루어져 d[0]를 제외한 d[1:n + 1]까지의 모든 리스트가 얕은 복사가 된 것이다.

얕은 / 깊은에 대해서 내가 의도적으로 사용하지 않는 한 의식해본 적이 없었는데,

이렇게 문제를 풀면서 내가 많은 것을 놓치고 있었다는걸 다시금 깨달았다.

분발하자!

다이나믹 프로그래밍 (DP)

- 메모리 공간을 더 사용하여 연산속도를 비약적으로 증가시키는 방법

- 동적 계획법이라고도 함

- 탑다운과 보텀업 방식으로 나뉨

다이나믹 프로그래밍의 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

메모이제이션 (캐싱)

- DP구현 방법중 하나, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식이 호출될 때 메모한 결과만을 그대로 가져오는 기법

탑다운 (Top-Down, 하향식)

- 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법

- 큰 문제를 해결 하기 위해 작은 문제를 호출한다고 해서 Top-Down 방식이라 함

- 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.

보텀업 (Bottom-Up, 상향식)

- 반복문을 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법

- 작은 문제부터 차근차근 답을 도출한다고 해서 보텀업 방식이라 한다.

- 다이나믹 프로그래밍의 전형적인 형태

- 보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP테이블'이라 부른다

다이나믹 프로그래밍과 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전 계산 결과를 일시적으로 기록해 놓은 것이므로 다이나믹 프로그래밍과는 별도의 개념이다.