우선순위 큐(Priority Queue)

일반적인 큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 이런 큐의 특성과 달리 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 일정한 규칙에 따라 우선순위를 선정하고 우선순위가 가장 높은 데이터가 가장 먼저 나오게 된다. 대표적인 예로는 병원의 응급 환자를 생각할 수 있으며, 은행의 업무를 기다리는 상황과 달리 위급한 우선순위에 따라 먼저 처리된다.

사용하기

  • 우선순위 큐도 Java에서 내부적으로 구현되어 있어 사용이 용이하다.
  • 큐와 동일하게 add(), peek(), poll() 등의 메소드를 사용할 수 있다.

[Code]

1
2
3
4
5
6
7
8
9
10
 public class Sample {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(4);
pq.add(19);
pq.add(2);
pq.add(1);
System.out.println(pq.poll()); // 1이 출력된다.
}
}
  • add() 대신 offer() 메소드를 사용해도 동일한 결과를 얻는다.

우선순위 변경하기

  • 우선순위를 정하는 기준은 Java의 정렬 기준과 동일하다.
  • Java는 기본적으로 낮은 숫자부터 큰 숫자까지 오름차순으로 정렬하게 되는데, 만약 다른 오름차순으로 정렬하고 싶다면 Comparator 클래스나 Comparable 인터페이스를 이용해야 한다.
  • Ex) 객체의 어떤 값에 따라 우선순위를 정해 정렬해야 할때, 오름차순이 아닌 내림차순 정렬을 할때 등등
  • Integer는 Collections.reverseOrder()를 사용해 내림차순 정렬을 할 수 있다.

[Code]

1
2
3
4
5
6
7
8
9
10
11
public class Sample {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.add(4);
pq.add(19);
pq.add(2);
pq.add(1);

System.out.println(pq.poll()); // 19가 출력된다.
}
}

우선순위 큐 예제

  • 고양시에서 강남까지 가는 방법이 있다고 하자.
  • 대중교통, 자가용, 도보, 자전거 총 4가지의 방법이 존재한다.
    • 대중 교통 : 1시간 10분
    • 자가용 : 45분
    • 도보 : 6시간 40분
    • 자전거 : 2시간 5분
  • 시간이 제일 적게 걸리는 순서로 정렬하면 -> 자가용, 대중교통, 자전거, 도보 순이다.
  • 우선순위 큐에 저장한 뒤, 데이터를 추출하면 위의 순서대로 추출된다.
  • 하지만, 큐는 들어간 순으로 나온다.

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package programmers;

import java.util.PriorityQueue;

/**
* created by victory_woo on 2020/05/12
*/
public class Sample {
public static void main(String[] args) {
PriorityQueue<Vehicle> pq = new PriorityQueue<>();
pq.add(new Vehicle("대중교통", 70));
pq.add(new Vehicle("자가용", 45));
pq.add(new Vehicle("오토바이", 45));
pq.add(new Vehicle("도보", 400));
pq.add(new Vehicle("자전거", 125));

while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
}

static class Vehicle implements Comparable<Vehicle> {
private String name;
private int time;

Vehicle(String name, int time) {
this.name = name;
this.time = time;
}

public String getName() {
return name;
}

public int getTime() {
return time;
}

@Override
public String toString() {
return "Vehicle{" +
"name='" + name + '\'' +
", time=" + time +
'}';
}

@Override
public int compareTo(Vehicle that) {
if (this.time == that.time) return this.name.compareTo(that.name);
return this.time - that.time;
}
}
}
// 결과
Vehicle{name='오토바이', time=45}
Vehicle{name='자가용', time=45}
Vehicle{name='대중교통', time=70}
Vehicle{name='자전거', time=125}
Vehicle{name='도보', time=400}
  • Vehicle 클래스를 만들었다. 그리고 자바에서 PriorityQueue를 사용하기 위해서는(객체인 경우) 우선순위 큐에 저장할 객체는 필수적으로 Comparable 인터페이스를 구현해야 한다.
  • compareTo 메소드를 오버라이드 하여 우선순위 조건을 설정하면 PriorityQueue가 우선순위가 높은 객체를 추출하게 된다.
  • 시간이 작은 순서로 정렬해야 하기 때문에 오름차순 정렬을 한다.
  • 다만, 시간이 같은 경우에는 이름의 사전순 정렬을 한다.(오름차순) name이 String이기 때문에 this.name.compareTo(that.name) 을 활용한다.
  • Int 형인 time 간의 연산에서 Integer.compareTo() 를 사용하지 않은 이유는 Integer와 int의 size가 메모리 차이 때문이다. int의 size가 훨씬 작아 연산시 적은 메모리를 사용한다는 점에서 서로의 값을 뺄셈하여 계산했다.
  • 관련 내용은 해당 Repository에 있으니 확인하면 좋을 것 같다.

