You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
* 개념
* Union-Find 자료구조라고도 한다.
* 서로 중복되지 않는 부분 집합들(공통 원소가 없는, 즉 "상호 배타적" 인 부분 집합들)로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조
* 주로 트리 구조를 이용하여 구현한다.
* 연산
* make-set(x) : x를 유일한 원소로 하는 새로운 셋을 만든다.
* union(x, y) : x가 속한 셋과 y가 속한 셋을 합친다. 즉, x와 y가 속한 두 집합을 합치는 연산
* find(x) : x가 속한 셋의 대표값(루트노드 값)을 반환한다. 즉, x가 어떤 집합에 속해 있는지 찾는 연산
* 사용 예제
* 전체 집합이 있을 때 구성 원소들이 겹치지 않도록 분할(partition)하는 데 자주 사용된다.
1. 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려는 경우
2. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 가입한 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하는 경우
[#issue1-1] Disjoint-set 구현 방법
기본적인 구현 방법
/* 초기화 */introot[MAX_SIZE];
for (inti = 0; i < MAX_SIZE; i++)
parent[i] = i;
/* find(x) */intfind(intx) {
// 루트 노드는 부모 노드 번호로 자기 자신을 가진다.if (root[x] == x) {
returnx;
} else {
// 각 노드의 부모 노드를 찾아 올라간다.returnfind(root[x]);
}
}
/* union(x, y) */voidunion(intx, inty){
// 각 원소가 속한 트리의 루트 노드를 찾는다.x = find(x);
y = find(y);
root[y] = x;
}
최적화한 구현 방법
/* 초기화 */introot[MAX_SIZE];
for (inti = 0; i < MAX_SIZE; i++)
root[i] = i;
/* find(x) */intfind(intx) {
if (root[x] == x) {
returnx;
} else {
// 경로 압축// find 하면서 만난 모든 값의 부모 노드를 root로 만든다. root[x] = find(root[x]);
}
}
/* union(x, y) */voidunion(intx, inty){
x = find(x);
y = find(y);
// 두 값의 root가 같으면(이미 같은 트리) 합치지 않는다.if(x == y)
return;
root[y] = x; // y의 root를 x로 변경
}
/* union2(x, y): 두 원소가 속한 트리의 전체 노드의 수 구하기 */intnodeCount[MAX_SIZE];
for (inti = 0; i < MAX_SIZE; i++)
nodeCount[i] = 1;
intunion2(intx, inty){
x = find(x);
y = find(y);
// 두 값의 root가 같지 않으면if(x != y) {
root[y] = x; // y의 root를 x로 변경nodeCount[x] += nodeCount[y]; // x의 node 수에 y의 node 수를 더한다.nodeCount[y] = 1; // x에 붙은 y의 node 수는 1로 초기화
}
returnnodeCount[x]; // 가장 root의 node 수 반환
}
[#issue2] 비트마스크의 개념과 사용 이유
* 개념
* 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트마스크(bitmask)라고 부른다.
* bit 연산을 이용해서 집합을 만들 수 있다.
* bit가 1이면 "켜져 있다.", 0이면 "꺼져 있다."
* 부호 없는 N bit의 값: 2^0 ~ 2^(n-1)
* 비트마스크 사용 이유
1. 더 빠른 수행 시간
2. 더 간결한 코드
3. 적은 메모리 사용량
4. 연관 배열을 배열로 대체 가능:
* 연관 배열 객체 map<vector,int>을 비트마스크를 이용해 정수 변수로 나타내면 단순한 배열 int[]를 사용할 수 있다.
* 비트마스크 사용 예제
* 집합 구현
* N bit 정수는 0 ~ (N-1)까지의 정수 원소를 가질 수 있는 집합
* 집합 {1, 4, 5, 6, 7, 9}: 2^1 + 2^4 + 2^5 + 2^6 + 2^7 + 2^9 = 754
* 집합 {1, 3, 4, 5, 9}: 2^1 + 2^3 + 2^4 + 2^5 + 2^9 = 570
[#issue2-1] 비트연산의 종류와 사용법
A
B
~A
A & B (AND)
A ㅣ B (OR)
A ^ B (XOR)
0
0
1
0
0
0
0
1
0
0
1
1
1
0
0
0
1
1
1
1
0
1
1
0
* shift left(<<), shift right(>>)
* A << B
* A를 B bit만큼 왼쪽으로 민다.
* A * 2^B
* A >> B
* A를 B bit만큼 오른쪽으로 민다.
* A / 2^B
* Ex) (A + C) / 2는 (A + C) >> 1과 동일
* A & B (AND)
* Ex) 어떤 수 N이 홀수 인지 판단하는 if(N % 2 == 1)는 if(N & 1)과 동일
* 비트 연산 사용법
* int S = 0; // 공집합
* int num = Integer.parseInt(st.nextToken()); // 임의의 숫자
1. add:
* S = S | (1 << num)
2. remove:
* S = S & ~(1 << num)
3. check:
* S & (1 << num)
* num이 집합에 없으면 return 0
4. toggle:
* S = S ^ (1 << num);
5. all:
* NUM SIZE: 집합에 들어갈 수 있는 num의 최대 수 + 1
* S = ((1 << NUM_SIZE) - 1)
[#issue3] 이진 트리의 개념과 종류
* 이진 트리의 개념
* 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조
* 이진 트리 표현 방법
1. 1차원 배열 표현
* 이진 트리의 i번째 노드를 배열의 i번째 요소에 저장하는 방법
* 장점: 노드의 위치를 index에 의하여 쉽게 접근할 수 있다.
* 단점: 특정 트리에서 기억 공간의 낭비가 심할 수 있다.
2. 연결리스트 표현
* 왼쪽 자식을 가리키는 포인터 필드와 오른쪽 자식을 가리키는 포인터 필드를 포함하는 노드로 표현하는 방법
* 장점: 기억 장소를 절약할 수 있고, 노드의 삽입과 삭제가 용이하다.
* 단점: 이진 트리가 아닌 일반 트리의 경우에는 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 하기 때문에 접근상의 어려움이 따른다.
* 이진 트리의 종류
* Full Binary Tree(정 이진 트리, Strictly Binary Tree)
* 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
* Complete Binary Tree(완전 이진 트리)
* 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.
* 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다.
* 마지막 레벨 h 에서 1부터 2h-1 개의 노드를 가질 수 있다.
* 또 다른 정의는 가장 오른쪽의 잎 노드가 (아마도 모두) 제거된 포화 이진 트리다.
* 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.
* Perfect Binary Tree(포화 이진 트리)
* 모든 내부 노드가 두 개의 자식 노드를 가진다.
* 모든 잎 노드가 동일한 깊이 또는 레벨을 갖는다.
[#issue3-1] 이진 트리와 관련된 용어들
* left child node(왼쪽 자식 노드): 왼쪽 부트리의 노드
* right child node(오른쪽 자식 노드): 오른쪽 부트리의 노드
* parent node(부모 노드): 해당 노드를 자식으로 하는 노드
* sibling node(형제 노드): 부모가 같은 두 노드
* external/leaf node(잎 노드): 차수가 0인 노드. 즉, 자식이 없는 노드
* internal/branch node(내부 노드): 차수가 0이 아닌 노드. 즉, 자식이 있는 노드
* degree(차수): 자식의 수
* depth(노드의 깊이): 루트 노드에서 자신까지 가는 경로의 길이. 루트 노드의 깊이는 0
* level(노드의 레벨): 루트 노드에서 자신까지 가는 (경로의 길이 + 1). 루트 노드의 레벨은 1
* height(노드의 높이): 그 노드와 단말 노드 사이의 경로의 최대 길이
* size(노드의 크기) 자기 자신 및 모든 자손 노드의 수
* 트리의 깊이와 레벨과 높이와 크기는 각각 노드의 길이와 레벨과 높이와 크기의 최댓값이다.
* 특히, 트리의 높이는 그 루트 노드의 높이와 같으며, 트리의 크기는 그 루트 노드의 크기와 같다.
[#issue4] 최대힙의 삽입과 삭제
* 최대힙(Max Heap)
* 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
* key(부모 노드) >= key(자식 노드)
* 즉, 가장 큰 값은 루트 노드
* N개가 힙에 들어가 있으면 높이는 log(N)
* 최대힙 삽입
1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.
* 최대힙 삭제
1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다.
* 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
3. 힙을 재구성한다.
int[] maxHeap;
intheapSize;
/* 최대힙 삽입 */voidinsert_max_heap(intx){
maxHeap[++heapSize] = x; // 힙 크기를 하나 증가하고 마지막 노드에 x를 넣는다.for (inti=heapSize; i>1; i/=2) {
// 마지막 노드가 자신의 부모 노드보다 크면 swapif (maxHeap[i/2] < maxHeap[i]) {
swap(i/2, i);
} else {
break;
}
}
}
/* 최대힙 삭제 */intdelete_max_heap(){
if (heapSize == 0) // 배열이 빈 경우return0;
intitem = maxHeap[1]; // 루트 노드의 값을 저장한다.maxHeap[1] = maxHeap[heapSize]; // 마지막 노드의 값을 루트 노드에 둔다.maxHeap[heapSize--] = 0; // 힙 크기를 하나 줄이고 마지막 노드를 0으로 초기화한다.for (inti=1; i*2<=heapSize;) {
// 마지막 노드가 왼쪽 노드와 오른쪽 노드보다 크면 반복문을 나간다.if (maxHeap[i] > maxHeap[i*2] && maxHeap[i] > maxHeap[i*2+1]) {
break;
}
// 왼쪽 노드가 더 큰 경우, 왼쪽 노드와 마지막 노드를 swapelseif (maxHeap[i*2] > maxHeap[i*2+1]) {
swap(i, i*2);
i = i*2;
}
// 오른쪽 노드가 더 큰 경우, 오른쪽 노드와 마지막 노드를 swapelse {
swap(i, i*2+1);
i = i*2+1;
}
}
returnitem;
}
