https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS 최장 공통 부분 수열을 찾는 문제이다. 2차원 배열을 사용해 두 문자열의 글자를 하나씩 늘려 하나하나 비교하는 방법을 사용한다 문제의 예시인 ACAYKP, CAPCAK 를 사용해 비교하면 A, C 의 LCS는 0 A, CA 의 LCS는 1 A, CAP 의 LCS는 1.. 이런식으로 첫번째, 두번째 문자열의 크기를 하나씩 늘려가며 비교한다. A C..
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 전형적인 다이나믹 프로그래밍을 이용한 문제이다 dp_max = [[0,0,0] for _ in range(n-1)] dp_max.insert(0, data[0]) dp_min = [[0,0,0] for _ in range(n)] dp_min.insert(0, data[0]) for i in range(1, n): dp_max[i][0] = data[i][0] + max(dp_max[i-1][0], dp_max[..
https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 입력받은 값을 a를 기준으로 정렬한 이후 b에 해당하는 값들 중 차례대로 증가하는 부분수열을 찾으면 교차하는 전깃즐이 없는 것들이 된다. 그래서 (전체 전깃줄의 수) - (가장 긴 증가하는 부분수열) 을 하면 답이 된다. 소스코드 import sys input = sys.stdin.readline n = int(input()) data = [list(map(int,input().split())) for ..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 연속으로 세잔은 먹을 수 없다고 한다. 그렇다면 경우의 수는 1. 이전 두 잔을 먹고 이번 잔을 먹지 않는 경우 2. 두번째 전 잔과 이번 잔을 먹는 경우 3. 이전 잔과 이번 잔을 먹는 경우 세 가지가 될 수 있다. 해당 포도주 까지의 최댓값을 저장할 dp 배열, 포도주의 양을 담은 data를 이용해 경우의 수를 다시 작성하면 1. dp[i-1] 2. dp[i-2] + data[i] 3. data..
