농부공학자

문제 2. 1로 만들기 문제만 봤을 때 그리디를 활용해서 풀려고 했다. 그런데 그리디로 풀면 안된다. 왜냐하면 예시를 살펴보면 입력이 26일 때 그리디를 사용하면 우선 순위가 5로 나누기, 3으로 나누기, 2로 나누기, -1 빼기 순서가 될 것이기 때문에 26 -> 13 -> 12 -> 4 -> 2 -> 1 순서로 될 것이기 때문에 최소 연산인 26 -> 25 -> 5 -> 1 이 수행될 수 없다. 그래서 DP를 활용할 방법을 살펴볼 것이다. 함수가 호출되는 과정을 살펴보면 입력으로 6이 들어왔을 때 -1을 한 값인 f(5), ÷3을 한 값인 f(3), ÷2를 한 값인 f(2) 로 나누어 지며 그 밑으로 f(1)이 나올 때까지 뻗어갈 수 있다. 이렇게 작은 문제들을 조합해서 해결될 수 있기 때문에 DP를..

문제 1. 개미 전사 DP를 활용하여 문제를 풀 수 있다. 문제를 해결하기 위해 i번째 식량창고까지의 최적의 해를 살펴보자 창고 0에서 최적의 해는 1이다. 창고 1에서 최적의 해는 1과 3을 비교했을 때 큰 값인 3이다. 창고 2에서 최적의 해는 1+1인 2와 3을 비교했을 때 큰 값인 3이다. 창고 4에서 최적의 해는 1+1인 2와 3+5인 8을 비교했을 때 큰 값인 8이다. 이런식으로 차례로 DP에 넣어 확인할 수 있다. 왼쪽부터 차례대로 식량창고를 털 때 i 번째를 털지 안털지의 여부는 2가지가 있다. 바로 앞의 창고가 털렸다면 i번째 창고는 털 수 없으며 털리지 않았다면 i번째 창고를 털 수 있다. 두 가지 중에 더 많은 식량을 털 수 있는 경우를 선택하면 된다. 글고 i - 1번째와 i - 2..

다이나믹 프로그래밍(Dynamic Programming) 알고리즘 다이나믹 프로그래밍은 동적 계획법이라고도 불리며, 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 자료구조에서 동적(Dynamic)이란 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다. DP는 이미 계산된 결과는 별도의 메모리 영역에 저장하고 다시 계산하지 않게 하는 방법이며, 탑다운(하향식)과 보텀업(상향식)이라는 두 가지 방식이 있다. 1. 탑다운(하향식) 방법 메모이제이션(Memoization)은 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다. 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져오며, 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다. ..