백준 2533 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 풀이 전 나의 생각 친구 관계 트리가 주어졌을 때, 최소 얼리 어답터의 수를 구해야 한다. 현재 선택한 친구가 얼리 어답터인 경우, 연결된 친구들은 모두 일반인이거나 얼리 어답터일 수 있다. 현재 선택한 친구가 일반인일 경우, 연결된 친구들은 모두 얼리 어답터가 되어야 한다. 조건 - 2 ≤ N ≤ 1,000,000 과정 이 문제에서 요구하는 것은 각 친구 즉, 노드들이 얼리 ..
알고리즘 및 자료구조/트리
백준 14267 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 풀이 전 나의 생각 상사가 직속 부하를 칭찬하며 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있을 때, 각자 얼마나 칭찬을 받았는지 구해야한다. 조건 - (2 ≤ n, m ≤ 100,000) - (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000) - 1번의 경우, 상사가 없으므로 -1이 입력된다. - 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사..
백준 20955 https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 풀이 전 나의 생각 뉴런과 시냅스가 주어질 때 모든 뉴런이 트리 구조가 될 때 까지의 연산 횟수를 구해야 한다. 조건 2 ≤ N ≤ 100,000 1 ≤ M ≤ min(N × (N – 1) / 2, 100,000) 1 ≤ u, v ≤ N u ≠ v 두 뉴런 사이에는 최대 1개의 시냅스만 존재한다. 과정 문제를 보면 뉴런은 노드고, 시냅스는 간선이라는 것을 알 수 있다. 이 문제의..
백준 1068 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 전 나의 생각 트리가 주어지고, 특정 노드를 삭제 했을 때 나올 수 있는 리프노드의 총 개수를 구해야 한다. 조건 - N은 50보다 작거나 같은 자연수 - 만약 부모가 없다면 (루트) -1이 주어진다. 과정 문제의 이름이 트리인 만큼 기본적인 트리의 풀이 방법인 DFS, BFS..등을 사용해서 리프노드에 도착했을 경우 최종값을 증가하며 풀어나가면 된다. 하지만 문제에서 요..
백준 22856 https://www.acmicpc.net/problem/22856 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 풀이 전 나의 생각 노드가 N개인 이진 트리가 주어질 때, 이를 중위 순회와 유사하게 순회하는 유사 중위 순회의 방식으로 순회하며 이동한 거리를 구해야 한다. 조건 1 ≤ N ≤ 100,000 1 ≤ a, b ≤ N 과정 유사 중위 순회의 방식음 다음과 같다. 현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로 이동한다. 그렇지 않고 현재 위..
백준 1240 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 풀이 전 나의 생각 N개의 노드로 이루어진 트리와 M개의 두 노드 쌍을 입력 받을 때 두 노드 사이의 거리를 구해내야 한다. 조건 2 ≤ N ≤ 1000 1 ≤ M ≤ 1000 트리 상에 연결된 두 점과 거리는 10000이하인 자연수이다. 트리 노드의 번호는 1부터 N까지 자연수이며, 두 노드가 같은 번호를 갖는 경우는 없다. 과정 조건을 통해 알 수 있는 것은 ..
백준 15681 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 풀이 전 나의 생각 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력해야 한다. 조건 - (2 ≤ N ≤ 10^5, 1 ≤ R ≤ N, 1 ≤ Q ≤ 10^5) - (1 ≤ U, V ≤ N, U ≠ V) - (1 ≤ U ≤ N) 과정 입력에 관한 조건들만 존재하기 때문에 이 부분은 넘어가고 이 문제에서 중요한 것..
백준 4803 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 풀이 전 나의 생각 그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성해야 한다. 조건 - n ≤ 500 - m ≤ n(n-1)/2 과정 주어진 조건들은 입출력의 값에 관한 것들이기 때문에 크게 신경쓰지 않아도 된다. 이 문제에서 신경써야할 것은 트리는 사이클이 없는 연결 요소라는 것이다. 그럼 이 문제에서 신경써야 할 부분은 트리의 사이클이 존재하는 부분을..
