2. Data Structure

1. Array

배열

연관된 데이터를 하나의 변수에 그룹핑해서 관리하기 위한 방법입니다. 배열을 이용하면 하나의 변수에 여러 정보를 담을 수 있고, 반복문과 결합하면 많은 정보도 효율적으로 처리할 수 있습니다.

배열의 특징

• 순차적으로 데이터를 저장하는 자료구조

• 주로 서로 연결된 데이터들을 순차적으로 저장할 때 사용

• 순서가 상관 없더라도 서로 연결된 데이터들을 저장할 때 사용

• 순서대로 저장

• 이미 생성된 것도 수정 가능

• 동일한 값 여러번 삽입 가능

• 배열안에 배열이 들어올 수 있음(Multi-dimentional)

배열 내부 구조

출처: https://chanyeong.com/blog/post/49

Array는 실제 메모리 상에서, 즉 물리적으로 데이터가 순차적으로 저장됩니다. 따라서 어느 자리에 있는지 번호로 지정할 수 있으며, 이 번호를 index라고 합니다.

배열의 장점

• Index를 가지고 있기 때문에 데이터에 바로 접근이 가능합니다.

  → 시간 복잡도를 O(1)로 갖게 되며 자료구조의 크기가 클수록 효율적입니다.
  

배열의 단점

• 삽입과 삭제가 오래 걸립니다.

  순차적으로 데이터를 저장하는 것은 Array의 특징이자 단점이 될 수 있습니다.

  

  출처: https://beginnersbook.com/2013/12/java-arraylist/
  

Array의 중간 요소를 삭제할 경우, 뒤에 있는 데이터를 삭제한 요소 수 만큼 앞으로 이동시켜줘야 합니다.

• 배열의 크기가 정적입니다.

  • 데이터를 새로 추가할 때 Resizing 문제가 생길 수 있습니다. Resizing이란 메모리의 사이즈를 다시 조정한다는 뜻입니다.

  • 배열은 메모리를 순차적으로 채우며, 처음 생성될 때 메모리를 미리 할당(pre-allocation)합니다.

    • 메모리를 미리 할당하면서 새로 추가되는 요소들도 순차적으로 메모리에 저장 될 수 있습니다. 하지만 처음 할당한 사이즈보다 많아진다면 resizing이 필요합니다.

    

• 배열 특성상 추가적으로 할당 된 메모리 또한 순차적으로 들어가야 하기 때문에 상대적으로 오래걸립니다.

  • 따라서 배열의 데이터를 삭제하고 추가할 때 실제 메모리 상에서 이루어지는 작업이 커서, 보통 정보가 자주 삭제/추가 되는 데이터일 경우 배열을 사용하지 않습니다.

[JAVA]ArrayList (참고)

배열에서 발전된 형태라고 보시면 됩니다.

일단 ArrayList의 장점은 배열의 크기를 임의로 변화시킬수 있다는 것과 List에 들어갈수 있는 타입들을 사용자가 직접 설정할수 있다는 것입니다. 일반적인 기본형 타입도 가능하고 자신이 만든 클래스의 객체 타입도 설정할수 있습니다.

• 메소드

  • add(Object elem): 객체 매개변수(elem)를 목록에 추가

  • remove(int index): index 매개변수로 지정한 위치에 있는 객체를 제거

  • remove(Object elem): 주어진 객체가 List에 있으면 그 객체를 제거

  • contains(Object elem): 객체 매개변수 elem에 매치되는 것이 있으면 '참'을 리턴

  • isEmpty(): 목록에 아무 원소도 없으면 '참'을 리턴

  • indexOf(Object elem): 객체 매개변수(elem)의 인덱스 또는 -1을 리턴

  • size(): 현재 목록에 들어있는 원소의 개수를 리턴

  • get(int index): 주어진 index 매개변수 위치에 있는 객체를 리턴

2. LinkedList

• 배열(Array)은 순차적으로 연결된 공간에 데이터를 나열하는 자료구조

• 링크드 리스트(Linked List)는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 자료구조 입니다.

  • 배열은 미리 특정한 연결된 공간을 확보하고 데이터를 쓰고 있는 자료구조

• 링크드 리스트는 필요할 때 마다 데이터를 추가할 수 있는 구조입니다. 배열의 단점을 극복한 자료구조가 링크드 리스트라고 볼 수 있습니다.

Linked List의 구조와 용어

링크드 리스트(Linked List)는 연결 리스트(Linked List) 혹은 단일(단방향) 연결 리스트(Singly Linked List)라고도 합니다.

배열과 달리 특정한 데이터를 저장할 때 해당 데이터를 저장하는 공간과 함께, 그 다음에 나올 데이터가 저장되어있는 공간을 가리키는 주소값을 동시에 가지고 있습니다. 링크드 리스트는 이 두 공간을 하나의 데이터로 관리합니다.

출처: https://velog.io/@keemtj/자료구조-링크드-리스트Linked-List

Node

Linked List는 노드라는 객체로 이루어져 있습니다.

• 위 그림과 같이 Data를 저장할 공간과 다음 주소를 가리킬 공간이 필요합니다. 사용자가 입력하는 정보를 DATA영역에 담고 노드가 추가될 때마다 Next address를 이용하여 다음 노드와 연결합니다.

