본문 바로가기

🏃 algorithm/boj105

BOJ 4963 - 섬의 개수 문제 백준 온라인 저지 - 4963번 풀이 과정 섬과 바다의 지도가 주어질 때 섬의 개수를 구하는 문제입니다. BFS 를 이용해서 컴포넌트의 개수를 구해주면 됩니다. 코드 import sys from collections import deque dx = [1, -1, 0, 0, -1, -1, 1, 1] dy = [0, 0, 1, -1, -1, 1, -1, 1] def in_range(x, y): return 0 2021. 6. 15.

BOJ 5568 - 카드 놓기 문제 백준 온라인 저지 - 5568번 풀이 과정 N 개의 카드뭉치에서 K 개의 카드를 뽑아 만들 수 있는 모든 수를 구하는 문제입니다. 입력 값이 크지 않기 때문에 모든 수열을 만들어보고 집합을 이용해서 중복된 값을 제거한 뒤 총 개수를 구하면 됩니다. 코드 from itertools import permutations def solution(): number_set = set() for candidate in permutations(cards, K): num = ''.join(map(str, candidate)) number_set.add(num) return len(number_set) if __name__ == '__main__': N = int(input()) K = .. 2021. 6. 14.

BOJ 5972 - 택배 배송 문제 백준 온라인 저지 - 5972번 풀이 과정 특정 시작 지점에서 목표 지점에 도달하기 위한 최소 비용을 찾는 문제입니다. 다익스트라 알고리즘 을 이용해서 한 정점에서 모든 정점까지의 최단 비용을 구하면 ElogV 의 시간 복잡도로 구할 수 있습니다. 코드 import sys import heapq INF = 2e9 def dijkstra(frm, to): dist = [INF] * (N + 1) pq = [] dist[frm] = 0 heapq.heappush(pq, [0, frm]) while pq: cost, here = heapq.heappop(pq) if dist[here] < cost: continue for there, there_cost in graph[here]: next_cost = .. 2021. 6. 10.

BOJ 1613 - 역사 문제 백준 온라인 저지 - 1613번 풀이 과정 역사의 한 지점을 그래프의 정점으로 나타내면 각 사건의 전후 관계는 정점의 도달성 문제로 생각할 수 있습니다. 따라서 정점의 최대 개수가 400개 이하이므로 O(N^3) 의 시간복잡도를 가지는 플로이드 와샬 알고리즘 을 활용하여 문제를 해결했습니다. 모든 정점간의 도달성 여부를 계산해준 뒤, 문제에서 주어지는 입력의 전후 관계를 출력해주도록 했습니다. 다만 Python3 의 속도 한계로 인해 PyPy로 제출해야 시간제한 이내에 수행이 가능했습니다. 코드 import sys n, k = list(map(int, sys.stdin.readline().split())) adj = [[0]*n for _ in range(n)] for _ in range(k): f.. 2021. 6. 9.

BOJ 5014 - 스타트링크 문제 백준 온라인 저지 - 5014번 풀이 과정 건물의 시작 층과 목표 층이 주어졌으므로 BFS 탐색을 통해 목표 지점에 도달하기 위한 최단 경로를 찾으면 됩니다. 층이 건물을 벗어나는 경우만 주의한다면 무난하게 풀 수 있는 문제입니다. 코드 import sys from collections import deque F, S, G, U, D = list(map(int, sys.stdin.readline().split())) def bfs(start): visit = [0 for _ in range(F+1)] q = deque() visit[start] = 1 q.append((start, 0)) while q: here, cost = q.popleft() if here == G: return cost fo.. 2021. 6. 9.

BOJ 1389 - 케빈 베이컨의 6단계 법칙 문제 백준 온라인 저지 - 1389번 풀이 과정 찬구 관계를 그래프로 표현하면 케빈 베이컨의 수가 한 정점으로부터 다른 모든 정점까지의 최단 거리의 합이라는 것을 알 수 있습니다. 따라서 플로이드 와샬 알고리즘 을 활용해 모든 정점간의 최단 거리를 구한 뒤 케빈 베이컨의 수가 가장 작은 사람을 찾는 방법으로 해결했습니다. 코드 import sys N, M = list(map(int, sys.stdin.readline().split())) adj = [[sys.maxsize] * N for _ in range(N)] for _ in range(M): frm, to = list(map(int, sys.stdin.readline().split())) adj[frm-1][to-1] = 1 adj[to-1][fr.. 2021. 6. 9.

이전 1 2 3 4 5 ··· 18 다음

티스토리툴바