다이나믹 프로그래밍7 [백준 1463/javascript] 1로 만들기 '적은 시간이 주어지고, 매 차례마다 선택지를 고르며 최소한의 선택 수를 만들어라' - 다이나믹 프로그래밍 . 계산 이전의 경우 + 1의 수를 갖는다면 다이나믹 프로그래밍을 시도해보자 특히나 시간 제한이 있고 그 시간이 적다면 더더욱 다이나믹 프로그래밍인지 의심해보자 선택지를 통한 최소 선택시의 수, 적은 시간 등은 이 문제가 다이나믹 프로그래밍으로 풀 근거가 된다 일부 풀이에서는 다이나믹 프로그래밍과 재귀를 혼동하곤 하는데 재귀는 top-down 방식으로 n 에서 n-1 로 내려오며 base 조건에서 리턴하여 푸는 방법이고 다이나믹 프로그래밍은 bottom-up 방식으로 최소범위값 (여기서는 1) 부터 1씩 늘려가며 값이 될 수 있는 하위 요소들을 분석하며 로직을 찾아 배열로 쌓아가며 찾는 방식이다 요.. 2022. 8. 19. [백준 2579/c++] 계단 오르기 다이나믹 프로그래밍을 이용한 문제이다 특이사항으로 1칸, 2칸 씩만 오를 수 있지만 1칸이 연속되면 안된다는 조건이 걸려있다 1칸 연속이 허용되지 않으면 1칸 2칸 혹은 2칸 1칸 혹은 2칸 2칸 의 순으로 가야되는 것인데 2-1 / 1-2 의 경우는 조건에 맞지 않아 문제가 생긴다 1의 위치가 뒤 앞으로 정해지지 않았을때 생기는 문제이니 1 이후에 2가 무조건 오거나 2 이후에 1이 무조건 오도록 오르게 하면 해결된다 하지만 1이후에 2가 무조건 오게 하는 방법은 1만큼 오르는 것이 필수가 아니므로 1-2 / 2-1 / 2- 2 중 일반화 했을때 1이 먼저 오는 1-2 의 경우는 2-2 를 나타내기 힘드므로 2가 먼저 오게 해서 2 이후에 1이 오는 경우, 안오는 경우 2가지만으로 하여 오르는 방법이 .. 2022. 7. 19. [백준 2748/c++]피보나치 수 2 이전 수와 현재 수를 더해서 다음 수를 만들어 내는 수열을 피보나치 수열이라고 한다 피보나치 수열은 다이나믹 프로그래밍 = 동적 계획법 의 분류에 해당되는데 스스로 재귀하며 답을 도출해내는 과정에서 이전의 계산한 결과는 배열에 넣어서 매번 따로 계산 없이 배열에서 이전 결과값을 그대로 가져와 사용하여 효과적으로 계산할 수 있다 벡터를 이용해서 풀었지만 수가 워낙 크다보니 배열이 많이 필요하지 않아서 앞으로는 간단히 정적 배열로 풀어도 될 것같다 https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으.. 2022. 7. 17. 이전 1 2 다음