[programmers-python] 동적계획법
동적 계획법
정의
-
복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 푸는 알고리즘.
-
입력 크기가 작은 부분 문제들을 해결한후, 해당 부분문제의 해를 활용해서 보다 큰 크기의 - 부분 문제를 해결한다. 최종적으로는 전체 문제를 해결한다.
-
memoization
프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
시간복잡도
복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 푸는 알고리즘.
입력 크기가 작은 부분 문제들을 해결한후, 해당 부분문제의 해를 활용해서 보다 큰 크기의 - 부분 문제를 해결한다. 최종적으로는 전체 문제를 해결한다.
memoization
프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
O(N)
구현 방식
top-down
중복되는 하위 문제를 결합하여 최종적으로 최적해를 구하는 방식
num = 10
dp = [0 for _ in range(num+1)]
def fibo(n):
if n <= 1:
return n
if dp[n]:
return dp[n]
else:
dp[n] = fibo(n-2) + fibo(n-1)
return dp[n]
print(fibo(num))
bottom-up
하위 문제들로 상위 문제의 최적해를 구하는 방식
def fibo_dp(num):
dp = [0 for _ in range(num+1)]
dp[0] = 0
dp[1] = 1
for index in range(2, num+1):
dp[index] = dp[index-1] + dp[index-2]
return dp[num]
print(fibo_dp(10))
문제 풀이
N으로 표현
Answer
DP에 사칙연산 결과의 집합을 넣어두고 다음 연산에서 꺼내 쓰는 방식이다.
def solution(N, number):
answer = -1
DP = []
for i in range(1, 9):
num_set = { int(str(N) * i) }
for j in range(0, i - 1):
for x in DP[j]:
for y in DP[-j - 1]:
num_set.add(x + y)
num_set.add(x - y)
num_set.add(x * y)
if y != 0:
num_set.add(x // y)
if number in num_set:
return i
DP.append(num_set)
return answer
정수 삼각형
Try
아래로 내려올 때마다 합을 구할 수 있는 모든 경우의 수를 DP list에 append 하는 식으로 했다.
def solution(triangle):
DP = []
for index, num in enumerate(triangle):
DP.append([])
if index == 0:
DP[0] = num
continue
for i_index, i in enumerate(DP[index-1]):
for j_index, j in enumerate(num):
if 0<= j_index - i_index < 2:
DP[index].append(i+j)
print(DP)
tri = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
solution(tri)
Answer
테스트 케이스가 계속 나가서 답을 찾아봤다.
위에서부터 작은 삼각형을 만들어서 점화식으로 더 큰값만 추가해주는 코드다.
이해가 가지 않았던 부분은 인접한 윗 숫자들 중 더 큰 수만 더해주는 부분이었다.
def solution(triangle):
for i in range(1, len(triangle)):
for j in range(i+1):
if j == 0:
triangle[i][j] += triangle[i-1][j]
elif j == i:
triangle[i][j] += triangle[i-1][j-1]
else:
triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
return max(triangle[-1])
Reference
Author And Source
이 문제에 관하여([programmers-python] 동적계획법), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dchecheb/programmers-python-동적계획법저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)