본문 바로가기
728x90
반응형

다이나믹 프로그래밍

Algorithm & Data Structure 2022. 8. 15. 백준 - 14002번(DP, LIS) https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net import sys from collections import deque n = int(sys.stdin.readline()) arr = list(map(int,sys.stdin.readline().split())) dp = [1 for _ in range(n+1)] for i in range(n): for j in..
Algorithm & Data Structure 2022. 8. 15. 백준 - 11045번(DP,LIS 응용) https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 가장 긴 바이 토닉 부분 수열 문제다. 가장 긴 증가하는 부분 수열에서 감소가 추가된 것이다. 따라서 가장 긴 증가하는 부분 수열, 즉 LIS를 찾아준 다음에 뒤에서부터 다시 LIS를 찾아준다. 이렇게 나온 두개의 inc 배열과 dec 배열을 합친 다음에 1을 빼준다. 왜 1을 빼주냐면 가장 큰 값 즉 증감이 변하는 부분의 값이 두 번 들어갔기 때문이다. 합쳐서 나온 리스트에서 가장 큰 값을 찾아주면 그게 정답이다...
Algorithm & Data Structure 2022. 8. 13. 백준 - 2565번(DP,BFS) https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net import sys from collections import deque n = int(sys.stdin.readline()) q = deque([]) arr = [] for _ in range(n): a,b = map(int,sys.stdin.readline().split()) q.append([a,b,1]) arr.append([a,b]) ans = 0 while q: x,y,cnt = q.pople..
백준 - 2225번(DP)
Algorithm & Data Structure 2022. 8. 12. 백준 - 2225번(DP) https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net import sys n,k = map(int,sys.stdin.readline().split()) dp = [[0 for _ in range(201)] for _ in range(201)] for i in range(201): dp[1][i] = 1 # k가 1일때는 n에 값에 상관없이 무조건 1가지 case만 가능 dp[i][1] = i # n이 1일때도 무조건 k가지 case만 가능 for i in range(2,201): dp[i][1] = i for j in range(2,201): dp[i][j] = (dp[i][..
728x90
반응형

티스토리툴바