링크 : https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 코드 from collections import defaultdict T = int(input()) n = int(input()) A = list(map(int, input().split())) m = int(input()) B = list(map(int, input().split())) sum_A, sum_..

링크 : https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 코드 import sys input = sys.stdin.readline for _ in range(int(input())): n = int(input()) rank = list(map(int,input().split())) degree = [0] * (n + 1) for i,v in enumerate(rank): degree[v] = i graph = [*degree] m = i..

링크 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 코드 a = "0"+input() b = "0"+input() dp = [[0] * (len(b)) for _ in range(len(a))] for i in range(1,len(a)): for j in range(1,len(b)): dp[i][j] = dp[i-1][j-1] + 1 if a[i] == b[j] else max(dp[i-..

링크 : https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 문제 코드 import heapq as hq import sys input = sys.stdin.readline n = int(input()) station = [] for _ in range(n): hq.heappush(station,list(map(int,input().split()))) l,p = map(int,input().split()) cn..

링크 : 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 문제 코드 n = int(input()) arr = list(map(int,input().split())) dp = [1] * n for i in range(n): for j in range(i): if arr[i] > arr[j]: dp[i] = max(dp[i],dp[j]+1) a = max(dp) pr..

링크 : https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 문제 코드 import sys input = sys.stdin.readline def union(a,b): a, b = find(a), find(b) if a == b: return network[a] parents[b] = a network[a] += network[b] return network[a] def find(node): if parents[node] != node:..

링크 : https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 코드 def BFS(s): visited = [[False] * (total + 1) for _ in range(total+1)] a,b = s[0],s[1] Q = deque() Q.append((a,b)) visited[a][b] = True while Q: x,y = Q.popleft() z = total - x - y if x == y == z: return True for ..

링크 : https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 코드 n, k = map(int, input().split()) n_len = len(str(n)) s1, s2 = set(), set() s1.add(n) for _ in range(k): while s1: x = str(s1.pop()) for i in range(n_len-1): for j in range(i+1, n_len): if x[j] == '0' and i == 0: continue y = x[:i] + x[j] + x[i+1:j] + x..

링크 : https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 문제 코드 import sys input = sys.stdin.readline def belman_ford(start): dist[start] = 0 for i in range(1,n+1): for j in range(m): now, next, weight = graph[j] if dist[now] != 1e9 and dist[..