[Algorithm] 동적 프로그래밍 (DP, Dynamic Programming)

2024. 3. 20. 17:09· → 알고리즘 관련
목차
  1. Dynamic Programming
  2. Dynamic Programming 의 예시
  3. 피보나치수열
  4. 동적 프로그래밍으로 피보나치 수열 계산

Dynamic Programming

동적 프로그래밍, 다이나믹 프로그래밍, 동적 계회법으로 불리는 Dynamic Programming은 큰 문제를 작은 문제로 나누고 작은 문제의 답들을 이용해 원래 문제의 답을 찾는 방법이다. 주어진 문제를 최대한 많이 이용할 수 있는 작은 문제들로 나누는 게 핵심이라고 생각한다. (그래야 재사용이 많이 가능하고, 메모리를 적게 쓴다)

출처: 나무위키

Dynamic Programming 의 예시

피보나치수열

가장 쉬운 예로는 피보나치 수열이 있다. 피보나치수열은 아래와 같이 표현할 수 있다.

f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2) when n > 1

 

만약 값을 재사용하지 않는다면...? 아래와 같이 5번째 값을 구하기 위해서는 15번의 연산이 필요하다.

 

아래와 같이 점화식을 통해 간단하게 n번째 피보나치수열을 구하는 함수를 만들 수 있다. 하지만 이 함수는 매우 비효율적이다. 매번 계산을 해줘야 하기 때문이다.

func fib(_ n: Int) -> Int {
    if n <= 1 {
        return 1
    } else {
        return fib(n-1) + fib(n-2)
    }
}

 

아래와 같이 count를 넣어보면 15번 계산이 된다는 것을 볼 수 있다.

import Foundation

var count = 0

func fib(_ n: Int) -> Int {
    if n <= 1 {
        count += 1
        return 1
    } else {
        count += 1
        return fib(n-1) + fib(n-2)
    }
}

print(fib(5)) // 8
print("count: \(count)") // count: 15

 

동적 프로그래밍으로 피보나치 수열 계산

Top-Down, Bottom-Up 방식이 존재한다. 둘 다 재사용할 결괏값을 저장할 메모리를 만드는 것은 동일하지만 Top-Down은 위에서부터 접근해서 결과값이 없다면 계산해주는 방식이고, Bottom-Up은 초기값으로부터 결과값을 모두 계산해 준 뒤 결과를 찾는 방식이다. 아래에 코드를 보면 좀 더 이해가 잘 될 것이다.

 

Top-Down 방식

큰 문제부터 시작해서 작은 문제로 분할해 가는 과정이다. 메모리를 만들어놓고 계산된 값을 넣어주고, 계산된 값이 없으면 계산해 준다. 불필요한 계산을 줄여줄 수 있다.

import Foundation

var memory = Array(repeating: 0, count: 6)

func fib(_ n: Int) -> Int {
    if n <= 1 {
        memory[n] = 1
        return 1
    } else if memory[n] != 0 {
        return memory[n]
    } else {
        memory[n] = fib(n-1) + fib(n-2)
        return memory[n]
    }
}

print(fib(5)) // 8
print(memory) // [1, 1, 2, 3, 5, 8]

 

Bottom-Up 방식

다양한 방식으로 구현할 수 있겠지만 내가 사용한 방식은 아래와 같다. 우선 배열을 만들어 준 후 초기값을 넣어 준 후 배열을 완성해 준다. 그리고 저장된 메모리에서 n번째를 return 해주면 된다. 이렇게 불필요한 반복계산을 줄여줄 수 있다.

import Foundation

func fib(_ n: Int) -> Int {
    var memory = Array(repeating: 0, count: n+1)
    
    memory[0] = 1
    memory[1] = 1
    
    if n >= 2 {
        for i in 2...n {
            memory[i] = memory[i-1] + memory[i-2]
        }
    }
    
    return memory[n]
}

print(fib(5)) // 8

 

어떻게 보면 계산한 값을 재활용한다는 간단한 아이디어인데 이런 아이디어만으로도 효율적으로 문제를 해결할 수 있다는 것이 신기하고 재밌다.

'→ 알고리즘 관련' 카테고리의 다른 글

[Algorithm] 시간복잡도에 대해서 (big-O, Ω, θ 표기법)  (2) 2024.03.26
[Algorithm] 힙(Heap) 구현하기 (Swift)  (0) 2024.03.21
[Algorithm] 순열과 조합 구하기 (Swift)  (0) 2024.03.09
[Algorithm] 팩토리얼 구하기 (Swift, 재귀 함수)  (0) 2024.03.09
[Swift] 진수 변환 (Radix)  (1) 2024.02.07
  1. Dynamic Programming
  2. Dynamic Programming 의 예시
  3. 피보나치수열
  4. 동적 프로그래밍으로 피보나치 수열 계산
'→ 알고리즘 관련' 카테고리의 다른 글
  • [Algorithm] 시간복잡도에 대해서 (big-O, Ω, θ 표기법)
  • [Algorithm] 힙(Heap) 구현하기 (Swift)
  • [Algorithm] 순열과 조합 구하기 (Swift)
  • [Algorithm] 팩토리얼 구하기 (Swift, 재귀 함수)
Swift librarian
Swift librarian
Swift librarian
Swift Library
Swift librarian
전체
오늘
어제
  • 분류 전체보기 (231)
    • 📺 Programming (5)
    • → Architecture (2)
    • → Design Pattern (0)
    • → Computer Science (15)
    • ⚙️ Algorithm (0)
    • → 알고리즘 관련 (22)
    • → Problems (104)
    • 🚀 Project (0)
    • → 알쏭달쏭 (0)
    • → Shook (2)
    • → Solver (8)
    • → Taster (7)
    • → Outline (4)
    • → Pointer (2)
    • → Guesser (3)
    • 🦜 Swift (2)
    • → Swift Archive (12)
    • → Swift Study (12)
    • → Xcode (6)
    • 🧰 Framework (0)
    • → Foundation (1)
    • → UIKit (2)
    • → SwiftUI (3)
    • → CoreData (2)
    • → MapKit (1)
    • → CoreHaptic (1)
    • → User Notification (1)
    • → StoreKit (2)
    • 🏛️ Library (0)
    • → TCA (0)
    • 🐈‍⬛ Git (8)
    • → Git의 원리 (2)
    • → Git 심화 (1)
    • 📦 Other (1)
    • 👦🏻 Log (0)

최근 글

hELLO · Designed By 정상우.v4.2.2
Swift librarian
[Algorithm] 동적 프로그래밍 (DP, Dynamic Programming)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.