본문 바로가기

분류 전체보기164

[백준] 최단경로(1753) Java 다익스트라 알고리즘 문제 링크 https://www.acmicpc.net/problem/1753 문제 요약 더보기 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 더보기 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하.. 2022. 1. 15.
[야매 알고리즘] B-tree(2) 야매 알고리즘? 더보기 알고리즘의 정확한 정의나 의미를 다루지 않고 핵심적인 작동 원리와 코드 예제를 정리하기 위한 시리즈입니다. 전부 짚고 넘어가면 좋겠지만 그럴 지식도 없고, 공부하는 것보다 정리하는데 더 많은 에너지와 시간을 소모할 것 같아서, 기억을 되살리기 위한 아카이브 정도로만 사용할 수 있게 간단하게 정리할 예정입니다. B-tree의 특징 이전 글에서 B-tree의 특징과 장점, 그리고 B-tree를 왜 사용하는지에 대해 대략적으로 알아봤다. 하지만 대략적인 특징을 아는 것으로는 B-tree를 구현할 수 없다. 이 글에선 B-tree의 특징을 좀 더 디테일하게, 그리고 좀 더 전공자 느낌 나게 알아보겠다. B-tree의 특징은 다음과 같다. 자식 노드의 개수를 최대 M개 가질 수 있는 B-t.. 2021. 9. 18.
[야매 알고리즘] B-tree(1) 야매 알고리즘? 더보기 알고리즘의 정확한 정의나 의미를 다루지 않고 핵심적인 작동 원리와 코드 예제를 정리하기 위한 시리즈입니다. 전부 짚고 넘어가면 좋겠지만 그럴 지식도 없고, 공부하는 것보다 정리하는데 더 많은 에너지와 시간을 소모할 것 같아서, 기억을 되살리기 위한 아카이브 정도로만 사용할 수 있게 간단하게 정리할 예정입니다. 왜 B-tree인가? B-tree는 AVL tree나 RB tree와 같은 self-balancing tree의 일종이다. B-tree의 가장 큰 특징이자 장점은 disk input/output 연산을 최소화하는 데 있다. 실무에서 다루는 데이터의 크기는 절대로 메인 메모리에 한 번에 올릴 수 없을 정도로 크기 때문에, 데이터에 접근하기 위해서는 disk access는 필연적.. 2021. 9. 17.
[백준] 최소 스패닝 트리(1197) Java, Prim 알고리즘 문제 링크 https://www.acmicpc.net/problem/1197 문제 요약 더보기 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 더보기 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨.. 2021. 8. 30.
[백준] 유럽여행(1185) Java 문제 링크 https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 문제 요약 더보기 민식이는 여름에 유럽여행을 떠날 계획이다. 방문할 나라는 총 N개의 나라이고 편리하게 1번부터 N번까지 번호를 붙였다. 또한 이 나라들 사이에 이동 가능한 길은 M개가 있는데 민식이는 귀찮기 때문에 N개의 나라가 서로 연결된 것을 유지시키면서 최대한 많은 길을 지도에서 제거하고자 한다. 즉, N-1개의 길만을 남겨야할 것이다. 각 .. 2021. 8. 29.

티스토리툴바