OILAT

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 동적 프로그래밍 (Dynamic Programming) - 3 학습 후기 동적 프로그래밍 그 3번째 시간이다. 여러 동적 프로그래밍 문제를 풀며 동적 프로그래밍의 대표적인 문제 유형을 강의에서 정리해주었다. 1. 문제 크기 N을 변수로 만들어서 표기하는 경우 ex) i를 1, 2, 3의 합으로 표현하는 경우의 수 2. 문제 크기 N과 마지막 상태를 함께 기록해줘야 하는 경우 ex) 계단 오르기 1) Dy[i][0]: i - 1번째 계단을 밟지 않고, i 번째 계단에 도착하며 얻는 최대 점수 2) Dy[i][1]: i - 1번째 계단을 밟고, i 번째 계단에 도착하며 얻는 최대 점수 3. 구간 L ~ R에 대한 문제를 해결할 ..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 동적 프로그래밍 (Dynamic Programming) - 2 학습 후기 동적 프로그래밍: 작은 문제로 큰 문제의 해를 구하는 방법 이번 강의에서는 이전 강의에서 동적 프로그래밍 푸는 과정에서 잘못했을 때 어떻게 다시 식을 세워야 하는지 알려주는 강의였다. https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 조건 계단의 수 1

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