• 전체적인 연결리스트 구조는 아래와 같이 나타낼 수 있습니다.

• 이와 같이 각 노드는 연속된 공간에 저장되어 있지 않고 메모리의 여러 부분에 분포되어 있습니다.

• 각 노드에 다음 노드의 주소를 저장함으로써 다음 노트를 탐색할 수 있습니다. 다음 주소를 가리켜야 하기 때문에 포인터를 이용해 구현할 수 있습니다.

• 노드가 가리키는 다음 주소가 NULL이면 이 노드는 마지막 노드라고 할 수 있습니다.

Linked List 구현

Linked List를 구현하기 위해서는 다음과 같은 함수를 구현해야 합니다.

초기화(init) / 삽입(Insert) / 삭제(Remove)

• Init

  • 노드를 생성하는 과정입니다.

  • 노드를 접근하기 위해서는 맨 처음 노드의 주소를 가리킬 노드가 필요합니다. 이 노드를 head라고 표현하겠습니다.

  • 또한 나중에 구현할 삽입의 시간복잡도를 줄이기 위해 마지막 노드를 가리키는 노드 tail을 하나 만들겠습니다.

  • 초기화하는 과정에서 다음 주소를 가리키는 포인터는 null로 설정합니다. null은 '가리키는 노드가 없음' 을 의미합니다.

    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    class LinkedList:
        def __init__(self, data):
            self.head = Node(data)
        
        #헤더부터 탐색해 뒤에 새로운 노드 추가하기
        def append(self, data):
            cur = self.head
            while cur.next is not None:
                cur = cur.next
            cur.next = Node(data)
    	
        #모든 노드 값 출력
        def print_all(self):
            cur = self.head
            while cur is not None:
                print(cur.data)
                cur = cur.next
    		def get_node(self, index):
    		        cnt = 0
    		        node = self.head
    		        while cnt < index:
    		            cnt += 1
    		            node = node.next
    		        return node

• Insert

  

  

  • 새로운 노드가 들어올때는 현재 노드의 next 를 new node로 바꿔주고 new node의 next를 원래 cur node의 next노드로 바꿔주면 됩니다.

  • 즉 [3] → [4] → [1] → [2]를 [3] → [4] → [5] → [1] → [2] 만들기 위해서 인덱스 2자리인 [1]에 들어가기 위해 [4] 노드 위치를 파악하고, 그 다음 next에 [5] 노드를 연결해줍니다. [5]의 next는 [1]이 연결되게끔 해야합니다.

    def add_node(self, index, value):
            new_node = Node(value)
            if index == 0: # 첫 번째 노드일때
                new_node.next = self.head
                self.head = new_node
                return
            node = self.get_node(index-1)
            next_node = node.next
            node.next = new_node
            new_node.next = next_node
            

• Remove

  • 삭제하는것은 더 간단합니다.

    

  • 삭제하고자 하는 index 번 째 노드의 전 노드를 찾아 바로 다음 노드가 될 것을 연결해주면 됩니다.

    def delete_node(self, index):
            if index == 0:
                self.head = self.head.next
                return
            node = self.get_node(index-1)
            node.next = node.next.next

Linked List의 장단점

장점

• 동적으로 메모리 사용 가능

• 메모리 효율적 사용

• 데이터 재구성 용이

• 대용량 데이터 처리 적합

단점

• 특정 위치 데이터 검색할 때 느림

  • 첫번째 혹은 마지막 노드를 탐색할때는 쉽게 찾을 수 있지만, 중간 노드를 탐색할 경우 첫 노드부터 순차적으로 탐색해야 하기 때문에 탐색이 느립니다.

• 메모리를 추가적으로 사용해야함

  • 데이터를 저장할 공간 뿐만 아니라, 다음 노드의 주소를 저장하는 공간이 추가적으로 필요하다는 단점이 있습니다.

Linked List의 다양한 구조

• 링크드 리스트는 앞에서 설명한 링크드 리스트(Linked List) 혹은 단일 연결 리스트(Singly Linked List) 이 외에도 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List)가 존재합니다.

이중 연결 리스트(Doubly Linked List)

• 위와 같은 Linked list를 이중 연결 리스트 혹은 더블 링크드 리스트라고 부릅니다.

• node의 pointer가 이전 node와 다음 node를 모두 가리키고 있는 것이 특징입니다. pointer가 양방향으로 연결되어 있기 때문에 node 탐색이 양쪽으로 모두 가능합니다.

• 예를 들어 찾고자 하는 데이터가 연결 리스트의 뒤 쪽에 존재할 경우 단일 연결 리스트는 처음 node부터 순차적으로 탐색이 필요합니다. 그러나 이중 연결 리스트는 마지막 node에서 시작하여 처음 node 방향으로 탐색이 가능하기 때문에 더 빠른 시간 안에 데이터를 찾을 수 있습니다.

원형 연결 리스트(Circular Linked List)

원형 연결 리스트란 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 연결 리스트 입니다.

