Data Structures

Array & ArrayList & LinkedList

Array와 LinkedList의 비교이다.

✨ Array

배열이며, 논리적 저장순서와 물리적 저장순서가 일치한다.
특정 자료형들이 메모리 공간 상에서 연속적으로 이루어져 있다.
immutable하다.
인덱스로 해당 원소에 접근할 수 있으며, 인덱스를 알고 있다면 O(1)의 시간 복잡도로 원소에 접근이 가능하다. 즉, Random Access가 가능하다.
삭제 또는 삽입 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤, shift해줘야 하므로 비용이 발생한다. O(n)
메모리 공간 활용에 제약이 있다.

✨ LinkedList

데이터 검색 시 처음 노드부터 순회해야 한다. 이유는 논리적 저장 순서와 물리적 저장 순서가 다르기 때문이다. O(n)
메모리 공간 상에서 각 노드들이 연속적으로 이루어져 있지 않고 흩어져 있으며, 각각의 노드가 자신의 다음 노드의 위치를 알고 있는 형태이다.
각 노드들이 메모리 공간 상의 어디에 위치하는지는 각각의 노드들만 알고 있고, 사용자는 제일 첫 번째 노드의 위치만 알고 있는 상태이다.
어떤 원소를 삽입, 삭제 시 그 원소를 찾기 위해 O(n)의 시간이 발생하고 추가적으로 작업을 완료하는 시간까지 O(n)의 시간이 걸린다.
결국, LinkedList는 검색과 삽입, 삭제 과정 모두 O(n)의 시간 복잡도를 갖는다.

✨ Dynamic Array(ArrayList)

이름처럼 내부적으로 배열을 사용하여 데이터를 관리한다.
인덱스를 가지고 있어 데이터 검색에 적합하고 속도가 빠르다.
- 시간 복잡도 : O(1)
데이터의 삽입, 삭제 시 해당 데이터를 제외한 모든 데이터를 임시 배열을 생성해 복사하므로 삽입, 삭제가 빈번할 경우 속도가 느리며 부적합하다.
- 시간 복잡도 : O(n)
동기화를 지원하지 않아 Vector보다 빠르다.

✨ 데이터 접근 속도

Array
- 인덱스를 사용하여 빠르게 접근하므로 시간 복잡도는 O(1)이다.
- Random Access가 가능하다.
LinkedList
- 특정 원소에 접근하기 위해서는 처음부터 순차적으로 검색하기 때문에 시간 복잡도는 O(N)이다.

✨데이터 삽입 속도

Array
- 데이터를 중간이나 맨 앞에 삽입할 경우, 이후의 데이터를 Shift해야 하므로 추가 과정과 시간이 소요된다.
- 따라서 데이터가 많은 경우, 비효율적이다.
- O(N)의 시간이 걸린다.
LinkedList
- 중간 삽입 없이 맨 앞과 맨 뒤에만 삽입한다면 O(1)의 시간 복잡도를 갖는다.
- 그렇지 않다면 삽입할 위치를 찾고(O(N))과 삽입 연산을 진행하기 때문에 O(N)의 시간 복잡도를 갖는다.
- 그럼에도 불구하고 Array보다 빠른 성능을 갖는다.

Array의 경우, 데이터를 삽입하여 모든 공간이 꽉 차게 되면 새로운 메모리 공간을 할당받아 옮겨야 하지만, LinkedList를 그럴 필요가 없다. 추가할 때마다 동적으로 메모리 공간을 할당받는다.

✨ 데이터 삭제 속도

Array
- 데이터 삭제의 경우, 그 위치의 데이터를 삭제한 후 전체적으로 Shift해줘야 하기 때문에 O(N)의 시간 복잡도를 갖는다.
LinkedList
- 삭제할 원소를 찾기 위해 O(N)의 시간 복잡도를 갖고 삭제한다. 하지만, Array보다 빠르게 삭제 연산을 수행한다.

✨ 메모리 할당

Array
- 메모리에는 Array가 선언되자 마자 Compile time에 할당되어 진다.
- 정적 메모리 할당이라고 한다.
LinkedList
- 메모리는 새로운 Node가 추가될 때 runtime에 할당되어 진다.
- 동적 메모리 할당이라고 한다.

✨ 결론

삽입과 삭제가 빈번하게 일어난다면 LinkedList를 사용하는 것이 좋다.
데이터에 접근하는 것이 빈번하게 일어난다면 Array를 사용하는 것이 좋다.
데이터의 검색이 주가 되는 경우에는 Dynamic Array(ArrayList)를 사용하는 게 좋다.
데이터의 삽입, 삭제가 빈번하다면 Dynamic Array(ArrayList)보다는 LinkedList를 사용하는 편이 낫다.

Stack & Queue (스택 & 큐)

스택과 큐는 선형 자료구조이다.

✨ Stack

