본문 바로가기

CS/Data Structure & Algorithm

동적 계획법(DP)

목차

    DP

    • 문제에 대한 정답이 될 가능성이 있는 모든 해결책체계적이고 효율적으로 탐색하는 풀이
    • Top-down / Bottom-up 방식이 존재
    • 최대/최소, 방법의 개수 등을 구할 때 주로 사용
    • 미래의 계산이 앞선 계산 결과에 영향을 받을 때 주로 사용

    DP 문제해결 과정

    1. 크고 복잡한 문제를 작은 문제들로 나눔 : subproblem(하위문제)
    2. 하위 문제의 답을 계산
      중복 계산해야 하는 하위 문제가 존재 : overlapping subproblem(중복하위문제)
      한 번 계산한 결과는 메모리에 저장하여 재계산하지 않도록 함 => 속도 향상(memoization, dp table)
    3. 하위 문제에 대한 답을 통해, 원래 문제에 대한 답을 계산 : potimal substructure(최적 부분 구조)
      * 최적 부분 구조: 하위 부분 문제에서 구한 최적의 답이, 합쳐진 큰 문제의 최적의 답을 구할 수 있는 구조

    피보나치 수열

    • f(n) = f(n-2) + f(n-1)
    • 완전탐색(재귀)으로 해결 시, 시간복잡도 O(2^n)
    • DP로 해결 시, 시간 복잡도 O(n)
    • 반복되는 계산 부분, memoization
    •  
    memo = {}
    def fibo(n):
    	#초기값
    	if n==1 or n==2:
    		return 1
        #dp 테이블에 없으면 직접 계산하여 추가
    	if n not in memo:
    		memo[n] = fibo(n-1) + fibo(n-2)
    	return memo[n]

    Top-down vs Bottom-up

    •   
      Top-down(memoization) Bottom-up(tabulation)
      재귀 사용 => 구현 시간이 빠름 반복문 사용 => 실행 시간이 빠름
      재귀풀이에서 중복되는 계산 값을 저장.
      이후 동일한 함수 호출시 재활용
      더 작은 subproblem에 대한 계산 결과를
      DP table에 저장하여 큰 문제 계산에 활용
      hash talbe 또는 list에 계산 결과를 저장
    • 재귀함수로 비효율적인 완전 탐색 코드 작성 -> 중복되는 subproblem에 계산 결과를 저장 -> 이후 바텀업으로의 전환 고려

    참고자료

    https://www.inflearn.com/course/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%85%EB%AC%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC

     

    'CS > Data Structure & Algorithm' 카테고리의 다른 글

    Dijkstra  (0) 2024.04.22
    그래프 순회  (0) 2024.04.16
    그래프  (0) 2024.04.16
    트리 순회  (0) 2024.04.16
    재귀 & 트리  (0) 2024.04.16