반응형 알고리즘39 [알고리즘/백준] 2193번 이친수 Python 파이썬 요즘도 여전히 다이나믹 프로그래밍 문제를 풀고 있습니다. 이번 문제는 위 조건에서 요구하는 이친수를 찾는 문제입니다. 그러면 무엇을 해야하는가? 전번 풀이에도 이야기했듯이 다이나믹 프로그래밍 문제를 풀 때는 규칙성을 찾는 것이 매우 중요하며 이를 찾기 위해 직접 몇가지의 경우의 수를 적어보면서 어떻게 결과가 도출되는지 과정을 살펴보는 것이었습니다. 그렇기 때문에 초반에 어떻게 결과가 도출되는지 아래와 같이 적어보았습니다. 위 풀이를 보면서 규칙성을 찾을 수 있게 되었습니다. 바로 전 2단계의 답 합이 다음 답이라는 것이었습니다. 즉 dp[i] = dp[i-1] + dp[i-2] 로 정의할 수 있습니다. 다음과 같은 코드로 통과하였습니다. import sys input = sys.stdin.readline.. 2023. 4. 19. [알고리즘/백준] 11057번 오르막 수 Python 파이썬 아쉽게도 골드 문제는 아니였지만 드디어 DP 문제를 풀이 안보고 풀 수 있게 되었습니다. 수의 길이 N이 주어졌을 때 오름차순을 이루는 수%10007 을 구하는 문제였습니다. DP 문제를 풀면서 느낀 점은 규칙성을 찾는 것이 매우 중요하다고 느꼈고 이를 적용시키기 위해서는 직접 몇가지의 경우의 수를 적어보면서 어떻게 결과가 도출되는지 과정을 살펴보는 것이었습니다. 먼저 다음과 같은 코드로 통과하였습니다. import sys input = sys.stdin.readline n = int(input()) dp = [ 1 for _ in range(10) ] for i in range(2, n+1): for j in range(10): if i == 2: dp[j] = 10 - j else: for k in .. 2023. 4. 18. [알고리즘/백준] 11052번 카드 구매하기 Python 파이썬 이번 문제는 기존에 풀던 게임 문제집이 아닌 다이나믹 프로래밍 알고리즘으로 넘어와서 문제를 풀게 되었습니다. 저번에 풀면서 느꼈지만 DP는 아직 DFS나 BFS만큼 이해가 너무 안되어 있는 거 같아 한동안 지속해서 관련 문제를 풀 필요성을 느끼게 되었습니다. 해당 문제는 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램으로 DP에 어떤 값을 누적시킬 건지 중요한 문제인 것 같습니다. 처음에 고민했던 방향은 1. dp 의 i 번째마다 비교하여 i 장 카드 최댓값 넣기 2. dp 의 i 번째마다 비교하여 n 장 카드 최댓값 넣기 였는데 아무래도 dp 값을 활용하는 특징상 후자는 아닌 것 같아 전자로 잡고 문제를 풀게 되었습니다. 아쉽게도 아직 .. 2023. 4. 12. [알고리즘/백준] 2294번 동전2 Python 파이썬 이번 문제는 DP 문제로 이해하는데 좀 걸린 문제입니다. 아직 제대로 DP에 대해 알고 응용할 수 있는 정도까지는 아닌 것 같습니다. 다른 분의 풀이를 보면서 이해하는데 시간을 들었습니다. 동전의 종류와 특정 값이 주어지면 특정 값을 맞추기 위한 최소 동전 갯수를 구하는 문제입니다. 처음에 보았을 때 DP 문제인건 감을 잡았는데 어떻게 풀어나가야할지 값이 안 잡히더라고요 일단 DP 문제인 만큼 어떤 값을 누적시켜서 사용할 거고 dp 배열이 k+1 원만큼 만들어지면서 각 i원에 어떤 것을 저장시키지 않을까 생각했습니다. 그 이후에는 막혀서 결국 풀이를 찾게 되었습니다. 핵심은 "dp[i]에 dp[n-c1], dp[n-c2], dp[n-c3] 중에 가장 개수가 적은 경우를 택하고 +1" 한 값을 누적해주는 .. 2023. 4. 10. 이전 1 2 3 4 5 ··· 10 다음 반응형