헤드의 포인터가 마지막 노드를 가리키도록 구성한 연결 리스트입니다. 또한 마지막 노드는 헤드 포인터인 Head를 가리키고, 첫 번째 노드는 head⇒ link가 가리킵니다. 그러므로 리스트의 마지막에 노드 삽입, 삭제시 맨 끝까지 힘들게 가지 않아도 됩니다.

• 장점: 한 노드에서 다른 모든 노드로의 접근이 가능함(노드의 삽입, 삭제가 단순해짐)

• 단점: 노드의 삽입, 삭제시 선행 노드의 포인터가 필요함

3. Array & ArrayList & LinkedList

정의

• Array

  • Index로 빠르게 값을 찾는 것이 가능

• Linked List

  • 데이터의 삽입 및 삭제가 빠름

• ArrayList

  • 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느림

비교

• 우선 배열은 선언할 때 크기와 데이터 타입을 지정해야 합니다.

• 따라서 데이터가 계속 늘어날 때, 최대 사이즈를 알 수 없을 때는 사용하기에 부적합합니다.또한 중간에 데이터를 삽입하거나 삭제할때도 매우 비효율적입니다.

• 대신, 배열을 사용하면 index가 존재하기 때문에 위치를 바로 알 수 있어 검색에 편한 장점이 있습니다.

이를 해결하기 위해 나온 것이 List입니다.

• List는 array처럼 크기를 정해주지 않아도 됩니다. 대신 array에서 index가 중요했다면, List에서는 순서가 중요합니다.

• 크기가 정해져있지 않기 때문에, 중간에 데이터를 추가하거나 삭제하더라도 array에서 갖고 있던 문제점을 해결 가능합니다. index를 가지고 있으므로 검색도 빠르다.

• 하지만, 중간에 데이터를 추가 및 삭제할 때 시간이 오래걸리는 단점이 존재합니다.

• Linked List는 종류가 무엇이든, 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식으로 되어있습니다.

• 이런 방식을 활용하면서, 데이터의 중간에 삽입 및 삭제를 하더라도 전체를 돌지 않아도 이전 값과 다음값이 가르켰던 주소값만 수정하여 연결시켜주면 되기 때문에 빠르게 진행할 수 있다.

• 이렇게만 보면 가장 좋은 방법 같아보이지만, List의 k번째 값을 찾아라에서는 비효율적입니다.

  

결론

array나 arrayList에서 index를 갖고 있기 때문에 검색이 빠르지만, LinkedList는 처음부터 살펴봐야하므로(순차) 검색에 있어서는 시간이 더 걸린다는 단점이 존재한다.

따라서 상황에 맞게 자료구조를 잘 선택해서 사용하는 것이 중요하다.

4. 스택(Stack) & 큐(Queue)

스택

입력과 출력이 한 곳으로 제한되어 있다.

LIFO (Last In First Out, 후입선출) 라고 하며 가장 나중에 들어온 것이 가장 먼저 나오는 자료구조이다.

함수

• push() : 가장 뒤에 데이터를 넣는다.

• pop() : 가장 뒤에서 데이터를 뺀다.

• isFull() : 스택이 가득 차있는지 확인한다.

• isEmpty() : 스택이 비어 있는지 확인한다.

구현

push와 pop을 할 때 해당 위치를 알고 있어야 하므로 현재의 위치를 갖고 있는 '스택 포인터(SP)'가 필요하다. 스택 포인터는 다음 값이 들어갈 위치를 가리키고 있다. (처음 기본값은 -1)

class stack(size) :
	sp = -1
	stack_size = 0
	def __init__(self):
		self.sp = -1
		self.stack_size = size
		self.stack = [0] * size

• push() : 데이터를 최상단에 넣는다.

#push 함수 구현
def push(o) {
	if len(stack) == 100 :
		return

	sp += 1
	stack[sp] = o;
}

스택 포인터가 최대 크기와 같으면 return

아니면 스택의 최상위 위치에 값을 넣는다.

• pop() : 데이터의 최상단 값을 뺀다.

#pop 함수 구현
def pop() {
	if len(stack) == 0 :
		return None
	o = stack[sp]
	sp -= 1
	return o
}

스택 포인터가 0이 되면 null return

아니면 스택의 최상위 위치에 있는 값을 꺼내온다.

• isEmpty()

def isEmpty() {
	return len(stack) == 0 
}

스택이 비어 있으면 True, 값이 있으면 False를 return

• isFull()

def isFull(){
	return len(stack) == stack_size
}

스택이 꽉차 있으면 True, 아니면 False를 return

동적 배열 스택

위와 같이 구현 하려면 stack_size라는 스택의 크기가 정해져 있어야 한다.

최대 크기가 없는 스택을 만드려면?

• 연결리스트 스택

• 배열 크기 늘리기

  1. 기존 스택의 2배 크기만큼 임시 배열을 만든다.

  2. 기존 스택을 임시배열에 복사한다. (0번째 인덱스부터)

  3. 복수 후 arr의 참조값을 stack에 덮어 씌운다.

  4. stack_size를 2배 증가시킨다.

  
  

