본문 바로가기

Algorithm 💡/DP41

[백준 1904번] 01타일 이번 문제는 간단히 정리하자면 주어진 n의 자리수를 가지며 00과 1을 가지고 만들 수 있는 문자열의 개수를 구하는 문제이다. 처음에 이 문제를 보았을 때 왜 이게 DP 문제이고, 어떤 방식으로 문제를 풀어야 할지 감도 오지않았고, 결국 30분정도 고민하다가 풀이 접근 방법에 대해 이해하기 위하여 다른 분의 풀이를 참고하였다 😢 다른 분들의 풀이마저도 처음에 이해하기 어려웠기 때문에 직접 n=1(일의 자리수)부터 n=5(만의 자리수) 까지 종이에 적어보면서 이해해보기로 하였다. 다른 분들의 풀이를 참고하고 경우의 수를 직접 손으로 적어보니 이 문제가 왜 DP 문제인지 새삼 알 수 있었다. 1) 문제 접근법 n = 1 : 1 n = 2 : 00, 11 n = 3 : 100, 001, 111 n = 4 : .. 2023. 3. 1.
[백준 9184번] 신나는 함수 실행 import sys input = sys.stdin.readline def w(a,b,c): if a 20: return w(20,20,20) if dp[a][b][c]: return dp[a][b][c] if a < b and b < c: dp[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c) return dp[a][b][c] dp[a][b][c] = w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1) return dp[a][b][c] dp = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)] while True: a, b, c = map(int,.. 2023. 3. 1.
[백준 24416번] 알고리즘 수업 - 피보나치 수 1 n = int(input()) dp = [0]*41 count_r = 0 count_d = 0 def fib_recursive(n): # 일반적인 재귀함수 피보나치 수열 계산 global count_r if n==1 or n==2: count_r += 1 return 1 else: return fib_recursive(n-1) + fib_recursive(n-2) def fib_dynamic(n): # 동적계획법을 사용한 피보나치 수열 계산 global count_d if n==1 or n==2: if dp[n] == 0: dp[n] = 1 return dp[n] else: if dp[n] != 0: return dp[n] else: count_d += 1 dp[n] = fib_dynamic(n-1) +.. 2023. 2. 28.
[프로그래머스 Lv.3] 정수 삼각형 이번 문제는 Dynamic Programming 문제의 대표적인 예제인 정수 삼각형로, 대각선 방향으로만 움직일 수 있을 때 거쳐간 숫자의 합이 최대가 되도록 만드는 문제이다. 단순하게 완전탐색(DFS/BFS)로 풀 순 있겠지만, 이 문제의 경우 삼각형의 높이가 한 층씩 높아질수록 경우의 수 가 2배씩 늘어나는 문제로 단순히 완전탐색 알고리즘으로 풀게 되면 문제의 조건(높이는 1이상 500이하) 때문에 O(2^n)의 시간복잡도로 인해 시간초과가 발생할 것이다. 따라서 모든 경우의 수를 전부 구하는 완전 탐색이 아니라, 별도의 자료구조에 정보들을 저장하면서 중복된 연산을 최대한 줄여주는 DP 알고리즘을 사용하여 풀어야만 한다. 먼저 이전에 포스팅한 DP 알고리즘에 대한 내용을 복습할 겸 이 문제가 왜 DP.. 2023. 2. 28.
[DP] Dynamic Programming 알고리즘의 개념 및 코드 1) Dynamic Programming 이란 ? Dynamic Programming은 또 다른 자료구조(메모리)에 계산한 정보들을 저장함으로써 중복되는 연산을 줄이고, 이로써 프로그램의 수행 속도를 개선하는 알고리즘이다. DP는 완전 탐색(BFS, DFS)과 같이 수많은 경우의 수를 따져보아야 할 때, 경우의 수가 수없이 많을 때 메모리 공간을 사용하여 수행시간을 단축시키는 알고리즘이다. 여러 개의 작은 문제들을 먼저 푼 후에 그 결과를 바탕으로 더 큰 문제를 해결하는 알고리즘으로, 한번 계산한 문제는 다시 계산하지 않도록 메모리에 저장하고, 필요한 경우 다시 계산하지 않고 저장된 값을 사용한다.(매 순간 최적의 값을 저장함) 쉽게 설명하면 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서.. 2023. 2. 27.

티스토리툴바