나중에 들어간 원소가 먼저 나오는 구조이다.
LIFO(Last in First Out)의 구조.
안드로이드의 액티비티를 관리하는 데 스택이 사용된다.
시간 복잡도 : O(n)
공간 복잡도 : O(n)
언제 사용? 함수의 콜 스택, 문자열 역순 출력, 연산자 후위 표기법 등

✨ Queue

먼저 들어간 원소가 먼저 나오는 구조이다.
FIFO(First in First out)의 구조.
큐는 활용 분야가 되게 많다. 안드로이드의 경우, 루퍼의 메시지 큐가 예시 중 하나이다.
시간 복잡도 : O(n)
공간 복잡도 : O(n)
언제 사용? 버퍼, 마구 입력된 것을 처리하지 못하고 있는 상황, bfs 탐색 등

✨ 2개의 스택으로 큐 구현

가끔 이런 문제가 면접에서 나온다고 한다. 어렵다고 생각했는데, 그리 어렵지 않고 간단하게 구현할 수 있다.

inbox에 데이터를 삽입한다(push) -> A,B
inbox에 있는 데이터를 추출(pop)하여 outbox에 삽입(push) 한다. -> B,A
outbox에 있는 데이터를 추출(pop)한다. -> A,B 순으로 출력된다.

즉, inbox 스택에 A,B 순으로 데이터를 삽입하면 위의 그림처럼 스택에 데이터가 쌓인다. 그리고 inbox 스택에 있는 데이터를 pop해서 outbox로 옮긴다. 그렇게 되면 outbox에는 B,A 순서로 데이터가 쌓인다.

그리고 다시 outbox 스택에 있는 데이터를 pop하게 되면 A,B 순으로 데이터가 출력된다.

✨ Stack 구현

TODO

✨ Queue 구현

TODO

Tree(트리)

✨ 트리의 개념

트리라는 이름이 나온 이유는 실제 나무를 거꾸로 세워놓은 듯한 모양이라서 트리라고 부른다.

선형 자료구조에서 배열이나 리스트 등도 존재하지만, 트리가 나온 이유는 뭘까?

일반 배열에서 삽입이나 삭제를 하는데 O(N)의 시간이 걸린다. 배열의 첫번째 원소에 삽입하는 경우 나머지 모든 요소들을 한 칸씩 뒤로 미뤄야 하므로 최악의 시간 복잡도 O(N)이 나온다. 하지만, 트리는 편향 트리가 아닌 이상 일반적인 트리에서는 O(log N) 정도의 시간으로 줄여진다.

또한 트리는 계층 구조를 이루는 경우에 굉장히 좋다.

회사의 조직도를 생각해보면, 맨 위에 회장님, 사장님이 있고, 부서별, 팀별로 각각 트리가 생길 것이다. 이런 경우, 원하는 부서를 타고 내려가기만 하면 되므로 다른 자료 구조보다 찾기가 훨씬 쉬울 것이다.

✨ 특징

Tree는 Stack이나 Queue와 같이 선형 구조가 아닌 비선형 자료구조이다.
계층적 관계를 표현한다.
루트 노드를 제외한 모든 노드는 단 하나의 부모 노드만을 갖는다.

✨ 트리의 구성 요소

Node : 트리를 구성하는 각각의 요소.
Edge : 트리를 구성하기 위해 노드와 노드를 연결하는 선.
Root Node : 트리 구조에서 최상위에 있는 노드.
Terminal Node : 하위에 다른 노드가 연결되어 있지 않은 노드.
Internal Node : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.

✨ Binary Tree(이진 트리)

루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 진다. (노드가 없을 수도 있다.) 나뉘어진 두 서브 트리도 모두 이진 트리어야 한다.
각 층별로 숫자를 매겨서 이를 트리의 레벨이라고 한다. 레벨은 1부터 시작하고 루트 노드의 레벨은 1이다. 트리의 최고 레벨을 가리켜 트리의 높이라고 한다.
종류
- Full Binary Tree(포화 이진 트리) : 모든 레벨이 꽉 찬 이진 트리를 의미한다.
  - 레벨 별로 노드의 개수가 1,2,4,8,16 ... 으로 늘어난다. 따라서 일반적인 이진트리에서 각 레벨 별 최대 노드의 개수는 2^(k - 1)이 된다.
  - 레벨 별 노드는 공비가 2인 등비 수열이라고 볼 수 있으므로 등비수열의 합으로 생각하면 높이가 h인 이진트리가 가질 수 있는 최대 노드 수는 2^h - 1이라고 할 수 있다.
- Complete Binary Tree(완전 이진 트리) : 왼쪽에서 오른쪽으로 순서대로 차곡 차곡 채워진 이진 트리를 의미한다.
  - 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리이다. 왼쪽이 비어있고 오른쪽이 들어가있는 트리는 완전 이진 트리가 아니다.