def push(o) {
	if stack.isFull(): # 스택이 가득 찼을 경우
		arr = [0] * (stack_size * 2)
		index = stack_size - 1 
		#값 옮기기
		while not stack.isEmpty():
			arr[index] = stack.pop()
			index -= 1
		stack_size *= 2
		stack = arr # 참조값 덮어 씌우기
	stack[sp] = o
	sp += 1	
}

이러면, 스택이 가득 찼을 때 자동으로 확장되는 스택을 구현 할 수 있다.

스택 사용

• 함수의 콜스택

• 문자열 역순으로 출력

• 연산자 후위표기법

큐

입력과 출력을 한 쪽 끝(front, rear)로 제한한다.

FIFO(First In First Out, 선입 선출) 이라고 하며 가장 먼저 들어온 것이 가장 먼저 나간다.

• front : 가장 첫 원소

• rear : 가장 끝 원소

→ 큐는 rear로 들어와서 front로 나온다.

함수

• enQueue() : 데이터를 rear에 넣는다.

• deQueue() : 데이터를 front에서 뺀다.

• isEmpty() : 큐가 비어있는지 확인한다.

• isFull() : 큐가 가득 차있는지 확인한다.

구현

데이터를 넣고 뺄 때 해당 값의 위치를 기억해야한다. 스택의 스택포인터와 비슷한 개념이다.

큐는 출구와 입구가 다르기 때문에 front의 위치와 rear의 위치를 기억한다

• front : deQueue 할 위치 기억

• rear : enQueue 할 위치 기억

class Queue(size):
	front = -1; rear = -1; size = 0
	def __init__(self):
		self.queue_size = size
		self.queue = [0] * size
			

enQueue

def enQueue(o) :
	if isFull():
			return 
	rear += 1
	queue[rear] = o

enQueue 시, 가득 찼다면 꽉 차 있는 상태에서 enQueue를 했기 때문에 overflow

아니면 rear에 값 넣고 1 증가 시킨다.

deQueue

def deQueue():
	if isEmpty() :
		return None
	tmp = queue[front]
	queue[front] = None
	front ++
	return tmp
    

deQueue를 할 때 공백이면 underflow

front에 위치한 값을 object에 꺼낸 후, 꺼낸 위치는 null로 채워줌

isEmpty

def isEmpty():
	return front == rear
    

front와 rear가 같으면 비어 있는 것이다.

isFull

def isFull():
	return (rear == queueSize - 1)

rear가 (큐 사이즈 - 1)와 같아지면 가득 찬 것이다

큐의 단점

• 큐에 빈 메모리가 남아 있어도, 꽉 차 있는 것으로 판단 할 수 있다

  • rear가 끝에 도달하면 꽉 찬 것이라고 판단하지만 앞에서 데이터를 삭제 했으면 그만큼의 메모리가 남아 있기 때문이다.

원형 큐

큐의 단점을 보완하기 위해 개선한 큐로 논리적으로 배열의 처음과 끝이 연결되어 있다.

공백, 포화 상태를 쉽게 구분하기 위해 자리 하나를 항상 비워둔다.

(index + 1) % size로 순환 시킨다.

• 원형 큐의 단점

  • 메모리 공간은 잘 활용하지만, 배열로 구현되어 있어 메모리 크기가 한정적이다.

연결 리스트 큐

이러한 원형 큐의 단점을 보완하기 위해 개선한 큐로 큐의 크기의 제한이 없고 삭제가 편리하다.

사용

• 버퍼
• 마구 입력된 것을 처리하지 못하고 있는 상황
• BFS

5. 힙(Heap)

힙은 우선순위 큐를 위해 만들어진 자료구조이다.

우선 순위 큐(Priority Queue)

• 우선 순위의 개념을 큐에 도입한 자료구조
  
  
• 데이터들이 우선순위를 가지고 있음. 우선 순위가 높은 데이터가 먼저 나감

특징

1. 완전 이진 트리의 일종

• 여러 값 중 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조

2. 반정렬 상태

• 힙 트리는 중복된 값을 허용한다.

  • 이진 탐색 트리는 중복된 값을 허용하지 않는다

힙 종류

1. 최대 힙(max heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

2. 최소 힙(min heap)

• 부모 노드의 키 값이 자식 노드의 키 값도가 작거나 같은 완전 이진 트리

python heap 사용하기

• heapq 라이브러리 import

import heapq

heap = [] #빈 배열을 만든 후 heapq라이브러리를 이용해서 힙처럼 사용한다.

python의 heapq 라이브러리는 숫자가 낮을 수록 우선 순위를 갖는다. (즉 최소힙이다)

함수

• heappush(heap, value) : heap에 value를 추가한다.

heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap)

🖨️ [10, 50, 20]

→ 우선순위를 갖는 0번째 인덱스 말고는 정렬되어 있지 않다.

• heapify(list) : 리스트를 heap으로 바꾼다.

l = [10,30,40,15,26,100]
heapq.heapify(l)
print(l)

🖨️ [10, 15, 40, 30, 26, 100]

→ 기존의 리스트가 heap으로 바뀌었다.

• heappop(heap) : 우선순위가 가장 큰 값을 뺀다.

t1 = heapq.heappop(heap)
t2 = heapq.heappop(l)

print(t1, t2)
print(heap)
print(l)

🖨️

