Queue는 왜 포인터가 두 개 필요할까? | Generics부터 기본 정렬과 Shellsort까지
컴퓨팅 문제와 알고리즘 3장에서는 Queue에서 시작해서 Generics, Iterator, Bag을 거쳐 정렬 알고리즘까지 다룬다.
처음 보면 서로 크게 관련 없어 보이는 내용들이 한 장에 모여 있다.
그런데 공부하면서 생각해보면 공통된 질문이 있다.
데이터를 어떤 구조로 저장하고, 어떤 방식으로 접근하고, 얼마나 효율적으로 처리할 것인가?
Queue에서는 데이터를 넣고 빼는 위치를 고민하고, Generics에서는 하나의 자료구조를 여러 타입에 안전하게 사용하는 방법을 고민한다.
Iterator는 자료구조 내부 구현을 몰라도 데이터를 순회할 수 있게 하고, 정렬에서는 데이터의 순서를 효율적으로 바꾸는 방법을 고민한다.
이번 글에서는 이 흐름을 따라 3장의 내용을 정리해보려고 한다.
1. Queue란?
Queue는 먼저 들어온 데이터가 먼저 나오는 자료구조다.
이를 FIFO라고 한다.
FIFO
First In First Out
먼저 들어온 데이터
→ 먼저 나간다.예를 들어 사람들이 줄을 서 있다고 생각하면 된다.
입구 → A → B → C → 출구A가 가장 먼저 들어왔다면 A가 가장 먼저 나간다.
Queue에서는 데이터를 넣는 연산을
enqueue라고 하고,
데이터를 제거하는 연산을
dequeue라고 한다.
중요한 점은 삽입 위치와 삭제 위치가 서로 다르다는 것이다.
dequeue enqueue
↓ ↓
[ A ] → [ B ] → [ C ] → [ D ]
↑ ↑
front rear새로운 데이터는 뒤쪽에 추가하고 가장 오래된 데이터는 앞쪽에서 제거한다.
따라서 Queue를 구현하려면 보통
front
rear두 위치를 관리해야 한다.
2. 왜 front와 rear가 모두 필요할까?
Queue의 핵심 연산을 다시 생각해보자.
enqueue
→ 가장 뒤에 데이터 추가
dequeue
→ 가장 앞의 데이터 제거따라서 빠르게 처리하려면
가장 앞이 어디인지
가장 뒤가 어디인지를 모두 알고 있는 것이 유리하다.
Linked List로 Queue를 구현한다면 개념적으로 다음과 같다.
front rear
↓ ↓
[A] → [B] → [C] → [D] → nulldequeue()를 하면
front
↓
[A] → [B] → [C]에서 A를 제거하고
front
↓
[B] → [C]처럼 front만 다음 노드로 이동시키면 된다.
반대로 enqueue(D)를 한다면 rear가 마지막 노드를 알고 있으므로 바로 뒤에 연결할 수 있다.
3. rear를 저장하지 않으면 어떻게 될까?
강의자료에는 다음과 같은 문제가 등장한다.
Null-terminated singly-linked list로 Queue를 구현하는데 front는 유지하고, 가장 최근에 추가된 item의 reference인 end는 유지하지 않는다면 enqueue와 dequeue의 최악 실행시간은 어떻게 될까?
여기서 핵심은 rear가 없다는 것이다.
현재 구조가 다음과 같다고 하자.
front
↓
[A] → [B] → [C] → [D] → nulldequeue()는 간단하다.
front가 이미 A를 가리키고 있으므로
front = front.next;처럼 처리할 수 있다.
따라서 데이터 개수 N에 관계없이 일정한 작업만 수행한다.
dequeue → O(1)그런데 enqueue는 다르다.
rear가 없으므로 마지막 노드를 모른다.
새로운 E를 추가하려면
A
↓
B
↓
C
↓
D
↓
null 발견
↓
E 연결처럼 처음부터 끝까지 이동해야 한다.
N개의 데이터가 있다면 최악의 경우 N개 정도를 따라가야 한다.
따라서
enqueue → O(N)
dequeue → O(1)이 된다.
이 문제를 통해 왜 Queue 구현에서 front와 rear를 함께 유지하는지가 이해된다.
포인터 하나를 더 저장하는 대신 연산 시간을 줄이는 것이다.
4. Linked List와 Array로 Queue를 구현하면?
Queue는 Linked List뿐 아니라 Array로도 구현할 수 있다.
Linked List 방식은 각 데이터가 다음 노드를 가리키는 링크를 가지고 있어야 한다.
[item | next] → [item | next] → [item | next]따라서 링크를 저장하기 위한 추가 공간이 필요하다.
반면 Array는 연속된 공간에 데이터를 저장할 수 있다.
[ A ][ B ][ C ][ D ][ ][ ]하지만 배열은 크기 문제를 고민해야 한다.
Queue에 앞으로 데이터가 몇 개 들어올지 클라이언트가 정확히 알 수 없다면 처음 배열의 크기를 어떻게 정할 것인지가 문제가 된다.
결국 자료구조 구현에서는 항상 이런 trade-off가 등장한다.
Linked List
→ 링크를 위한 추가 공간 필요
Array
→ 크기 관리 문제 발생5. 그런데 Queue에 String만 넣어야 할까?
자료구조를 구현하다 보면 또 다른 문제가 생긴다.
예를 들어 다음과 같은 Stack이 있다고 하자.
class StringStack {
String[] data;
}String을 저장할 때는 문제가 없다.
그런데 Integer도 저장하고 싶다면?
class IntegerStack {
Integer[] data;
}Double도 저장하려면?
class DoubleStack {
Double[] data;
}자료형이 달라질 때마다 거의 똑같은 코드를 다시 작성해야 한다.
이것은 상당히 비효율적이다.
코드를 복사해서 계속 수정해야 하고, 한 구현에서 버그를 수정했다면 다른 구현도 모두 수정해야 할 수 있다.
그래서 Generics가 필요해진다.
6. Object로 받으면 되지 않을까?
Java의 모든 클래스는 Object를 기반으로 하므로 다음처럼 만들 수도 있다.
class Stack {
Object[] data;
}그러면 String도 넣을 수 있고 Integer도 넣을 수 있다.
stack.push("Hello");
stack.push(Integer.valueOf(10));하지만 꺼낼 때 문제가 생긴다.
String value = (String) stack.pop();Object로 저장했기 때문에 다시 원래 타입으로 casting해야 한다.
그리고 잘못된 타입으로 casting하면 문제가 실행 중에 발견된다.
강의자료에서 강조하는 원칙이 여기서 나온다.
Welcome compile-time errors.
Avoid run-time errors.즉,
가능하다면 오류를 실행 중에 발견하지 말고 컴파일할 때 발견하자.
이것이 Generic을 사용하는 중요한 이유다.
7. Generic을 사용하면?
Generic을 사용하면 자료구조를 다음처럼 만들 수 있다.
public class Stack<Item> {
private Item[] s;
public void push(Item item) {
...
}
public Item pop() {
...
}
}여기서 Item은 특정 자료형 하나를 의미하는 것이 아니다.
사용할 때 실제 타입을 지정한다.
Stack<String> s1;
Stack<Integer> s2;같은 Stack 구현을 사용하면서 저장할 데이터 타입만 바꿀 수 있다.
Stack<Item>
↓
Stack<String>
Stack<Integer>
Stack<Double>이렇게 하면 클라이언트에서 불필요한 casting을 줄일 수 있고 타입이 맞지 않는 문제를 컴파일 단계에서 발견할 수 있다.
8. Generic 배열은 바로 만들 수 없다
강의자료의 구현에서 주의할 부분이 하나 있다.
다음 코드는 Java에서 허용되지 않는다.
s = new Item[capacity];Generic type의 배열을 직접 생성할 수 없기 때문이다.
그래서 강의에서는 다음과 같은 형태를 사용한다.
s = (Item[]) new Object[capacity];먼저 Object 배열을 만들고
new Object[capacity]이를
(Item[])로 casting하는 방식이다.
Generic 자료구조 구현 문제를 볼 때 자주 등장하는 형태이므로 기억해둘 필요가 있다.
9. primitive type은 Generic에 넣을 수 있을까?
다음과 같이 작성할 수 있을까?
Stack<int> stack;Java Generic에는 primitive type을 직접 사용할 수 없다.
대신 Wrapper Class를 사용한다.
int → Integer
long → Long
float → Float
double → Double
byte → Byte
short → Short
char → Character
boolean → Boolean따라서
Stack<Integer> stack = new Stack<>();처럼 사용한다.
그런데 실제 사용할 때는 다음처럼 작성할 수 있다.
stack.push(17);17은 int인데 Integer를 요구하는 곳에 넣을 수 있다.
이것이 Autoboxing이다.
개념적으로 Java가
stack.push(Integer.valueOf(17));처럼 처리해주는 것이다.
반대로 Integer를 int로 꺼내는 것도 자동으로 처리할 수 있다.
int a = stack.pop();이를 Unboxing이라고 생각할 수 있다.
10. Iterator는 왜 필요할까?
자료구조 안에 데이터가 여러 개 있다고 하자.
클라이언트 입장에서는 자료구조가 내부적으로
Array인지
Linked List인지알고 싶지 않을 수도 있다.
그냥
저장된 데이터를 처음부터 하나씩 보고 싶다.
는 요구가 있을 수 있다.
이때 Iterator를 사용할 수 있다.
Iterator는 데이터를 하나씩 순회하기 위한 인터페이스다.
핵심 메서드는
hasNext()
next()이다.
hasNext()
→ 다음 데이터가 존재하는가?
next()
→ 다음 데이터를 가져온다.11. Iterable과 Iterator는 다르다
이 둘은 이름이 비슷해서 구분할 필요가 있다.
Iterable은 Iterator를 제공하는 객체다.
개념적으로
interface Iterable<Item> {
Iterator<Item> iterator();
}형태다.
반면 Iterator는 실제 순회를 담당한다.
interface Iterator<Item> {
boolean hasNext();
Item next();
}즉 관계를 생각하면
Iterable
│
│ iterator()
↓
Iterator
│
├── hasNext()
└── next()이다.
자료구조가 Iterable을 구현하면 다음과 같은 enhanced for문을 사용할 수 있다.
for (String item : stack) {
System.out.println(item);
}12. enhanced for문 뒤에서는 무엇이 일어날까?
다음 코드는 매우 간단해 보인다.
for (String item : stack) {
System.out.println(item);
}하지만 Iterator를 명시적으로 사용하면 다음과 같은 흐름이다.
Iterator<String> it = stack.iterator();
while (it.hasNext()) {
String item = it.next();
System.out.println(item);
}즉
for-each를 이해하려면
Iterable
→ iterator()
→ Iterator
→ hasNext()
→ next()의 연결을 알고 있으면 된다.
13. Bag은 무엇일까?
이번 장에서는 Bag이라는 자료구조도 등장한다.
Bag은 데이터를 추가하고 순회할 수 있는 자료구조다.
특징은 순서가 중요하지 않다는 것이다.
Bag
add(A)
add(B)
add(C)
→ 저장
순회 가능
→ 하지만 순서 자체가 핵심이 아님강의자료에서는 Bag을
Stack without pop
또는
Queue without dequeue처럼 생각할 수 있다고 설명한다.
즉 데이터를 넣은 뒤 제거 순서를 관리하는 것보다 데이터를 모아두고 순회하는 것에 초점이 있다.
14. Stack은 실제 어디에서 사용될까?
Stack은 LIFO 구조다.
Last In First Out마지막에 들어온 데이터가 먼저 나온다.
Stack은 실제 여러 곳에서 사용된다.
Compiler Parsing
Java Virtual Machine
문서 편집기의 Undo
웹 브라우저의 Back 버튼
함수 호출 관리예를 들어 브라우저에서
Google
↓
Naver
↓
GitHub순서로 이동했다고 하자.
뒤로 가기를 누르면 가장 최근 페이지인 GitHub에서 이전 페이지로 돌아간다.
이런 구조가 Stack의 LIFO와 잘 맞는다.
15. 수식 계산에도 Stack을 사용할 수 있다
강의자료에서는 Stack의 응용으로 Two-Stack Algorithm을 소개한다.
하나는 연산자를 저장한다.
Operator Stack다른 하나는 값을 저장한다.
Value Stack규칙은 다음과 같다.
숫자
→ Value Stack에 push
연산자
→ Operator Stack에 push
왼쪽 괄호 (
→ 무시
오른쪽 괄호 )
→ 연산자 하나와 값 두 개를 pop
→ 계산
→ 결과를 Value Stack에 다시 push예를 들어
(1 + ((2 + 3) * (4 * 5)))같은 수식을 두 개의 Stack을 이용해 계산할 수 있다.
이 예제에서 중요한 것은 Stack이 단순히 데이터를 뒤집는 자료구조가 아니라 아직 처리하지 않은 연산을 임시로 보관하는 데 사용할 수 있다는 것이다.
16. Stack 두 개로 Queue를 만들 수 있을까?
강의자료에는 흥미로운 문제가 나온다.
Stack 두 개를 이용해서 Queue를 구현하라.
처음에는 이상하다.
Stack은
LIFO이고 Queue는
FIFO다.
서로 반대인데 어떻게 Stack으로 Queue를 만들 수 있을까?
핵심은 두 번 뒤집는 것이다.
예를 들어 Stack1에
A
B
C
D순서로 넣었다고 하자.
Stack의 top에는 가장 최근 데이터가 있다.
Stack1
TOP
↓
[D]
[C]
[B]
[A]이 데이터를 하나씩 pop해서 Stack2에 넣는다.
Stack2
TOP
↓
[A]
[B]
[C]
[D]순서가 다시 뒤집혔다.
이제 Stack2에서 pop하면
A가 먼저 나온다.
즉 가장 먼저 들어온 A가 가장 먼저 나온다.
FIFO가 만들어졌다.
17. 그런데 매번 옮기면 느리지 않을까?
여기서 중요한 것이 Amortized Analysis다.
매 연산마다 모든 데이터를
Stack1 → Stack2로 옮긴다면 비용이 상당히 커질 수 있다.
하지만 데이터를 한 번 이동시킨 뒤 Stack2에 남겨두고 필요한 동안 계속 사용하면 이야기가 달라진다.
각 원소의 이동을 보면 대략
Stack1에 push
↓
필요할 때 Stack2로 이동
↓
Stack2에서 pop정도의 제한된 횟수만 처리된다.
어떤 한 번의 연산은 O(N)이 걸릴 수 있지만 여러 연산 전체의 비용을 나눠보면 연산 하나당 평균적인 비용을 상수 수준으로 볼 수 있다.
이것이 amortized constant time을 이해하는 핵심이다.
최악의 한 번만 보는 것이 아니라 여러 연산에 걸친 전체 비용을 나누어 생각한다.
18. 메모리 사용량도 알고리즘의 비용이다
알고리즘을 평가할 때 실행 시간만 중요한 것은 아니다.
메모리를 얼마나 사용하는지도 중요하다.
Java 객체에는 우리가 선언한 필드만 들어 있는 것이 아니다.
개념적으로
Object Overhead
Fields
Padding등이 존재할 수 있다.
예를 들어 Integer 객체라면 단순히
int x;4바이트만 사용하는 것으로 끝나지 않는다.
객체 자체를 관리하기 위한 추가 메모리가 필요하다.
Linked List의 Node도 마찬가지다.
class Node {
Item item;
Node next;
}여기에는
item reference
next reference
object overhead등이 필요하다.
그래서 Linked List가 Array보다 추가적인 메모리를 사용할 수 있다는 설명과 연결된다.
19. 배열도 데이터만큼의 메모리만 사용하는 것은 아니다
배열 역시 객체다.
예를 들어
int[] a = new int[N];이라면 N개의 int 값뿐 아니라 배열 객체 자체를 관리하기 위한 메모리도 존재한다.
강의자료에서는 배열의 종류에 따라 필요한 메모리를 비교한다.
int[]
double[]
Date[]
double[][]특히 객체 배열은 객체 자체를 배열 안에 직접 저장하는 것이 아니라 객체를 가리키는 reference들을 저장한다는 점을 구분해야 한다.
Date[]
[ref] → Date 객체
[ref] → Date 객체
[ref] → Date 객체따라서 객체 배열의 메모리를 계산할 때는
배열 자체
+
reference
+
실제 객체를 구분해서 생각해야 한다.
20. 이제 정렬로 넘어가자
3장의 후반부에서는 Elementary Sorts를 다룬다.
대표적으로
Selection Sort
Insertion Sort
Shellsort가 등장한다.
먼저 Selection Sort와 Insertion Sort의 차이를 이해해야 한다.
21. Selection Sort는 어떻게 동작할까?
Selection Sort는 이름 그대로 가장 작은 값을 선택한다.
배열이 다음과 같다고 하자.
[5, 3, 4, 1, 2]첫 번째 위치에 들어갈 가장 작은 값을 찾는다.
[5, 3, 4, 1, 2]
↑
최소1을 찾았다.
첫 번째 값 5와 교환한다.
[1, 3, 4, 5, 2]이제 첫 번째 위치는 정렬이 끝났다.
다음 범위에서 다시 가장 작은 값을 찾는다.
[1 | 3, 4, 5, 2]
↑
최소2와 3을 교환한다.
[1, 2, 4, 5, 3]이 과정을 반복한다.
즉 Selection Sort의 핵심은
현재 위치
↓
오른쪽에서 최소값 탐색
↓
현재 위치와 최소값 교환이다.
22. Selection Sort 코드를 읽어보자
강의자료의 핵심 코드는 다음 구조다.
for (int i = 0; i < n; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (less(a[j], a[min])) {
min = j;
}
}
exch(a, i, min);
}한 줄씩 보면 어렵지 않다.
int min = i;현재 위치를 일단 최소값이라고 가정한다.
그다음
for (int j = i + 1; j < n; j++)로 오른쪽 데이터를 전부 확인한다.
더 작은 값이 발견되면
min = j;로 최소값의 위치를 바꾼다.
탐색이 끝나면
exch(a, i, min);으로 현재 위치와 최소값을 교환한다.
강의자료에서 Selection Sort 코드 부분에 '코드 시험' 표시가 있으므로 직접 손으로 추적할 수 있어야 한다.
23. Selection Sort는 이미 정렬되어 있으면 빨라질까?
다음 배열을 생각해보자.
1 2 3 4 5이미 정렬되어 있다.
그렇다면 Selection Sort는 바로 끝날까?
아니다.
Selection Sort는 현재 값이 정말 최소인지 확인하기 위해 오른쪽 데이터를 계속 검사한다.
첫 번째 단계에서는
N - 1번 비교한다.
그다음에는
N - 2번 비교한다.
계속하면
(N-1) + (N-2) + ... + 1이 된다.
이는 대략
N² / 2에 비례한다.
따라서 Selection Sort는 입력 배열이 이미 정렬되어 있더라도 비교 횟수가 크게 줄지 않는다.
24. Insertion Sort는 어떻게 동작할까?
Insertion Sort는 앞부분이 이미 정렬되어 있다고 생각하고 새로운 값을 적절한 위치에 끼워 넣는다.
카드를 손으로 정렬하는 모습을 생각하면 이해하기 쉽다.
예를 들어
[2, 5, 7 | 4]앞의
2, 5, 7은 이미 정렬되어 있다.
새로운 값 4를 넣으려면 왼쪽으로 이동하면서 비교한다.
4 < 7
→ 이동
4 < 5
→ 이동
4 > 2
→ 멈춤결과는
[2, 4, 5, 7]이 된다.
즉 Insertion Sort는
현재 원소를 왼쪽의 정렬된 영역에서 알맞은 위치까지 이동시킨다.
25. Selection Sort와 Insertion Sort의 결정적인 차이
Selection Sort는 매번 남은 데이터 전체를 확인해서 최소값을 찾는다.
Selection Sort
최솟값 찾기
↓
교환
↓
최솟값 찾기
↓
교환반면 Insertion Sort는 현재 데이터가 이미 올바른 위치에 가까우면 많은 이동을 할 필요가 없다.
그래서 입력 데이터가 이미 어느 정도 정렬되어 있는가가 성능에 영향을 준다.
강의자료에서 Insertion Sort의 Best Case는
이미 오름차순으로 정렬된 배열이다.
이 경우 각 원소마다 바로 왼쪽 정도만 확인하면 된다.
따라서
N - 1 compares
0 exchanges정도가 된다.
반면 Worst Case는 역순이다.
5 4 3 2 1새로운 원소가 들어올 때마다 왼쪽 끝까지 이동해야 한다.
강의자료에서는 대략
1/2 N² compares
1/2 N² exchanges로 설명한다.
강의자료에 '삽입정렬 시험'이라고 직접 표시되어 있으므로 Best Case와 Worst Case의 차이를 특히 확인할 필요가 있다.
26. 왜 Insertion Sort를 개선하려고 했을까?
Insertion Sort에는 약점이 있다.
원소가 한 번에 크게 이동하지 못한다.
예를 들어 작은 값이 배열의 아주 오른쪽에 있다고 하자.
[9, 8, 7, 6, 5, 4, 3, 2, 1]
↑1이 맨 앞으로 가려면
1칸
1칸
1칸
1칸
...씩 계속 이동해야 한다.
즉 멀리 떨어진 위치로 이동해야 하는 원소가 많으면 비효율적이다.
여기서 등장하는 것이 Shellsort다.
27. Shellsort는 Insertion Sort를 어떻게 개선할까?
Shellsort는 Insertion Sort의 확장이라고 볼 수 있다.
핵심 아이디어는 간단하다.
처음부터 옆에 있는 데이터만 비교하지 말고 멀리 떨어진 데이터끼리 먼저 정렬하자.
이를 h-sort라고 한다.
예를 들어
h = 4라면 바로 옆의 데이터가 아니라 4칸 떨어진 데이터들을 비교한다.
0 ↔ 4 ↔ 8
1 ↔ 5 ↔ 9
2 ↔ 6 ↔ 10
3 ↔ 7 ↔ 11이렇게 하면 멀리 떨어져 있던 값이 한 번에 큰 거리를 이동할 수 있다.
강의자료에서 표현한 핵심은
Big increments
→ small subarray
Small increments
→ nearly in order이다.
처음에는 큰 간격으로 거칠게 정렬한다.
그다음 간격을 줄인다.
큰 h
↓
부분적으로 정렬
↓
더 작은 h
↓
더 정렬됨
↓
h = 1
↓
Insertion Sort마지막에 h가 1이 되면 일반적인 Insertion Sort와 같은 형태가 된다.
하지만 그 시점에는 배열이 이미 상당히 정렬되어 있으므로 Insertion Sort가 훨씬 빠르게 동작할 수 있다.
28. Shellsort의 h는 어떻게 정할까?
강의에서는 Knuth의 3x+1 증가 수열을 사용한다.
1, 4, 13, 40, 121, ...다음 h를 만드는 식은
h = 3h + 1이다.
코드에서는 다음과 같은 구조가 등장한다.
int h = 1;
while (h < N / 3) {
h = 3 * h + 1;
}예를 들어 데이터가 16개라면 사용할 수 있는 h는
1
4
13이다.
실제 정렬은 큰 값부터 진행한다.
13-sort
↓
4-sort
↓
1-sort즉
멀리 떨어진 데이터 먼저 정리
↓
간격을 줄이면서 다시 정리
↓
마지막에 일반 Insertion Sort라고 이해하면 된다.
29. Shellsort 코드에서 Insertion Sort가 보이는 이유
Shellsort 코드를 보면 다음과 비슷한 부분이 등장한다.
for (int i = h; i < N; i++) {
for (int j = i;
j >= h && less(a[j], a[j-h]);
j -= h) {
exch(a, j, j-h);
}
}일반 Insertion Sort와 상당히 비슷하다.
차이는
1칸씩 이동하는 것이 아니라
h칸씩 이동한다는 것이다.
일반 Insertion Sort가
j--처럼 이동한다면 Shellsort는
j -= h처럼 이동한다.
그리고 h를 계속 줄이다가 마지막에는
h = 1이 된다.
그러면
j -= 1;이 되므로 사실상 Insertion Sort와 같은 형태가 된다.
그래서 Shellsort를 Insertion Sort의 확장 버전이라고 이해할 수 있다.
30. Shellsort는 왜 더 빠를 수 있을까?
Insertion Sort의 문제는 큰 값이나 작은 값이 멀리 이동해야 할 때 한 칸씩 이동한다는 것이다.
Shellsort는 큰 h부터 시작하므로 한 번의 교환으로 훨씬 멀리 이동할 수 있다.
Insertion Sort
A B C D E F G H
↑
한 칸씩 이동
Shellsort
A B C D E F G H
↑ ↑
h칸 단위 이동 가능그 결과 마지막 h = 1 단계에서는 배열이 이미 거의 정렬된 상태가 된다.
Insertion Sort는 거의 정렬된 배열에서 효율적이므로 마지막 단계가 빠르게 끝날 수 있다.
강의자료에서는 Knuth의 3x+1 증가 수열을 사용하는 Shellsort가 최악의 경우에도 대략 N^(3/2)에 비례한다고 설명하고 있으며, 추가 메모리를 사용하지 않고 코드도 비교적 작다는 점을 언급한다.
31. 마지막은 Shuffling
정렬과 반대로 데이터를 무작위로 섞어야 하는 경우도 있다.
Shuffling의 목표는 단순히 아무렇게나 섞는 것이 아니다.
강의자료에서는 두 가지 목표를 제시한다.
1. Linear time에 배열을 무작위 permutation으로 만든다.
2. 가능한 모든 순열이 동일한 확률로 등장하도록 한다.즉 공정하게 섞어야 한다.
여기서 Knuth Shuffle을 사용한다.
32. Knuth Shuffle
강의자료의 코드는 다음 구조다.
public static void shuffle(Object[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int r = StdRandom.uniform(i + 1);
Object tmp = a[i];
a[i] = a[r];
a[r] = tmp;
}
}핵심은 현재 위치 i에 도달했을 때
0 ~ i범위에서 임의의 위치 r을 선택한다는 것이다.
그리고
a[i]
a[r]을 교환한다.
각 위치를 한 번씩 처리하므로 전체 반복은 N번이다.
따라서 실행 시간은
O(N)으로 볼 수 있다.
33. 3장을 하나의 흐름으로 보면
처음에는 Queue, Generic, Iterator, 정렬이 왜 한 장에 같이 있는지 조금 뜬금없어 보였다.
하지만 전체를 다시 보면 계속 같은 질문을 하고 있었다.
Queue
→ 데이터를 어떤 순서로 넣고 뺄 것인가?
Generics
→ 같은 자료구조를 여러 타입에 어떻게 안전하게 사용할 것인가?
Iterator
→ 내부 구현을 몰라도 데이터를 어떻게 순회할 것인가?
Bag
→ 순서가 중요하지 않은 데이터는 어떻게 모아둘 것인가?
Stack
→ LIFO 구조를 어디에 활용할 수 있는가?
Two-Stack Queue
→ 기존 자료구조를 조합해서 다른 자료구조를 만들 수 있는가?
Memory
→ 자료구조가 실제로 얼마나 많은 공간을 사용하는가?
Selection Sort
→ 최솟값을 반복해서 선택하면 정렬할 수 있는가?
Insertion Sort
→ 정렬된 영역에 새로운 값을 삽입하면 어떻게 되는가?
Shellsort
→ Insertion Sort의 한 칸 이동 문제를 어떻게 개선할 수 있는가?
Shuffling
→ 데이터를 공정하게 무작위 순서로 만들려면 어떻게 해야 하는가?결국 자료구조와 알고리즘은 단순히 코드를 외우는 문제가 아니었다.
어떤 연산을 빠르게 만들기 위해 무엇을 저장하고, 어떤 비용을 감수할 것인가를 계속 판단하는 과정이었다.
시험 전에 다시 볼 부분
이번 강의자료에서 특히 다시 볼 부분은 Queue의 front/rear, Generic, Iterator 그리고 정렬 코드다.
Queue에서는 다음 문제를 바로 판단할 수 있어야 한다.
Singly Linked List
front만 유지
rear는 유지하지 않음
enqueue → O(N)
dequeue → O(1)Generic에서는
Object 사용
→ casting 필요
→ type mismatch가 runtime에 발견될 가능성
Generics 사용
→ casting 감소
→ type mismatch를 compile time에 발견의 차이를 이해해야 한다.
Iterator에서는
Iterable
→ iterator() 제공
Iterator
→ hasNext()
→ next()관계를 기억한다.
그리고 정렬에서는 특히 다음 차이가 중요하다.
Selection Sort
→ 남은 범위에서 최소값을 찾음
→ 이미 정렬되어 있어도 비교를 계속함
Insertion Sort
→ 왼쪽의 정렬된 영역에 현재 값을 삽입
→ 이미 정렬된 배열에서 매우 적은 작업
→ 역순에서는 많은 비교와 교환
Shellsort
→ h칸 떨어진 데이터부터 정렬
→ h를 줄여가며 배열을 거의 정렬된 상태로 만듦
→ 마지막 h=1에서는 Insertion Sort코드 역시 단순히 외우기보다 각 반복문의 역할을 이해해야 한다.
Selection Sort
i
→ 이번에 확정할 위치
j
→ 오른쪽에서 최소값 탐색
min
→ 현재까지 발견한 최소값의 위치Shellsort에서는
h
→ 비교할 데이터 사이의 간격
j -= h
→ 한 칸이 아니라 h칸씩 왼쪽으로 이동라는 의미를 잡고 있으면 코드를 훨씬 쉽게 읽을 수 있다.
마무리
3장을 공부하면서 가장 중요하다고 느낀 것은 자료구조의 모양 자체보다 왜 그런 구현을 선택하는지 이해하는 것이었다.
Queue에서 front와 rear를 모두 저장하는 이유도 결국 시간 때문이다.
rear 없음
→ enqueue 때 마지막 노드를 찾아야 함
→ O(N)
rear 있음
→ 마지막 위치를 이미 알고 있음
→ 빠르게 삽입 가능Generic도 마찬가지다.
Object
→ 무엇이든 받을 수 있음
→ 대신 casting과 runtime type error 문제
Generic
→ 사용할 타입을 지정
→ compile time에 type 검사Insertion Sort와 Shellsort의 관계도 같은 관점에서 이해할 수 있다.
Insertion Sort의 문제
→ 멀리 있는 데이터도 한 칸씩 이동
Shellsort
→ 처음에는 큰 간격으로 이동
→ 배열을 부분적으로 정렬
→ 간격을 줄임
→ 마지막에는 거의 정렬된 배열에 Insertion Sort 적용결국 이번 장을 관통하는 질문은 이것이라고 생각한다.
“이 연산을 더 효율적으로 만들기 위해 어떤 정보를 추가로 저장하거나, 어떤 처리 순서를 선택해야 할까?”
Queue의 rear 하나부터 Shellsort의 h까지, 서로 달라 보였던 개념들이 결국 이 질문으로 연결됐다.
