전체 글

문제 설명그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.https://www.acmicpc.net/problem/1197      제한 사항      풀이문제를 요약하면, 최소 스패닝 트리를 만들고 가중치를 출력하는 것이다.최소 스패닝 트리란, 그래프의 모든 노드를 포함하는 최소 가중치 트리를 말한다. 최소 스패닝 트리를 구하는 방법은 크게 두 가지이다.크루스칼 알고리즘프림 알고리즘 해당 문제에서는 크루스칼 알고리즘을 사용하였다.크루스칼 알고리즘은 간선 리스트를 통해 최소 스패닝 트리에 포함되는 노드를 확장하는 방법이다.우선, 간선리스트의 가중치를 ..

문제 설명세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 안 된다. 다음과 같은 경우를 생각해보자.첫 번째 단어 : cat두 번째 단어 : tree세 번째 단어 : tcraete보면 알 수 있듯이, 첫 번째 단어와 두 번째 단어를 서로 섞어서 세 번째 단어를 만들 수 있다. 아래와 같이 두 번째 예를 들어보자.첫 번째 단어 : cat두 번째 단어 : tree세 번째 단어 : catrtee이 경우 역시 가능하다. 그렇다면 "cat"과 "tree"로 "cttaree"를 형성하는건 불가능하다는걸 눈치챘을 것이다.      제한 사항      풀이문제를 요약하면, 두 단..

문제 설명각 노드가 자식을 최대 K개 가질 수 있는 트리를 K진 트리라고 한다. 총 N개의 노드로 이루어져 있는 K진 트리가 주어진다.트리는 "적은 에너지" 방법을 이용해서 만든다. "적은 에너지" 방법이란, 이전 깊이를 모두 채운 경우에만, 새로운 깊이를 만드는 것이고, 이 새로운 깊이의 노드는 가장 왼쪽부터 차례대로 추가 한다.아래 그림은 노드 9개로 이루어져 있는 3진 트리이다.노드의 개수 N과 K가 주어졌을 때, 두 노드 x와 y 사이의 거리를 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/11812      제한 사항      풀이문제를 요약하면, N개의 노드를 K진 트리로 만들어 Q개의 쿼리를 처리하면 된다.Q개의 쿼리는 주어지는 두 노드의 거리를 구하는..

문제 설명인하대 컴퓨터 공학과에 재학 중인 이산이는 오랜만에 미팅을 나가 볼까 한다. 미팅은 N명이 원탁에 앉아서 진행된다고 한다. 질투가 난 이산이 친구 명기는 X의 저주를 걸었다. 그 저주는 N명이 동시에 2명씩 짝을 지어 악수할 때 사람의 팔이 교차되거나 한 사람이라도 악수를 하지 못하면 그 미팅은 실패하게 되는 저주다. 하지만 명기는 이산이에게 저주를 풀 기회를 주었다. 미팅에 성공할 경우의 수를 구하여 큰소리로 외치면 저주가 풀린다. 하지만 이산이는 계산 능력이 부족해서 당신에게 도움을 청했다. 이산이가 걸린 저주를 풀어주는 프로그램을 만들어주자.미팅에 참가한 사람이 4명일 경우 미팅에 성공할 경우는 다음 그림과 같이 2가지이다.미팅에 참가한 사람이 6명일 경우 미팅에 성공할 경우는 다음 그림과..

문제 설명어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.https://www.acmicpc.net/problem/2042      제한 사항      풀이문제를 요약하면, 트리에 대한 정보가 주어지고, M개의 쿼리가 주어지면 해당하는 연산을 하는 것이다.쿼리의 종류로는 특정한 지점의 수를 변경하는 것과 주어진 구간의 곱을 출력하는 것이 있다. 해당 문제를 풀기 위해서는 구간 트리를 사용..

문제 설명N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.      제한 사항      풀이문제를 요약하면, LCA를 찾는 문제이다.LCA란 최소 공통 조상을 의미한다.예시에 주어진 트리를 보자.주어진 트리는 위와 같이 생겼고, 6번과 11번의 LCA는 2번이다. LCA를 구하는 유명한 방법은 두 가지이다.두 노드의 레벨을 동일하게 맞춘 뒤, 한 칸씩 위로 올라가며 LCA 탐색오일러 투어를 통한 LCA 탐색 첫 번째 방법은 부모 노드와 깊이를 모두 기록해야 된다.조금 번거롭다고 생각하여 간..

문제 설명트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/1167      제한 사항      풀이문제를 요약하면, 트리의 지름을 구하는 것이다.트리의 지름이란 트리에 있는 노드 간의 거리가 가장 먼 두 노드의 거리를 말한다.트리의 지름을 구하는 방법은 크게 두 가지이다.DFS를 이용하는 방법DP를 이용하는 방법DFS를 이용하는 방법은 간단하다.임의의 노드를 고른 뒤 DFS를 통해 가장 먼 노드를 찾아낸다.가장 먼 노드는 트리의 지름에 포함되는 노드이다.따라서, 그 노드에서 가장 먼 노드를 다시 구하면 그 거리가 트리의 지름이 된다. 이를 증명하는 것은 간단하다.트리의 지름..