컴공 공부 블로그

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 이번 문제는 제가 1학년 때 과제로 풀어봤었던 비슷한 문제입니다. 뭣모르고 풀었던, 심지어 자바로 풀어봤던 문제라 스택이나 큐를 쓰는건지도 몰랐었죠... 나중에 조교님께서 정답 코드를 공개해주시고서야 알았습니다. 휴학을 하면서 다른 공부를 하다가 먹고 놀면서 백수 비슷한 삶을 누리다가 복학 준비 기념으로 백준에서 문제를 하나 풀어보려니 비슷한 문제를 찾아서 파이썬으로..

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..