코딩테스트 관련 내용정리 (3)

▼▼▼ 이전글 보러가기 ▼▼▼

 

2021.02.20 - [코딩테스트] - 코딩테스트 관련 내용 정리 (1)

2021.02.20 - [코딩테스트] - 코딩테스트 관련 내용정리 (2)

코딩테스트 관련 내용정리 (2)

 

다이내믹 프로그래밍 (Dynamic Programming) 

---

1. 큰 문제를 작은 문제로 나눌 수 있는 경우

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

>> 다이나믹 프로그래밍을 적용하여 효율적으로 문제를 해결할 수 있다.

 

코딩테스트에서의 다이나믹 프로그래밍 문제는 대체로 간단한 형태로 출제되므로 방법만 제대로 습득하면 코딩테스트에서 문제를 풀기에는 큰 어려움이 없을 것

특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 '중복 여부'를 확인해보자. 

 

메모지에이션(memoziation) (=캐싱(caching))

---

다이나믹 프로그래밍을 구현하는 방법 중 한 종류로,한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 

 

 

실전문제 - 개미전사

---

[문제]

- 서로 인접하지 않은 식량창고만 털 수 있음

- 식량의 최댓값을 구하시오

 

[입력 조건]

- 첫째 줄에는 식량창고의 

 

입력 예	출력 예
4 1 3 1 5	8

 

[풀이]

(1) (i-1)번째 식량창고를 털기로 결정했다면 현재 창고는 털 수 없음 (→ 인접하지 않은 식량창고만 털 수 있으므로)

(2) (i-2)번째 식량창고를 털기로 결정했다면 현재 창고는 털 수 있음

 

위 두가지 경우 중 최댓값을 선택하면 된다.

 

점화식으로 표현하면 다음과 같다. 

ki 는 i 번째 식량창고에 있는 식량의 양을 의미

 

 

 

바텀업 방식으로 이 문제를 해결하면 다음과 같다.

 

 

참고문헌 및 출처 | 나동빈. 2020. 이것이 취준을 위한 코딩 테스트다 with 파이썬. 한빛미디어