- Skewed Binary Tree(편향 이진 트리) : 모든 노드가 부모의 왼쪽 자식이기 때문에 왼쪽으로 편향되어 있거나 반대로 모든 노드가 부모의 오른쪽 자식이기 때문에 오른쪽으로 편향되어 있는 이진 트리를 말한다.

B Tree & B+ Tree

이진 트리는 하나의 부모가 두 개의 자식밖에 가지지 못하고, 균형이 맞지 않으면 검색 효율이 선형 검색 급으로 떨어진다. 하지만 이진 트리 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN)의 성능을 보이는 장점이 있기 때문에 계속 개선시키기 위한 노력이 이루어지고 있다.

✨ B Tree

데이터 베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종이다.
이진 트리를 확장해서, 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이 B Tree.
자식 수에 대한 일반화를 진행하면서, 하나의 레벨에 더 저장되는 것 뿐만 아니라 트리의 균형을 자동으로 맞춰주는 로직까지 갖추었다. 단순하고 효율적이며, 레벨로만 따지면 완전히 균형을 맞춘 트리이다.
Ex)
- 대량의 데이터를 처리해야 할 때, 검색 구조의 경우 하나의 노드에 많은 데이터를 가질 수 있다는 점은 상당히 큰 장점이다.
- 대량의 데이터는 메모리보다 블럭 단위로 입출력하는 하드디스크 or SSD에 저장해야 하기 때문!
- 한 블럭이 1024 바이트이면, 2바이트를 읽으나 1024바이트를 읽으나 똑같은 입출력 비용이 발생한다.
- 따라서 하나의 노드를 모두 1024바이트로 꽉 채워서 조절할 수 있으면 입출력에 있어서 효율적인 구성을 갖출 수 있다.
  - B-Tree는 이러한 장점을 토대로 많은 데이터베이스 시스템의 인덱스 저장 방법으로 애용하고 있다.

규칙

노드의 자료수가 N이면, 자식 수는 N+1이어야 한다.
각 노드의 자료는 정렬된 상태여야 한다.
루트 노드는 적어도 2개 이상의 자식을 가져야 한다.
루트 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다.
외부 노드로 가는 경로의 길이는 모두 같다.
입력 자료는 중복될 수 없다.

✨ B+ Tree

데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드가 추가로 있다.
기존의 B-Tree와 데이터의 연결리스트로 구현된 색인구조.
B-Tree의 변형 구조로 index 부분과 leaf 노드로 구성된 순차 데이터 부분으로 이루어진다. 인덱스 부분의 key 값은 leaf에 있는 key 값을 직접 찾아가는데 사용한다.

장점

블럭 사이즈를 더 많이 이용할 수 있다. (Key 값에 대한 하드디스크 액세스 주소가 없기 때문)
Leaf 노드끼리 연결 리스트로 연결되어 있어서 범위 탐색에 매우 유리하다.

단점

B-Tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+Tree는 무조건 leaf 노드까지 내려가봐야 한다.

✨ 비교

B-Tree : 각 노드에 데이터가 저장된다.
- 각 노드에서 key와 data 모두 들어갈 수 있고, data는 disk block으로 포인터가 될 수 있다.
B+ Tree : index 노드와 leaf 노드로 분리되어 저장된다.
- 각 노드에서 key만 들어간다. 따라서 data는 leaf 노드에만 존재한다.
- add, delete 연산 모두 leaf 노드에서만 이루어진다.
또한, leaf 노드는 서로 연결되어 있어서 임의 접근이나 순차 접근 모두 성능이 우수하다.

Binary Search Tree(이진 탐색 트리)

✨ 이진 탐색 트리의 목적은?

이진 탐색 + 연결 리스트
이진 탐색
- 탐색에 소요되는 시간 복잡도는 O(logN)
- 하지만 삽입, 삭제가 불가능.
연결 리스트
- 삽입, 삭제의 시간 복잡도는 O(1)
- 하지만 탐색하는 시간 복잡도는 O(N)
이 두 가지를 합하여 장점을 모두 얻기 위해 고안된 것이 이진 탐색 트리
즉, 효율적인 탐색 능력을 가지고 자료의 삽입, 삭제도 가능하게 만드는 것이다.

✨ 특징

이진 트리의 일종으로 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다.
이진 탐색 트리의 노드에 저장된 키는 유일하다.
1. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.
2. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.
3. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.
탐색의 시간 복잡도는 O(logN)이다. 최악의 경우, 편향 트리가 되어 O(N)이 될 수도 있다.
이진 탐색 트리의 순회는 중위 순회(in order) 방식이다.(왼쪽 - 루트 - 오른쪽)
중위 순회로 정렬된 순서를 읽을 수 있다.
중복된 노드가 없어야 한다.

중복이 없어야 하는 이유는??

