동적계획법
-
[Greedy] 그리디 알고리즘알고리즘/이론 2020. 1. 3. 00:33
그리디 알고리즘을 설명하기전에 우리는 동적 계획법을 숙지할 필요가 있습니다. 먼저 동적 계획법이란 A라는 연산을 여러번 반복을 해야하는 문제가 있다면 A의 답을 미리 계산해놓고 후에 A 연산이 또 다시 등장할때 미리 계산해놨던 A의 답을 다시 쓰는 것을 말합니다. 너무 설명이 난해하죠? 간단한 예시를 들어보겠습니다. ''' 아래는 흔히들 알고계시는 피보나치 수열입니다. F0 = 0F1 = 1F2 = 1F3 = 2F4 = 3F5 = 5F6 = 8... 뜬금없이 피보나치 수열이 왜 등장할까요? 우리가 동적 계획법을 사용하지않고 피보나치 수열을 구하는 함수를 작성한다고 생각해봅시다. F0 = 0 , F1 = 1 로 초기화를 시키고F(int n) 이라는 함수를 선언하고 F(int n){ if (n == 0 ||..