문제 링크 9251번: LCS (acmicpc.net) 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 소스 코드 a = input() b = input() def lcs(a,b): m,n = len(a),len(b) dp = [[None for _ in range(n+1)] for _ in range(m+1)] for row in range(m+1): for col in range(n+1): if row == 0 or col == 0: # 둘 중 하나가 글자가 아..
알고리즘/BOJ
문제 링크 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 소스 코드 import sys n = int(input()) k = int(input()) centers = sorted(list(map(int,sys.stdin.readline().strip().split()))) # 센터 위치 오름차순 dists = sorted([centers[i]-centers[i-1] for i in range(1,n)],reverse=..
문제 링크 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 소스 코드 a,b,c = map(int,input().split()) def div(a,b,c): if b == 1: return a % c tmp = div(a,b//2,c) if b % 2 == 1: return tmp**2 * a % c else: return tmp**2 % c print(div(a,b,c)) 해설 분할정복, 재귀 문제에 주어진 a,b,c의 범위는 최대 21억으로 일반적인 곱셈 연산을 수행하면 무조건 시간초과가 나게 되어있습니다..
문제 링크 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 소스 코드 n = int(input()) m = int(input()) graph = [] for i in range(n): graph.append(list(map(int,input().split()))) plan = list(map(int,input().split())) parent = [x for x in range(n+1)] # 0부터 n까지 def find_parent(x): i..
문제 링크 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 소스 코드 from itertools import combinations from collections import deque n,m = map(int,input().split()) graph = [[] for _ in range(n)] viruses = [] answers = [] walls = 0 for i in range(n): temp = list(map(int,input().split(..
문제 링크 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 소스 코드 import sys n,k = map(int,sys.stdin.readline().rstrip().split()) bag = [[0 for _ in range(k+1)] for _ in range(n+1)] items = [(0,0)] for i in range(n): w,v = map(int,sys.stdin..
