Partially Committed

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 상황은 되게 단순하다. 가중치가 존재하는 트리 구조가 주어졌을 때, 임의의 A 노드부터 B 노드까지의 경로가 존재할 것이고 그 중 최장 경로를 트리의 지름이라고 정의한다. 트리의 지름을 반환하면 된다. 음.. 어떻게 풀지? 일단 시간 제한은 2초로 평범한 편이고, 데이터를 보니까 노드의 개수는 100000 개이다. 에지의 개수는 주어지지 않았으나, 최대 100000 - 1 개..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net N 명의 선수가 선분을 번갈아가면서 그리는 게임을 M 차례까지 진행했을 때, 중간에 사이클이 생긴다면 사이클이 생겼던 회차를, M 번 진행하는 동안 사이클이 발생하지 않았다면 0 을 출력하면 된다. 예제를 통해 생각해보자. 0 과 1 을 선택하여 0-1 선분을 긋는다는 것은 0 과 1 은 같은 집합으로 Clustering 된다는 것이다. m 번의 회차마다 주어지는 두 포인트를 같은 집합으로 ..

https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 브루트포스로 문제를 해결하기에는 N 이 너무 큰 경우에 시간 초과가 발생할 수 있다. 이때 다양한 방법으로 최적화를 시도할 수 있겠지만, 분할정복처럼 N 을 절반씩 나눠서 연산한 다음에 결과를 합쳐서 문제를 푸는 것을 meet in the middle 알고리즘이라고 한다. 다만, 재귀적으로 반복해서 N/2, N/4 ... 1 처럼 계속 쪼개는 게 아니고 맨 처음에 1회만 반으로 쪼개는 것이다. 예..

(title: [백준 13549/1956/1620/2629] 자바) A. 숨바꼭질3 BOJ 13549 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 난이도 Gold 5 풀이 시간 20 분 분류 다익스트라 / 0-1 BFS 시간복잡도 다익스트라 : O(nlogn) 0-1 BFS : O(V+E) = O(N+N) ~= O(N) 공간복잡도 일차원 그래프에서 다익스트라 알고리즘을 수행하여 쉽게 해결할 수 있다. 다익스..