Algorithm202 BOJ 6497 - 전력난 문제 백준 온라인 저지 - 6497번 풀이 과정 모든 도시를 최소 비용으로 연결하는 방법을 찾는 문제입니다. 크루스칼 알고리즘 을 활용해서 MST 를 구축하고 절약 가능한 비용을 계산하면 됩니다. 코드 import sys import heapq sys.setrecursionlimit(10**6) parent = [] def union(u, v): u, v = find(u), find(v) if u == v: return parent[u] = v def find(u): if parent[u] == u: return u parent[u] = find(parent[u]) return parent[u] def solution(N, edges): ret = 0 for _ in range(N): cost, src,.. 2021. 3. 8. BOJ 6156 - Cow Contest 문제 백준 온라인 저지 - 6156번 풀이 과정 두 소들 간의 싸움 경기 결과가 주어질 때 순위를 결정할 수 있는 소들의 수를 구하는 문제입니다. 특정 소의 순위를 결정하기 위해서는 해당 소에게 진 소들의 수와 해당 소를 이긴 소들의 합이 N - 1 이어야 합니다. 때문에 각 소들을 그래프의 정점이라고 생각한다면 모든 소들 사이의 도달 가능성을 플로이드 와샬 알고리즘을 이용해 파악하고 각 소들에 대해서 특정 소 A 에 도달 가능한 정점의 수와 A 에서 도달 가능한 소들의 수를 세어주면 됩니다. 코드 import sys N, M = list(map(int, sys.stdin.readline().split())) results = [list(map(int, sys.stdin.readline().split().. 2021. 3. 8. BOJ 9625 - BABBA 문제 백준 온라인 저지 - 9625번 풀이 과정 동적 계획법 을 활용한 문제입니다. 각 문자가 일정 규칙으로 변환되는데 이를 활용해서 점화식을 세우면 됩니다. 저 같은 경우 문장의 길이가 피보나치 수열을 따르면서 B 의 개수도 피보나치 수열의 개수대로 증가된다는 것을 이용해서 문제를 풀었는데 다른 분들의 풀이를 보니 그냥 A 와 B 각각에 대해서 점화식을 세우고 순회를 하면 간단하게 해결할 수 있었습니다. K 가 작기 때문에 완전 탐색 으로 구현해도 풀 수 있을 것 같기는 한데 이후에 비슷한 유형에 대비해서 접근 방법을 기억해놔야 할 것 같습니다. 코드 K = int(input()) def solution(): dp = [-1] * (K + 1) dp[0], dp[1] = 1, 1 for i in ran.. 2021. 3. 8. BOJ 11952 - 좀비 문제 백준 온라인 저지 - 11952번 풀이 과정 문제에서 주어진 좀비로 점령된 도시들을 이용해서 위험한 지역을 찾고, 이를 통해 도시 방문 비용을 계산하고 다익스트라 알고리즘을 이용해 최단거리를 계산합니다. 이때 도시에게 점령당한 도시는 최단 거리 계산 시 고려하지 않도록 하는 것에 유의합니다. 좀비에게 점령당한 도시를 기준으로 S 이하의 거리를 가지는 위험한 도시를 판단하기 위해서는 BFS 를 이용했습니다. 코드 import sys from collections import deque import heapq N, M, K, S = list(map(int, sys.stdin.readline().split())) P, Q = list(map(int, sys.stdin.readline().split())).. 2021. 3. 8. BOJ 20055 - 컨베이어 벨트 위의 로봇 문제 백준 온라인 저지 - 20055번 풀이 과정 문제에서 제시한 규칙대로 동작하는 컨베이어 벨트를 구현하면 되는 문제입니다. 2차원 배열을 이용해서 컨베이어 벨트를 나타냈지만 사실 그냥 1차원 배열을 이용해서 구현해도 될 것 같습니다. 문제에서 주어진 네 가지 단계를 각각의 함수로 구현해서 검사해주는 방식으로 구현했습니다. 코드 import sys from collections import deque N, K = list(map(int, sys.stdin.readline().split())) belts = list(map(int, sys.stdin.readline().split())) def init_conveyor(): conveyor = [[0] * N for _ in range(2)] convey.. 2021. 3. 8. BOJ 20044 - Project Teams 문제 백준 온라인 저지 - 20044번 풀이 과정 두 명씩 팀원을 구성할 때, 팀원들의 코딩 능력의 합들 중 가장 작은 경우를 최대화하는 문제입니다. 두 명씩 묶기 때문에 능력치를 기준으로 오름차순으로 정렬한 다음 양 끝에 있는 학생들끼리 묶어주면 되는 그리디 문제입니다. 코드 import sys N = int(input()) stats = list(map(int, sys.stdin.readline().split())) def solution(): stats.sort() answer = sys.maxsize for i in range(N): s = stats[i] + stats[2 * N - i - 1] answer = min(answer, s) return answer print(solution()) 2021. 3. 8. 이전 1 ··· 15 16 17 18 19 20 21 ··· 34 다음
