본문 바로가기
반응형

전체 글572

[알고리즘 algorithm] LCS에 대하여 LCS : Longest Common Subsequence 두 수열이 주어졌을 때, 두 수열 모두의 부분 수열에 해당하는 수열 중 가장 긴 수열을 의미한다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net a = input() b = input() dp = [[0]*(len(b)+1) for _ in range(len(a)+1)].. 2021. 8. 15.
[위상 정렬] 백준 1005번 : ACM Craft / 골드 3 * https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net import sys import collections input = sys.stdin.readline tc = int(input()) for _ in range(tc): n, k = map(int, input().split()) times = list(map(int, input().split())) deg = [0 for _ in range(n)] graph = collections.defa.. 2021. 8. 15.
[위상 정렬] 백준 2252번: 줄 세우기 / 골드 2 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net import sys import collections input = sys.stdin.readline n, k = map(int, input().split()) deg = [0 for _ in range(n)] graph = collections.defaultdict(list) for _ in range(k): a, b = map(int, input()... 2021. 8. 15.
[위상 정렬] 백준 1766번: 문제집 / 골드 2 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net import heapq import collections import sys input = sys.stdin.readline n, m = map(int, input().split()) deg = [0 for _ in range(n+1)] graph = collections.defaultdict(list) for _ in range(m): a, b = map(int, .. 2021. 8. 15.
[기하학] 백준 2166번 : 다각형의 면적 / 골드 5 https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net n = int(input()) points = [] for i in range(n): points.append(list(map(int, input().split()))) # add first point again for the line connecting the beginning and the end. points.append(points[0]) area = 0 for i in range(n): cur_x, cur_y = .. 2021. 8. 13.
[다이나믹 프로그래밍] 백준 2096번: 내려가기 / 골드 4 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 import sys n = int(sys.stdin.readline()) max_dp = list(map(int, sys.stdin.readline().split())) min_dp = max_dp for i in range(1, n): a, b, c = map(int, sys.stdin.readline().split()) na1 = a + max(max_dp[0], max_dp[1]) nb1 = b + max.. 2021. 8. 13.
반응형

티스토리툴바