번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료 구조. 일반적으로 배열에는 같은 종류의 데이터들이 순차적으로 저장되어, 값의 번호가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 됨. 의 빠른 Access가 가능함.
| Lang | Material |
|---|---|
 |
1차원 배열의 주요 메서드와 특징: List |
|
다차원(2차원 이상) 배열의 생성 및 사용: List |
|
[외부 링크] Python, Memory, and Objects: mutable object, immutable object, interning 개념 설명 잘되어있음. |
|
[외부 링크] assignment("=") vs shallow copy vs deep copy |
|
배열 내 데이터의 탐색: 순차탐색 |
|
배열 내 데이터의 탐색: 이진탐색 |
|
Python Built-in List 자료형의 Operation 별 시간복잡도 정리 |
연결 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조. 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 됨.
연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는
의 시간이 걸리는 단점도 갖고 있다.
| Lang | Material |
|---|---|
|
단일 연결 리스트 구현 |
|
이중 연결 리스트 구현 |
|
원형 연결 리스트 구현 |
|
Straight Traversal |
|
Reverse Traversal |
Last in First Out(LIFO) 구조의 자료형. 원소 삽입 삭제의 시간복잡도가 으로 매우 빠름. 하지만 이론상 스택의 top을 제외한 나머지 스택 내 데이터의 탐색 시 원소를 하나씩 꺼내어 옮겨 담으면서 수행해야하는 단점이 있음.
💡 언제 사용할까?
재귀 알고리즘이나 백트래킹이 필요한 작업에서 활용하기 좋음.
| Lang | Material |
|---|---|
|
List를 활용한 구현 |
|
deque 모듈 사용 |
|
괄호 검사 |
|
역순 문자열 만들기 |
|
후위 표기법으로의 변환 |
First in First Out(FIFO) 구조의 자료형. 원소 삽입 삭제의 시간복잡도가
으로 매우 빠름.
💡 언제 사용할까?
-
데이터를 입력된 순서대로 처리하는 경우
-
BFS 구현 시
| Lang | Material |
|---|---|
|
List를 활용한 구현 |
|
collections.deque 모듈 사용 방법 및 Operation 별 Time Complexity 정리 |
|
선형 큐 구현 |
|
순환 큐 구현 |
|
콜센터 대기 순서 |
|
프로세스 관리 |
|
BFS 문제 |
계층적 관계(Hierarchical Relationship)을 표현하는 비선형 자료구조. 파일시스템과 같이 큰 데이터를 처리하는 소프트웨어들은 대부분 빠른 탐색을 위해, 데이터를 트리 자료구조 형태로 저장하여, 이진 탐색과 같은 탐색 기법을 활용함. 트리 구현을 위해서는 회로 Cycle이 존재하지 않아야 함.
이번 챕터에서는 Tree 자료구조의 기초인 Binary Tree, Perfect Binary Tree, Perfect Binary Tree, Complete Binary Tree, Binary Search Tree(BST)에 대해 알아본다. 더 복잡한 형태의 Tree 자료구조에 대해 궁금하다면 Tree-Advanced 챕터에서 알아보자.
루트 노드를 중심으로 두개의 서브 트리로 나뉘어지고, 나뉘어진 두 서브 트리 또한 모두 이진 트리인 트리의 형태를 이진 트리라고 함. 이처럼 이진 트리는 재귀적으로 정의되기 때문에, 재귀적 정의 과정이 Leaf Node에 도달했을 때에도 정의를 만족하기 위해, 공집합 또한 이진 트리로 포함하여야 함.
배열로 구성된 이진 트리는 노드의 갯수가 n개이고, root가 0이 아닌 1에서 시작할 때, 다음과 같은 특징이 성립함.
| i'th Node | Parent |
|---|---|
| Parent Node | i // 2 |
| Left Child Node | i * 2 |
| Right Child Node | i * 2 + 1 |
💡 i = 4일 때의 예시는 다음과 같다.
| Array Index | 0 | 1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Unused ❌ | Root Node | Parent Node | - | i th Node |
- | - | - | Left Child Node | Right child Node | |
| - | - | i // 2 |
- | i |
- | - | i * 2 |
i * 2 + 1 |
트리의 모든 내부 노드가 두개의 자식 노드를 가지며, 모든 Leaf Node가 동일한 깊이 또는 레벨을 갖는 트리. 다시 말해, 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 꽉 찬 이진 트리를 의미.
부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 채워지는 이진 트리. 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드들이 왼쪽부터 순서대로 채워져 있는 노드의 형태를 의미.
모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리를 의미. (자식 노드의 갯수가 홀수 개가 아니여야 함.)
효율적인 탐색을 위해서는 데이터를 찾는 방법 뿐만 아니라 데이터를 저장하는 방법 또한 중요하게 고려해야함. Binary Search Tree(이진 탐색 트리)는 이진트리의 일종으로, 특정 규칙에 따라 데이터를 저장하고, 이 규칙을 이후 데이터 탐색 시 활용하는 형태의 자료구조.
-
규칙 1. 이진 탐색 트리에서 노드에 저장된 키는 유일해야 함.
-
규칙 2. 부모 노드의 키가 왼쪽 자식 노드의 키보다 커야 함.
-
규칙 3. 부모 노드의 키보다 오른쪽 자식 노드의 키가 커야 함.
-
규칙 4. 특정 노드를 기준으로 왼쪽과 오른쪽의 서브트리 또한 이진 탐색 트리인 조건을 만족해야 함.
💡 이진 탐색 트리의 탐색 연산의 시간복잡도
이진 탐색 트리의 탐색 연산은
의 시간 복잡도를 가짐. 이는 트리의 높이가 하나씩 증가될수록, 추가되는 노드의 수가 두 배씩 증가하기 때문.
이와 같은 이진 탐색 트리는
Skewed Tree(편향 트리)가 될 수 있음. 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생하기 때문. 이 경우, 성능에 영향을 미치게 되며, 탐색의 Worst Case가 되고 시간 복잡도는이 됨.
이처럼 배열보다 많은 메모리를 사용하며 데이터를 저장했지만 탐색에 필요한 시간 복잡도가 같게 되는 비효율적인 상황이 발생함. 이를 해결하기 위해
Rebalancing 기법이 등장함.균형을 잡기 위한 트리 구조의 재조정을 Rebalancing이라 하며, 이 기법을 구현한 트리에는 여러 종류가 존재하는데, 그 중에서 하나가Red-Black Tree.
💡 코딩테스트에서의 이진 탐색 트리 문제
사실 코딩테스트에서는 문제 해결을 위해 필수적으로 이진 탐색 트리 자료구조를 구현해야하는 문제는 출제 빈도가 높지 않음.
이진트리 및 전반적인 트리 구조에서 각가의 노드를 정확히 한 번만, 체계적으로 방문하는 과정을 말함. Tree Traversal 방식은 노드를 방문하는 순서에 따라 다음과 같이 분류됨. 아래의 트리 순회 방식 각각에 대한 설명은 이진 트리를 기준으로 작성되었지만, 다른 트리의 형태에도 일반화가 가능함.
| Tree Traversal | Description |
|---|---|
| in-order(중위 순회) | 왼쪽 자식 노드(L), 내 노드(P), 오른쪽 자식 노드(R) 순서로 방문. |
| pre-order(전위 순회) | 내 노드(P), 왼쪽 자식 노드(L), 오른쪽 자식 노드(R) 순서로 방문. |
| post-order(후위 순회) | 왼쪽 자식 노드(L), 오른쪽 자식 노드(R), 내 노드(P) 순서로 방문. |
| level-order(레벨 순회) | 내 노드(P)를 방문하고, 내 노드로부터 노드의 깊이가 낮은 순서대로 노드를 방문하는 방식.(Depth = [0, 1, 2, ..., N(Depth)]) |
| Lang | Material |
|---|---|
|
Binary Search Tree 구현 |
|
주어진 트리가 이진트리인지 여부를 확인하는 알고리즘 구현 |
해시 테이블은 associative 방식으로 데이터를 저장하는 자료구조이다. 해시 테이블에서 데이터는 각 데이터 값에 고유한 인덱스 값이 있는 배열 형식으로 저장된다. 해시 테이블에서 저장하고자 하는 데이터에 대한 고유한 인덱스 값은 Hashing Algorithm을 이용하여 생성되고, 이 인덱스 값이 배열에 저장한다. 이처럼 각각의 데이터에 대한 인덱스가 존재하기 때문에, 원하는 데이터의 인덱스를 알면, 데이터의 크기와 관계 없이 매우 빠른 속도(average case에 대해 )로 데이터 액세스가 가능하다.
| Operations | Description | Time Complexity |
|---|---|---|
| Search | 해시 테이블에서 요소를 검색. | 일반적으로 |
| Insert | 해시 테이블에 새로운 요소를 추가. | 일반적으로 |
| Delete | 해시 테이블에 저장된 요소를 삭제. | 일반적으로 |
| Basic Terminology | Description |
|---|---|
Hash Function |
데이터의 효율적 관리를 목적으로 임의의 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 함수. |
Hash Key |
Hash Function에 의해 고정된 길이의 데이터로 매핑되는 원본 데이터의 값. |
Hashcode/Hash Value(Index) |
Hash Function에 의해 생성된 고정된 길이의 데이터. |
Hashing |
매핑하는 과정 자체를 의미. |
Hashing Algorithm |
Hashing에 사용되는 알고리즘. |
Hash Table |
Hash Function을 사용하여 Hash Key를 Hash Value로 매핑하고, 이 Hash Value를 index(key)로 하여 데이터를 저장하는 형태의 자료구조. |
Bucket/Slot |
Hash Table에서 데이터가 저장되는 공간. 데이터 저장 위치는 Hash Key에 대응됨. |
Hash Collision |
서로 다른 두 개의 Key를 동일한 Hash Function을 통해 변환하였을 때, 동일한 Hash Value를 갖는 현상. 리얼 월드에서 Hash Table을 활용할 때, Hash Function은 대개 고정된 길이의 Hash Value가 표현 가능한 범위보다 더 많은 Key 값이 사용될 수 있고, 이는 Hash Collision을 야기할 수 있음. |
해시 테이블에서 Hash Function(해시 함수)은 데이터의 고유한 인덱스 값을 생성하고자 할 때 사용된다. 여기서 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 뜻하며, 해시 함수에 의해 반환된 데이터의 고유한 값을 hashcode라고 한다. 이와 같이 해시 테이블은 데이터를 저장할 때 해시 함수에 의해 생성된 hashcode 값을 배열에 저장하기 때문에, 일반적인 경우 access가 가능하다.
이처럼 Hash Table은 배열의 인덱스를 통해 자료를 저장하는 자료구조인데, 왜 데이터의 access/store에 대한 Time Complexity가 균일하게 이 나오는 것이 아니라 average case에 대해서만
이 나오는 것일까? 🤔
이는 서로 다른 두개의 데이터에 대해 해시 함수가 동일한 hashcode를 반환하는 Hash Collision이 발생할 수 있기 때문이다. (해시 테이블에서는 Collision을 해결하고자 access/store 과정에서 해시 충돌을 회피하는 로직이 추가된다.) 이렇게 되면 서로 다른 두개의 데이터가 같은 인덱스로 계산되는 동일한 키 값(hashcode)를 갖기 때문에, 배열 내에 데이터를 저장할 때 해당 인덱스로 접근되는 동일한 위치에 데이터가 저장되야 하는 현상(Collision)이 발생한다. Collision을 조금 더 깊게 이해하기 위해, 해시 테이블보다 단순한 형태인 Direct-address Table을 먼저 한번 살펴보자.
Direct-address Table은 Hash Table과 달리 data의 key를 직접적으로 버킷의 인덱스로 활용하는 자료구조이다. 이 때 Direct-address Table은 해시 테이블의 크기와 동일한 키 갯수를 사용하기 때문에, Collision 문제가 발생하지 않는다는 장점이 있다. 하지만 전체 키 집합(U)에 비해 실제 사용하는 키 집합(K)이 작은 경우, 사용되지 않는 키를 위한 메모리 할당을 해야하기 때문에 메모리 효율성이 크게 떨어지게 된다.
따라서 보통 Direct-address Table을 그대로 사용하기보다는, 해시 테이블의 크기(m)이 실제 사용하는 키의 갯수(n)보다 적은 해시 테이블을 운용한다. 이처럼 해시 테이블의 크기를 실제 사용하는 키보다 적게 운용하기 때문에, 서로 다른 데이터에 대한 Hash Value가 동일하게 산출되는 Collision이 발생하게 되는 것이다. 이 때, Hash Collision이 발생을 정량화하기 위한 지표로, 해시 테이블의 한 버킷에 평균 몇개의 키가 매핑되는가를 나타내는 load factor(적재율)를 활용한다.
Direct-address Table의 load factor는 1 이하이며, load factor가 1 보다 큰 경우 Hash Collision 문제가 발생하게 된다.
앞서 Direct-address Table에서 살펴보았듯이, Hash Function를 무조건 1:1 로 만드는 것보다 Collision 을 최소화하는 방향으로 설계하고, 발생하는 Collision 에 대비해 어떻게 대응할 것인가가 더 중요하다. 1:1 대응이 되도록 만드는 것이 거의 불가능하기도 하지만 그런 hash function를 만들어봤자 그건 array 와 다를바 없고 메모리를 너무 차지하게 된다.
Collision이 많아질 수록 Search 에 필요한 Time Complexity가 에서
에 가까워진다. 어설픈 hash function는 hash 를 hash 답게 사용하지 못하도록 한다.
그렇다면 이러한 Hashmap 자료구조를 설계할 때, Collision을 해결하기 위해 어떤 대응책을 세울 수 있을까? 🤔
일반적으로 Hashmap 자료구조의 Collision을 해결하기 위한 접근 방법은 크게 두 가지로, Collision을 낮추는 방향으로의 접근인 좋은 Hash Function을 사용하는 방법과 Collision이 발생하더라도 이를 적절히 대응하는 접근 방법으로 나눌 수 있다.
먼저, 좋은 Hash Function은 어떤 조건들을 가지고 있을까? 🤔
좋은 Hash Function의 조건은 Simple Uniform Hash를 만드는 것을 말하며, Simple Uniform Hash의 조건은 다음과 같다.(좋은 Hash Function에 대해 더 깊게 알고싶다면 링크 1, 링크 2를 읽어보자.)
1. 버킷 배열의 크기가 m일 때, Hash Value들이 0 ~ m-1 사이의 범위에 해당되는 정수 값으로 균일한(uniform) 확률로 나타나야 함.
2. Hash Function에 의해 생성된 각각의 Hash Value들은 서로 연관성을 가지지 않아야 함.(독립적으로 생성되야 함.)
이를 간단히 말하면, 좋은 Hash Function은 특정 값에 치우치지 않고 해시값을 고르게 생성하는 Hash Function이라고 할 수 있다.
좋은 Hash Function을 지향하는 Hash Function은 정말 다양하지만, 이들 중 가장 대표적인 방법은 Division Method, Multiplication Method, Universal Hashing 3가지 정도가 있다. (이들에 대한 설명은 하단 표의 별도의 문서를 참고하자.)
| Type | Material |
|---|---|
| 📖 | Hashing with Division Method |
| 📖 | Hashing with Multiplication Method |
| 📖 | Hashing with Universal Hashing |
이처럼 Collision을 피하기 위해 좋은 해시 함수를 선택하는 것은 매우 중요하다. 하지만 사실, 해시 함수는 다대일(many-to-one) 대응이기 때문에, 비둘기집 원리(Pigeonhole principle)에 의해 해시 함수값이 충돌하는 입력 값들의 집합이 반드시 존재하게 된다. 하지만 해시 함수를 사용할 때, 대부분 입력 값 집합에 대해 충돌이 적게 나는 해시함수를 사용하기를 원하는데, 수학적으로, 해시 함수에 충돌이 나는 입력 값 집합이 들어오지 않는다고 보장하는 것은 불가능하다.
앞서 말했듯이 해시함수는 many-to-one 대응이기 때문에 collision이 발생하지 않는 것을 항상 보장할 수는 없다. 그렇다면 collision의 발생을 전제하고, 어떻게하면 발생된 collision을 대처할 수 있을까? 🤔
이를 위한 방법은 여러 가지가 있는데, 대표적인 2가지만 꼽자면 해시 테이블의 크기를 고정시키고 저장할 위치를 잘 찾고자 하는 1)Open Addressing 방식과, chaining을 사용해, 해시 테이블의 크기를 유연하게 만드는 2)Separate Chaining 방식이 있다. (각 방식에 대한 자세한 설명은 아래 표 내의 문서에 별도로 정리하였으니 관심있으면 읽어보자.)
| Type | Material |
|---|---|
| 📖 | Open Addressing(개방 주소법) 방식의 개념 및 삽입/삭제/탐색 연산에 대한 시간복잡도 |
| 📖 | Separate Chaining(분리 연결법) 방식의 개념 및 삽입/삭제/탐색 연산에 대한 시간복잡도 |
| Lang | Material |
|---|---|
|
Dictionary 자료형 |
|
[외부 링크] CPython의 Dictionary는 Open Addressing과 Random Probing 방식을 사용함 |
| Lang | Material |
|---|---|
|
인접행렬 구현 |
|
인접 리스트 구현 |
|
간선리스트 구현 |
집합(Set)은 원소(Member)라는 구별되는 객체들이 연관되어 모인 것을 말하며, 서로 다른 연관된 원소들의 순서 없는 모임이다.
| Lang | Material |
|---|---|
|
set 자료형 |
-
https://www.tutorialspoint.com/data_structures_algorithms/index.htm
-
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure
-
동빈북
-
파이썬 알고리즘 인터뷰