Data Structures - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:20:05Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:20 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[알고리즘 설계와 분석#Data Structures\|알고리즘 설계와 분석]]		상위 문서: [[알고리즘 설계와 분석#Data Structures\|알고리즘 설계와 분석]]

Pinkgo: /* Path Compression */

2025-11-17T16:59:38Z

Path Compression

← 이전 판		2025년 11월 17일 (월) 16:59 판
185번째 줄:		185번째 줄:
	===Path Compression===		===Path Compression===
	[[파일:Figure 2. Path Compression.png\|섬네일\|Figure 3. Path Compression]]		[[파일:Figure 2. Path Compression.png\|섬네일\|Figure 3. Path Compression]]
	Path Compression은 Union by Size 방식보다 더욱 빠른 ~~연상을~~ 가능케 하는 방식이다. 이상적인 Union-Find 트리 구조는 깊이가 1인 트리이다. 이런 트리 구조에서는 Find 연산의 시간복잡도는 O(1)이기 때문이다. 따라서 Path Compression 방식은 Find 연산 중의 과정에서 만난 모든 노드들이 바로 루트를 가리키게 수정하도록 하는 것을 핵심적인 아이디어로 삼는다. Figure 3는 왼쪽 트리가 주어졌을 때, Find(4)를 수행하면 4 → 3 → 2 → 1을 따라 루트를 찾는 과정에서 만난 모든 노드(4, 3, 2)의 부모 포인터를 1로 직접 갱신하는 것을 보여준다. 이를 통해서 트리의 높이를 확 줄일 수 있다.		Path Compression은 Union by Size 방식보다 더욱 빠른 연산을 가능케 하는 방식이다. 이상적인 Union-Find 트리 구조는 깊이가 1인 트리이다. 이런 트리 구조에서는 Find 연산의 시간복잡도는 O(1)이기 때문이다. 따라서 Path Compression 방식은 Find 연산 중의 과정에서 만난 모든 노드들이 바로 루트를 가리키게 수정하도록 하는 것을 핵심적인 아이디어로 삼는다. Figure 3는 왼쪽 트리가 주어졌을 때, Find(4)를 수행하면 4 → 3 → 2 → 1을 따라 루트를 찾는 과정에서 만난 모든 노드(4, 3, 2)의 부모 포인터를 1로 직접 갱신하는 것을 보여준다. 이를 통해서 트리의 높이를 확 줄일 수 있다.

	이 경우 Union-Find 연산들의 평균 수행 시간이 O(α(n))로 감소한다. 이때 α(n)은 inverse Ackermann function(역 아커만 함수)인데, n이 우주에 존재하는 원자 수보다 커도 α(n) <= 5이다. 따라서 아무리 큰 그래프라도 “상수 시간”에 가깝게 동작한다.		이 경우 Union-Find 연산들의 평균 수행 시간이 O(α(n))로 감소한다. 이때 α(n)은 inverse Ackermann function(역 아커만 함수)인데, n이 우주에 존재하는 원자 수보다 커도 α(n) <= 5이다. 따라서 아무리 큰 그래프라도 “상수 시간”에 가깝게 동작한다.

Pinkgo: /* Path Compression */

2025-11-17T16:59:29Z

Path Compression

← 이전 판		2025년 11월 17일 (월) 16:59 판
185번째 줄:		185번째 줄:
	===Path Compression===		===Path Compression===
	[[파일:Figure 2. Path Compression.png\|섬네일\|Figure 3. Path Compression]]		[[파일:Figure 2. Path Compression.png\|섬네일\|Figure 3. Path Compression]]
	Path Compression은 Union by Size 방식보다 더욱 빠른 ~~영상을~~ 가능케 하는 방식이다. 이상적인 Union-Find 트리 구조는 깊이가 1인 트리이다. 이런 트리 구조에서는 Find 연산의 시간복잡도는 O(1)이기 때문이다. 따라서 Path Compression 방식은 Find 연산 중의 과정에서 만난 모든 노드들이 바로 루트를 가리키게 수정하도록 하는 것을 핵심적인 아이디어로 삼는다. Figure 3는 왼쪽 트리가 주어졌을 때, Find(4)를 수행하면 4 → 3 → 2 → 1을 따라 루트를 찾는 과정에서 만난 모든 노드(4, 3, 2)의 부모 포인터를 1로 직접 갱신하는 것을 보여준다. 이를 통해서 트리의 높이를 확 줄일 수 있다.		Path Compression은 Union by Size 방식보다 더욱 빠른 연상을 가능케 하는 방식이다. 이상적인 Union-Find 트리 구조는 깊이가 1인 트리이다. 이런 트리 구조에서는 Find 연산의 시간복잡도는 O(1)이기 때문이다. 따라서 Path Compression 방식은 Find 연산 중의 과정에서 만난 모든 노드들이 바로 루트를 가리키게 수정하도록 하는 것을 핵심적인 아이디어로 삼는다. Figure 3는 왼쪽 트리가 주어졌을 때, Find(4)를 수행하면 4 → 3 → 2 → 1을 따라 루트를 찾는 과정에서 만난 모든 노드(4, 3, 2)의 부모 포인터를 1로 직접 갱신하는 것을 보여준다. 이를 통해서 트리의 높이를 확 줄일 수 있다.

	이 경우 Union-Find 연산들의 평균 수행 시간이 O(α(n))로 감소한다. 이때 α(n)은 inverse Ackermann function(역 아커만 함수)인데, n이 우주에 존재하는 원자 수보다 커도 α(n) <= 5이다. 따라서 아무리 큰 그래프라도 “상수 시간”에 가깝게 동작한다.		이 경우 Union-Find 연산들의 평균 수행 시간이 O(α(n))로 감소한다. 이때 α(n)은 inverse Ackermann function(역 아커만 함수)인데, n이 우주에 존재하는 원자 수보다 커도 α(n) <= 5이다. 따라서 아무리 큰 그래프라도 “상수 시간”에 가깝게 동작한다.

Pinkgo: /* Path Compression */

2025-11-17T16:50:35Z

Path Compression

← 이전 판		2025년 11월 17일 (월) 16:50 판
187번째 줄:		187번째 줄:
	Path Compression은 Union by Size 방식보다 더욱 빠른 영상을 가능케 하는 방식이다. 이상적인 Union-Find 트리 구조는 깊이가 1인 트리이다. 이런 트리 구조에서는 Find 연산의 시간복잡도는 O(1)이기 때문이다. 따라서 Path Compression 방식은 Find 연산 중의 과정에서 만난 모든 노드들이 바로 루트를 가리키게 수정하도록 하는 것을 핵심적인 아이디어로 삼는다. Figure 3는 왼쪽 트리가 주어졌을 때, Find(4)를 수행하면 4 → 3 → 2 → 1을 따라 루트를 찾는 과정에서 만난 모든 노드(4, 3, 2)의 부모 포인터를 1로 직접 갱신하는 것을 보여준다. 이를 통해서 트리의 높이를 확 줄일 수 있다.		Path Compression은 Union by Size 방식보다 더욱 빠른 영상을 가능케 하는 방식이다. 이상적인 Union-Find 트리 구조는 깊이가 1인 트리이다. 이런 트리 구조에서는 Find 연산의 시간복잡도는 O(1)이기 때문이다. 따라서 Path Compression 방식은 Find 연산 중의 과정에서 만난 모든 노드들이 바로 루트를 가리키게 수정하도록 하는 것을 핵심적인 아이디어로 삼는다. Figure 3는 왼쪽 트리가 주어졌을 때, Find(4)를 수행하면 4 → 3 → 2 → 1을 따라 루트를 찾는 과정에서 만난 모든 노드(4, 3, 2)의 부모 포인터를 1로 직접 갱신하는 것을 보여준다. 이를 통해서 트리의 높이를 확 줄일 수 있다.

	이 경우 Union-Find 연산들의 평균 수행 시간이 O(α(n))로 감소한다. 이때 α(n)은 inverse Ackermann function(역 아커만 함수)인데, n이 우주에 존재하는 원자 수보다 커도 α(n) <= ~~5입니다~~. 따라서 아무리 큰 그래프라도 “상수 시간”에 가깝게 동작한다.		이 경우 Union-Find 연산들의 평균 수행 시간이 O(α(n))로 감소한다. 이때 α(n)은 inverse Ackermann function(역 아커만 함수)인데, n이 우주에 존재하는 원자 수보다 커도 α(n) <= 5이다. 따라서 아무리 큰 그래프라도 “상수 시간”에 가깝게 동작한다.

	===Implementation of Union-Find===		===Implementation of Union-Find===

Pinkgo: /* Union-Find */

2025-10-17T05:58:57Z

Union-Find

← 이전 판		2025년 10월 17일 (금) 05:58 판
168번째 줄:		168번째 줄:

	==Union-Find==		==Union-Find==
			[[파일:Figure 2. Union-Find Example.png\|섬네일\|Figure 2. Union-Find Example]]
	Union-Find 자료구조는 두 연산(Find, Union)을 효율적으로 수행하기 위해 사용하는 자료구조이다. [[Minimum Spanning Trees#Kruskal’s Algorithm\|Kruskal 알고리즘]]의 경우와 같이 그래프의 여러 정점들을 여러 집합으로 관리할 때, 두 정점이 같은 연결요소(component)에 속하는지, 또는 두 집합을 합칠지를 빠르게 판단해야 한다. 이때 사용하는 연산은:		Union-Find 자료구조는 두 연산(Find, Union)을 효율적으로 수행하기 위해 사용하는 자료구조이다. [[Minimum Spanning Trees#Kruskal’s Algorithm\|Kruskal 알고리즘]]의 경우와 같이 그래프의 여러 정점들을 여러 집합으로 관리할 때, 두 정점이 같은 연결요소(component)에 속하는지, 또는 두 집합을 합칠지를 빠르게 판단해야 한다. 이때 사용하는 연산은:
	# Find(i): i가 속한 “집합의 대표(root)”를 반환.		# Find(i): i가 속한 “집합의 대표(root)”를 반환.

Pinkgo: /* Union-Find */

2025-10-17T05:57:38Z

Union-Find

← 이전 판		2025년 10월 17일 (금) 05:57 판
175번째 줄:		175번째 줄:
	#* 두 집합의 루트를 찾아, 한쪽 루트를 다른 루트 밑에 붙인다.		#* 두 집합의 루트를 찾아, 한쪽 루트를 다른 루트 밑에 붙인다.
	#* 즉, “find(i) == find(j)”가 되도록 만든다.		#* 즉, “find(i) == find(j)”가 되도록 만든다.
	이를 구현하기 위해서 각 집합(set)은 하나의 트리로 표현된다. 이때 각 트리의 루트 노드(root)가 해당 집합의 “대표 이름(name of the set)”에 해당한다. 또한 각 노드는 “부모 포인터(parent pointer)”를 가지므로, 각 원소는 자신의 부모를 알고 있고, 루트는 자기 자신을 부모로 가진다. Figure 1은 이를 잘 보여준다. 왼쪽의 각 트리 자료구조는 각각의 집합을 나타내며, 오른쪽 그림은 각 원소의 부모는 나타내는 배열 p[i]를 보여준다.		이를 구현하기 위해서 각 집합(set)은 하나의 트리로 표현된다. 이때 각 트리의 루트 노드(root)가 해당 집합의 “대표 이름(name of the set)”에 해당한다. 또한 각 노드는 “부모 포인터(parent pointer)”를 가지므로, 각 원소는 자신의 부모를 알고 있고, 루트는 자기 자신을 부모로 가진다. Figure 2은 이를 잘 보여준다. 왼쪽의 각 트리 자료구조는 각각의 집합을 나타내며, 오른쪽 그림은 각 원소의 부모는 나타내는 배열 p[i]를 보여준다.

	===Union by Size===		===Union by Size===
183번째 줄:		183번째 줄:

	===Path Compression===		===Path Compression===
	[[파일:Figure 2. Path Compression.png\|섬네일\|Figure 2. Path Compression]]		[[파일:Figure 2. Path Compression.png\|섬네일\|Figure 3. Path Compression]]
	Path Compression은 Union by Size 방식보다 더욱 빠른 영상을 가능케 하는 방식이다. 이상적인 Union-Find 트리 구조는 깊이가 1인 트리이다. 이런 트리 구조에서는 Find 연산의 시간복잡도는 O(1)이기 때문이다. 따라서 Path Compression 방식은 Find 연산 중의 과정에서 만난 모든 노드들이 바로 루트를 가리키게 수정하도록 하는 것을 핵심적인 아이디어로 삼는다. Figure 2는 왼쪽 트리가 주어졌을 때, Find(4)를 수행하면 4 → 3 → 2 → 1을 따라 루트를 찾는 과정에서 만난 모든 노드(4, 3, 2)의 부모 포인터를 1로 직접 갱신하는 것을 보여준다. 이를 통해서 트리의 높이를 확 줄일 수 있다.		Path Compression은 Union by Size 방식보다 더욱 빠른 영상을 가능케 하는 방식이다. 이상적인 Union-Find 트리 구조는 깊이가 1인 트리이다. 이런 트리 구조에서는 Find 연산의 시간복잡도는 O(1)이기 때문이다. 따라서 Path Compression 방식은 Find 연산 중의 과정에서 만난 모든 노드들이 바로 루트를 가리키게 수정하도록 하는 것을 핵심적인 아이디어로 삼는다. Figure 3는 왼쪽 트리가 주어졌을 때, Find(4)를 수행하면 4 → 3 → 2 → 1을 따라 루트를 찾는 과정에서 만난 모든 노드(4, 3, 2)의 부모 포인터를 1로 직접 갱신하는 것을 보여준다. 이를 통해서 트리의 높이를 확 줄일 수 있다.

	이 경우 Union-Find 연산들의 평균 수행 시간이 O(α(n))로 감소한다. 이때 α(n)은 inverse Ackermann function(역 아커만 함수)인데, n이 우주에 존재하는 원자 수보다 커도 α(n) <= 5입니다. 따라서 아무리 큰 그래프라도 “상수 시간”에 가깝게 동작한다.		이 경우 Union-Find 연산들의 평균 수행 시간이 O(α(n))로 감소한다. 이때 α(n)은 inverse Ackermann function(역 아커만 함수)인데, n이 우주에 존재하는 원자 수보다 커도 α(n) <= 5입니다. 따라서 아무리 큰 그래프라도 “상수 시간”에 가깝게 동작한다.

Pinkgo: /* Path Compression */

2025-10-17T05:50:54Z

Path Compression

@@ 188번째 줄: / 188번째 줄: @@
 이 경우 Union-Find 연산들의 평균 수행 시간이 O(α(n))로 감소한다. 이때 α(n)은 inverse Ackermann function(역 아커만 함수)인데, n이 우주에 존재하는 원자 수보다 커도 α(n) <= 5입니다. 따라서 아무리 큰 그래프라도 “상수 시간”에 가깝게 동작한다.
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 ==각주==

Pinkgo: /* Implementation of Union-Find */

2025-10-17T05:48:10Z

Implementation of Union-Find

@@ 176번째 줄: / 176번째 줄: @@
 #* 즉, “find(i) == find(j)”가 되도록 만든다.
 이를 구현하기 위해서 각 집합(set)은 하나의 트리로 표현된다. 이때 각 트리의 루트 노드(root)가 해당 집합의 “대표 이름(name of the set)”에 해당한다. 또한 각 노드는 “부모 포인터(parent pointer)”를 가지므로, 각 원소는 자신의 부모를 알고 있고, 루트는 자기 자신을 부모로 가진다. Figure 1은 이를 잘 보여준다. 왼쪽의 각 트리 자료구조는 각각의 집합을 나타내며, 오른쪽 그림은 각 원소의 부모는 나타내는 배열 p[i]를 보여준다.
 ===Union by Size===

Pinkgo: /* Path Compression */

2025-10-17T05:47:55Z

Path Compression

← 이전 판		2025년 10월 17일 (금) 05:47 판
207번째 줄:		207번째 줄:

	이 경우 Union-Find 연산들의 평균 수행 시간이 O(α(n))로 감소한다. 이때 α(n)은 inverse Ackermann function(역 아커만 함수)인데, n이 우주에 존재하는 원자 수보다 커도 α(n) <= 5입니다. 따라서 아무리 큰 그래프라도 “상수 시간”에 가깝게 동작한다.		이 경우 Union-Find 연산들의 평균 수행 시간이 O(α(n))로 감소한다. 이때 α(n)은 inverse Ackermann function(역 아커만 함수)인데, n이 우주에 존재하는 원자 수보다 커도 α(n) <= 5입니다. 따라서 아무리 큰 그래프라도 “상수 시간”에 가깝게 동작한다.

	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">

Pinkgo: /* Path Compression */

2025-10-17T05:46:31Z

Path Compression

← 이전 판		2025년 10월 17일 (금) 05:46 판
203번째 줄:		203번째 줄:

	===Path Compression===		===Path Compression===
			[[파일:Figure 2. Path Compression.png\|섬네일\|Figure 2. Path Compression]]
	Path Compression은 Union by Size 방식보다 더욱 빠른 영상을 가능케 하는 방식이다. 이상적인 Union-Find 트리 구조는 깊이가 1인 트리이다. 이런 트리 구조에서는 Find 연산의 시간복잡도는 O(1)이기 때문이다. 따라서 Path Compression 방식은 Find 연산 중의 과정에서 만난 모든 노드들이 바로 루트를 가리키게 수정하도록 하는 것을 핵심적인 아이디어로 삼는다. Figure 2는 왼쪽 트리가 주어졌을 때, Find(4)를 수행하면 4 → 3 → 2 → 1을 따라 루트를 찾는 과정에서 만난 모든 노드(4, 3, 2)의 부모 포인터를 1로 직접 갱신하는 것을 보여준다. 이를 통해서 트리의 높이를 확 줄일 수 있다.		Path Compression은 Union by Size 방식보다 더욱 빠른 영상을 가능케 하는 방식이다. 이상적인 Union-Find 트리 구조는 깊이가 1인 트리이다. 이런 트리 구조에서는 Find 연산의 시간복잡도는 O(1)이기 때문이다. 따라서 Path Compression 방식은 Find 연산 중의 과정에서 만난 모든 노드들이 바로 루트를 가리키게 수정하도록 하는 것을 핵심적인 아이디어로 삼는다. Figure 2는 왼쪽 트리가 주어졌을 때, Find(4)를 수행하면 4 → 3 → 2 → 1을 따라 루트를 찾는 과정에서 만난 모든 노드(4, 3, 2)의 부모 포인터를 1로 직접 갱신하는 것을 보여준다. 이를 통해서 트리의 높이를 확 줄일 수 있다.