검색을 목적으로 하는 자료구조인데, 굳이 중복이 많은 경우에 이 트리를 사용해 검색 속도를 느리게 할 필요가 없다. 트리에 삽입하는 것보다 노드에 count를 가지게 하여 처리하는 것이 훨씬 효율적이다.

✨ BST 핵심 연산

검색
삽입
삭제
트리 생성
트리 삭제

✨ 시간 복잡도

균등 트리 : 노드 개수가 N개일 때, O(logN)
편향 트리 : 노드 개수가 N개일 때, O(N)

삽입, 검색, 삭제 시간 복잡도는 트리의 Depth에 비례.

✨ 삭제의 3가지 case

자식이 없는 단말 노드일 때 -> 그냥 삭제
자식이 1개인 노드일 때 -> 지워진 노드에 자식을 올리기
자식이 2개인 노드일 때 -> 오른쪽 자식 노드에서 가장 작은 값 or 왼쪽 자식 노드에서 가장 큰 값 올리기

편향된 트리(정렬된 상태 값을 트리로 만들면 한쪽으로 뻗음)는 시간 복잡도가 O(N) 이므로 트리를 사용할 이유가 사라진다. 이를 바로 잡도록 도와주고 개선된 트리는 AVL Tree, RedBlack Tree가 있다.

✨ 이진 트리의 순회 방법

전위 순회(Pre Order) : 루트 -> 왼쪽 -> 오른쪽
중위 순회(In Order) : 왼쪽 -> 루트 -> 오른쪽
후위 순회(Post Order) : 왼쪽 -> 오른쪽 -> 루트

Trie (트라이)

✨ Trie 자료구조란?

일반 트리 자료구조 중 하나로, Digital Tree, Radix Tree, Prefix Tree라고도 불린다.
텍스트 자동 완성 기능과 같이 문자열을 저장하고 탐색하는데 유용한 자료구조이다.

✨ Trie 자료구조의 형태는?

각 노드는 <Key, Value> 맵을 가지고 있다. Key는 하나의 알파벳이 되고, Value는 그 Key에 해당하는 자식 노드가 된다.
다음은 DEV, DEAR, PIE, POP, POW라는 단어가 들어있는 Trie 자료구조를 도식화한 것이다. 휴대폰 전화번호부에서 검색을 하거나 사전에서 단어를 찾는 것과 같다.
예를 들어, 아래 그림에서 'DEV'라는 문자열을 찾으려면 루트 노드에서부터 순차적으로 [D] -> [E] -> [V] 를 탐색한다.
그림에서 볼 수 있듯이 루트 노드는 특정 문자를 의미하지 않고, 자식 노드만 가지고 있다.
유의할 점은 '부모 노드'나 '자신이 어떤 알파벳(Key)에 해당하는 노드(Value)'인지를 가지고 있는게 아니라는 점입니다.
즉, 루트 노드는 [D], [P]라고 하는 알파벳을 Key로 하는 자식 노드들을 가지고 있고, [D]는 [E]를 Key로 하는 자식 노드, [P]는 [I]와 [O]를 Key로 하는 자식 노드들을 가지고 있는 것이다.
또 루트 노드를 제외한 노드의 자손들은 해당 노드와 공통 접두어를 가진다는 특징이 있다. 즉, 'DE' 노드의 자손인 'DEAR'와 'DEV'는 'DE-'를 공통 접두어로 가지며, 'P'의 자손인 'POW'와 'PIE'는 'P-'를 공통 접두어로 가진다.

✨ Trie 자료구조의 특징

정렬된 트리 구조이다.(데이터에 따라 이진트리일 때도 있다.)
Trie는 자식 노드를 Map<Key, Value> 형태로 가지고 있다.
루트 노드를 제외한 노드의 자손들은 해당 노드와 공통 접두어를 가진다.
루트 노드는 빈 문자와 연관있다.(특정 문자가 할당되어 있지 않다.)

Red Black Tree

RBT(Red-Black Tree)는 BST 를 기반으로하는 트리 형식의 자료구조이다. 결론부터 말하자면 Red-Black Tree 에 데이터를 저장하게되면 Search, Insert, Delete 에 O(log n)의 시간 복잡도가 소요된다. 동일한 노드의 개수일 때, depth 를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어이다. 동일한 노드의 개수일 때, depth 가 최소가 되는 경우는 tree 가 complete binary tree 인 경우이다.

✨ Red-Black Tree 의 정의

Red-Black Tree 는 다음의 성질들을 만족하는 BST 이다.

각 노드는 Red or Black이라는 색깔을 갖는다.
Root node 의 색깔은 Black이다.
각 leaf node 는 black이다.
어떤 노드의 색깔이 red라면 두 개의 children 의 색깔은 모두 black 이다.
각 노드에 대해서 노드로부터 descendant leaves 까지의 단순 경로는 모두 같은 수의 black nodes 들을 포함하고 있다. 이를 해당 노드의 Black-Height라고 한다. cf) Black-Height: 노드 x 로부터 노드 x 를 포함하지 않은 leaf node 까지의 simple path 상에 있는 black nodes 들의 개수

