링크 : https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 코드 def bf(start): dis = [0] * (n + 1) for i in range(n): for way in graph: cur,next_node,cost = way if dis[next_node] > dis[cur] + cost: dis[next_node] = dis[cur] + cost if i >= n-1: return False return True for..

링크 : https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 코드 import sys sys.setrecursionlimit(10**6) n = int(input()) inOrder, postOrder = list(map(int,input().split())), list(map(int,input().split())) arr = [0] * (n+1) for i in range(n): arr[inOrder[i]] = i def preOrder(inStart,inEnd,postS..

링크 : https://www.acmicpc.net/source/57235108 로그인 www.acmicpc.net 코드 ''' 먼저 처음 물을 대려면 우물을 먼저 하나 파야한다. 이 우물을 어디에 먼저 팔 것인가는 최소 스패닝 트리 문제 특성상 그리디하게 선정할 수 있을 것 같은데 어떤 기준으로 그리디하게 선정할 것인가가 문제이다. 1. 다른 논에서 끌어올 때 가장 많은 비용이 드는 것. 2. 우물을 팔 때 가장 적은 비용이 드는 것. 1번으로 했을 떄는 우물을 팔 떄 비용이 훨씬 더 엄청나게 많이 들 수도 있다는 단점이 존재한다. 2번으로 했을 때는 해당 우물은 적은 비용으로 팔 수 있을 지 몰라도 다른 논에 물을 댈 때 엄청나게 많은 비용이 발생할 수 있다. 그렇다면 2번으로 먼저 한 후에 어떤 논..

링크 : 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-..