🦊 2. Data Structures

01. 해시테이블

해시테이블(hash table)은 효율적인 탐색을 위한 자료구조로서 키(key)를 값(value)에 대응시킨다.

간단한 해시테이블은 연결리스트(linked list)와 해시 코드 함수(hash code function)만 있으면 된다.

키와 값을 해시테이블에 넣을 때는 다음 과정을 거친다.

1. 키의 해시 코드를 계산한다. (키의 개수는 무한하지만 int 의 개수는 유한하기 때문에 서로 다른 두 키가 같은 해시 코드를 가리킬 수도 있다 :: 충돌)
2. hash(key) % array_length 와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다.
3. 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다. 충돌에 대비하여 반드시 연결리스트를 이용해야 한다.

수행 시간

• 최악의 경우 : 충돌이 자주 발생한다면 O(N)
• 최선의 경우 : 충돌을 최소화 한다면 O(1)
• 균형 이진 탐색 트리일 경우 : O(logN)

ArrayList 와 가변 크기 배열

특정 언어에서는 배열의 크기를 자동으로 조절할 수 있지만, 자바 같은 언어에서는 배열의 길이가 고정되어 있다. 이런 경우에는 배열을 만들 때 배열의 크기를 함께 지정해야 한다.

동적 가변 크기 기능이 내재되어 있는 배열과 비슷한 자료구조를 원할 때 보통 ArrayList 를 사용한다.

ArrayList는 필요에 따라 크기를 변화시키면서도 O(1) 의 접근 시간을 유지한다.

배열이 가득 차는 순간, 배열의 크기를 두 배 늘리는데, 이 때 시간은 O(N) 이다.

하지만 자주 발생하는 일이 아니기 때문에 상환 입력 시간으로 계산하면 여전히 O(1) 을 유지한다.

상환 입력 시간은 왜 O(1)이 되는가.

배열의 크기를 K로 늘리면 그 전 배열의 크기는 K의 절반이었을 것이므로 K/2 만큼의 원소를 복사해야 한다.

크기가 N인 배열에서 N개의 원소를 삽입하기 위해 복사해야 하는 원소의 총 개수는

N/2 + N/4 + N/8 + ... + 2 + 1 로 N보다 작다.

따라서 N개의 원소를 삽입할 때 소요되는 작업은 O(N) 이 된다.

평균적으로 각 삽입은 O(1) 이 소요된다고 할 수 있다.

StringBuilder

문자열의 리스트가 주어졌을 때 이 문자열들을 하나로 이어 붙이려고 한다. 이 때의 수행시간은?

String joinWords(String[] words) {
	String sentence = "";
	for (String w : words) {
		sentence = sentence + w;
	}
	return sentence;
}

문자열을 이어붙일 때 마다 2개의 문자열을 읽어 들인 뒤 문자를 하나하나 새로운 문자열에 복사해야 한다.

처음에는 x개, 2번째는 2x개, 3번째는 3x개 … n번째는 nx개 복사해야 한다.

따라서 총 수행시간은 O(x + 2x + ... + nx) = O(xn^2) 가 된다.

StringBuilder 는 이 문제를 해결할 수 있다. StringBuilder 는 단순하게 가변 크기 배열을 이용해서 필요한 경우에만 문자열을 복사하게끔 할 수 있다.

String joinWords(String[] words) {
	StringBuilder sentence = new StringBuilder();
	for (String w : words) {
		sentence.append(w);
	}
	return sentence.toString();
}

02. 연결리스트

연결리스트는 차례로 연결된 노드를 표현해주는 자료구조이다.

단방향 연결리스트에서 각 노드는 다음 노드를 가리킨다.

양방향 연결리스트에서 각 노드는 다음 노드와 이전 노드를 함께 가리킨다.

배열과는 달리 연결리스트에서는 특정 인덱스를 상수 시간에 접근할 수 없다.

리스트에서 K번째 원소를 찾고 싶다면 K번 루프를 돌아야한다.

다만 연결리스트의 장점은 리스트의 시작 지점에서 아이템을 추가하거나 삭제하는 연산을 상수 시간에 할 수 있다.

연결리스트 만들기

가장 기본적인 연결리스트를 구현한 코드이다

class Node {
	Node next = null;
	int data;
	public Node(int d) {
		data = d;
	}

	void appendToTail(int d) {
		Node end = new Node(d);
		Node n = this;
		while (n.next != null) {
			n = n.next;
		}
		n.next = end;
	}
}

연결리스트에 접근할 때 head 노드의 주소를 참조하는 방법을 사용했다.

이런 식으로 구현할 때 조심해야 하는 부분이 있다.

여러 객체들이 동시에 연결리스트를 참조하는 도중에 head 가 바뀌면?

