[Algorithm] 2. Data Abstraction and Basic Data Structures

저번 시간까지 알고리즘과 문제를 분석하는 방법에 대해 배웠다.

이번 시간에는 데이터 추상화와 기본 자료구조에 대해 알아보도록 하겠다.

 

 

 

 

● Abstract Data Type(ADT)

- 추상자료형은 어떤 자료구조가 저장해야할 데이터와 기능을 명세한다.

- 추상자료형의 구성 요소

  ① 구조 : 데이터 구조 선언

  ② 기능 : 연산들 정의

- ADT는 클래스로 구분된다.

  → C++나 자바에서 나오는 클래스가 바로 구현되어있는 형태이다. 클래스에는 변수들, 어떤 데이터로 구성이 되며, 그 클래스의 인스턴스, 객체에 대한 어떤 기능들을 할 수 있을지가 정의되어 있다.

- 알고리즘을 설계하고 정확도를 증명하는 것은 ADT의 연산과 세부 사항에 달려있다.

- 추상 자료형은 '구현 방법'은 명세되어있지 않다. 그렇기 때문에 추상자료형의 성능을 알 수는 없다. 성능을 알고 싶다면 해당 추상자료형을 어떻게 구현하는지를 알아야한다,

 

 

 

 

● Stack

- 스택은 삽입과 삭제가 한쪽 끝, top이라고 불리는 같은 곳에서 이루어지는 선형 구조이다.

- 보통 선형 자료형은 linked list나 배열로 구현한다.

- 마지막에 들어간 원소가 맨 먼저 나온다. 데이터가 들어가고 나가는 곳이 top으로 같고, 삽입, 삭제 연산 모두 여기서 일어난다.

- last in, first out (LIFO)

 

* stack 기능들

① push : 삽입 연산. top에서 이루어진다.

② top : 스택에 맨 마지막에 있는 원소를 알려준다.

③ pop : 불필요한 자료를 지우는 삭제 연산이다. 삭제할 데이터를 탐색하는 과정 없이 맨 마지막에 들어간 원소만 삭제하면 된다.

array	linked list
O(1)	O(1)
O(1)	O(1)
O(1)	O(1)

 

 

 

 

 

● Queue

- 삽입이 한 쪽 끝인 rear, back에서 일어나고, 삭제가 다른 쪽 끝인 front에서 일어나는 선형 자료구조

- first in, first out (FIFO)

- queue는 특정 원소를 탐색해주는데, 바로 다음으로 queue 밖으로 나갈 원소, 맨 앞에 있는 원소, queue에 가장 오래 남아있던 원소이다.

- service를 받을 때 많이 사용되는데, 먼저 온 사람이 먼저 서비스 받으므로 stack과 달리 queue는 데이터가 들어오고 나가는 곳이 분리되어있다. front에서는 삭제, rear에서는 삽입 연산이 일어난다.

 

* queue 기능들

① search : front()

② insertion : enqueue()

③ deletion : dequeue() → front에 있는 원소만 삭제하면 된다.

 

array	linked list
O(1)	O(1)
O(1)	O(1)
O(1)	O(1)

 

 

 

 

● Binary Tree ADT

- 이진 트리는 tree의 특별한 케이스로, 보통 root부터 작업이 시작된다.

- parent-child relation에 의해 tree가 정리된다.

- tree와 stack, queue의 차이점은 tree는 선형 자료구조가 아니라 계층구조라는 것이다.

 

- 이진 트리 T는 노드라고 불리는 원소들을 가지고 있으며, 노드는 비어있거나 아래의 조건을 만족한다.

  ① root라는 구별되는 노드 r이 있다.

  ② 나머지 노드는 L, R이라는 두 부분집합으로 나뉜다.

      L은 T의 왼쪽 subtree이고, R은 T의 오른쪽 subtree이다.

 

- 이진 트리에는 깊이가 d라고 하면 최대 2^d만큼의 노드들이 있다.

- n개의 노드로 구성되어있는 이진 트리는 「log(n+1)」-1 ~ log(n)만큼의 키(height)을 가진다.

