본문 바로가기

알고리즘/백준

 (64)
[BOJ] [Python] 1914: 하노이 탑 전형적인 하노이 탑 구현 문제이다. def honoi_tower(n, start, tmp, end): if n == 1: print(start, end) else: honoi_tower(n-1, start, end, tmp) print(start, end) honoi_tower(n-1, tmp, start, end) num = int(input()) print(2 ** num - 1) if num
[BOJ] [Python] 5052 : 전화번호 목록 하나라도 문자열 전체가, 다른 문자열과 겹친다면 NO를 출력한다. (아니면 YES.) 트라이를 이용해서 해결했다. 주의해야 할 점은 '911', '91125426'과 같은 입력이 같이 들어올 때이다. 1. '91125426'이 먼저 들어오고 그 후에 '911'이 들어온다. search 함수에서, '911'이 트라이를 돌면서 문자열 전체가 겹친다면 True를 반환한다. 2. '911'이 먼저 들어오고 그 후에 '91125426'이 들어온다. search 함수에서, '91125426'이 트라이를 돌면서 data가 None이 아니라면 어떤 문자열과 겹치는 것이다. True를 반환한다. 1, 2가 모두 해당이 안 된다면 insert 함수를 실행시켜, 문자열을 트라이에 넣어준다. import sys class N..
[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..
[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..
[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:..

티스토리툴바