본문 바로가기

DP

 (21)
백준 14003 가장 긴 증가하는 부분 수열 5 - 파이썬 문제. 풀이. O(NlogN)로 문제를 풀어야한다. https://turret1234.tistory.com/151 백준 12015 가장 긴 증가하는 부분 수열2 - 파이썬 문제. 풀이. 이분 탐색을 이용하여 dp배열의 최댓값과 비교하여 큰 값이면 오른쪽에, 낮은 값이면 dp배열의 값에서 이분 탐색을 이용하여 해당 값이 들어갈 위치를 결정하여 dp 배열에 넣고 dp 배 turret1234.tistory.com 기본적인 풀이방법은 위 링크와 같다. 여기서 경로를 저장한 배열을 만들고 연산마다 경로를 추가하여주면된다. 소스코드. import sys from bisect import bisect_left input = sys.stdin.readline n = int(input()) numbers = [0] + ..
백준 14002 가장 긴 증가하는 부분 수열 4 - 파이썬 문제. 풀이. https://turret1234.tistory.com/138 백준 11053 - 가장 긴 증가하는 부분 수열 문제. 풀이. 첫번째 위치부터 수열의 길이의 최댓값을 저장하고 자기 자신보다 작은 숫자들 중 가장 큰 길이를 자기 위치에 넣고 +1을 하고 dp의 최댓값을 출력하면 된다. 소스코드. import sys A = int turret1234.tistory.com 기본적으로 가장 긴 증가하는 부분 수열의 길이를 구하는 방법은 위의 링크와 같다. 여기서 추가적으로 경로를 담아야하는데. 경로를 담는 dp배열을 추가하여 연산마다 경로를 담아준다. 소스코드. import sys input = sys.stdin.readline n = int(input()) numbers = list(map(int..
백준 12852 1로 만들기 2 - 파이썬 문제. 풀이. 최솟값과 경로를 담는 dp 배열을 생성해서 연산마다 최솟값과 경로를 배열에 담아준다. 그리고 경로를 뒤집어서 출력하면 된다. 소스코드. import sys input = sys.stdin.readline n = int(input()) dp = [[0, []] for _ in range(n + 1)] dp[1][0] = 0 # 최소값 dp[1][1] = [1] # 경로를 담는 리스트 for i in range(2, n+1): # x -1 dp[i][0] = dp[i-1][0] + 1 dp[i][1] = dp[i-1][1] + [i] # x // 3 if i % 3 == 0 and dp[i // 3][0] + 1 < dp[i][0]: dp[i][0] = dp[i//3][0] + 1 dp[i][..
백준 11066 파일 합치기 - 파이썬 문제. 풀이. 정답률이 50퍼가 넘던데 문제가 너무 어려웠다. 크누스 최적화라는 알고리즘을 사용해서 풀었다. 크누스 최적화는 특수한 조건일 때 시간 복잡도를 O(n^3)에 O(n^2)까지 줄일 수 있는 알고리즘이다. 우선 크누스 최적화 알고리즘을 적용할려면 다음과 같은 조건을 만족해야한다. 사각 부등식: C[a][c] + C[b][d]
파이썬 2629 양팔저울 - 백준 문제. 풀이. 양팔 저울이 잴 수 있는 무게는 양팔에 올라간 추의 무게 차이이다. 예를들어 1,3,7 무게의 추가 있다면 잴 수 있는 경우는 1, 2, 3, 4, 6, 7, 8, 10, 11의 무게를 잴 수 있다. 여기서 2, 4, 6 같은 경우에는 |왼쪽 저울 - 오른쪽 저울|의 값이다. 즉 dp[i][j] = i번쨰 추를 놓으려고 할때 현재의 무게차이 j 이다. 소스코드. import sys def scale(weight, n, now, left, right): new = abs(left - right) # possible에 현재 무게차이가 들어 있지 않다면 추가 if new not in possible: possible.append(new) if now == n: return # 방문하는 dp가 이..
백준 7579 앱 - 파이썬 문제. 풀이. 냅색 알고리즘을 이용하는 문제이다. 우선dp 배열을 행은 켜진 app의 개수, 열은 cost들을 다 더한 값 만큼 생성해준다. 그리고 반복문으로 dp배열을 돌면서 다음과 같은 조건을 체크한다. 1) 현재 앱의 i번째 앱의 코스트가 j보다 크다면 끄지 못하므로 이전 행의 값을 가져온다. dp[i][j] = dp[i-1][j] 2) 현재 앱의 cost가 j보다 작거나 같을 경우 현재 앱을 껏을때의 메모리와 그렇지 않을 경우의 메모리 중 큰 값을 dp에 입력한다 dp[i][j] = max(memory+dp[i-1][j-cost] 3) 현재 dp[i][j[의 값이 M 이상이라면 현재 cost와 이전의 result 값을 비교해 더 작은 값을 저장한다. dp[i][j[ = min(result, j) ..
백준 1912 연속합 - 파이썬 문제. 풀이. dp[0]에 arr[0]의 값을 넣어준 뒤 연속으로 더하는게 더 큰 숫자면 더한 값을 dp에 넣어주고 더하지 않고 새로운 숫자를 넣어주는게 값이 더 크다면 그 값을 dp에 넣어주는 방식으로 계속 진행을 한다. 그리고 dp에서 제일 큰 값을 출력한다. 소스코드. import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) dp = [arr[0]] for i in range(n-1): dp.append(max(dp[i] + arr[i+1], arr[i+1])) print(max(dp))
백준 2565 전깃줄 - 파이썬 문제. 풀이. 2차원 배열로 입력을 받고 A또는 B 기준으로 정렬을 하고 A 기준으로 정렬을 했다면 B에 대하여 LIS를 구하여서 n 값에서 LIS를 빼면 된다. B 기준으로 정렬을 했다면 A에 대하여 LIS를 구하고 n 값에서 LIST를 뺀다. 소스코드. import sys n = int(sys.stdin.readline()) wire = [] dp= [0] * n for i in range(n): A, B = map(int, sys.stdin.readline().split()) wire.append([A, B]) wire = sorted(wire, key = lambda x: x[0]) for i in range(n): for j in range(i): if wire[i][1] > wire[j][1]..

티스토리툴바