[백준] 1003번 피보나치 함수 (C++) - dynamic programming

문제

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

코드

#include <iostream>
#include <utility>

using namespace std;

int main(){
  int t;
  cin >> t;

  pair<int, int> fibo[40] = {{1,0}, {0,1}};
  
  for(int i=0; i<t; i++){
    int n;
    cin >> n;

    for(int j=2; j<=n; j++){
      fibo[j] = make_pair(fibo[j-1].first+fibo[j-2].first, fibo[j-1].second+fibo[j-2].second);
    }
    cout << fibo[n].first << " " << fibo[n].second << '\n';
  }

  return 0;
}

정리

동적계획법(dynamic programming)이란?

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

 

부분 문제 반복 : 어떤 문제가 여러개의 부분 문제로 쪼개지고 같은 부분 문제가 반복되는 경우

최적 부분 구조 : 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성되는 구조

메모이제이션 : 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법, 동적 계획법의 핵심이 되는 기술

 

동적 계획법 접근 방법

Top-down : 하향식, 위→아래, 큰 문제→부분 문제, 재귀 호출 방법, 점화식을 이해하기 쉽다는 장점

Bottom-up : 상향식, 아래→위, 부분 문제→큰 문제, 반복문 활용 방법, 시간과 메모리 사용량을 줄일 수 있다는 장점

 

위 코드는 bottom-up 방법으로 문제를 풂

참조

https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

https://velog.io/@gillog/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

https://namu.wiki/w/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

https://velog.io/@kimdukbae/%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-Dynamic-Programming