참고

Comment and share

정점과 간선의 집함, Graph
그래프 관련 용어 정리

정점과 간선의 집함, Graph

그래프란 정점과 간선의 집합을 말한다.
ex) 트리는 그래프. [싸이클이 허용되지 않는 그래프이다.]

그래프 관련 용어 정리

  • V(vertex) : 정점을 의미한다.
  • E(edge) : 간선을 의미한다.
  1. Directed Graph(Digraph)
    말 그대로 정점과 간선의 연결관계에 있어서 방향성이 포함되어 있는 그래프를 말한다.
V = {1,2,3,4,5,6}
E = {(1,4),(2,1),(3,4),(5,6)}
(u,v) = vertex u에서 vertex v로 가는 edge
  1. Undirected Graph
    정점과 간선의 연결관계에 있어서 방향성이 없는 그래프를 말한다.
  1. Degree
    Undirected Graph에서 각 정점(Vertex)에 연결된 Edge의 개수를 Degree라고 한다.
    Directed Graph에서는 간선에 방향성이 존재하기 때문에 Degree가 두 개로 나뉘게 된다.
    각 정점으로부터 나가는 간선의 개수를 Outdegree라고 하고, 들어오는 간선의 개수를 Indegree라고 한다.
  1. 가중치 그래프(Weight Graph)
    가중치 그래프란 간선에 가중치 정보를 두어서 구성한 그래프를 말한다. 반대의 개념인 비가중치 그래프는 모든 간선의 가중치가 동일한 그래프이다.
  1. 부분 그래프(Sub Graph)
    부분 집합과 유사한 개념으로 부분 그래프라는 것이 존재한다.
    부분 그래프는 본래의 그래프의 일부 정점 및 간선으로 이루어진 그래프를 말한다.

그래프를 구현하는 두 방법

[무슨 말일까…?ㅠ^ㅠ]

  1. 인접 행렬(adjacent matrix)
    정방 행렬을 사용하는 방법이다.
    해당하는 위치의 value 값을 통해서 vertex(정점)간의 연결 관계를 O(1)으로 파악할 수 있다.
    Edge 개수와는 무관하게 V^2의 Space Complexity(공간 복잡도)를 갖는다.
    => Dense graph를 표현할 때 적절한 방법이다.

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

[어려운 용어가 많이 나온다… 더 공부하자!!]

그래프 탐색

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

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

