알고리즘/동적프로그래밍(DP)42

• 

  [swea] 3304번: 최장 공통 부분 수열 - 파이썬(python) s1 = CAPCAK, s2 = ACAYKP 의 문자열에서 최장 공통부분, Longest Common Subsequence (LCS) 을 찾자. dp값을 구하는 방법은 다음과 같다. if (arr[i] == arr[j]) dp[i][j] = dp[i-1][j-1] + 1; if (arr[i] != arr[j]) dp[i][j] = max(dp[i][j-1], dp[i-1][j]); 만약 s1의 i번째 문자열과 s2의 j번째 문자열이 같다면, 이는 dp[i-1][j-1] +1 과 같을 것이다. s1의 i-1번째까지와 s2의 j-1번째까지 비교한 값 + 1 의 값이기 때문이다. ex) dp[2][3] 의 경우, dp[1][2] (C와 AC 를 비교한 값 : 1) + 1과 같다. 만약 s1의 i번째 문자열과 .. 알고리즘/동적프로그래밍(DP) 2022. 11. 12.

• 

  [이코테] 편집거리 - 파이썬(python) 문제 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다. 삽입(Insert) : 특정한 위치에 하나의 문자를 삽입합니다. 삭제(Remove) : 특정한 위치에 있는 하나의 문자를 삭제합니다. 교체(Replace) : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다. 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미합니다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요. 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3입니다. 입력 조건 두 문자열 A와 B가 한 줄에 하.. 알고리즘/동적프로그래밍(DP) 2022. 10. 20.

• 

  [백준] 18353번: 병사 배치하기 - 파이썬(python) 문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자. 이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다. 병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 .. 알고리즘/동적프로그래밍(DP) 2022. 10. 19.

• [백준] 1932번: 정수 삼각형 - 파이썬(python) 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 예제 입력.. 알고리즘/동적프로그래밍(DP) 2022. 10. 19.

• 

  [프로그래머스] 사칙연산 - 파이썬(python) 나의 풀이 import math def solution(arr): N = math.ceil(len(arr) / 2) # dp[] 는 피연산자만 담아둔다 # 즉, dp[i][j] 는 i번째숫자~j번째숫자까지의 최대/최솟값이다 max_dp = [[float('-inf') for _ in range(N)] for _ in range(N)] min_dp = [[float('inf') for _ in range(N)] for _ in range(N)] for step in range(N) : # i~j 까지의 간격 for i in range(N-step) : j = i + step if step == 0 : # 간격이 0 일때는 자기자신이 최대/최소 max_dp[i][i] = int(arr[i*2]) min_dp.. 알고리즘/동적프로그래밍(DP) 2022. 9. 20.

• 

  [프로그래머스] 도둑질 - 파이썬(python) 나의 풀이 def solution(money): # 방법1. 맨 뒷 집을 제외한 경우 dp1 = [0]*len(money) dp1[0] = money[0] dp1[1] = max(money[0], money[1]) # 0,1번 집 중 더 돈이 많은 집 하나만 털 수 있음 for i in range(2,len(money)) : if i != len(money) - 1 : dp1[i] = max(dp1[i-2]+money[i], dp1[i-1]) else : dp1[i] = max(dp1[i-2]+0, dp1[i-1]) # 마지막집이 없다고 가정했으므로 dp[i] 는 i-2, i-1 중 더 큰 값이 된다. # 방법2. 맨 앞 집을 제외한 경우 dp2 = [0]*len(money) dp2[0] = 0 # 맨 .. 알고리즘/동적프로그래밍(DP) 2022. 9. 19.

• 

  [프로그래머스] 등굣길 - 파이썬(python) 나의 풀이 def solution(m, n, puddles): dp = [[0]*(m+1) for _ in range(n+1)] print(dp) for i in range(1, n+1) : for j in range(1, m+1) : if i == 1 and j == 1 : dp[i][j] = 1 elif [j,i] in puddles : dp[i][j] = 0 else : dp[i][j] = dp[i-1][j] + dp[i][j-1] # print("dp[{}][{}] = {}".format(i,j,dp[i][j])) return dp[n][m] % 1000000007 (1,1) 을 집으로, (n,m) 을 학교 좌표로 만들기 위해, 이차원 배열을 [n+1][m+1] 의 크기로 초기화한다. 이번 문제는.. 알고리즘/동적프로그래밍(DP) 2022. 9. 19.

