반응형 Dynamic Programming6 [Python][이코테] 1로 만들기 / DP 문제 설명 정수 x가 주어질 때 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지이다. x가 5로 나누어 떨어지면, 5로 나눈다. x가 3으로 나누어 떨어지면, 3으로 나눈다. x가 2로 나누어 떨어지면, 2로 나눈다. x에서 1을 뺀다. 정수 x가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 구하시오. 예를 들어 정수가 26이면 26 - 1 = 25 25 / 5 = 5 5 / 5 = 1 입력 조건 첫째 줄에 정수 x가 주어진다. (1 ≤ x ≤ 30,000) 출력 조건 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 입력 예시 26 출력 예시 3 솔직히 어떻게 풀어야 할지 감도 안 잡혀서 걍 풀이를 보고 풀이를 보고도 뭐지.. 싶어서 하나하나 돌.. 2022. 10. 23. [Python][이코테] 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 Dynamic Programming 모든 프로그램은 컴퓨터의 연산 속도와 한정된 메모리 공간에 제한되어 있다. 다이나믹 프로그래밍은 이러한 제한 속에서 우리는 주어진 요소들을 최대한으로 활용하는 효율적인 알고리즘을 작성해야 한다. 다이나믹 프로그래밍은 동적 프로그래밍, 동적 계획법 이라고도 한다. 피보나치 수열 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 문제로 피보나치 수열이 있다. 피보나치 수열을 우리가 학창 시절 배운 점화식을 이용해 풀어보면 HTML 삽입 미리보기할 수 없는 소스 피보나치는 첫 번째 항과 두 번째 항이 1이기 때문에 위와 같이 정의된다. 즉 n번째 피보나치 수 = (n - 1)번째 수 + (n - 2)번째 수 단, 1번째와 2번째 수는 1 이를 코드로 구현하.. 2022. 10. 22. 이전 1 2 다음 반응형