2. 너비 우선 탐색(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로 구한 경로는 최단 경로이다.

참고

Comment and share

HastTable

Hash(또는 HashMap)은 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 인덱스를 이용한 빠른 검색 속도를 갖는다. 특정한 값을 searching하는데 데이터 고유의 인덱스로 접근하게 되므로 average case에 대하여 시간 복잡도가 O(1)이 되는 것이다.
[항상 O(1)이 아니고 average case에 대해서 O(1)인 것은 collision 때문이다.]

그리고 데이터의 삽입과 삭제 시 기존 데이터를 밀어내거나 다시 채우는 작업이 필요없도록 특별한 알고리즘을 이용하여 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 삽입 시 다른 데이터의 사이에 끼어들거나 삭제 시 다른 데이터로 채울 필요가 없으므로 추가적인 데이터의 이동이 없다.

'특별한 알고리즘’이라는 것을 통해서 고유한 인덱스 값을 설정하는 것이 중요한 포인트이다.
앞서 언급한 특별한 알고리즘을 해시 메소드 또는 해시 함수라고 하고 이 메소드에 의해 반환되는 데이터의 고유한 숫자 값hashCode라고 한다.
Java에서는 Object 클래스의 _hashCode()_라는 메소드를 이용하여 모든 객체의 hashcode 값을 쉽게 구할 수 있다.

hash 메소드를 구현하는 가장 간단한 방법은 나머지 연산자를 이용하는 것이다. 저장할 데이터의 값을 저장할 hash table의 크기로 나누고 나머지 연산 결과를 데이터의 인덱스로 사용하는 것이다. 하지만 이렇게 하면 문제점이 발생한다.

만약 3의 배수로 이루어진 데이터 9개를 저장한다고 가정해보자.
저장하려는 데이터 : 3,6,9,12,15,18,21,24,27
hashcode 값 계산
3 % 9 == 3
6 % 9 == 6
9 % 9 == 0
12 % 9 == 3
15 % 9 == 6
18 % 9 == 0
21 % 9 == 3
24 % 9 == 6
27 % 9 == 3

계산 결과 hashcode 값이 0,3,6으로 집중되고 있다. 이렇게 되면 같은 index로 접근하게 되는 value가 많아져 데이터를 저장할 수 없게 되는 충돌 현상이 발생한다. 이를 Collision이라고 한다.

이런 충돌을 최소화 하기 위한 가장 간단한 방법은 나머지 연산의 값이 중복되지 않도록 테이블의 크기를 소수(Prime number)로 만드는 것이다. 위와 동일한 입장일 경우, 저장하려는 데이터의 크기가 9이므로 9보다 큰 소수인 11로 나머지 연산을 해보자.

hashcode 값 계산
3 % 11 == 3
6 % 11 == 6
9 % 11 == 9
12 % 11 == 1
15 % 11 == 4
18 % 11 == 7
21 % 11 == 10
24 % 11 == 2
27 % 11 == 5

중복되는 값이 깨끗하게 사라진 것을 확인할 수 있다. 하지만 이 방법으로 모든 것이 해결된 것일까?? 위의 과정에서 데이터의 성질이 달라져 다른 값이 들어올 수 있게 된 경우는 어떨까?

예를 들어 26이라는 데이터를 추가적으로 저장해야 한다면 데이터의 크기는 10이 되고 10보다 큰 소수는 11로 나머지 연산자 방법을 수행해준다.

26 % 11 == 4

결과를 확인해보니 다시 중복이 발생하였다. 바로 Collision이 발생한 것이다. Hash Table의 크기를 소수로 만드는 것은 충돌을 줄일 수는 있지만 원천적으로 해결해주지는 못한다.

충돌이 많아질수록 Searching에 필요한 시간 복잡도가 O(1)에서 O(n)에 가까워진다.
어설픈 해쉬 함수는 해시를 해시답게 사용하지 못하도록 한다. 좋은 해쉬 함수를 선택하는 것은 해쉬 테이블의 성능 향상에 필수적인 것이다.

두 개의 키가 같은 인덱스로 hashing(hash 함수를 통해 계산됨을 의미)되면 같은 곳에 저장할 수 없게 된다.(Collision)
따라서 해싱된 인덱스에 이미 다른 값이 들어가 있다면 데이터를 저장할 다른 위치를 찾은 뒤에야 저장할 수 있는 것이다. 따라서 충돌 해결은 필수적이며 그 방법들에 대해 알아보고자 한다.

기본적인 두 가지 방법을 알아보자. 해시 충돌을 해결하기 위한 다양한 자료가 있지만, 다음 두 가지 방법을 응용한 방법들이다.

Open Address 방식(개방 주소법)

해시 충돌이 발생하면 즉 삽입하려는 해시 버킷이 이미 사용 중인 경우, 다른 해시 버킷에 해당 자료를 삽입하는 방식이다.

  • 버킷(bucket)이란 바구니와 같은 개념으로 데이터를 저장하기 위한 공간이라고 생각하면 된다.

공개 주소 방식이라고도 불리는 이 알고리즘은 Collision(충돌)이 발생하면 데이터를 저장할 장소. 즉 다른 해시 버킷을 찾아 헤맨다. 이 과정에서도 여러 방법들이 존재하는데 다음 3가지에 대해 간단하게 알아보자.

  1. Linear Probing
    순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 계속 진행된다. Worst case의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있다.

  2. Quadratic probing
    2차 함수를 이용해 탐색할 위치를 찾는다.

  3. Double hashing probing

하나의 해쉬 함수에서 충돌이 발생하면 2차 해쉬 함수를 이용해 새로운 주소를 할당한다. 위 두가지 방법에 비해 많은 연산량을 요구한다.

Seperate Chaining 방식(분리 연결법)

참고로 Java 7에서는 Seperate Chaining 방식을 사용하여 HashMap을 구현하고 있다.

Why?

HashMap의 특성상 remove() 메소드가 빈번하게 일어날 수 있는데 데이터를 삭제할 때 OpenAddress 방식은 처리가 효율적이기 어렵다. 또한 저장된 Key-value 쌍의 개수가 일정 개수 이상 많아지면 보통 Seperate Chaining 방식에 비해 Open Address 방식이 느리다.

연결 리스트를 사용하는 방식(LinkedList)

각각의 버킷들을 연결리스트(Linked List)로 만들어 Collision이 발생하면 해당 버킷의 list에 추가하는 방식이다. 연결 리스트의 특징을 그대로 이어받아 삭제 또는 삽입 간단하다. 하지만 단점도 그대로 물려받아 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 된다.

일반적으로 Open Address 방법은 Seperate Chaining 방식보다 느리다. Open Address의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다. 반면에 Seperate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case에 가까워지는 것을 줄일 수 있다.

보조 해시 함수에 대한 글

Tree를 사용하는 방식(Red-Black-Tree)

기본적인 알고리즘은 Seperate Chaining 방식과 동일하며 연결 리스트 대신 트리를 사용하는 방식이다. 여기서 연결 리스트를 사용할 것인가와 트리를 사용할 것인가에 대한 기준은 하나의 버킷에 할당된 Key-Value 쌍의 개수이다.

트리는 기본적으로 메모리 사용량이 많고 데이터 개수가 적을 때 Worst Case를 살펴보면 트리와 연결 리스트의 성능 상의 차이가 거의 없다. 따라서 메모리 측면을 봤을 때 데이터 개수가 적을 때는 연결 리스트를 사용한다.

데이터가 적다는 것은 얼마나 적다는 것을 의미할까??

앞에서 언급한 것처럼 기준은 하나의 버킷에 할당되는 Key-Value 쌍의 개수이다. 이 Key-Value 쌍의 개수가 6개, 8개를 기준으로 결정한다.

오잉…? 왜 기준이 2개인가?? 이는 아래에서 설명하겠다.

결론부터 말하자면 연결 리스트의 기준과 트리의 기준을 6과 8로 잡은 것은 변경하는데 소요되는 비용을 줄이기 위함이다.
한 가지 상황을 가정해보자.
해시 버킷에 6개의 Key-Value 쌍이 들어있다. 그리고 하나의 값이 추가되었다. 만약 기준이 6과 7이라면 자료 구조를 연결 리스트에서 트리로 변경해야 한다. 그러다가 바로 하나의 값이 삭제된다면 다시 트리에서 연결 리스트로 자료구조를 변경해야 한다.

각각 자료구조로 넘어가는 기준이 1이라면 Switching 할 때 생기는 비용이 너무 많이 필요하게 되는 것이다. 그래서 2라는 여유를 남겨두고 기준을 잡아준 것이다.
따라서 데이터의 개수가 6개 -> 7개로 증가했을 때는 연결 리스트의 자료구조를 취하고 있을 것이고
8개 -> 7개로 감소했을 때는 트리의 자료 구조를 취하고 있을 것이다.

  • 참고로 Java 8을 구현하는데 사용하는 트리는 RBT이다.

해시 버킷 동적 확장(Resize)

해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생할 수도 있다. 그래서 HashMap은 Key-Value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두배로 늘린다. 이렇게 늘리면 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다.

일정 개수 이상??

해시 버킷 크기를 두 배로 확장하는 임계점은 현재 데이터 개수가 해시 버킷의 개수의 75%가 될 때이다. 0.75라는 숫자는 load factor로 HashMap의 생성자에서 지정할 수도 있다.

참고

Comment and share

RBT(Red-Black Tree)는 BST를 기반으로 하는 트리 형식의 자료구조이다.

먼저 레드 블랙 트리를 알아보기 전에 BST가 무엇인지 한번 더 알고 넘어가자.

BST(Binary Search Tree)는 이진 탐색 트리이다.
효율적인 탐색을 위해 어떻게 찾을까만 고민해서는 안된다. 그보다는 효율적인 탐색을 위한 저장 방법이 무엇일까를 고민해야 한다. 이진 탐색 트리는 이진 트리의 일종이다. 단 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다.

  • 규칙1 : 이진 탐색 트리의 노드에 저장된 키는 유일하다.
  • 규칙2 : 루트 노드의 키가 왼쪽 서브트리를 구성하는 어떠한 노드의 키보다 크다.
  • 규칙3 : 루트 노드의 키가 오른쪽 서브트리를 구성하는 어떠한 노드의 키보다 작다.
  • 규칙4 : 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

Red Black Tree

결론부터 말하자면 Red-Black-Tree에 데이터를 저장하게 되면 Search, Insert, Delete에 O(log n)의 시간 복잡도가 소요된다. 동일한 노드의 개수일 때, depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어이다. 동일한 노드의 개수일 때, depth가 최소가 되는 경우는 tree가 Complete Binary Tree인 경우이다.

1. Red-Black-Tree의 정의

Red-Black-Tree를 앞으로 RBT라고 부르도록 하겠다.
RBT는 다음의 성질을 만족하는 BST이다.

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

[무슨 말일까…? 어렵다!]

2. RBT의 특징

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

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

삽입

우선 BST의 특성을 유지하면서 노드를 삽입한다. 그리고 삽입된 노드의 색깔을 Red로 지정한다. Red로 지정하는 이유는 Black-Height의 변경을 최소화하기 위함이다. 삽입 결과 RBT의 특성 위배시 노드의 색깔을 조정하고 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가 그대로 유지된다.

Comment and share

Heap

Heap 자료구조는 일종의 Tree의 형식을 하고 있으며, Tree 중에서도 배열에 기반한 Complete Binary Tree(완전 이진 트리)이다.

배열에 트리의 값을 넣어줄 때, 0번째는 건너뛰고 1부터 루트노드가 시작된다. 이는 노드의 고유번호 값과 배열의 index를 일치시켜 혼동을 줄이기 위함이다.

힙에는 최소 힙(min heap)과 최대 힙(max heap) 두 종류가 있다.

Max Heap이란, 각 노드의 값이 해당 children의 값보다 크거나 같은 Complete Binary Tree(완전 이진 트리)를 말한다.[Min Heap은 그 반대.]

Max Heap에서는 Root node에 있는 값이 제일 크므로 최대값을 찾는데 소요되는 연산의 시간 복잡도는 O(1)이다. 그리고 Complete Binary Tree이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다.
(즉, 배열의 장점 중 하나인 Random Access가 가능하다)
Min Heap에서는 최소값을 찾는데 소요되는 연산의 시간 복잡도가 O(1)이다.

Heap의 구조를 계속 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요하다. 여기서 Heap은 맨 마지막 노드를 루트 노드로 대체시킨 후, 다시 Heapify 과정을 거쳐 Heap 구조를 유지한다. 이런 경우 결국에는 O(log n)의 시간 복잡도로 최대값 또는 최소값에 접근할 수 있다.

[Heap 구조를 유지시키는 더 자세한 내용을 추가 예정.]

Comment and share

Tree

트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다.
트리는 계층적 관계를 표현하는 자료구조이며, 표현에 집중한다.
무엇인가를 저장하고 꺼내야 한다는 사고를 벗어나 트리라는 자료구조를 보자.

트리를 구성하고 있는 구성요소들

  • Node(노드) : 트리를 구성하고 있는 각각의 요소를 의미
  • Edge(간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미
  • Root Node(루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미
  • Terminal Node(=leaf Noed, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미
  • Internal Node(내부 노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.

트리의 속성 중 가장 중요한 것은 루트 노드를 제외한 모든 노드는 단 하나의 부모 노드만을 가진다는 것이다. 이 속성 때문에 트리는 다음의 성질을 만족한다.

  • 임의의 노드에서 다른 노드로 가는 경로(path)는 유일하다.
  • 회로(cycle)가 존재하지 않는다.
  • 모든 노드는 서로 연결되어 있다.
  • 엣지를 하나 자르면 트리가 두 개로 분리된다.
  • 엣지의 수(E) = 노드의 수(V) - 1

Binary Tree(이진 트리)

루트 노드를 중심으로 두 개의 서브 트리(큰 트리에 속하는 작은 트리)로 나누어진다. 또한 나뉘어진 두 서브 트리 모두 이진 트리어야 한다.

즉, 각 노드가 자식을 최대 2명을 가지는 트리를 의미한다. 재귀적인 정의라 맞는듯 하면서도 이해가 쉽지 않다. 덧붙이자면 공집합도 이진 트리로 포함시켜야 한다. 그래야 재귀적으로 조건을 확인해갔을 때, leaf Node에 다 달았을 때 정의가 만족되기 때문이다.

트리에서는 각 층 별로 숫자를 매겨서 이를 트리의 Level이라고 한다. 루트 노드부터 시작하고 루트 노드의 Level은 1이다. 그리고 트리의 최고 Level을 가리켜 해당 트리의 height(높이)라고 한다.

  1. 완전 이진 트리(Complete Binary Tree)

위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진 트리라고 한다.

  1. 포화 이진 트리(Full Binary Tree)

모든 레벨에서 노드들이 꽉 채워진 이진트리를 말한다.(= 잎새 노드를 제외한 모든 노드가 자식 노드를 2개 가진다.)

포화 이진 트리의 노드 수가 n개라면 잎새노드의 수는 n/2를 올림한 숫자가 된다. 그리고 노드의 개수는 2^(k+1) - 1이 된다.

  1. 편향 이진 트리(skewed binary tree)

모든 노드가 부모의 왼쪽 자식이기 때문에 왼편으로 편향되어 있거나 반대로 모든 노드가 부모의 오른쪽 자식으로 되어 오른쪽으로 편향되어 있는 이진트리를 말한다.

이러한 경우 사실 트리를 쓰는 이유가 사라지게 된다. 트리의 특정한 경우이지만 이렇게 된다면 탐색, 삽입, 삭제, 메모리 성능 등 모든 면에서 배열에 비해 좋은 것이 없다.

BST(Binary Search Tree)

효율적인 탐색을 위한 저장 방법이 무엇일까를 고민해야 한다.
이진 탐색 트리는 이진 트리의 일종이다.
단, 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다.
그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다.

  • 규칙1 : 이진 탐색 트리의 노드에 저장된 키는 유일하다.
  • 규칙2 : 루트 노드의 키가 왼쪽 서브트리를 구성하는 어떤 노드의 키보다 크다.
  • 규칙3 : 루트 노드의 키가 오른쪽 서브트리를 구성하는 어떤 노드의 키보다 작다.
  • 규칙4 : 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

이진 탐색 트리의 탐색 연산은 O(log n)의 시간 복잡도를 갖는다.
사실 정확히 말하면 O(h)라고 표현하는 것이 맞다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두배씩 증가하기 때문이다.
이러한 이진 탐색 트리는 편항 트리가 될 수 있다. 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생할 수 있기 때문이다.
이럴 경우 성능에 영향을 미치게 되며, 탐색의 Worst cost가 발생하고 시간 복잡도는 O(n)이 된다.

배열보다 많은 메모리를 사용하여 데이터를 저장했지만 탐색에 필요한 시간 복잡도가 같게 되는 비효율적인 상황이 발생했다.
이를 해결하기 위해 Rebalancing 기법이 등장했다.

균형을 잡기 위한 트리 구조의 재조정을 Rebalancing이라고 한다. 이 기법을 구현한 트리에는 여러 종류가 존재하는데 그 중에서 하나는 추후에 살펴볼 Red-black-Tree 이다.

이진 트리의 순회 방법

이진 트리의 순회 방법을 간단하게 정리하면 아래와 같다. 루트의 위치를 기준으로 이름을 기억하면 된다.

  1. 전위 순회(Preorder) : 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리
  2. 중위 순회(Inorder) : 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리
  3. 후위 순회(Postorder) : 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트

Comment and share

2019.03.20 일자 기준으로 공부했던 내용을 수정하려고 한다. 이유는 이렇게 정리해놨지만 머리에 기억으로 남지 않기 때문이다.

먼저, Array VS LinkedList를 비교해보겠다.

Array(배열)

  • 논리적 저장순서와 물리적 저장 순서가 일치한다.
  • 인덱스로 해당 원소에 접근이 가능하다.
  • 인덱스만 알고 있다면 시간 복잡도 O(1)만에 해당 원소로 접근할 수 있다.
  • 즉, Random Access가 가능하다.
  • 배열의 원소를 삭제할 경우 삭제한 원소보다 큰 인덱스를 가진 원소들을 옮겨줘야(Shift) 하기 때문에 시간 복잡도 O(n)이 걸린다.
  • 삽입의 경우, 새로운 원소를 추가하고 모든 원소들의 인덱스를 1씩 Shift 해줘야 하므로 시간 복잡도 O(n)이 걸린다.
  • 제한적인 크기를 갖는다.

즉, 삭제 또는 삽입 과정에서 해당 원소에 접근하여 작업을 완료한 뒤 Shift를 해줘야 하는 cost가 발생해 O(n)의 시간복잡도를 갖는다.

LinkedList

  • 자료의 주소 값으로 노드를 이용해 서로 연결되어 있는 구조를 갖는다.
  • 삽입과 삭제의 경우 LinkedList가 Array보다 속도가 빠르다고 하지만 엄밀히 말하면 경우에 따라 다르다고 하는게 맞다. (아래에서 설명하겠다.)
  • 원하는 값을 찾기 위해서 최소 한 번은 리스트를 순회하여야 하므로 O(n)의 시간 복잡도를 갖는다.
  • 트리의 근간이 되는 자료구조이다.

LinkedList 역시 삽입과 삭제를 위해서 해당 노드를 찾아가는 동안 O(n)의 시간 복잡도를 갖는다. 추가적으로 데이터를 삽입 / 삭제하기 위한 시간 복잡도까지 계산하면 결국 O(n)의 시간 복잡도를 갖는 셈이다.

하지만 위에서 경우에 따라서 다르다고 하지 않았는가?
삽입의 경우
일단, LinkedList는 어느 곳에 삽입하던지 O(n)의 시간복잡도를 갖는다. (만약, 중간 삽입이 없다면 즉 맨 앞과 맨 뒤에만 삽입한다면 -> 시간 복잡도 : O(1))

삭제의 경우
삭제의 경우도 삽입과 마찬가지이다. 어느 곳에 삽입하던지 O(n)의 시간 복잡도를 갖는다. (만약, 중간 삭제가 없고 맨 앞과 뒤에서만 삭제한다면 -> 시간 복잡도 : O(1))

Array VS LinkedList

# 데이터 접근 속도

Array는 인덱스를 사용해 빠르게 원소에 접근할 수 있다. 따라서 Random Access를 지원한다. 시간 복잡도 O(1)로 빠르게 찾을 수 있다.

LinkedList는 순차 접근 방식을 사용한다. 특정 원소에 접근하기 위해서는 처음부터 원소에 도달할 때까지 순차적으로 검색하면서 찾는다. 시간 복잡도 O(N)

# 데이터의 삽입 속도

경우에 따라 다르다.
만약 배열에 공간이 많이 남아있고 맨 끝에 삽입한다면 삽입 속도 역시 O(1)에 가능하다. 하지만 이런 경우는 발생하기 힘든 케이스이다.

Array(배열)의 경우 데이터를 중간이나 맨 앞에 삽입할 경우 그 이후의 데이터를 한 칸씩 미뤄야 하는 추가 과정과 시간이 소요된다. 데이터가 많을 경우 비효율적이다. 그렇기 때문에 LinkedList가 필요하게 되었다.

LinkedList는 어느 곳에 삽입하던지 O(N)의 시간 복잡도를 갖는다.(만약, 중간 삽입이 없다면 O(1)의 시간복잡도를 갖는다.) 이유는 삽입할 위치를 찾고(O(N)) 삽입 연산을 진행하기 때문에 O(N)의 시간 복잡도를 갖는다. 그럼에도 Array보다 빠른 성능을 보인다.

또한 Array의 경우 데이터 삽입 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받지만 LinkedList는 그럴 필요가 없다. 추가할 때마다 동적으로 할당하는 것으로 알고 있다.

# 데이터의 삭제 속도

이 부분도 경우에 따라 다르다.
Array는 데이터 삭제의 경우 그 위치의 데이터를 삭제 후, 전체적으로 Shift 해줘야 한다. (O(N))

LinkedList의 경우 삭제할 원소를 찾기 위해서 O(N)의 시간 복잡도를 갖고 삭제를 한다. 결구 O(N)의 시간 복잡도를 갖는다. 하지만 Array 보다 빠르게 삭제 연산을 수행한다.

# 메모리 할당

  • Array에서 메모리는 Array가 선언되자 마자 Compile time에 할당되어 진다. 이것을 정적 메모리 할당이라고 한다.

  • Stack 영역에 메모리 할당이 이루어진다.

  • LinkedList에서 메모리는 새로운 node가 추가될 때 runtime에 할당되어 진다. 이것은 동적 메모리 할당이라고 한다.

  • Heap 영역에 메모리 할당이 이루어진다.

# size

Array의 size는 반드시 선언 시점에 지정되어있어야 한다.

LinkedList의 size는 다양할 수 있다. node들이 추가될 때 runtime 시점에서 LinkedList의 size가 커질 수 있기 때문이다.

결론

  • 삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다.
  • 데이터의 접근하는 게 중요하다면 Array를 사용하는 것이 좋다.

전반적인 내용을 보면 Array보다 LinkedList(포괄적인 범위에서 List라고 하겠다.)의 사용이 훨씬 좋아보인다. 하지만 일반적인 알고리즘 문제를 풀 때는 List보다 Array가 훨씬 빠르고 좋다. 왜냐하면 대부분의 알고리즘 문제는 메모리 공간의 범위를 파악할 수 있도록 N의 크기가 주어지기 때문이다.

그래서 배열의 크기를 MAX로 초반에 잡을 수 있다면 훨씬 더 편리하고 List와는 다른 속도를 보인다. 왜냐하면 위에서 본 것처럼 List의 입력마다 메모리의 할당이 일어나고 삭제에서는 메모리 해제가 일어난다. 이런 작업은 시간복잡도에 포함되지는 않지만 시스템 콜(System Call)을 사용하는 구문은 시간 소요가 꽤 걸린다.

사용하려는 목적에 따라서 Array와 List를 구분해서 사용하면 된다.

자자, 위에서는 Array와 LinkedList의 차이점을 살펴보았다. 이번에는 ArrayList와 LinkedList의 차이를 살펴보겠다. 사실 위에서 본 것과 차이는 거의 없다고 생각한다. 이유는 ArrayList가 단지 내부적으로 Array(배열)를 사용하고 List 인터페이스를 구현했기 때문에 거의 똑같다고 생각한다. 그래도 한 번 살펴보자.

ArrayList vs LinkedList

1. ArrayList

  • 내부적으로 데이터를 배열에서 관리하며 데이터의 추가, 삭제를 위해서 임시 배열을 생성해 데이터를 복사하는 방법을 사용한다.
  • 대량의 자료를 추가/삭제 하는 경우 그만큼 데이터의 복사가 많이 일어나게 되어 성능 저하가 발생
  • 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 존재해야 한다.
  • 반면 인덱스를 가지고 있어서 한 번에 참조가 가능해 데이터 검색에 유리하다.

ArrayList는 삽입과 삭제를 할 일이 없거나 배열의 끝에서만 하게 될 경우 유용하게 쓰일 수 있다. 원소에 대해 빠르게 접근할 수 있을 뿐만 아니라, 원소들이 메모리에 연속으로 배치해 있어 CPU 캐시 효율도 더욱 높다.

2.LinkedList

  • 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있으면 된다.
  • ArrayList와 달리 데이터의 추가, 삭제시 불필요한 데이터의 복사가 없어 데이터의 추가, 삭제시에 유리하다.
  • 반면, 데이터 검색 시에는 처음부터 노드를 순회하기 때문에 성능상 불리하다.

3. 데이터의 검색,삽입,삭제시 성능 비교

검색

  • ArrayList : 인덱스 기반이기 때문에 O(1)의 시간복잡도를 갖는다.
  • LinkedList : 검색 시 모든 요소를 순차적으로 탐색해야 하기 때문에 O(N)의 시간 복잡도를 갖는다.

삽입,삭제

  • ArrayList : 삽입,삭제 이후 다른 데이터를 복사해야 하기 때문에 O(N)의 시간복잡도를 갖는다.
  • LinkedList : 이전 노드와 다음 노드를 참조하는 상태만 변경하면 되기 때문에 삽입, 삭제 시에 O(1)의 시간 복잡도를 갖는다. 하지만 이 부분도 경우에 따라 다르다.

참고

Comment and share

Stack

  • Last In First Out(LIFO)의 구조로 나중에 들어간 원소가 가장 먼저 나오는 자료구조이다.
  • 반대로 제일 먼저 들어간 원소가 가장 늦게 나온다.
  • 함수의 콜스택에 쓰이고 문자열을 역순으로 출력할 때, 연산자 후위표기법 등에 쓰인다.

Queue

  • First In First Out(FIFO)의 구조로 먼저 들어간 원소가 먼저 나오는 구조를 갖는다.
  • 컴퓨터 버퍼에서 주로 사용된다. 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼를 만들어 대기 시킨다.

참고

Comment and share

  • page 1 of 1
Author's picture

VictoryWoo

기록을 통해 사람들과 공유하는 것을 좋아합니다.


Android Developer