강의자료/알고리즘

[알고리즘] 동적계획법(Dynamic)

원당컴1 2023. 1. 18. 10:23
동적계획법 알고리즘이란

동적계획법은 문제의 최적해를 구하거나 답의 개수를 세는 과정에 사용하는 알고리즘 설계기법

- 전체 문제를 작은 문제로 단순화 한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식

 

 

동적계획법 알고리즘 설계 방법

1. 전체 문제를 작은 문제로 단순화한다. -> 부분문제를 정의

2. 재귀적인 구조를 활용할 수 있는 점화식을 만든다.

3. 작은 문제를 해결한 방법으로 전체 문제를 해결한다.

 

메모이제이션 기법

메모이제이션(Memoization)은 동적계획법에서 아주 중요한 개념이다.

함수의 값을 계산한 뒤 계산된 값을 배열에 저장하는 방식이다.

이러한 메모이제이션은 필요한 때마다 함수를 다시 호출하지 않고 값을 빠르게 가져 올 수 있다.

 

 

동적알고리즘 예시문제

www.acmicpc.net/problem/10164

 

10164번: 격자상의 경로

입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으

www.acmicpc.net

해결방법)

1) 부분문제를 정의한다. -> 왼쪽 위를 (0,0)으로 두고 (y,x) 까지 위치 좌표까지 갈 수 있는 최대 값을 저장하는 sum 배열을 만들자.

2) 점화식을 구한다. -> sum(y,x) 의 값은 sum(y-1,x) + sum(y,x+1) 라는 것을 구할 수 있다.

3) 배열을 이용해서 (0,0) 위치는 1을 넣고 해당 위치까지의 값을 채워 나가면 된다.

    for(i=1;i<21;i++)
    {
        for(j=1;j<21;j++)
        {
            sum[i][j]=sum[i-1][j]+sum[i][j-1];
        }
    }

 

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기

'강의자료 > 알고리즘' 카테고리의 다른 글

[알고리즘] 부분합  (8) 2023.02.08
[알고리즘] 조합탐색  (12) 2023.02.01
[알고리즘] 분할정복  (12) 2023.01.11
[자료구조] Suffix Array(접미사 배열)  (11) 2023.01.04
[자료구조] Persistent Segment Tree (PST)  (12) 2022.12.27