시간 날 때, 끄적끄적

문제 링크 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 입력으로 받는 수 x에 대해 세 가지 종류의 연산을 반복해 1로 만들 수 있는 방법 중 연산 횟수가 가장 작은 방법의 연산 수를 찾는 문제 연산의 종류는 다음과 같다. x가 3으로 나누어 떨어지면, 3으로 나눈다. x가 2로 나누어 떨어지면, 2로 나눈다. 모두 해당 없으면 1을 뺀다. 고민한 부분 단순하게 생각해 숫자를 가장 빠르게 줄일 수 있는 연산 순서로 조건을 확인하도록 구현했다가 틀렸다. 연산 횟수의 수열이 증가하는 수열이 아니기 때문에 어떤 연산을 적용하는 것이 가장 좋은지 알 수 없다. 1부터 x까지 거꾸로 거슬러 올라가며 그 사이에 있는 값..

다이나믹 프로그래밍이란 dynamic programming은 최적의 답을 찾기 위한 수학적인 개념으로 복잡한 문제를 간단한 문제의 sequence로 변형해 풀이하는 divide and conquer 최적화 방법 중 하나이다. divide and conquer 방법의 단점은 동일한 계산을 반복해서 수행해야하는 단점이 있는데 중간 계산 결과를 저장해 한 번만 계산하도록 하는 memoization으로 이 문제를 극복합니다. dynamic programming을 적용할 수 있는 문제는 '최적성 원리'가 성립하는 문제다. 최적성의 원리는 문제 전체의 최적해가 작은 부분의 최적해로 구성될 때 성립한다. 이 경우 문제를 점화식 형태로 구성해 풀이한다. 피보나치 수열 피보나치 수열은 첫 두 항이 1로 시작하고, 연속된..

문제링크 문제 설명 N+1일째 퇴사를 하기로 하고 N일까지 상담을 할 수 있을 때 최대로 받을 수 있는 수익을 계산하는 문제 매일 다른 상담을 선택할 수 있지만 상담에 소요되는 시간과 상담 비용은 모두 다르다 고민한 부분 단순히 loop를 순회하며 풀이할 수 있을 것이라고 생각했지만 해결하지 못해 다른 분들의 풀이를 공부했다. dynamic programming이라는 방법으로 풀 수 있었는데 dynamic programming은 프로그램 중간에 계산된 결과를 다른 공간에 저장해두고 이후에 참조해 사용하는 방식이다 Lesson learned dynamic programming이라는 개념을 알고는 있었지만 관련된 문제를 해결해 본 적은 없었다. 이번 문제는 다른 분들의 풀이를 보고 이해했지만 비슷한 문제가 ..