More actions
No edit summary |
(Repair batch-0005 pages from live compare) |
||
| (8 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
__TOC__ | __TOC__ | ||
[https://www.slideshare.net/InseoPark1/dynamic-programming-step-by-step 강의 자료] | |||
== Dynamic Programming이란? == | == Dynamic Programming이란? == | ||
| Line 5: | Line 6: | ||
* 사실 그냥 멋있어서 붙인 이름 | * 사실 그냥 멋있어서 붙인 이름 | ||
* 문제를 작은 문제로 나누는 것에서 출발 | * 문제를 작은 문제로 나누는 것에서 출발 | ||
== 문제 == | == 문제 == | ||
| Line 13: | Line 13: | ||
** 결과를 합친다. | ** 결과를 합친다. | ||
=> Divide And Conquer (분할 정복) | => Divide And Conquer (분할 정복) | ||
** Memoization : 동일한 계산을 반복해야 할 때, 이전 계산 값을 저장함으로써 빠르게 계산하는 방법 | ** Memoization : 동일한 계산을 반복해야 할 때, 이전 계산 값을 저장함으로써 빠르게 계산하는 방법 | ||
** Dynamic Programming 에서 핵심이 되는 기술 | |||
** 예시 | ** 예시 | ||
** 피보나치 함수 ( f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1 ) | |||
** 기본 정의에 의한 Fibonacci 구현 | |||
=> 중복이 많이 발생 | => 중복이 많이 발생 | ||
=> 중복에 대한 결과를 미리 저장한다면 | => 중복에 대한 결과를 미리 저장한다면 | ||
=> Memoization(메모이제이션)! | => Memoization(메모이제이션)! | ||
*** 이항계수 | *** 이항계수 | ||
*** 구간합 구하기 | *** 구간합 구하기 | ||
*** 2차원 구간합 | |||
== 실제 문제 풀이 == | == 실제 문제 풀이 == | ||
* 백준 2748 - 피보나치 수 2 | * 백준 2748 - 피보나치 수 2 풀어보세요 | ||
* 백준 11051 - 이항계수 | * 백준 11051 - 이항계수 풀어보세요 | ||
* 백준 11659 - 구간합 구하기 4 풀어보세요 | |||
* 백준 11660 - 구간합 구하기 5 풀어보세요 | |||
Latest revision as of 00:44, 27 March 2026
Dynamic Programming이란?
- 한국어로는 동적 계획법
- 사실 그냥 멋있어서 붙인 이름
- 문제를 작은 문제로 나누는 것에서 출발
문제
- 문제를 푸는법
- 문제를 나눈다.
- 문제를 푼다.
- 결과를 합친다.
=> Divide And Conquer (분할 정복)
- Memoization : 동일한 계산을 반복해야 할 때, 이전 계산 값을 저장함으로써 빠르게 계산하는 방법
- Dynamic Programming 에서 핵심이 되는 기술
- 예시
- 피보나치 함수 ( f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1 )
- 기본 정의에 의한 Fibonacci 구현
=> 중복이 많이 발생 => 중복에 대한 결과를 미리 저장한다면 => Memoization(메모이제이션)!
- 이항계수
- 구간합 구하기
- 2차원 구간합
실제 문제 풀이
- 백준 2748 - 피보나치 수 2 풀어보세요
- 백준 11051 - 이항계수 풀어보세요
- 백준 11659 - 구간합 구하기 4 풀어보세요
- 백준 11660 - 구간합 구하기 5 풀어보세요