10 10
[30, 50]
[15, 26, 40, 30, 100]

→ 우선 순위가 가장 높은 값이 빠지고 남은 것중에 우선 순위가 높은 것이 0번째 인덱스로 이동되었다.

힙큐의 장점

지속적으로 값이 가장 우선순위 큰 것을 뽑아 내야 할 경우 매번 리스트 순회하여 최댓값을 찾고 뽑아야 하지만 힙큐는 트리 구조로 가장 큰 우선순위가 항상 앞에 있도록 해 놓았기 때문에 시간이 감소 된다

• 리스트에서 우선순위 값 찾기 → O(N)

• 힙큐에서 찾기 - > O(logN)

6. 이진탐색트리(Binary Search Tree)

참고, 참고1

이진 트리

• 이진 트리는 모든 노드가 정확하게 두 개의 서브트리를 가지고 있는 트리이다.

  • 다만 서브트리는 공백이 될 수 있다.

• 즉 노드의 유한 집합으로서 공백이거나 루트와 두 개의 분리된 이진트리인 경우 왼쪽서브트리와 오른쪽 서브트리로 구성된다.

  • 여기서 중요한점은 왼쪽과 오른쪽 서브트리를 확실하게 구분한다는 것이다.

    • 일반적인 트리에서 두개의 트리는 같지만 이진 트리에서는 두개의 트리는 다른 트리이다. 이는 이진트리에서는 서브트리의 위치가 다르기 때문이다.

    

• 편향 이진 트리(skewed binary tree)

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

  

• 포화 이진트리(full binary tree)

  • 포화 이진트리란 이진트리가 보유할 수 있는 최대의 노드를 가지고 있는 형태이다.

  • 높이가 h인 이진 트리에서 있을 수 있는 최대 노드 수는$2^h⁺¹-1$ 이다.

  • 아래 그림은 높이가 2인 포화 이진트리이다.

  

• 완전 이진트리(complete binary tree)

  • 위 포화 이진트리 같은 경우에는 루트 노드를 1번으로 하고 레벨 별로 왼편에서 오른 편으로 차례로 노드 위치에 번호를 $2^h⁺¹-1$까지 부여가 가능하다.

  • 그런데 만일 높이가 h이고 노드 수가 n, 일때 n <= ( $2^h⁺¹-1$ )인 이진트리를 노드의 레벨 순수에 따라 노드 번호를 붙인다면 이때 각 노드 번호의 위치가 포화 이진트리 번호 1에서 n까지의 위치와 모두 정확하게 일치한다면 이 트리를 완전 이진트리라고 한다.

  • 즉 루트 노드를 1이라고 하고 그외에 모든 노드가 왼쪽에서부터 오른쪽까지 꽉 차서 노드의 수가 n<=($2^h⁺¹-1$)라면 완전 이진트리이다. 아래 그림은 완전 이진트리의 예이다.

  

이진트리의 순차 표현

• 이진 트리는 유일하게 붙여지는 포화 이진 트리 번호를 이용하면 순차 표현 즉 1차원 배열로 쉽게 표현할 수 있다.

  • 즉 포화 이진트리 번호를 배열의 인덱스로 사용하면 된다.

  • 아래 그림은 이진 트리의 순차표현을 보여준다.

    • 이때 1차원 배열에시 인덱스 0은 실제 사용하지 않고 인덱스 1은 항상 루트 노드를 나타낸다.

• n개의 노드를 가진 이진트리를 1차원 배열로 표현했을 때 포화 이진트리 번호를 인덱스로 사용하면 어떤 노드 i의 부모, 왼쪽자식, 오른쪽 자식의 인덱스를 쉽게 알 수 있다.

<완전 이진트리를 표현한 1차원 배열에서 인덱스 관계>

• 장점

  • 이진트리의 순차표현은 어떠한 이진 트리의 표현에도 적용할 수 있다

• 단점

  • 저장공간을 효율적으로 사용하지 못할 수 있다는 단점

    • 그 예가 위에 편향 이진트리이다.

  • 트리의 중간에 삭제와 삽입을 하게 될 경우 많은 노드들의 이동이 불가피 하게 된다.

이진탐색 트리의 목적

• 이진탐색 + 연결리스트

  • 이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN), but 삽입,삭제가 불가능

  • 연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), but 탐색하는 시간복잡도가 O(N)

  • 이 두가지를 합하여 장점을 모두 얻는 것이 '이진탐색트리'

• 효율적인 탐색 능력을 가지고, 자료의 삽입 삭제도 가능하게 만들자

이진탐색 트리 특징

• 각 노드의 자식이 2개 이하

• 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼

• 중복된 노드가 없어야 함

  • 검색 목적 자료구조인데, 굳이 중복이 많은 경우에 트리를 사용하여 검색 속도를 느리게 할 필요가 없음.

  • 트리에 삽입하는 것보다, 노드에 count 값을 가지게 하여 처리하는 것이 훨씬 효율적

• 이진탐색트리의 순회는 '중위순회(inorder)' 방식 (왼쪽 - 루트 - 오른쪽)

  • 중위 순회로 정렬된 순서를 읽을 수 있음

• BST 핵심연산

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

