union-find(Disjoint-set) union-find(Disjoint-set)은 데이터들을 하나의 집합으로 묶어 표현할 필요가 있을 때 사용된다. 예를 들어 게임에서 하나의 파티를 표현하고 싶을 때 같은 1번 파티라는 것을 표현하기 위해 사용된다. 이와 같은 연산을 하기 위해서 필요한 3가지 연산이 있습니다. 1. 초기화(init): 초기에는 특별한 집합이 없는 자기 자신을 가리키는 초기화를 만듭니다. 2. 합치기(union): 두 원소 a와 b가 주어졌을 때 이 둘을 하나의 집합으로 만듭니다. 3. 찾기(find): 해당 원소가 어떤 집합에 속해있는지 찾습니다. 이러한 집합을 표현하는데 있어서 가장 쉬운 방법은 트리를 이용한 것입니다. 트리에서 한 집합에 속하는 원소들을 하나의 트리로 묶어줍..

가가오 문제 중 투포인터가 나왔다 필자는 투포인터라는 존재를 모른채 이진 탐색 문제인줄 알고 오지게 삽질하다가 못풀었다. 그래서 그 분노로 투포인터에 대해 공부하고 백준 문제 4문제 정도를 풀었다. 투 포인터는 이름 그대로 두개의 점을 사용하여 연속된 수의 집합의 합 및 개수들을 구할 수 있게 해준다. 여기서 주의 할 점은 연속된 집합이다. 시작은 start, end 둘다 첫 요소를 가리키며 시작한다. 목표하는 숫자에 비해 작으면 end를 계속 늘려가주며 더해준다. 그러다 목표하는 숫자에 비해 커지거나 같아지면 start요소의 값을 빼주고 start를 늘린다. 사실 글만 보면 어떤 느낌인지 느낌이 안올 것이다. 그래서 그림을 준비했다. 위 그림을 통해서도 알 수 있지만 크게 생각할 점은 두가지다. 집합의..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 학창시절 아빠 폰 게임으로 많이 한 스도쿠이다. 스도쿠를 생각해보면 두가지 조건이 있다. 조건 1. 가로, 세로 줄에 1 ~ 9까지의 모든..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, www.acmicpc.net 이진 검색트리의 순회를 활용하여 문제를 풀어보겠습니다. 이 문제의 입력은 이진 검색 트리를 전위순회한 값으로 주어지고 있습니다. ..

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 이문제는 트리 순회의 특징을 이용하여 문제를 해결해야한다. 사용할 트리의 특징들이 무엇 이냐면 1. 후위순회(postorder)의 가장 마지막 노드는 루트 노드이다. 후위순회를 돌때 가장 마지막 노드는 트리의 루트노드이다. 2. 중위순회(inorder) 중위순회에서는 루트의 왼쪽 노드들은 루트의 왼쪽에 위치한 노드들이고 오른쪽 노드들은 오른쪽에 위치한 노드들이다. 그림을 보면 루트 노드를 구분한 후 왼쪽과 오른쪽 도 처음과 똑같은..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼 www.acmicpc.net 노드간의 가중치가 주어질 때 각 노드간의 최대 길이를 구하는 문제이다. 이 문제는 트리도 결국 그래프와 다르지 않다는 것을 인지하는 ..