코딩테스트 - 패스트캠퍼스 챌린지 37일차

수강한 강의

Part 3. 알고리즘 유형별 풀이

Chapter 02 알고리즘
- 동적 프로그래밍 (Dynamic Programming) - 1

학습 후기
동적 프로그래밍(Dynamic Programming)란 문제의 크기를 변화하면서 정답을 계산하는데, 작은 문제의 결과를 이용해서 큰 문제의 정답을 빠르게 계산하는 알고리즘이다.
동적 프로그래밍 시나리오
1. 문제가 원하는 정답을 찾기 위해 가장 먼저 완전 탐색 접근을 시도해 본다.
2. 근데, 완전 탐색 과정에서 탐색하게 되는 경우가 지나치게 많아서 도저히 안 될 경우
3. 모든 경우를 빠르게 탐색하는 방법으로 다이내믹 프로그래밍 접근을 시도해 볼 수 있다.
동적 프로그래밍을 푸는 규격화된 방법
1. 풀고 싶은 가짜 문제를 정의한다.
2. 가짜 문제를 풀면 진짜 문제를 풀 수 있는가?
3. 가장 작은 문제 해결하기
4. 3번을 기반으로 점점 더 큰 문제들을 해결하기, 점화식 구하기
5. 1 ~ 4가 성공적으로 끝난다면 가짜 문제로 진짜 문제 해결하기

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

9095번: 1, 2, 3 더하기

동적 프로그래밍으로 풀 때 가짜 문제를 사용해서 먼저 작은 문제로 풀고 그 후에 답을 구해낸다. 문제에서 주어진 조건을 활용하여 실제 문제를 풀기 전에 전처리를 하여 배열을 만들고 진짜 문제에서는 바로 답을 나올 수 있도록 구한다.

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

11726번: 2×n 타일링

2 * n 타일링에서 진짜 문제는 N이 주어질 때 타일을 채우는 거라면 가짜 문제로 일단 i를 사용하여 어느 정도 직접 계산해본다. 점화식을 구할 때 i를 직접 찾아볼 수 있는 범위까지 구해본 후 마지막에 오는 게 무엇인지 확인하여 공통점을 찾아본다. 이때 공통점은 마지막에 가로로 2개의 타일이 오는 경우와 세로로 1개의 타일이 오는 경우이다. 이 공통점을 가지고 점화식을 구하면 (Dy[i-1] + Dy[i-2]) % 10,007 = Dy [i]이다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.