본문 바로가기
반응형

전체 글287

[Algorithm][Python]깊이/너비 우선 탐색 알고리즘(DFS/BFS) + 코드 너무 중요한 알고리즘이죠. 대표적인 그래프 탐색 알고리즘인 깊이 우선 탐색, 너비 우선 탐색에 대해서 알아봅시다. 이 그래프를 기본으로 해서 알아보겠습니다. 깊이 우선 탐색(Depth First Search) 먼저 알아볼 것은 깊이 우선 탐색, DFS 입니다. 이번 포스팅에서는 기본 그래프를 트리로 사용하고 있지만 트리에만 사용할 수 있는 것은 아닙니다. DFS는 이름 그대로 그래프를 탐색함에 있어서 깊이를 우선적으로 탐색하는 방법을 말합니다. DFS의 탐색 순서입니다. 1 → 2 → 4 → 5 → 3 → 6 → 7 의 순서로 탐색을 진행하는 모습을 확인할 수 있는데요. 저는 DFS를 보면서 호기심이 많은 사람이다 라고 생각했던 기억이 있습니다. 각 노드를 하나의 방이라고 보고 간선이 문이라고 한다면 깊.. 2023. 8. 12.
[BOJ][Python]11404 풀이 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net import sys ssr = sys.stdin.readline INF = 10000001 n = int(ssr()) m = int(ssr()) min_cost = [[INF for _ in range(n)] for _ in range(n)] for _ in range(m): a, b, c = map(int, ssr().split()) min_cost[a-1][b-1] = min(min_cost[.. 2023. 8. 11.
[BOJ][Python]9251 풀이 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net s1, s2 = input(), input() lcs = [[0 for _ in range(len(s2)+1)] for _ in range(len(s1)+1)] for i in range(1, len(s1)+1): for j in range(1, len(s2)+1): if s1[i-1] == s2[j-1]: lcs[i][j] = lcs[i-1][j-1].. 2023. 8. 10.
[BOJ][Python]2206 풀이 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline INF = 1000001 def bfs(): dpos = [(1, 0), (-1, 0), (0, 1), (0, -1)] visited = [[0 for _ in range(m)] for _ in range(n)] visited[0][0] = 1 q = de.. 2023. 8. 9.
[BOJ][Python]1918 풀이 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net def f(equation): priority = {'+':1, '-':1,'*':2,'/':2,'(':0} stack = [] for i in equation: if i.isalpha(): print(i, end='') else: if len(stack) == 0 or i == '(': stack.append(i) elif i == ')': while True: tmp = stack.pop(.. 2023. 8. 8.
[BOJ][Python]28432 풀이 https://www.acmicpc.net/problem/28432 28432번: 끝말잇기 첫 줄에 끝말잇기 기록의 길이 $N$ 이 주어집니다. $(1 \le N \le 100)$ 둘째 줄부터 다음 $N$개의 줄에는 끝말잇기의 기록 $S_1, \cdots, S_N$이 한 줄에 하나씩 주어집니다. 여기서, 하나의 $S_i$는 “?” 로 www.acmicpc.net import sys ssr = sys.stdin.readline n = int(ssr()) s = [] loc = 0 for i in range(n): word = ssr().rstrip() s.append(word) if word == '?': loc = i m = int(ssr()) first, last = '', '' a = '' if n .. 2023. 8. 7.
[BOJ][Python]1738 풀이 https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 주어 www.acmicpc.net import sys ssr = sys.stdin.readline INF = 987654321 def bellman_ford(): for i in range(1, n+1): for cur_node, next_node, next_cost in edges: cost = max_cost[cur_node] + next_cost if max_cost[cur_node] != -IN.. 2023. 8. 7.
[BOJ][Python]1865 풀이 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net import sys ssr = sys.stdin.readline INF = 10001 def bellman_ford(): min_time = [INF for _ in range(n+1)] min_time[1] = 0 for i in range(1, n+1): for j in range(1, n+1): for next_node, next_time in routes[j]: if min_t.. 2023. 8. 6.
[BOJ][Python]11657 풀이 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 ssr = sys.stdin.readline INF = 5000001 def bellman_ford(): for i in range(n): for cur_node, next_node, next_time in routes: if min_time[cur_node] != INF and min_time[cur_node]+ne.. 2023. 8. 5.
[Algorithm][Python]유니온-파인드(Union-Find) 알고리즘 + 코드 이번에는 유니온 파인드 알고리즘에 대해서 한 번 알아봅시다. 아직 학부생이던 시절에 저보다 먼저 알고리즘 공부를 하던 친구가 유니온 파인드 한 번 써보라고, 진짜 너무 편하다고 했던 기억이 나는데요. 그 때 저는 DFS/BFS도 모르던 시절이라 그런게 있구나 생각만 하고 넘겼습니다. 사실상 그런 일이 있었다는 것도 거의 잊고 지내다가 평소처럼 알고리즘 문제를 풀었는데 별로 런타임이 빠르지 않았고, 해당 문제가 어떤 태그가 있나 살펴보다가 분리 집합이라는 알고리즘으로 분류가 되어있어서 이걸 사용하면 좀 빨라지려나 싶어서 찾아봤던게 유니온 파인드와의 첫 만남이었네요. 사실 이게 유니온 파인드구나를 알았을 때는 약간의 당황과 겁이 났습니다. 저한테 유니온 파인드는 상당히 먼 얘기일거라고 생각하고 있었거든요. .. 2023. 8. 3.
반응형

티스토리툴바