본문 바로가기

알고리즘

 (138)
[BOJ] [Python] 4358 : 생태학 트라이를 이용해 해결했다. 시간복잡도는 O(N * M)이다. (N : 최대 그루 수, M : 최대 이름 길이) 입력이 N은 1,000,000, M은 30이니까, 30,000,000으로 1초내 수행이 가능하다. (문자열 탐색 알고리즘을 사용하지 않으면 O(N * N * M)이라 시간 초과이다.) import sys class Node(object): def __init__(self, key, data=None): self.key = key self.data = data self.children = {} class Trie(object): def __init__(self): self.head = Node(None) def insert(self, string): curr_node = self.head for ..
[BOJ] [Python] 14621 : 나만 안되는 연애 모든 노드를 방문하고, 최단 거리를 구하기 위해 프림 알고리즘을 사용했다. 사심 경로의 첫 번째 특징은 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다는 것이다. 다시 말해서, 남초-남초 대학과 여초-여초 대학인 길은 선택해서는 안 된다. 이것은 현재 노드에서 현재 노드와 연결된 노드를 order 리스트에 넣어줄 때, 확인하면 된다. import sys import heapq input = sys.stdin.readline n, m = map(int, input().split()) graph = [[] for i in range(n + 1)] gender = [''] gender += list(map(str, input().split())) for _ in range(m): u, v, d ..
[BOJ] [Python] 1197 : 최소 스패닝 트리 최소 신장 트리를 만들기 위해 프림 알고리즘을 사용했다. import sys import heapq input = sys.stdin.readline V, E = map(int, input().split()) graph = [[] for i in range(V + 1)] for _ in range(E): A, B, C = map(int, input().split()) graph[A].append((C, (A, B))) graph[B].append((C, (B, A))) count = 0 dp = [0] * (V + 1) order = [] now_node = 1 # 시작 노드 result = 0 # 가중치 합 for edge in graph[1]: heapq.heappush(order, edge) whil..
[최소 신장 트리] 프림[Prim] 알고리즘 최소 신장 트리란? 주어진 그래프의 모든 정점을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리이다. 최소 신장 트리를 구하는 방법은 여러 가지가 있다. 그중에 프림 알고리즘에 대해 알아보자. 프림 알고리즘은 그리디 알고리즘이다. 동작 순서 1. 그래프에서 임의의 정점을 선택하여 집합 A에 넣는다. 2. 그 정점과 연결된 변들을 집합 B에 넣는다. 3. 집합 B에서, 변의 양쪽 정점이 모두 집합 A에 있지 않은 것 중에 가장 가중치가 작은 변을 찾는다. 4. 3번에서 찾는 변의 양쪽 정점 중 집합 A에 없는 정점을, 집합 A에 넣는다. 모든 정점이 집합 A에 들어올 때까지 2~4번을 반복한다. 알고리즘이 종료됐을 때 만들어진 트리는 최소 신장 트리가 된다. 아래는 코드이다. https://so..
[BOJ] [Python] 18116 : 로봇 조립 Union-Find 알고리즘으로 해결했다. 이 문제의 핵심은 루트 노드 밑에 몇 개의 노드가 존재하는지 파악하는 것이다. import sys input = sys.stdin.readline n = int(input()) parent = [-1 for i in range(1000000 + 1)] def find(x): if parent[x] < 0: return x else: y = find(parent[x]) parent[x] = y return y def union(x, y): x = find(x) y = find(y) if x == y: return if parent[x] < parent[y]: A, B = x, y else: A, B = y, x parent[A] += parent[B] parent..
[그래프/트리] 분리 집합[Disjoint Set] 분리 집합은 서로소 집합이다. (상호 배타적 집합) Union-Find 알고리즘을 사용하고, 트리 구조를 이용해 구현한다. 참고로, 트리 구조는 부모노드가 자식 노드를 가리키는 형태이지만, 분리 집합은 자식 노드가 부모노드를 가리키는 형태이다. Union-Find Union-Find는 서로소 집합 알고리즘이다. 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 집합에 속하는지 판별하는 알고리즘이다. Union-Find는 두 가지 수행이 필요하다. Find 노드 x가 어느 집합에 포함되어 있는지 찾는다. Union 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합친다. Union-Find 구현 초기화 parent = [i for i in range(0, n + 1)]..
[BOJ] [Python] 16562 : 친구비 Union-Find 알고리즘으로 해결했다. 친구비가 큰 노드가 작은 노드 쪽으로 들어간다. 만약 친구비가 같다면, 트리의 높이를 따진다. 트리의 높이가 작은 쪽이 긴 쪽으로 들어간다. n, m, k = map(int, input().split()) cash = [0] cash += list(map(int, input().split())) parent = [i for i in range(0, n + 1)] rank = [0] * (n + 1) # 트리 높이 def find(x): if x == parent[x]: return x else: y = find(parent[x]) parent[x] = y return y def union(x, y): x = find(x) y = find(y) if x == y:..
[BOJ] [Python] 1005 : ACM Craft 위상 정렬로 해결했다. import sys input = sys.stdin.readline T = int(input()) # 테스트케이스의 개수 for _ in range(T): N, K = map(int, input().split()) # 건물의 개수, 건설 순서 규칙의 총 개수 dp = [0] * (N + 1) queue = [] graph = [] check = [0] * (N + 1) # 전입 차수 val = [0] # 건설 시간 order = [1] * (N + 1) # 출력될 수 있는 순서 result = [0] * (N + 1) # 건물 시간 결과 val += list(map(int, input().split())) for _ in range(N + 1): graph.append([]) fo..
[정렬] 위상 정렬(Topological Sort) 위상 정렬은 사이클이 발생하지 않는 방향 그래프에서 사용한다. 순서를 결정할 때 사용하는 알고리즘으로, 순서가 정해져 있는 작업을 신경 쓴다. 위상 정렬은 아래처럼 동작한다. 1. 진입차수가 0인 정점(들)을 큐에 넣는다. (진입차수란 상대 정점에서 자신의 정점으로 오는 간선의 수이다.) 2. 큐에 있는 원소를 꺼낸다. 3. 진입차수가 0인 정점(들)을 큐에 삽입한다. 4. 큐가 빌 때까지 2~3번을 반복한다. 위상 정렬이 모든 원소를 방문했다면, 큐에서 꺼낸 순서가 결과이다. (모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재하는 것으로 위상 정렬을 사용할 수 없다.) 동작 방식을 보면 알 수 있듯이, 위상 정렬은 답이 여러 개가 될 수 있다.
[BOJ] [Python] 14567 : 선수과목 (Prerequisite) 위상 정렬로 해결했다. import sys input = sys.stdin.readline n, m = map(int, input().split()) dp = [0] * (n + 1) queue = [] graph = [] check = [0] * (n + 1) result = [1] * (n + 1) for _ in range(n + 1): graph.append([]) for _ in range(m): A, B = map(int, input().split()) graph[A].append(B) check[B] += 1 # 진입 차수 dp[B] = 1 for i in range(1, len(dp)): if dp[i] == 0: queue.append(i) result[i] = 1 while queue:..

티스토리툴바