PS109 [Baekjoon-Python] 1285 : 동전 뒤집기 https://www.acmicpc.net/problem/1285 접근 비트마스크를 적용하기 위해 H = 0, T = 1 이진수로 치환한다. 행 방향으로 뒤집을 수 있는 모든 경우의 수를 구한다. 열 방향으로 탐색하면서 T 개수가 많으면 뒤집는다. 풀이 from sys import stdin N = int(stdin.readline()) coins = [] reverse_coins = [] for _ in range(N): i = N - 1 bit = 0 for state in stdin.readline().rstrip(): if state == "T": # (1) bit += 1 2024. 1. 15. [Baekjoon-Python] 1948 : 임계경로 https://www.acmicpc.net/problem/1948 접근 위상 정렬 알고리즘을 사용해서 각 도시까지 도달하는 최대 시간을 구한다. 현재 간선이 다음 도시로 가는 최대 시간이라면 다음 도시에 현재 도시를 저장한다. 도착 도시부터 시작하여 저장된 도시의 간선을 탐색해서 간선의 개수를 구한다. 풀이 from sys import stdin from collections import deque def topological_sort(start): q = deque([(start, 0)]) while q: now, dist = q.popleft() for next, next_dist in graph[now].items(): in_degree[next] -= 1 cost = dist + next_dist.. 2024. 1. 15. [Baekjoon-Python] 1504 : 특정한 최단 경로 https://www.acmicpc.net/problem/1504 접근 다익스트라 알고리즘으로 1, u, v의 정점에서 모든 정점까지의 최단 경로를 구한다. 1 -> u -> v -> N, 1 -> v -> u -> N 경로 중 최솟값을 구한다. 경로가 없을 때는 두 개 이상의 네트워크가 존재할 때이다. 풀이 from sys import stdin from heapq import heappop, heappush def dijkstra(start): distance = [1e9] * (N + 1) distance[start] = 0 q = [] heappush(q, (0, start)) while q: dist, node = heappop(q) if distance[node] < dist: continue.. 2024. 1. 15. [Baekjoon-Python] 1238 : 파티 https://www.acmicpc.net/problem/1238 접근 다익스트라 알고리즘을 사용한다. 정방향 그래프를 탐색해서 X에서 각각의 노드까지 가는 최단 경로를 구한다. 역방향 그래프를 탐색해서 각각의 노드에서 X까지 가는 최단 경로를 구한다. 두 경로를 더한다. 풀이 from sys import stdin from heapq import heappop, heappush def dijkstra(start, graph): distance = [1e9] * (N + 1) distance[start] = 0 q = [] heappush(q, (0, start)) while q: dist, node = heappop(q) for next, next_dist in graph[node].items(): c.. 2024. 1. 15. [Baekjoon-Python] 1167 : 트리의 지름 https://www.acmicpc.net/problem/1167 접근 임의의 노드 x에서 가장 먼 노드 y를 찾은 후, 노드 y에서 가장 먼 노드 z까지의 거리를 구한다. 트리 구조는 중간 경로를 공유하기 때문에 두 번의 탐색으로 트리의 지름을 구할 수 있고, 첫 탐색은 어떤 노드를 선택해도 상관없다. 풀이 from sys import stdin def dfs(now, diameter): for next, d in graph[now].items(): if visited[next] == -1: visited[next] = diameter + d dfs(next, visited[next]) V = int(stdin.readline()) graph = [{} for _ in range(V + 1)] for .. 2024. 1. 15. [Baekjoon-Python] 1005 : ACM Craft https://www.acmicpc.net/problem/1005 접근 위상 정렬 알고리즘을 사용한다. 이전 순서의 건설 시간을 메모이제이션해서 현재 건물의 건설 시간을 계산한다. 현재 건물은 이전 순서의 건설 시간의 최댓값이 지난 후 건설이 시작된다. 풀이 from sys import stdin from collections import deque def topological_sort(target): q = deque() for i in range(1, N + 1): if in_degree[i] == 0: q.append(i) # (1) dp = [0] * (N + 1) while q: now = q.popleft() dp[now] += time[now - 1] # (2) if now == target.. 2024. 1. 15. [Baekjoon-Python] 1043 : 거짓말 https://www.acmicpc.net/problem/1043 접근 진실을 아는 사람과 파티에 오는 사람들에 교집합이 있으면 합집합을 구한다. 진실을 아는 사람과 교집합이 없는 파티의 수를 구한다. 풀이 from sys import stdin N, M = map(int, stdin.readline().split()) truth = set(stdin.readline().split()[1:]) party = [] for _ in range(M): party.append(set(stdin.readline().split()[1:])) for _ in range(M): for p in party: if truth & p: truth = truth.union(p) cnt = 0 for p in party: if.. 2024. 1. 14. [Baekjoon-Python] 2252 : 줄 세우기 https://www.acmicpc.net/problem/2252 접근 위상 정렬 알고리즘을 사용한다. 풀이 from sys import stdin from collections import deque def topological_sort(): q = deque() for i in range(1, N + 1): if in_degree[i] == 0: q.append(i) # (1) while q: node = q.popleft() print(node, end=" ") for i in graph[node]: # (2) in_degree[i] -= 1 if in_degree[i] == 0: q.append(i) N, M = map(int, stdin.readline().split()) graph = [[] .. 2024. 1. 14. [Baekjoon-Python] 11779 : 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 접근 다익스트라 알고리즘을 사용하여 출발 도시에서 도착 도시까지 가는데 발생하는 최소 비용을 구한다. 현재 노드에서 다음 노드로 갈 때 최소 비용이면 다음 노드에 현재 노드 번호를 저장한다. 풀이 from sys import stdin from heapq import heappush, heappop def dijkstra(start): q = [] heappush(q, (0, start)) while q: dist, now = heappop(q) for next, next_dist in graph[now].items(): cost = dist + next_dist if cost < distance[next]: distance[next],.. 2024. 1. 14. [Baekjoon-Python] 2805 : 나무 자르기 https://www.acmicpc.net/problem/2805 접근 나무 높이는 최대 10억이므로 이분 탐색으로 높이를 구해야 한다. low를 1, high를 N개의 나무 중 최대 길이로 설정한다. low와 high의 중간 값인 mid로 나무를 잘라서 M보다 크거나 같은지 확인한다. M미터를 만들 수 있으면 low = mid + 1, 만들 수 없으면 high = mid - 1로 설정한다. low가 high보다 작거나 같을 때까지 반복한다. N개의 나무 중 최대 높이를 L이라고 할 때, 시간복잡도는 O(NlogL) 풀이 from sys import stdin from collections import Counter _, M = map(int, stdin.readline().split()) trees =.. 2024. 1. 14. 이전 1 ··· 7 8 9 10 11 다음
