TIL

🌱 난 오늘 무엇을 공부했을까?

📌 dynamic programming

• 동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
  • 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달
• 동적 계획 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용
• Memoization 기법을 사용함
  • Memoization : 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
• 상향식 접근법
• 분할 정복과 비교를 많이 한다.

📍 분할 정복

• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 하향식 접근법

📍 DP와 분할 정복의 공통점

• 문제를 잘게 쪼개서, 가장 작은 단위로 분할

📍 DP와 분할 정복의 차이점

• 동적 계획법
  • 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨
  • Memoization 기법 사용 (부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)
• 분할 정복
  • 부분 문제는 서로 중복되지 않음
  • Memoization 기법 사용 안함

📍 피보나치 수열로 보는 재귀함수, DP

• DP

func fibo(_ n: Int) -> Int {
    var cache: [Int] = [0, 1]
    
    guard n > 1 else { return n }
    
    for num in 2...n {
        cache.append(cache[num - 2] + cache[num - 1])
    }
    
    return cache[n]
}

• 재귀함수

function fibo(n: Int) {
    if n == 0 {
        return 0
    } else if n == 1 {
        return 1
    } else {
        return fib(n-1) + fib(n-2)
    }
}