• 시간 복잡도

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

  • 편향 트리 : 노드 개수가 N개일 때 O(N)

  • 삽입, 검색, 삭제: 트리의 Depth에 비례

• 삭제의 3가지 Case

  • 자식이 없는 leaf 노드일 때 → 그냥 삭제

  • 자식이 1개인 노드일 때 → 지워진 노드에 자식을 올리기

  • 자식이 2개인 노드일 때 → 오른쪽 자식 노드에서 가장 작은 값 or 왼쪽 자식 노드에서 가장 큰 값 올리기

• 편향된 트리(정렬된 상태 값을 트리로 만들면 한쪽으로만 뻗음)는 시간복잡도가 O(N)이므로 트리를 사용할 이유가 사라짐

  → 이를 바로 잡도록 도와주는 개선된 트리가 AVL Tree, RedBlack Tree

이진탐색트리 구현 (재귀)

노드 생성 및 삽입

# 노드 생성과 삽입
class Node:
    def __init__(self,data):
        self.left = None
        self.right = None
        self.data = data
        
class BinarySearchTree(Node):
    def insert(self, data):
        self.root = self._insert_value(self.root, data)
        return self.root is not None

    def _insert_value(self, node, data):
        if node is None:
            node = Node(data)
        else:
            if data <= node.data:
                node.left = self._insert_value(node.left, data)
            else:
                node.right = self._insert_value(node.right, data)
        return node

노드 탐색

# 노드 탐색
    def find(self, key):
        return self._find_value(self.root, key)

    def _find_value(self, root, key):
        if root is None or root.data == key:
            return root is not None
        elif key < root.data:
            return self._find_value(root.left, key)
        else:
            return self._find_value(root.right, key)

노드 삭제

def delete(self, key):
        self.root, deleted = self._delete_value(self.root, key)
        return deleted

    def _delete_value(self, node, key):
        if node is None:
            return node, False

        deleted = False
        # 해당 노드가 삭제할 노드일 경우
        if key == node.data:
            deleted = True
            # 삭제할 노드가 자식이 두개일 경우
            if node.left and node.right:
                # 오른쪽 서브 트리에서 가장 왼쪽에 있는 노드를 찾고 교체
                parent, child = node, node.right
                while child.left is not None:
                    parent, child = child, child.left
                child.left = node.left
                if parent != node:
                    parent.left = child.right
                    child.right = node.right
                node = child
            # 자식 노드가 하나일 경우 해당 노드와 교체
            elif node.left or node.right:
                node = node.left or node.right
            # 자식 노드가 없을 경우 그냥 삭제
            else:
                node = None
        elif key < node.data:
            node.left, deleted = self._delete_value(node.left, key)
        else:
            node.right, deleted = self._delete_value(node.right, key)
        return node, deleted

이진트리순회

• 전위 순회 (Pre-order traversal) : root → Left → Right

• 중위,정위 순회 (In-order traversal) : Left → root → Right

• 후위 순회 (Post-order traversal) : Left → Right → root

<백준- 트리순회>

'''

#입력값

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

'''

from sys import stdin
from collections import defaultdict

n = int(stdin.readline())

tree = defaultdict(list)

for _ in range(n):
  root, l, r = stdin.readline().strip().split()
  tree[root] = [l, r]

print(tree)

result = [""] * 3 #전위, 중위, 후위

def traverse(node):
  result[0] += node
  if tree[node][0] != ".":
    traverse(tree[node][0]) #왼쪽

  result[1] += node
  if tree[node][1] != ".":
    traverse(tree[node][1]) #오른쪽

  result[2] += node

traverse("A")

for i in result:
  print(i)

<BFS 순회 - LEVEL 순회>

class BinarySearchTree(object):
    ...
    def level_order_traversal(self):
        def _level_order_traversal(root):
            queue = [root]
            while queue:
                root = queue.pop(0)
                if root is not None:
                    print(root.data)
                    if root.left:
                        queue.append(root.left)
                    if root.right:
                        queue.append(root.right)
        _level_order_traversal(self.root)


출처: https://geonlee.tistory.com/78 [빠리의 택시 운전사]

• 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 알고리즘은 트리를 포함한 각종 그래프를 순회하는 데에 사용할 수 있습니다. 트리는 사이클을 가지지 않기 때문에, 구현시 이미 방문한 노드(visited)를 기억할 필요가 없습니다.

7. 해시(Hash)

참고

• 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것

• 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다.

Lee → 해싱함수 → 5
Kim → 해싱함수 → 3
Park → 해싱함수 → 2
...
Chun → 해싱함수 → 5 // Lee와 해싱값 충돌

• 충돌(collision) 현상

  • 결국 데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생함

• 해시 테이블을 쓰는 이유

  • 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해

  • 하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능

• 언제나 동일한 해시값 리턴, index를 알면 빠른 데이터 검색이 가능해짐

• 해시테이블의 시간복잡도

  • O(1) - (이진탐색트리는 O(logN))

충돌 문제 해결

• 체이닝(Chaining) : 연결리스트로 노드를 계속 추가해나가는 방식 (제한 없이 계속 연결 가능, but 메모리 문제)
  