✨ Red-Black Tree 의 특징

Binary Search Tree 이므로 BST 의 특징을 모두 갖는다.
Root node 부터 leaf node 까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2 보다 크지 않다. 이러한 상태를 balanced 상태라고 한다.
노드의 child 가 없을 경우 child 를 가리키는 포인터는 NIL 값을 저장한다. 이러한 NIL 들을 leaf node 로 간주한다.

RBT 는 BST 의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어진 자료구조이다. 이를 어떻게 해결한 것인가?

✨ 삽입

우선 BST 의 특성을 유지하면서 노드를 삽입을 한다. 그리고 삽입된 노드의 색깔을 RED 로 지정한다. Red 로 지정하는 이유는 Black-Height 변경을 최소화하기 위함이다. 삽입 결과 RBT 의 특성 위배(violation)시 노드의 색깔을 조정하고, Black-Height 가 위배되었다면 rotation 을 통해 height 를 조정한다. 이러한 과정을 통해 RBT 의 동일한 height 에 존재하는 internal node 들의 Black-height 가 같아지게 되고 최소 경로와 최대 경로의 크기 비율이 2 미만으로 유지된다.

✨ 삭제

삭제도 삽입과 마찬가지로 BST 의 특성을 유지하면서 해당 노드를 삭제한다. 삭제될 노드의 child 의 개수에 따라 rotation 방법이 달라지게 된다. 그리고 만약 지워진 노드의 색깔이 Black 이라면 Black-Height 가 1 감소한 경로에 black node 가 1 개 추가되도록 rotation 하고 노드의 색깔을 조정한다. 지워진 노드의 색깔이 red 라면 Violation 이 발생하지 않으므로 RBT 가 그대로 유지된다.

Java Collection 에서 TreeMap 도 내부적으로 RBT 로 이루어져 있고, HashMap 에서의 Separate Chaining에서도 사용된다. 그만큼 효율이 좋고 중요한 자료구조이다.

Heap

힙은 자료구조의 일종으로 우선 순위 큐를 위해서 만들어졌다.

우선 순위 큐 : 우선순위의 개념을 큐에 도입한 자료구조.
- 데이터들이 우선순위를 가지고 있으며, 우선순위가 높은 데이터가 큐에서 먼저 빠져 나간다.
언제 사용?
- 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산.
- 우선 순위 큐는 배열, 연결 리스트, 힙으로 구현한다. (힙으로 구현하는 게 가장 효율적이다.)
시간 복잡도
- 삽입 : O(logN)
- 삭제 : O(logN)
스택 : LIFO, 큐 : FIFO

✨ 개념

Tree의 형식을 취하고 있으며 Tree 중에서도 배열을 기반으로 한 (Complete Binary Tree)완전 이진 트리이다.
최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리이다.
배열에 트리의 값을 넣어줄 때는 0번째는 건너뛰고 1번째부터 루트 노드가 시작된다. 이유는 노드의 고유 번호와 index를 일치시켜 혼동을 줄이기 위함이다.
중복된 값을 허용. (이진 탐색 트리는 중복 값을 허용하지 않음.)
힙의 종류로는 최대힙과 최소힙이 존재한다.
- 최대힙 : 각 노드의 값이 자식 노드의 값보다 크거나 같은 Complete Binary Tree를 말한다.
- 최소힙은 최대힙의 반대이다.
- 최대힙에서는 Root Node에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 시간 복잡도는 O(1)이다.
- Complete Binary Tree이기 때문에 배열을 이용해 관리할 수 있으며, 인덱스를 통한 Random Access가 가능하다.
- Index 번호는 노드 개수가 n개일 때, i번째 노드에 대하여 왼쪽 자식은 ix2, 오른쪽 자식은 ix2+1가 된다.

✨ 구현

힙을 저장하는 표준적인 자료구조는 배열이다.

구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않고, 1부터 시작한다.

특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.

<부모 노드와 자식 노드의 관계>

왼쪽 자식 index : (부모 index) * 2
오른쪽 자식 index : (부모 index) * 2 + 1
부모 index : (자식 index) / 2

<힙의 삽입>

힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입.
새로운 노드를 검사해서 부모 노드와 교환한다.

[최대 힙 삽입 구현]

부모 노드 : 자신의 인덱스 / 2 이므로 마지막 노드와 비교하여 마지막 노드가 더 크면 위치를 바꿔준다.

<힙의 삭제>

최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제된다. (최대 힙에서 삭제 연산은 최대값 요소를 삭제하는 것이다.)
삭제된 루트 노드에서는 힙의 마지막 노드를 가져온다.
힙을 재구성 한다.