- 높이가 h인 이진 트리는 최대 2^(h+1)-1의 노드들을 가진다.

 

-모든 자료구조는 그 안에 있는 데이터를 모두 찾아볼 수 있는 방법이 있어야한다.

→ 선형 구조인 자료구조들은 맨 앞에서부터 따라가면 모두 찾을 수 있다.

→ 계층 구조는 앞, 뒤가 정의가 안 되는데, 어떤 child부터 방문할 것인지 등을 정해야하고,

    여기서 특별한 알고리즘인 순회(traversal)라는 개념이 필요하다.

    전위 순회, 중위 순회, 후위 순회가 있고 재귀적으로 정의 가능하다.

 

 

 

 

 

 

● Priority Queue

- 앞에서 설명한 queue의 일반화된 개념이다.

  queue가 시간 순서에 따라서 서비스에 대한 우선순위가 결정되는 자료구조라고 한다면 우선순위 큐는 그 데이터를

  시간 순서뿐만 아니라 우선순위까지 같이 고려한다.

- 우선순위는 나이, 크기 등의 어떤 가치가 될 수 있고, 도착 시간보다 이 우선순위에 따라 순서가 결정된다.

  → priority queue에는 항상 비교연산자, 비교 함수가 정의되어야한다.

- 다음으로 탐색되거나 제거되는 원소는 현재 우선순위 큐에서 가장 중요한 원소일 것이다.

 

- cost의 관점 : 가장 작은 우선순위 먼저. min priority queue. 값이 작을수록 우선순위가 높다.

- profit의 관점 : 가장 큰 우선순위 먼저. max priority queue. 값이 클수록 우선순위가 높다.

 

- 우선순위 큐 추상 자료형에도 삽입, 삭제, 탐색 연산이 있다. 특히 탐색과 삭제 연산은 제한적이다.

- 탐색은 우선순위가 가장 큰 것을 반환하는데, max priority queue는 key가 가장 큰 것일 것이고,

  min priority queue는 key가 가장 작은 것일 것이다.

 

- 우선순위 queue를 구현하는 방법은 다양한다. 순서 없는 배열로 구현할 수도 있고 정렬된 (key에 대해) 배열로도

 구현 가능하다.

- 추상자료형은 마치 창문이 없어서 안을 들여다볼 수 없는 방같은 것이다. 앞에 설명서가 붙어있어서 지정된 형식대로

  호출해서 값을 알 수 있는 것이다.

- 방 안에 어떻게 자료가 들어있는지에 따라 수행시간(성능)이 달라질 수도 있지만 기능은 어쨋든 동일하다.

 

- priority queue에서의 삽입 연산은 같은 타입의 원소라면 아무거나 넣어줄 수 있다.

- 삭제 연산은 탐색과 마찬가지로 우선순위가 가장 큰 것을 삭제하고, 이 값을 반환하거나 하지 않는다.

 

- 만약 순서가 없는 배열에 min 함수를 호출했다면 최악의 경우에는 선형 시간, O(n) 시간이 걸릴 것이다. 정렬된

  배열에서는 가장 작은 원소는 맨 앞에 있기 때문에 O(1) 시간이 걸릴 것.

  (circular array일 때 만약 그냥 배열이면 하나씩 당기므로 O(n) 시간이 걸릴 수 있다.)

- 보통은 우선순위 큐를 heap. 특히 binary heap으로 구현하는 것이 효율적이라고 배웠다.

  heap은 나중에 sorting algorithm에서 자세히 배우도록 하겠다.

 

 

 

 

 

 

 

 

● Union-Find ADT for disjoint sets

- 서로 교집합의 원소가 없는 공집합이 없는 집합에서 합집합을 만들자.

- Union 연산을 하면 두 개의 교집합이 없는 서로 다른 집합을 묶어서 하나의 집합으로 만든다. 이 때 새로운 집합 id는 unique한 set id를 가지는데, 보통 기존 집합들 둘 중의 하나이다.

- 두 개의 기존 집합들의 set id를 s, t라고 한다면 새로운 집합은 s나 t 중 하나의 set id를 가지게 되는 것이다.

