코딩뚠뚠

풀이 일시 : 2020-08-08 ​ 다이나믹프로그래밍 : 하나의 문제는 단 한번만 풀도록 하는 알고리즘으로 효율성을 개선하는 알고리즘이다. 가정1 - 큰 문제를 작은 문제로 나눌 수 있다. 가정2 - 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 작동한다. 이미 계산한 결과는 배열에 저장함으로써 나중에 꺼내서 쓰기만 하면 되게끔 한다. ​ 문제 : dp로 피보나치 구현 풀이 : #include int d[100] = { 0, }; //배열 선언 및 전체 0으로초기화 int fibonacci(int x) { if (x == 1) return 1; //1과 2는 피보나치에서 뭘 더해서 나오는 수가 아니기때문에 거른다 if (x == 2) return 1; if (d[x] != 0){ return..

Dynamic Programing, DP, 동적프로그래밍, 동적계획법 으로 중요한 알고리즘 중 하나이다. DP란 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 방식은 분할정복과 같으나 분할정복은 계산한 부분문제를 단 한번만 쓰고 더이상 사용하지않는다. 그러나 동적프로그래밍에서는 계산한부분을 남겨놓고 계속해서 필요할때 끌어다 쓴다. 동작방식 1. 구하고자 하는 큰 문제를 작은 문제들로 나눈다. (점화식을 세운다.) 2. 가장 작은 부분문제를 푼 뒤 값을 저장한다. = 메모이제이션 3. 메모이제이션 된 문제들의 값을 이용해 점차 더 큰 문제들의 답을 구한다. 4. 가장 큰 문제를 풀이할때까지 반복한다. ☆무엇을 어떻게 저장할지 정하는게 중요하다. 적용방법 1. Botton-Up 방식 : 반복문을 이용 e..