https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 이 문제는 상당히 생각하기 어렵다... 처음에는 어떻게 접근해야 하는지조차 몰랐었다.. 그래서 주변에 물어봐서 이해했다. tree-dp를 처음 풀어본 문제는 아래의 문제였다. https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1..
https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 이 문제는 유니온 파인드를 사용한 문제인데 조금 문제를 잘못읽고 시작해서 어려움을 겪고 시작했다.. 그다음에는 시간 초과로 어려움을 겪고....그 다음은 오답으로 어려움을 겪은 고통 받은 문제이다. 문제에서 요구하는 것은 친구관계인 입력이 각 줄에 주어지고, 각줄을 처리하면서 생긴 친구 그룹에 속한 사람의 수를 출력하는 것이다. 예를 들어, 아래와 같은 입력이 주어지면, Fred Bar..
https://www.acmicpc.net/problem/17352 union_root(1,3)-> parent = [0,2,3,3,4] 부모 노드를 정의한다. find_root(1) -> [0, 3, 3, 3, 4] find_root(2) -> [0, 3, 3, 3, 4]으로 정의되어서 1과 4의 root가 달라서 1 4를 출력한다. public void union_root(int x, int y){ x=find_root(x); y=find_root(y); if(x!=y){ parent[x]=y; } } public int find_root(int x){ if(x==parent[x]) return x; return parent[x]=find_root(parent[x]); } 그래서 union_root는..
https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 이 문제는 세그먼트 트리를 구현하면 된다. 트리를 구간 곱으로 초기화하고, 리프노드를 바꿔야 할 때는 노드 갱신 메서드를 사용해서 바꿔서 계산해준다. 구간 곱을 계산하는 메서드를 구현하는 과정에서 처음에 구하려는 구간 곱의 범위 밖에 있는 경우에 리턴 값을 0으로 해서 구간 곱이 모두 0이 되어서 안되었다. 그래서 이유가 뭔가 생각했는..
https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 이 문제도 운동(1956)문제와 같은 플로이드 워셜을 이용한 문제이다. 로직은 1956과 거의 똑같기 때문에 간단하게 동작 방식만을 설명하자면, 시작 지점과 도착 지점 사이의 중간지점 즉, 거쳐가는 지점이 있다고 가정하고, 최단거리를 구하는 것이다. 다익스트라가 특정 정점에서 특정 정점으로 가는 최단거리였다면 그걸 전체 정점에서 전체 정점으로 가는 최단거리라고 생각하면 된다. 정답 코드는 아래와 ..
https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 다익스트라 알고리즘으로 특정 정점에서 다른 특정 정점까지의 최단거리를 확인하였다. 그렇다면 모든 정점에서 모든 정점으로 가는 최단거리는 어떻게 구할까? 이때 사용하는 알고리즘이 플로이드 워셜이다. 플로이드 워셜은 모든 정점에 대해서 모든 정점으로 가는 최단거리를 중간 지점 노드를 사용하여 계산한다. 음의 간선 사이클이 존재하지 않는다면 음의 가중치를 가진 경우에도..
https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 이 문제는 세그먼트트리를 이용하는 문제이다. 세크먼트 트리는 주어진 쿼리를 빠르게 처리하기 위한 자료구조로 여기서는 구간합을 구하는 용도로 사용되었다. 예를들어 1~10까지의 수가 있고 이중에서 몇몇 값들을 바꾸어서 구간의 합을 구하는 경우에 아래의 그림과 같은 세그트리를 만들 수 있다. 각각의 노드에는 구간의 합을 저장하여 필요에 따라 ..
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 생각하기 너무 힘들었다.. 그래서 다른 사람의 해결책을 보면서 원리를 이해했다. 이 문제에서의 핵심은 메모리를 관리하는 것이다. 그래서 동전의 사용을 dp로 저장하였다. 동작 방식은 먼저 0부터 k까지의 수를 만드는 과정을 기록할 배열을 둔다고 생각한다. 예를 들어 n=3 k=10이고 1,2,5가 동전으로 주어졌다고 생각해보자.(설명에서 헷갈리는 것을 줄이기 위해 동전을 one,two,..
