<청춘> 격정적으로 사는 것

밤을 새고 공부한 다음 날 새벽에 느꼈던 생생한 환희와 야생적인 즐거움을 잊을 수 없다

2021/07/21 2

[다이나믹 프로그래밍 / 동적계획법] 실전 문제 <2> 1로 만들기 / 이것이 취업을 위한 코딩테스트다 with 파이썬

1로 만들기 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다. X가 5로 나누어떨어지면, 5로 나눈다. X가 3으로 나누어떨어지면, 3으로 나눈다. X가 2로 나누어떨어지면, 2로 나눈다. X에서 1을 뺀다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다. 26 - 1 = 25 25 / 5 = 5 5 / 5 = 1 입력 조건 첫째 줄에 정수 X가 주어진다. (1 ≤ X ≤ 30,000) 출력 조건 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 입력 예시 26 출력 예시 3 내 풀이 X = int(input()) d = [0] ..

코딩테스트 2021.07.21

다이나믹 프로그래밍 (Dynamic Programming) / 동적계획법 - 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

컴퓨터를 활용해도 해결하기 어려운 문제? 최적의 해를 구하기에 시간이 매우 많이 필요한 문제 - 컴퓨터 연산 속도에 한계가 있음 메모리 공간이 매우 많이 필요한 문제 - 메모리 공간을 사용할 수 있는 데이터의 개수가 한정적 다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있다. → 다이나믹 프로그래밍 (Dynamic Programming) / 동적계획법 피보나치 수열 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 수열이다. 1 1 2 3 5 8 13 21 34 55 89 ... 점화식이란 인접한 항들 사이의 관계식으로, 점화식을 이용해 수열을 간결하게 표현할 수 있다. 피보나..