[이것이 코딩 테스트다] 못생긴 수 - 다이나믹 프로그래밍
문제못생긴 수란 오직 2, 3, 5 만을 소인수로 가지는 수를 의미합니다.1은 못생긴 수라고 가정합니다.이때 n 번째 못생긴 수를 찾는 프로그램을 작성하십시오. 입력 조건첫 째 줄에 n이 입력됩니다.(1 출력 조건n 번째 못생긴 수를 출력합니다.해결 과정첫번째 아이디어이다.1, 2, 3, 4, ..., n 순으로 탐색한다. 다시 말하면 1부터 n까지 선형탐색을 한다. 현재 위치의 수를 소인수분해해서 못생긴 수인지 파악하는 방법이다.하지만 소인수분해를 계산해야하는 시간적 번거로움이 생긴다.2, 3, 5로 나머지가 0이 아닐 때까지 나누는 함수를 만드는 것은 금방이다. 하지만 991번째 못생긴 수 부터 1000번째 못생긴 수를 보면, 소인수분해 계산에서 시간초과에 걸릴 수 있다고 생각했다.* [ ..., 5..
2024. 9. 7.
[이것이 코딩 테스트다] 효율적인 화폐 구성 - 다이나믹 프로그래밍
이 문제는 대학교 1학년 때 공부했던 이산수학에서 다룬 문제여서 금방 풀 수 있었다.그때 문제도 마찬가지로 2와 3의 화폐로 모든 화폐를 표현할 수 있냐는 문제였던 것 같다.2, 3, 2+2, 2+3, 3+3, ... 1 이하의 정수를 제외한 모든 화폐를 표현할 수 있었다. 문제의 입력 조건으로는 최대 입력이 100이라서 O(n^2) 으로도 충분하다. 그래서 2중 for문을 채택했다. 최소 화폐 단위가 2, 3, 7이라고 가정하자. 그러면a[i]를 위 화폐 단위로 만들 수 있을 때, a[i](최소 화폐 개수)는 min(a[i], a[i - 2]+1, a[i - 3]+1, a[i - 7]+1) 이다.이것은 이해를 돕기위해 세운 약간 어거지(?) 점화식이다. 실제로는 각 화폐 단위를 하나 씩만 비교하여 따진..
2024. 9. 6.