[최대 힙 삭제 구현]

✨ Binary Heap : Heapify

두 개의 서브 트리가 최대힙(최소힙)일 때, root를 포함하는 전체가 heap이 되도록 위치를 조정하는 과정을 말한다.
루트에서 작은 값이 흘러 내려가면서 처리되는 방식으로 진행된다. 최대힙의 경우 root가 child보다 작으면 두 개의 child node 중 값이 큰 노드를 root와 교체하고 교체할 노드가 없을 때까지 반복한다.

Tree Map

Node와 Edge로 이루어진 자료구조
Tree의 특성을 이해하자

트리는 값을 가진 노드(Node)와 이 노드들을 연결해주는 간선(Edge)으로 이루어져있다.

그림 상 데이터 1을 가진 노드가 루트(Root) 노드다.

모든 노드들은 0개 이상의 자식(Child) 노드를 갖고 있으며 보통 부모-자식 관계로 부른다.

아래처럼 가족 관계도를 그릴 때 트리 형식으로 나타내는 경우도 많이 봤을 것이다. 자료구조의 트리도 이 방식을 그대로 구현한 것이다.

트리는 몇 가지 특징이 있다.

트리에는 사이클이 존재할 수 없다. (만약 사이클이 만들어진다면, 그것은 트리가 아니고 그래프다)
모든 노드는 자료형으로 표현이 가능하다.
루트에서 한 노드로 가는 경로는 유일한 경로 뿐이다.
노드의 개수가 N개면, 간선은 N-1개를 가진다.

가장 중요한 것은, 그래프와 트리의 차이가 무엇인가인데, 이는 사이클의 유무로 설명할 수 있다.

트리 순회 방식

트리를 순회하는 방식은 총 4가지가 있다. 위의 그림을 예시로 진행해보자

전위 순회(pre-order)
각 루트(Root)를 순차적으로 먼저 방문하는 방식이다.
(Root → 왼쪽 자식 → 오른쪽 자식)
1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14
중위 순회(in-order)
왼쪽 하위 트리를 방문 후 루트(Root)를 방문하는 방식이다.
(왼쪽 자식 → Root → 오른쪽 자식)
8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 →14 → 7
후위 순회(post-order)
왼쪽 하위 트리부터 하위를 모두 방문 후 루트(Root)를 방문하는 방식이다.
(왼쪽 자식 → 오른쪽 자식 → Root)
8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1
레벨 순회(level-order)
루트(Root)부터 계층 별로 방문하는 방식이다.
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14

Code

public class Tree<T> { 
    private Node<T> root;
    public Tree(T rootData) {
        root = new Node<T>();
        root.data = rootData;
        root.children = new ArrayList<Node<T>>();
    }

    public static class Node<T> {
        private T data;
        private Node<T> parent;
        private List<Node<T>> children;
    }
}

Graph (그래프)

✨ 정점과 간선의 집합, Graph

cf) 트리 또한 그래프이며, 그 중 사이클이 허용되지 않는 그래프를 말한다.

✨그래프 관련 용어 정리

✨Undirected Graph 와 Directed Graph (Digraph)

말 그대로 정점과 간선의 연결관계에 있어서 방향성이 없는 그래프를 Undirected Graph 라 하고, 간선에 방향성이 포함되어 있는 그래프를 Directed Graph 라고 한다.

Directed Graph (Digraph)

V = {1, 2, 3, 4, 5, 6} E = {(1, 4), (2,1), (3, 4), (3, 4), (5, 6)} (u, v) = vertex u에서 vertex v로 가는 edge

Undirected Graph

V = {1, 2, 3, 4, 5, 6} E = {(1, 4), (2,1), (3, 4), (3, 4), (5, 6)} (u, v) = vertex u와 vertex v를 연결하는 edge

✨Degree

Undirected Graph 에서 각 정점(Vertex)에 연결된 Edge 의 개수를 Degree 라 한다. Directed Graph 에서는 간선에 방향성이 존재하기 때문에 Degree 가 두 개로 나뉘게 된다. 각 정점으로부터 나가는 간선의 개수를 Outdegree 라 하고, 들어오는 간선의 개수를 Indegree 라 한다.

✨가중치 그래프(Weight Graph)와 부분 그래프(Sub Graph)

가중치 그래프란 간선에 가중치 정보를 두어서 구성한 그래프를 말한다. 반대의 개념인 비가중치 그래프 즉, 모든 간선의 가중치가 동일한 그래프도 물론 존재한다. 부분 집합과 유사한 개념으로 부분 그래프라는 것이 있다. 부분 그래프는 본래의 그래프의 일부 정점 및 간선으로 이루어진 그래프를 말한다.

✨그래프를 구현하는 두 방법

인접 행렬 (adjacent matrix) : 정방 행렬을 사용하는 방법

