문제 링크 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: # 둘 중 하나가 글자가 아..
전체 글
문제 링크 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://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 소스 코드 import heapq as hq def solution(N, road, K): graph = [[500001 for _ in range(N+1)] for _ in range(N+1)] for i in range(1,N+1): graph[i][i] = 0 for a,b,k in road: graph[a][b] = min(graph[a][b],k) graph[b][a] = mi..
문제 링크 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(..