본 글은 누구나 자료 구조와 알고리즘 (제이 웬그로우 저, 길벗 출판)을 읽고 공부한 내용을 나름대로 정리하였습니다. 내용은 직접 책을 구매하시어 읽어보시는 것을 추천합니다.
1. 자료구조의 필요성
컴퓨터로 우리가 하는 일은 무엇일까요? 사무에서는 보고서를 작성하거나 자료를 정리하고, 학생은 발표를 위해 PPT를 작성합니다. 여가시간에는 게임을 하기도 하고 유튜브를 보기도 합니다. 이런 일들은 모두 어딘가에 데이터를 저장하거나 어딘가로부터 불러오는 일이 필요합니다.
아주 적은 양의 데이터를 저장하거나 불러오는 것은 간단합니다. 하지만 데이터의 양이 점점 많아지면 많아질수록 이를 처리하는 데 필요한 시간과 사용하는 메모리는 점점 늘어납니다. 우리는 시간이 부족하고 메모리를 사기엔 돈이 부족하죠. 그래서 같은 데이터를 처리하더라도 좀 더 빠르고 확실하게 처리하고 싶습니다. 즉 데이터 처리를 좀 더 효율적으로 만들 필요가 있습니다.
자료구조는 데이터를 처리하는 데 있어서 어떻게 하면 좀 더 효율적으로 처리할 수 있을지를 고민한 결과물입니다. 우리가 이를 알고 이용한다면 한정된 시간과 컴퓨팅 자원을 가지고 좀 더 빠르고 효율적인 결과물을 내놓을 수 있을 것입니다.
2. 연산
자료구조는 데이터를 처리하기 위한 일종의 작업이 필요합니다. 이를 연산(Operation)이라고 합니다. 연산은 대표적으로 다음과 같이 4가지로 정리할 수 있습니다.
- 읽기: 데이터를 자료구조로부터 읽어내는 것
- 검색: 데이터를 자료구조에서 찾아내는 것
- 삽입: 데이터를 자료구조로 넣는 것
- 삭제: 데이터를 자료구조로부터 지우는 것
3. 시간 복잡도와 공간 복잡도
우리가 책장정리를 한다고 가정해 봅시다. 책장 정리할 때 해야 할 일은 무엇일까요? 큰 일을 벌일 마음가짐도 필요하겠지만 책장을 정리할 시간과 책이 있을 공간이 필요합니다. 우리가 책장을 정리하는 것과 같이** 데이터를 정리(= 처리)하기 위해서도 역시 시간과 공간이 필요**합니다. 데이터 처리를 책장정리로 대입하여 설명하면 아래와 같습니다.
- 데이터를 정리할 시간 (= 책장을 정리할 시간)
- 데이터가 존재할 공간 (= 책이 존재할 공간)
자료구조는 각자의 목적에 맞게 데이터를 처리합니다. 그렇다면 우리는 어떤 자료구조가 데이터를 처리하는 데 있어 도대체 얼마나 많은 시간과 공간을 사용하는지 알고 싶어집니다. 데이터를 처리하는 데 얼마나 많은 복잡함을 요구하느냐는 것을 시간 복잡도와 공간 복잡도라는 단어로 표현합니다.
시간 복잡도와 공간 복잡도를 통해 어떤 자료구조가 어떤 상황에 맞는지를 알아보고, 우리는 각 상황에 맞춰 프로그래밍을 하면 됩니다.
4. 빅-오 표기법
시간 복잡도와 공간 복잡도는 어떻게 측정할 수 있을까요? 프로그램을 돌려놓고 타이머로 시간을 재면 될까요? 그 시간 동안 얼마나 많은 메모리를 썼는지를 확인하면 될까요? 이런 방식으로 측정하면 측정 시점의 데이터수에 따라, 혹은 컴퓨터 환경(예를 들면 CPU나 메모리)에 따라 결괏값이 들쭉날쭉해질 것입니다.
그래서 이를 정량화하기 위해 빅-오 표기법(Big-O notation)이라는 것을 사용합니다. 빅-오 표기법을 이용하여 시간 복잡도를 표현할 때는 얼마나 많은 처리 단계가 존재하는가를, 공간 복잡도를 표현할 때는 얼마나 많은 공간(변수나 배열 같은 메모리 공간)을 사용하는가를 표현할 수 있습니다.
O( [처리 단계를 표현하는 식] )
그럼 한 번 어떤 빅-오 표기법이 존재하는지 살펴 보겠습니다. 주로 시간 복잡도를 위주로 살펴보겠습니다.
int multiply(int a) {
return a * 10; // 처리단계
}위의 예제를 확인해보겠습니다. 위의 함수는 int형의 인자를 받아서 단순히 10을 곱합니다. 이를 표로 표현하면 다음과 표현할 수 있습니다.
| 인자 | 결과값 | 처리 수 |
|---|---|---|
| 1 | 10 | 1 |
| 2 | 20 | 1 |
| 100 | 1000 | 1 |
| 999 | 9990 | 1 |
| N | N * 10 | 1 |
인자는 단 하나이고 처리단계도 단 하나입니다. 따라서 이 힘수는 빅-오 표기법으로 다음과 같이 표현합니다.
O(1)
int sum(int[] numbers) {
int sum = 0;
for (int num : numbers) { // 배열에서 숫자 꺼내기
sum += num; // 꺼낸 숫자를 더하기
}
return sum;
}위의 함수는 numbers라는 int형의 배열을 인수로 받아 안에 있는 숫자를 전부 더하여 결과로 내놓습니다. numbers의 개수가 늘어나면 늘어날수록 더해야 할 것이 늘어납니다. 이를 표로 표현하면 다음과 같습니다.
| 인자 | 결과값 | 처리 수 |
|---|---|---|
| [ 1 ] | 1 | 2 |
| [ 1, 2 ] | 3 | 4 |
| [ 1, 2, .. , 10 ] | 55 | 20 |
| [ 1, 2, .. , 999 ] | 499500 | 1998 |
| [ 1, 2, .. , N ] | (N^2 + N) / 2 | 2N |
인자의 배열이 늘어나면 늘어날수록 처리단계가 균등하게 늘어나게 됩니다. 한 번의 루프당 처리단계가 2번이므로 이를 빅-오 표기법으로 표현하면 다음과 같습니다.
O(2N) = O(N)
void sort(int[] src) {
for (int cnt = src.length - 1; cnt > 0; cnt--) {
for (int si = 0; si < cnt; si++) {
if (src[si] > src[si + 1]) { // 배열로부터 자료 꺼내기 & 자료 비교 (단계 1)
int tmp = src[si]; // 변수에 자료 복사 (단계 2)
src[si] = src[si + 1]; // 한 공간에서 다른 공간으로 자료 복사 (단계 3)
src[si + 1] = tmp; // 변수로부터 자료 복사 (단계 4)
}
}
}
}위의 함수는 1차원 배열을 인수로 받아서 정렬하고 있습니다. 내부에서 루프가 중첩되어 있어서 내부 루프 안의 처리단계가 외부 루프 한 번에 cnt만큼 돌아가고 있습니다. 위를 표로 표현하면 다음과 같습니다.
| 인자 | cnt의 경우의 수 | 처리 수 |
|---|---|---|
| [ 1 ] | [] | 4 * 0 = 0 |
| [ 2, 1 ] | [ 1 ] | 4 * 1 = 4 |
| [ 5, 4, .. , 1 ] | [ 4, 3, 2, 1 ] | 4 * (4 + 3 + 2 + 1) = 40 |
| [ 10, 9, .. , 1 ] | [ 9, 8, .. , 1 ] | 4 * (9 + 8 + .. + 1) = 180 |
| [ N, N - 1, .. , 1 ] | [ N - 1, N - 2, .. , 1 ] | 4 * ( (N - 1) + (N - 2) + .. + 1 ) = 2N^2 - 2N |
인자의 배열이 늘어나면 늘어날수록 처리단계를 급격하게 2차원 곡선을 그리며 올라갑니다. 표의 제일 아래와 같이 N개의 배열이 인자로 주어진다면 처리할 단계는 2N^2 - 2N개를 처리해야 합니다. 이를 빅-오 표기법으로 표현하면 아래와 같습니다.
O(2N^2 - 2N) = O(N^2)
int findIndex(int[] sortedArray, int value){
int result = -1;
int begin = 0;
int end = sortedArray.length;
int idx = (end - begin) / 2;
while (begin <= idx && idx < end) {
// 인덱스의 값을 가져오기 (단계 1)
int s = sortedArray[idx];
// 찾으려는 값과 같다면 결과값으로 준비 (단계 2)
if (s == value) {
result = idx;
break;
}
// 인덱스 값보다 찾으려는 값이 크면 end에 인덱스 복사(단계 3)
if (s > value) end = idx;
// 인덱스 값보다 찾으려는 값이 작으면 begin에 인덱스 + 1 복사(단계 4)
else begin = idx + 1;
// idx를 새로 정의 (단계 5)
idx = begin + (end - begin) / 2;
}
return result;
}위의 함수는 정렬된 1차원 배열과 int형 값을 인자로 받아 int형 값과 같은 값이 존재하는 배열칸의 인덱스를 결괏값으로 내놓습니다. 값을 찾고자 하는 범위를 반씩 나누어 찾기 때문에 배열을 한 칸씩 도는 것보다 빠르게 찾을 수 있습니다. 위를 표로 표현하면 다음과 같습니다.
1) sortedArray의 갯수를 고정한 경우
| 인자1 (sortedArray) | 인자2 (value) | [ begin, end ]의 순서 | 처리 수 |
|---|---|---|---|
| [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] | 6 | [ 0, 10 ] | 5 * 1 |
| [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] | 3 | [ 0, 10 ], [ 0, 5 ] | 5 * 2 |
| [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] | 1 | [ 0, 10 ], [ 0, 5 ], [ 0, 2 ], [ 0, 1 ] | 5 * 4 |
| [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] | 99 | [ 0, 10 ], [ 6, 10 ], [ 9, 10 ] | 5 * 3 |
2) value를 고정한 경우
| 인자1 (sortedArray) | 인자2 (value) | [ begin, end ]의 순서 | 처리 수 |
|---|---|---|---|
| [ 1, 2, 3, 4, 5 ] | 2 | [ 0, 5 ], [ 0, 2 ] | 5 * 2 |
| [ 1, 2, .. , 10 ] | 2 | [ 0, 10 ], [ 0, 5 ], [ 0, 2 ] | 5 * 3 |
| [ 1, 2, .. , N ] | 2 | [ 0, N ], [ 0, N / 2 ], [ 0, N / 2^2 ], .. , [ 0, 2 ] | 5 * log2 N |
배열의 범위를 반씩 나누게 되므로 배열의 전체 갯수가 많아지더라도 처리에 필요한 숫자는 급격하게 줄어듭니다. 이를 빅-오 표기법으로 표현하면 아래와 같습니다.
O(5 * log2 N) = O(log N)
위 그래프는 데이터 수(n)에 따라 얼마나 복잡도(N)가 높아지는지 보여주고 있습니다. 보면서 아셨겠지만 빅-오 표기법은 계수와 낮은 차수의 항에 대해서는 생략합니다. 즉 항이 제일 높은 것만 살려두시면 됩니다.
지금까지 각각의 자료구조를 알아보기 이전에 필요한 내용을 살펴보았습니다. 다음 글부터는 자료구조를 하나씩 살펴보려고 합니다.
댓글