본문 바로가기

문제 풀이41

[이것이 코딩 테스트다] 못생긴 수 - 다이나믹 프로그래밍 문제못생긴 수란 오직 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.
[S3] 백준 1463 - 1로 만들기(Python) https://www.acmicpc.net/problem/1463 풀이👀1부터 X까지 반복문으로 1회 순환한다.i (1에 대해서 dp[i]라 할 때, dp[i]는 1에서 출발하여 주어진 조건을 만족하며 i를 만들기 위해 필요한 연산 최소 횟수이다.그러면dp[i]는 (dp[i-1], dp[i//2], dp[i//3], dp[i//5]) 중에서 최솟값을 찾은 다음, +1을 한 값으로 결정난다.코드💻# 1로 만들기X = int(input())dp = [10**7] * (X+1)dp[1] = 0for i in range(2, X+1): dp[i] = dp[i-1] + 1 if i%2 == 0: dp[i] = min(dp[i//2] + 1, dp[i]) if i%3 == 0: .. 2024. 9. 5.
[이것이 코딩 테스트다] 1로 만들기 - 다이나믹 프로그래밍 백준 1로 만들기와 같은 유형의 문제다.X에서 1로 만들기 방법이다. X에서 1로 한 번 순회한다.현재 위치 i (1에서 연산가능한 모든 숫자에 최소 연산 횟수를 기록한다.i가 1이 될 때까지 위 과정을 반복한다.# 1로 만들기X = int(input())dp = [10**8] * (X+1)dp[X] = 0for i in range(X, 0, -1): dp[i-1] = min(dp[i]+1, dp[i-1]) if i%2 == 0: dp[i//2] = min(dp[i]+1, dp[i//2]) if i%3 == 0: dp[i//3] = min(dp[i] + 1, dp[i//3]) if i%5 == 0: dp[i//5] = min(dp[i] + 1, .. 2024. 9. 5.
[G4] 백준 12970 - AB (Python3) https://www.acmicpc.net/problem/12970풀이 아이디어문자열의 길이에 따라 A와 B로 만들 수 있는 조합의 최대 개수가 정해져있다. 직접 여러 길이의 문자열을 만들어가며 풀이할 때 알게 된 특징이다.길이가 10인 문자열로 만들 수 있는 조합의 최대 개수는 AAAAABBBBB로, 5*5=25개이다.길이가 11인 문자열로 만들 수 있는 조합의 최대 개수는 AAAAAABBBBB → 5*6=30 or AAAAABBBBBB → 6*5=30길이가 30인 문자열로 만들 수 있는 조합의 최대 개수는 15A15B → 15*15=225최대 개수의 공식은 $ \lfloor\frac{N^2}{4}\rfloor $ 이다. 그렇다면 최소 개수는 몇 개일까? 당연히 0개이다. 모든 길이에 대해서 A 혹은 .. 2024. 5. 4.
[G5] 백준 11729 - 하노이 탑 이동 순서 (Python3) https://www.acmicpc.net/problem/11729풀이 아이디어재귀적인 방법을 사용하여 하노이 탑 문제를 해결합니다. 첫 번째 장대에 있는 원판들을 세 번째 장대로 옮기는 과정에서 아래의 과정을 반복한다.n-1개의 원판을 두 번째 장대로 옮긴다.가장 큰 원판을 첫 번째 장대에서 세 번째 장대로 옮긴다.두 번째 장대에 있는 n-1개의 원판을 세 번째 장대로 옮긴다.초기 상태의 가장 큰 원판을 목표하는 곳(세 번째 장대)으로 옮기고나면, 다시 두 번째 장대의 n-1개의 원판을 첫 번째 장대로 옮겨서 n-1번째로  큰 원판을 세 번째로 옮긴다.풀이👀재귀 함수 hanoi_tower를 정의한다. 이 함수는 매개변수로 원판의 개수 n, 출발지 기둥 frm, 보조 기둥 tmp, 목표 기둥 to를 받.. 2024. 5. 4.
[S1] 백준 2156 - 포도주 시식 (Python3) https://www.acmicpc.net/problem/2156풀이 아이디어DP 테이블을 사용하여 각 잔을 선택하는 경우와 선택하지 않는 경우 등을 나누어 최대값을 갱신한다.풀이👀포도주 잔이 1개일 때는 그대로 마시는 것이 최대값이므로 DP tabel의 0번째 인덱스의 초기값으로 설정한다.포도주 잔이 2개일 때는 첫 번째 잔과 두 번째 잔을 모두 마실 수 있으므로 두 잔의 양을 더한 값을 최대값으로 설정한다.포도주 잔이 3개 이상일 때는 연속으로 3잔을 마실 수 없기 때문에 경우를 나누어 최대값을 갱신한다.case1)  i번째 잔을 마시지 않는 경우: d[i-1]case2)  i-1번째 잔을 마시지 않고 i번째 잔을 마시는 경우: d[i-2] + wine[i]case3)  i-1번째 잔과 i번째 잔을.. 2024. 4. 28.
[S1] 백준 1149 - RGB거리 (Python3) https://www.acmicpc.net/problem/1149풀이 아이디어동적 계획법(DP, Dynamic Programming) 알고리즘으로 해결한다.각 집의 Red, Green, Blue 으로 색칠하는 비용이 주어졌을 때, 각 집을 칠할 때의 최소 비용을 계산한다. 이때 DP table을 이용해서 이전 집까지의 최소 비용을 가지고 현재 집을 칠할 때의 최소 비용을 구한다.풀이👀'현재 위치(i번째 집)에 대해서 전 후가 다른 색깔의 집이어야 한다.'는 조건이 걸려있다. 쉽게 풀어 설명하면 '연속해서 같은 색을 칠하지 말라'는 조건이다. 1. 첫 번째 집부터 마지막 집까지 반복하면서, 이전 까지의 최솟값으로 현재 집을 색칠할 때 최소 비용을 계산한다.코드🐱‍👓N = int(input())RGB .. 2024. 4. 28.

티스토리툴바