해당하는 위치의 value 값을 통해서 vertex 간의 연결 관계를 O(1) 으로 파악할 수 있다. Edge 개수와는 무관하게 V^2 의 Space Complexity 를 갖는다. Dense graph 를 표현할 때 적절할 방법이다.

인접 리스트 (adjacent list) : 연결 리스트를 사용하는 방법

vertex 의 adjacent list 를 확인해봐야 하므로 vertex 간 연결되어있는지 확인하는데 오래 걸린다. Space Complexity 는 O(E + V)이다. Sparse graph 를 표현하는데 적당한 방법이다.

✨ 그래프 탐색

그래프는 정점의 구성 뿐만 아니라 간선의 연결에도 규칙이 존재하지 않기 때문에 탐색이 복잡하다. 따라서 그래프의 모든 정점을 탐색하기 위한 방법은 다음의 두 가지 알고리즘을 기반으로 한다.

✨ 깊이 우선 탐색 (Depth First Search: DFS)

그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다라는 방법을 우선으로 탐색한다. 일단 연결된 정점으로 탐색하는 것이다. 연결할 수 있는 정점이 있을 때까지 계속 연결하다가 더이상 연결되지 않은 정점이 없으면 바로 그 전 단계의 정점으로 돌아가서 연결할 수 있는 정점이 있는지 살펴봐야 할 것이다. 갔던 길을 되돌아 오는 상황이 존재하는 미로찾기처럼 구성하면 되는 것이다. 어떤 자료구조를 사용해야할까? 바로 Stack 이다. Time Complexity : O(V+E) … vertex 개수 + edge 개수

✨너비 우선 탐색 (Breadth First Search: BFS)

그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. Tree 에서의 Level Order Traversal 형식으로 진행되는 것이다. BFS 에서는 자료구조로 Queue 를 사용한다. 연락을 취할 정점의 순서를 기록하기 위한 것이다. 우선, 탐색을 시작하는 정점을 Queue 에 넣는다.(enqueue) 그리고 dequeue 를 하면서 dequeue 하는 정점과 간선으로 연결되어 있는 정점들을 enqueue 한다. 즉 vertex 들을 방문한 순서대로 queue 에 저장하는 방법을 사용하는 것이다. Time Complexity : O(V+E) … vertex 개수 + edge 개수 ! BFS 로 구한 경로는 최단 경로이다.

✨ Minimum Spanning Tree

그래프 G 의 spanning tree 중 edge weight 의 합이 최소인 spanning tree를 말한다. 여기서 말하는 spanning tree란 그래프 G 의 모든 vertex 가 cycle 이 없이 연결된 형태를 말한다.

✨ Kruskal Algorithm

초기화 작업으로 edge 없이 vertex 들만으로 그래프를 구성한다. 그리고 weight 가 제일 작은 edge 부터 검토한다. 그러기 위해선 Edge Set 을 non-decreasing 으로 sorting 해야 한다. 그리고 가장 작은 weight 에 해당하는 edge 를 추가하는데 추가할 때 그래프에 cycle 이 생기지 않는 경우에만 추가한다. spanning tree 가 완성되면 모든 vertex 들이 연결된 상태로 종료가 되고 완성될 수 없는 그래프에 대해서는 모든 edge 에 대해 판단이 이루어지면 종료된다. Kruskal Algorithm의 세부 동작과정 Kruskal Algorithm 관련 Code

어떻게 cycle 생성 여부를 판단하는가?

Graph 의 각 vertex 에 set-id라는 것을 추가적으로 부여한다. 그리고 초기화 과정에서 모두 1~n 까지의 값으로 각각의 vertex 들을 초기화 한다. 여기서 0 은 어떠한 edge 와도 연결되지 않았음을 의미하게 된다. 그리고 연결할 때마다 set-id를 하나로 통일시키는데, 값이 동일한 set-id 개수가 많은 set-id 값으로 통일시킨다.

Time Complexity

Edge 의 weight 를 기준으로 sorting - O(E log E)
cycle 생성 여부를 검사하고 set-id 를 통일 - O(E + V log V) => 전체 시간 복잡도 : O(E log E)

✨ Prim Algorithm

초기화 과정에서 한 개의 vertex 로 이루어진 초기 그래프 A 를 구성한다. 그리고나서 그래프 A 내부에 있는 vertex 로부터 외부에 있는 vertex 사이의 edge 를 연결하는데 그 중 가장 작은 weight 의 edge 를 통해 연결되는 vertex 를 추가한다. 어떤 vertex 건 간에 상관없이 edge 의 weight 를 기준으로 연결하는 것이다. 이렇게 연결된 vertex 는 그래프 A 에 포함된다. 위 과정을 반복하고 모든 vertex 들이 연결되면 종료한다.

Time Complexity

=> 전체 시간 복잡도 : O(E log V)

Hash (해시)