• 오픈 어드레싱(Open Addressing) : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 (해당 키 값에 저장되어있으면 다음 주소에 저장)
  

  • 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함

    • 해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 입력되어 있음을 발견하면, 현재 주소에서 고정 폭(예를 들면 1)으로 다음 주소로 이동합니다.

    • 특징 : Cluster(클러스터) 현상이 매우 잘 발생한다.
      
      

  • 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함

    • 선형 탐사가 다음 주소를 찾기 위해 고정폭만큼 이동하는 것에 비해 제곱 탐사는 이동폭이 제곱수로 늘어나는 것이 다르다.

    • 특징 : 서로 다른 해시 값을 갖는 데이터에 대해서는 클러스터가 형성 되지 않도록 하는 효과가 어느 정도 있지만, 같은 해시 값을 갖는 데이터에 대해서는 2차 클러스터 발생

해시 구현

<해시 테이블>

• 해쉬 함수: key % 8

• 해쉬 키 생성: hash(data)

hash_table = [0 for i in range(8)]

def hash_func(data):
    return hash(data) % 8

def set_data(data,value):
    key = hash_func(data)
    hash_table[key] = value

def get_data(data):
    key = hash_func(data)
    return hash_table[key]

<체이닝>

hash_table = [0 for i in range(8)]

def hash_func(key):
    return key % 8

def set_data(data,value):
    hash_idx = hash(data)
    hash_key = hash_func(hash_idx)
    if hash_table[hash_key] != 0:
        for i in range(len(hash_table[hash_key])):
            if hash_table[hash_key][i][0] == hash_idx:
                hash_table[hash_key][i][1] = value
                return True
        hash_table[hash_key].append([hash_idx,value])
        return True
    else:
        hash_table[hash_key] = [[hash_idx,value]]
        return True

def get_data(data):
    hash_idx = hash(data)
    hash_key = hash_func(hash_idx)
    if hash_table[hash_key]:
        for value in hash_table[hash_key]:
            if value[0] == hash_idx:
                print(value[1])
                return value[1]
        print("None")
        return None
    else:
        print("None")
        return None

<오픈 어드레싱 - Linear Probing>

• 폐쇄 해슁 또는 Close Hashing 기법 중 하나

  • 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법

• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법

• 저장공간 활용도를 높이기 위한 기법

hash_table = [0 for i in range(8)]

def hash_func(key):
    return key % 8

def set_data(data,value):
    hash_idx = hash(data)
    hash_key = hash_func(hash_idx)
    if hash_table[hash_key]:
        for i in range(hash_key,len(hash_table)):
            if hash_table[i] == 0:
                hash_table[i] = [hash_idx,value]
                return True
            elif hash_table[i][0] == hash_key:
                hash_table[i][1] = value
                return True
    else:
        hash_table[hash_key] = [hash_idx,value]
        return True

def get_data(data):
    hash_idx = hash(data)
    hash_key = hash_func(hash_idx)
    if hash_table[hash_key]:
        for idx in range(hash_key,len(hash_table)):
            if hash_table[idx] == 0:
                return None
            elif hash_table[idx][0] == hash_idx:
                return hash_table[idx][1]
    return None

8. 트라이(Trie)

트라이(Trie)의 형태

• Trie: 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

• 위에 보이는 트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있다. 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있다.

• DFS 형태로 검색을 해보면 사진의 번호에 나와있듯이 to, tea, ted, ten, A, i, in, inn이라는 단어들이 자료구조에 들어가 있음을 알 수 있다.

트라이(Trie)의 예시

• 주황색으로 된 노드들이 입력된 문자열들이다.
• 현재 be, bee, can, cat, cd가 들어가 있다.

사용목적

목적

• 문자열의 탐색을 하고자할 때 시간복잡도를 보면 알 수 있다. 단순하게 하나씩 비교하면서 탐색을 하는것보다 훨씬 효율적이다.

  • 단, 빠르게 탐색이 가능하다는 장점이 있지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있다.

• 검색어 자동완성, 사전에서 찾기, 문자열 검사 같은 부분에서 사용할 수 있다.

시간 복잡도

• 제일 긴 문자열의 길이를 L 총 문자열들의 수를 M이라 할 때 시간복잡도는 아래와 같다.

• 생성시 시간복잡도

  • O(M*L), 모든 문자열들을 넣어야하니 M개에 대해서 트라이 자료구조에 넣는건 가장 긴 문자열 길이만큼 걸리니 L만큼 걸려서 O(M*L)만큼 걸린다. 물론 삽입 자체만은 O(L)만큼 걸린다.

• 탐색시 시간복잡도

  • O(L), 트리를 타고 들어가봤자 가장 긴 문자열의 길이만큼만 탐색하기 때문에 O(L)만큼 걸린다.

트라이(Trie)를 이용한 기본 문제

백준 온라인 저지 5052번

 https://www.acmicpc.net/problem/5052

• 쉬운 풀이

**import sys
import math

def solution(numbers):
    numbers.sort()
    for i in range(len(numbers) - 1): 
        if numbers[i] in numbers[i+1][0:len(numbers[i])]:
            print("NO")
            return False
    print("YES")
    return True

numbers = []
t = int(input())