- Find 연산을 통해 현재의 원소의 set id를 알 수 있다.

- 보통 원소들은 정수이고, set id는 leader라고 부르는 집합 안의 특정 원소이다. 원소들 중의 한 값이고,

  최대값, 최소값 이런 식으로 지정한다.

 

* Union-Find 함수들

① UnionFind create(int n)

- 정수를 하나 주면 그만큼의 원소 하나짜리 disjoint set을 n개 만들어준다. 꼭 이런 식이 아니어도 되는데

  여기에서는 이렇게 create를 한다고 치자.

- 예: {{1}, {2}, {3}, ...}

② int Find(UnionFind sets, int e)

- 정수 e가 속해있는 집합의 set id를 반환한다.

③ void makeSet(unionFind sets, int e)

- e를 원소로 하는 원소 하나짜리 집합을 만들고 그것을 기존에 있는 집합에 넣어준다.

- e는 그 집합에 원래는 없었어야하고, {e}를 기존의 집합과 union하는 것.

④ void union(UnionFind sets, int s, int t)

- s, t는 서로 다른 set id

- s가 나타내는 집합과 t가 나타내는 집합을 합집합하고 그것은 min(s, t) 또는 max(s, t) 또는 다른 값으로 이름을

  지정할 수 있다.

 

 

 

 

 

 

 

● Dictionary ADT

- dictionary is a general associative storage structure.

- dictionary의 안의 item, entry는 다음의 정보들을 가지고 있다.

  → identifier (key)

  → associated information that needs to be stored and retrieved.

  → no order implied for identifiers in a dictionary ADT

 

- 사전 자료형은 key와 부속 데이터의 pair이다. (key, data) 형태.

  → 어떤 데이터은 각각을 구분해주는 identifier가 있고, 그것을 key라고 부른다.

- 만약 순서가 정렬되어있지 않으면 O(n)으로 사전의 기능 탐색, 삽입, 삭제 연산이 가능하다.

  ① 탐색 : 임의의 key를 가진 원소를 탐색.

  ② 삽입 : 임의의 key를 가진 원소를 삽입.

  ③ 삭제 : 임의의 key를 가진 원소를 삭제.

막강한 기능이나, 구현 방법에 따라 수행 시간이 많이 달라진다.

 

* dictionary 구현방법

① 정렬된 배열 사용

- sorted array → binary search

- 최악 수행시간 : O(log n) → 어마어마하게 짧은 것.

  → 1000개이면 10번, 1000000개이면 20번.

  → 2^10 ~ 10^3 (kilo)

  → 2^20 ~ 10^6 (mega)

  → 2^30 ~ 10^9 (giga)

- 하지만 이 경우에는 정렬된 상태를 유지하는 데 시간이 걸린다. 삽입의 경우는 삽입하고 뒤로 밀어줘야 하고,

  삭제의 경우는 삭제하고 다시 당겨줘야한다.

  → 최악 수행시간 : O(n)

  → 삽입, 삭제가 자주 발생하지 않을 때 사용하자.

 

② 정렬되지 않은 배열 사용

- O(1) 시간에 삽입. 뒤에 계속 붙이면 된다.

- 탐색에 최대 O(n) 시간이 걸린다.

- 삽입만 자주 발생하는 경우에 사용한다.

  → 예 : 시스템 이벤트 로그

 

③ balanced binary search tree

- 균형 이진 탐색 트리 → AVL tree

- 최악 수행 시간 : O(log(n)) → 탐색, 삽입, 삭제 연산 모두.

- linked structure

 

④ Hashing ( = Hash Table)

- 평균 수행시간이 빠른 자료구조이다.

- 배열을 이용한 구현 방법을 사용한다.

- 배열을 이용한 것도 hash 자체로도 시간이 짧게 걸린다.

- load factor는 (저장된 item 개수) / (배열의 크기)

- 적절히 유지하기만 하면 평균적으로 O(1) 시간이 걸린다.

 

 

 

 

 

다음 시간부터는 sorting algorithm에 대해 알아보도록 하겠다.