Hash Or HashTable은 내부적으로 배열을 사용해 데이터를 저장한다.
해시 알고리즘을 이용해 고유한 인덱스를 얻는다.
인덱스를 이용하여 빠른 검색 속도를 갖는다.
해시란 다양한 길이를 가진 데이터를 고정된 길이의 데이터로 매핑한 값을 말한다.

✨ 해시 함수

데이터를 효율적으로 관리하기 위해, 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 해시 코드, 해시라고 한다.

✨ 해시 테이블

키와 값을 매핑해둔 데이터 구조이다. 해시 함수로 얻은 해시를 키로 활용하여 index로 사용하고 해당 index에 데이터를 저장하여 효율적인 검색을 위해 사용된다.
동기화를 지원한다.
key, value에 널 값을 허용하지 않는다.

Lee -> 해시 함수 -> 5 Koo -> 해시 함수 -> 2 Kim -> 해시 함수 -> 1 ... ... Choi -> 해시 함수 -> 5 // Lee와 해싱값 충돌.

결국 데이터가 많아지면, 다른 데이터가 같은 해시 값을 가지게 되어 충돌이 발생하게 된다.

해시 테이블의 근본적인 문제는 결국 index의 충돌이다. 해시는 원래 데이터가 같으면 해시값도 항상 같다. 그러나 서로 다른 데이터 또한 동일한 해시값을 가질 수 있기 때문에 해시 충돌이 발생한다.

Collision 현상.

그럼에도 해시 테이블을 쓰는 이유?

적은 자원으로 많은 데이터를 효율적으로 관리하기 위함이다.
하드 디스크나 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해진다.

언제나 동일한 해시 값을 리턴, index를 알면 빠른 검색이 가능해진다.
해시 테이블의 시간 복잡도 : O(1) [이진 탐색 트리는 O(logN)]

✨ 충돌 해결 방법

Separate Chaining

Key에 대한 index가 가리키는 자료구조를 LinkedList를 이용하는 방식이다.
index로 인해서 충돌이 발생하면 그 index가 가리키고 있는 LinkedList에 노드를 추가한다.
데이터를 검색할 때, 선형 탐색을 하기 때문에 느리다는 단점이 있다.
- 시간 복잡도 : O(N)
LinkedList 대신 트리를 이용하면 성능을 개선시킬 수 있다.
JDK 1.8의 경우 index에 노드가 8개 이하인 경우에는 LinkedList를 사용하고 8개를 넘어갈 경우에는 트리 구조로 데이터 저장 구조를 바꾸도록 설계되어 있다.

Open Addressing

해시 충돌이 발생하면 해시 함수로 얻은 주소가 아닌 다른 주소 공간에 데이터를 저장하는 방식이다. (해당 키 값에 데이터가 저장되어 있다면 다음 주소에 저장.)
선형 탐사(Linear Probing)
- 현재 주소에서 고정 크기(ex.1)만큼 다음 주소로 이동하여 데이터를 저장한다.
제곱 탐사(Quadratic Probing)
- 고정 크기만큼 이동하는 것이 아닌 이동 크기가 제곱수로 늘어나는 방식이다. (1,4,9,16...)
이중 해싱(Double Hashing)
- 해시 충돌 시 다른 해시 함수를 한번 더 적용하는 방식이다.
재해싱(Rehashing)
- 해시 테이블의 크기를 늘리고, 늘어난 해시 테이블의 크기에 맞추어 모든 데이터를 다시 해싱하는 방식이다.

Open Addressing 방식은 삭제 처리시에 문제가 발생할 수 있다.

데이터 A를 저장하고 데이터 B를 저장할 때 충돌(A와 같은 값)이 발생한다고 가정하자.

이때, 데이터 A가 삭제될 경우 찾으려고 하는 index를 찾기 전에 데이터가 삭제되어서 검색을 멈추기 때문에 데이터 B를 조회할 수 없게 된다.

이러한 문제점을 해결하기 위해 데이터를 삭제한 후에 더미 노드를 삽입한다. 실제로 값을 가지진 않지만 검색 시 다음 index까지 연결하는 역할을 한다. 데이터 삭제가 빈번하여 더미 노드가 증가한 경우, 조회할 데이터가 존재하지 않음에도 불구하고 더미 노드 때문에 검색을 수행하므로 더미 노드가 일정 갯수가 넘어가면 해시 테이블을 리빌딩해야 한다.

✨ HashTable ve HashMap

HashMap : Map 인터페이스를 구현하기 위해 HashTable을 사용한 클래스로 key와 value에 Null이 허용된다. 동기화를 지원하지 않는다.
HashTable : HashMap보다 속도는 느리지만, 동기화를 지원하며 key와 value에 null이 허용되지 않는다.

읽어보면 좋은 글

PreviousComputer Architecture NextAlgorithms

Last updated 2 months ago