head 가 바뀌었음에도 어떤 객체는 이전 head 를 계속 가리킬수도 있다.

할 수 있다면 Node 클래스를 포함하는 LinkedList 클래스를 만드는게 좋다.

클래스 안에 head Node 변수를 단 하나만 정의해 놓음으로써 이 문제를 해결할 수 있다.

Runner 기법

Runner (부가 포인터)는 연결리스트 문제에서 많이 활용되는 기법이다.

연결리스트를 순회할 때 두 개의 포인터를 동시에 사용하는 것이다.

이 때, 한 포인터는 다른 포인터보다 앞서도록 한다.

예를 들어

A1 -> A2 -> ... -> An -> B1 -> B2 -> ... -> Bn

이 리스트를 다음처럼 정렬하고자 한다.

A1 -> B1 -> A2 -> B2 -> ... -> An -> Bn

앞선 포인터 P1 을 두고 따라오는 포인터 P2가 한 번 움직일 때마다 포인터 P1이 두 번 움직이도록 설정하자.

그러면 P1 이 연결리스트 끝에 도달하면 P2는 가운데 지점에 있게 된다.

이 상태에서 P1을 다시 맨 앞으로 옮기고 P2로 하여금 원소를 재배열하도록 할 수 있다.

즉, 루프가 실행될 때마다 P2가 가리키는 원소를 P1 뒤로 옮기는 것이다.

재귀 문제

연결리스트 관련 문제 가운데 상당수는 재귀 호출에 의존한다.

재귀 호출 깊이가 n이 될 경우 해당 재귀 알고리즘이 적어도 O(n) 만큼의 공간을 사용한다는 사실을 기억하라.

03. 스택과 큐

스택 자료구조는 데이터를 쌓아 올린다는 의미이다.

때로는 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있다.

스택은 LIFO(Last-In-First-Out)에 따라 자료를 배열한다.

가장 최근에 스택에 추가한 항목이 가장 먼저 제거된다.

스택의 연산은 다음과 같다.

• pop(): 가장 위의 항목을 제거한다.
• push(item) : 아이템 하나를 스택 가장 윗 부분에 추가한다.
• peek() : 가장 위의 항목을 반환한다.
• isEmpty() : 비어있으면 true를 반환한다.

배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 없다.

하지만 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다.

public class MyStack {
	private static class StackNode {
		private T data;
		private StackNode Next;
		private StackNode(T data) {
			this.data = data;
		}
	}
	private StackNode top;

	public T pop() {
		if (top == null) throw new EmptyStackException();
		T item = top.data;
		top = top.next;
		return item;
	}

	public void push(T item) {
		StackNode t = new StackNode(item);
		t.next = top;
		top = t;
	}

	public T peek() {
		if (top == null) throw new EmptyStackException();
		return top.data;
	}

	public boolean isEmpty() {
		return top == null;
	}
}

스택은 재귀 알고리즘을 사용할 때 유용하다.

재귀적으로 함수를 호출해야 하는 경우 임시 데이터를 스택에 넣어주고, 재귀 함수를 빠져 나와 퇴각 검색(backtrack)을 할 때 스택에 넣어 두었던 임시 데이터를 빼준다.

스택은 이런 일련의 행위를 직관적으로 가능하게 해준다.

스택은 또한 재귀 알고리즘을 반복적 형태(iterative)를 통해 구현할 수 있게 해준다.

큐 구현하기

큐는 FIFO(First-In-First-Out) 순서를 따른다.

큐의 연산은 다음과 같다.

• add(item) : 아이템 하나를 리스트의 끝 부분에 추가한다.
• remove() : 리스트의 첫 번째 항목을 제거한다.
• peek() : 가장 위의 항목을 반환한다.
• isEmpty() : 비어있으면 true를 반환한다.

연결리스트의 반대 방향에서 항목을 추가하거나 제거하도록 구현한다면 근본적으로 큐와 같다.

public class MyQueue {
	private static class QueueNode {
		private T data;
		private QueueNode Next;
		private QueueNode (T data) {
			this.data = data;
		}
	}
	private QueueNode first;
	private QueueNode last;

	public void add(T item) {
		QueueNode t = new QueueNode(item);
		if (lst != null) {
			last.next = t;
		}
		last = t;
		if (first == null) {
			first = last;
		}
	}

	public T remove() {
		if (first == null) throw new NoSuchElementException();
		T data = first.data;
		first = first.next;
		if (first == null) {
			last = null;
		}
		return data;
	}

	public T peek() {
		if (first == null) throw new NoSuchElementException();
		return first.data;
	}

	public boolean isEmpty() {
		return first == null;
	}
}

큐에서 처음과 마지막 노드를 갱신할 때 실수가 나오기 쉽다.

큐는 너비 우선 탐색과 캐시를 구현하는 경우에 종종 사용된다.