for _ in range(t):
    n = int(input())
    for _ in range(n):
        numbers.append(input())
    solution(numbers)
    numbers.clear()**

• 해쉬맵(딕셔너리)

**def solution(phone_book):
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                return False
    return True**

9. B-Tree & B+Tree

B+Tree

• 실제 DB의 인덱싱은 B+트리로 이루어져있다. 다음 그림은 인덱싱을 나타낸 것이다. 인덱싱은 어떠한 자료를 찾는데 key값을 이용해 효과적으로 찾을 수 있는 기능이다.

  

  
  

• 다음과 같은 인덱싱을 B+트리로 나타내면 아래 그림과 같다.

  

• B+트리에는 리프노드에 새로운 data값들이 들어가 있다. B트리의 경우에는 편의상 data를 생략하여 그렸지만, 각 key값이 data를 가지고 있었다고 생각하면 된다. 그럼 B트리와 B+트리 달라진 점에 대해서 알아보자.

  1. 모든 key, data가 리프노드에 모여있다. B트리는 리프노드가 아닌 각자 key마다 data를 가진다면, B+트리는 리프 노드에 모든 data를 가진다.

  2. 모든 리프노드가 연결리스트의 형태를 띄고 있다. B트리는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+트리는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어든다.

  3. 리프노드의 부모 key는 리프노드의 첫번째 key보다 작거나 같다. 그림의 B+트리는 리프노드의 key들을 트리가 가지고 있는 경우여서, data 삽입 또는 삭제가 일어날 때 트리의 key에 변경이 일어난다. 해당 경우뿐만 아니라 data의 삽입과 삭제가 일어날 때 트리의 key에 변경이 일어나지 않게 하여 더욱 편하게 B+트리를 구현하는 방법도 존재하기 때문에 작거나 같다라는 표현을 사용한다.

• B트리와 같이 M차 B+트리는 다음과 같은 특징을 같는다.

  • 노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있다.

  • 노드에는 최대 M−1개 부터 [M/2]−1개의 키가 포함될 수 있다.

  • 노드의 키가 x개라면 자식의 수는 x+1개이다.

  • 최소차수는 자식수의 하한값을 의미하며, 최소차수가 t라면 M=2t−1을 만족한다. (최소차수 t가 2라면 3차 B트리이며, key의 하한은 1개이다.)

key 삽입과정

모든 설명의 과정은 리프노드가 삽입 또는 삭제 될 때 트리의 key가 변경되는 경우로 진행한다. 검색과정은 B트리와 동일하기 때문에 생략하고 삽입의 과정부터 시작해본다. 삽입의 과정도 B트리와 매우 유사하지만 리프노드에서 최대 key개수를 초과할 때가 다르다.

💡 Case 1. 분할이 일어나지 않고, 삽입 위치가 리프노드의 가장 앞 key 자리가 아닌 경우

B트리와 똑같은 삽입 과정을 수행한다.

💡 Case 2. 분할이 일어나지 않고, 삽입 위치가 리프노드의 가장 앞 key 자리인 경우

삽입 후 부모 key를 삽입된 key로 갱신하고, data를 넣어준다.

💡Case 3. 분할이 일어나는 삽입과정

1. 분할이 일어나는 노드가 리프노드가 아니라면 기존 B트리와 똑같이 분할을 진행한다. 중간 key를 부모 key로 올리고, 분할한 두개의 노드를 왼쪽, 오른쪽 자식으로 설정한다.
2. 분할이 일어나는 노드가 리프노드라면 중간 key를 부모 key로 올리지만, 오른쪽 노드에 중간 key를 포함하여 분할한다. 또한 리프노드는 연결리스트이기 때문에 왼쪽 자식노드와 오른쪽 자식 노드를 이어줘 연결리스트 형태를 유지한다. 해당 부분이 B트리의 분할과 다른 점이다.

key 삭제과정

삭제과정 역시 기존 B트리와 유사하지만 삭제할 key k는 무조건 리프노드에 존재하는 점, k를 삭제하기 위해 검색하는 과정에서 index에 존재할 수 있다는 점이 다르다. 해당 부분을 위주로 삭제 과정을 보자.

💡 Case 1. 삭제할 key k가 index에 없고, 리프노드의 가장 처음 key가 k가 아닌경우

• 기존의 B트리 삭제과정과 동일하다.

💡 Case 2. 삭제할 key k가 리프노드의 가장 처음 key인 경우

• 삭제할 key k가 리프노드의 가장 처음 key인 경우에는 항상 k가 index 내에 존재한다.

  1. 먼저 리프노드의 k를 삭제하는 과정을 수행한다. key의 개수가 최소 key의 개수라면 B트리의 삭제 과정 중 형제노드의 key를 빌려오는 경우나 부모key와 병합하는 등 과정들은 동일하게 수행한다. 단, 리프노드가 병합할 때는 부모key와 오른쪽 자식의 처음 key가 동일하기 때문에 부모key를 가져오는 과정만 생략하고 왼쪽 자식과 오른쪽 자식을 병합만 하면 된다.

  2. 리프노드의 k를 삭제한 후, index내의 k를 inorder successor로 변경한다.