개발 안 합니다.

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. LCS는 다이나믹 프로그래밍의 일종이다. ❗다이나믹 프로그래밍이란? - 다이나믹 프로그래밍(Dynamic Programming, 동적계획법 또는 동적 프로그래밍이라고도 불린다.)은..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 그래프 탐색을 이용하여 푸는 문제이다. dfs 또는 bfs를 이용해 풀 수 있다. ① 지도가 N x N 크기의 행렬이라면 (0, 0)부터 (N-1, N-1)까지 탐색한다. ② 0인 경우는 그냥 지나가고, 1인 경우는 count 후 그래프 탐색(dfs 또는 bfs)을 한다. ③ 1인 해당 좌표를 0으로 바꾸고 상, 하, 좌, 우를 확인한다. 상, 하, 좌, 우 좌표가 1이라면 0으로 바꾸고 다시..

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 from collections import deque def topology_sort(indegree, edge, n): result = [] # 큐에서 꺼낸 순서, 위상 정렬의 결과 queue = deque() for i in range(1, n+1): if indegree[i] == 0: # 진입 차수가 0인 정점을 큐에 삽입한다. queue.appe..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net import sys INF = sys.maxsize input = sys.stdin.readline def floydwarshall(distance, V): for k in range(1, V+1): for i in range(1, V+1): for j in range(1, V+1): distance[i][j] = min(distance[i][j], distance[i][k] + distance[..

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 INF = sys.maxsize input = sys.stdin.readline def bellmanford(edge_list, V, E, start): distance = [INF] * (V + 1) distance[start] = 0 updated = False for _ in range(V): updated = ..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net import heapq import sys INF = sys.maxsize input = sys.stdin.readline def dijkstra(edge_list, V, E, start): distance = [INF] * (V + 1) distance[start] = 0 p_queue = [(0, start)] while (p_queue): cost, de..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net def preorder(tree, node, visit_list): visit_list.append(node) if (tree[node][0] != '.'): preorder(tree, tree[node][0], visit_list) if (tree[node][1] != '.'): preorder(tree, tree[node][1], visit_list) def inorder(tree,..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net parent = {} rank = {} def make_set(V): for v in range(1, V+1): parent[v] = v # 부모 정점을 자신으로 초기화한다. rank[v] = 0 # rank가 높은 정점이 부모가 된다. def find(v): # root 정점을 반환한다. if parent[v] != v: parent[v] = fin..