• 

  [프로그래머스] 정수 삼각형 - 파이썬(python) 나의 풀이 def solution(triangle): d = triangle[:] for i in range(1, len(d)) : for j in range(0,i+1) : if j == 0 : d[i][j] += d[i-1][j] elif j == i : d[i][j] += d[i-1][i-1] else : d[i][j] += max(d[i-1][j-1], d[i-1][j]) return max(d[len(d)-1]) 전형적인 bottom up 동적프로그래밍 문제이다. dp[] 에는항상 dp[i][j] 까지의 최댓값 경로가 저장되어 있다. 따라서 dp[i][j] 를 구하려면, dp[i-1][j-1] 와 dp[i-1][j] 둘 중 더 큰값을 나의 값에 더해주면 된다. 만약 한 줄에서 첫번째 값(j=0).. 알고리즘/동적프로그래밍(DP) 2022. 9. 17.

• 

  [프로그래머스] N으로 표현 - 파이썬(python) 나의 풀이 from itertools import product def solution(N, number): d = [[] for _ in range(9)] if N == number : return 1 d[1] = [N] d[2].extend(list(set([10*N+N, N+N, N-N, N*N, N//N]))) if number in d[2] : return 2 for i in range(3, 9) : d[i].extend([int(str(N) * i)]) for j in range(1, int(round(i/2))+1) : for k in product(d[j], d[i-j]) : t1 = k[0] + k[1] t2 = k[0] - k[1] t3 = k[1] - k[0] t4 = k[0] * k.. 알고리즘/동적프로그래밍(DP) 2022. 9. 17.

• 

  [Python] 백준 11052번: 카드 구매하기 풀이 소스코드 n = int(input()) p = list(map(int, input().split())) p.insert(0,0) dp = [0 for _ in range(n+1)] for i in range(1, n+1): for j in range(1,i+1): dp[i] = max(dp[i], p[j] + dp[i-j]) print(dp[n]) 문제가 길어서 지레 겁먹었지만, 사실상 그리 어렵지 않은 문제이다. 여느 dp문제처럼 작은 문제 부터 풀어나가면 된다. 즉 1부터 n까지 각각의 카드수를 위한 금액의 최댓값을 구해나가는 것이다. 4 3 5 15 16 을 예시로 들자. dp[1] 은 언제나 p[1] 과 동일할 것이므로 3 일 것이다. dp[2] 는 dp[1] + p[1] 또는 p[2] 둘 중 큰.. 알고리즘/동적프로그래밍(DP) 2021. 2. 4.

• 

  [Python] 백준 2011번: 암호코드 풀이 소스코드 n = list(map(int,input())) l = len(n) dp = [0 for _ in range(l+1)] if (n[0] == 0) : print("0") else : n = [0] + n dp[0]=dp[1]=1 for i in range(2, l+1): if n[i] > 0: dp[i] += dp[i-1] temp = n[i-1] * 10 + n[i] if temp >= 10 and temp 이전 dp 값을 더한다. ( 이전 dp 가 가지는 방법들 뒤에 한 자리수로 추가하기만 하면 되므로 이전 dp값을 default로 가질 수 있다. ) 예) 2 5 1 1 4 에서 빨강색까지는 이미 구했다고 하자. 2 5 1 1 / 25 1 1 / 2 5 11 / 25 11 이렇게 4가지의 방.. 알고리즘/동적프로그래밍(DP) 2021. 2. 4.

• 

  [Python] 백준 2225번: 합분해 풀이 소스코드 n, k = map(int,input().split()) dp = [[0] * (k+1) for _ in range(n+1)] dp[0][0] = 1 for i in range(0, n+1): for j in range(1, k+1): dp[i][j] = dp[i-1][j] + dp[i][j-1] print(dp[n][k] % 1000000000) 만약 n=20, k=5 라면 20을 5개로 나눈 것은 [0+(20을 4개로 나눈것)] + [1+(19를 4개로 나눈것)] + ... + [19+(1을 4개로 나눈것)] + [20+(0을 4개로 나눈것)] 일 것이다. 즉 점화식으로 표현한다면, dp[n][k] = dp[0][k-1] + dp[1][k-1] + ... dp[n-1][k-1] + dp[n].. 알고리즘/동적프로그래밍(DP) 2021. 2. 3.