프로그래밍을 배우다보면은 생각지도 못한 배울 것들을 만나게 된다.
특히 점점 심화된 개념을 배우면 배울수록, 코드를 어떻게 짜야할 지 넓은 관점에서 생각하게 한다.
처음 프로그래밍을 배웠을 때는, if문과 for문만 있으면 세상 모든 문제를 다 풀수만 있을 것 같았다.
물론 지금도 for문과 if문을 엄청 자주 쓰지만, 사실 중요한건 단순히 문제를 해결하느냐가 아니고
어떤 방식으로 문제를 해결하느냐가 중요한 것같다.
그런 관점에서 자료구조의 개념은, 문제를 조금 더 넓은 시각에서 볼 수 있게 해주는 것 같다.
각각의 장단점을 가진 여러 자료구조를 문제 해결방식의 하나로 쓰면서, 어떤 코드가 조금 더 효율적일까를 고민하게 만들어준다.
따라서 자료구조는 조금 더 전문적인 프로그래밍 지식을 원한다면, 꼭 알아둬야 할 지식이다.
자료구조(Data Structure)
자료구조란 간단하게 말해서, 자료를 어떻게 저장할 것인가에 관한 개념이다.
우리 주변에는 아주 많은 자료구조들을 만날 수가 있다.
은행에서 번호표를 뽑으면, 대기번호 74번이라고 적힌 종이를 뽑고 자리에서 대기한다.
'나'는 은행 창구 대기자 명단 자료구조의 '74번' 데이터로 저장 된 것이다.
또 어떤 줄서서 기다리는 맛집 가게에서는, 내 휴대폰번호 뒷자리를 적어 대기명단을 작성한다.
나는 맛집의 대기명단 자료구조에서 내 휴대폰 번호 뒷자리의 데이터로 저장 된 것이다.
가장 기본적인 자료구조에는 스택과 큐가 있다.
스택(Stack)
스택은 쌓는다는 뜻이다.
자료를 저장할 때, 바닥에서부터 하나씩 위로 쌓아올린다고 생각하면 된다.
책을 밑에서부터 한 권씩 쌓는다고 가정해보자. 책을 다시 빼내려면, 다시 위에서부터 한 권 씩 빼내야 한다.
그게 스택의 기본 구조다.
스택은 자료를 아래에서부터 하나씩 추가하고, 제거할 때는 위에서부터 하나씩 제거할 수가 있다.
이를 후입선출(LIFO, Last-In First-Out)의 구조라고 한다.
여기서 자료를 추가하는 것을 push라고 하며, 반대로 자료를 제거하는 것을 pop이라고 한다.
자바스크립트에서 배열 메소드 중 .push(), .pop()이라는 메소드가 바로 이를 표현한 메소드인 것이다.
프로그래밍에서도 스택의 자료구조가 이따금씩 쓰이곤 한다.
예를 들어, 자바스크립트의 함수 호출구조는 콜스택(Call Stack)으로 표현된다.
어떤 함수가 실행될 때 마다, 콜스택에 함수에 관한 정보가 담긴 스택이 담기고 함수가 실행된다.
그리고 함수가 다 실행되고나면 콜스택에서 함수에 관한 정보가 하나씩 빠져나간다.
이것이 대표적인 스택의 예시이다.
그리고 뒤로가기(Ctrl + Z), 앞으로 가기 기능(Undo, Redo Mechanism)도 스택으로 구현할 수가 있다.
우리가 작업을 실행할 때마다, 스택에 작업 내용이 쌓인다. 그리고 뒤로가기를 하면은 위에 있는 가장 최근에 실행 작업들이 취소되는 것이다.
큐(Queue)
큐는 줄을 서다, 줄이라는 뜻이다.
리그오브레전드(롤)를 할 때, 또는 롤을 하는 주변 사람들을 볼 때 게임 매칭을 하면서 '큐 잡는다'는 얘기를 많이 들어보았을 것이다.
만약에 게임 매칭을 할 때, 먼저 게임 매칭 버튼을 누른 사람이 먼저 잡힐 것이다.
안그러면 제일 먼저 매칭 버튼을 누른 사람이 제일 마지막에 매칭이 되는 불공정한 일이 일어날 것이다.
위에서 설명한 은행 창구의 번호표나 맛집의 대기명부도 마찬가지이다. 먼저 번호표를 뽑은 순서대로, 명부를 작성한 순서대로 빠져나갈 수가 있다.
이와 마찬가지로, 가장 먼저 들어온 자료구조가 가장 먼저 나가는 것이 큐이다.
이를 선입선출(FIFO, First-In First-Out)의 구조라고도 한다.
큐에서 자료를 추가하는 것을 Enqueue, 자료를 삭제하는 것을 Dequeue라고 한다.
큐가 프로그래밍에서 쓰이는 예는, 우선순위가 같은 작업을 처리할 때 보통 먼저 예약된 작업이 먼저 실행된다.
프린터가 먼저 예약된 프린트를 하는 것과 같다. 이 때 큐가 쓰이게 된다.
그리고 자바스크립트에서 비동기 작업을 처리할 때 쓰는 Callback Queue라는 개념이 있는데, 이 때도 Queue가 쓰이게 된다.
연결 리스트(Linked List)
연결 리스트는 자료구조의 전체 정보를 저장하지 않는다.
단지 맨 처음 노드의 하나만을 알고 있을 뿐이다. 다만 맨 처음의 노드는 그 다음의 노드를 알고 있다.
그리고 그 다음 노드도 다음에 오는 노드를 알고 있다.
만약 어떤 학교의 한 반에서 학생들을 줄세우는 경우를 생각해보자.
물론 줄을 어떻게 서야할 지 전체 명단을 갖고있어도 되지만, 간단하게 자기 다음 학생이 누구인지만 기억하라고 할 수도 있다.
맨 처음의 학생만 알면은, 자기 다음 학생을 계속 알고있을테니 줄을 설 수가 있다.
이렇게 한 노드가 자기 다음의 노드를 알고있는 경우를 연결리스트 구조라고 한다.
연결리스트에서 가장 앞의 노드를 head, 가장 마지막 node를 tail이라고 한다. tail의 next(다음 노드)는 null을 가리키게 될 것이다.
연결 리스트의 대표적인 예시로는, 웹 브라우저의 방문 기록을 들 수가 있다.
웹 브라우저의 방문 기록은 연결 리스트의 형식으로 저장되어서, 하나의 방문 기록이 이전 방문 기록을 갖고 있는 것이다.
그래서 이전 버튼을 누를 때 방문 기록에 있는 이전 방문 기록으로 뒤로 가기를 할 수 있는 것이다.
시간 복잡도(Time complexity)와 Big O 표기법(Big O Notation)
지금까지 세 개의 자료구조를 알아보았다. 자료구조는 설명했던 것보다 더 많다. 가장 기본이 되는 개념만 소개하였다.
그렇다면 이 자료구조의 효율성을 어떻게 판단할 수 있을까. 자료구조가 얼마나 효율적인지, 무엇이 더 효율적인지를 알아야 프로그램에서 제대로 써먹을 수가 있다.
바로 자료 구조에서 어떤 동작을 할 때의 시간 복잡도로 판단할 수가 있다.
시간 복잡도란 어떤 동작에 대해, 그것이 실행 시간과의 연관성을 나타낸 것이다.
예를 들면 어떠한 환경에서도 일정한 시간동안 동작하는 일이 있을 것이고,
아니면 여러 환경이나 변수에 따라 시간이 일정하게 늘어나거나, 혹은 가파르게/완만하게 늘어날 수도 있다.
이것을 이것을 나타낸 것이 시간 복잡도이며, 이 시간 복잡도를 표현할 때는 보통 Big O 표기한다.
Big O 표기법은 시간 복잡도를 표현하는 다양한 방법 중에 하난데, 가장 대표적인 표기법이다.
표기하는 방법은 대문자 O와 ()(소괄호를 적고) 안에 시간 복잡도를 쓰면 된다.
예를 들어, 어떠한 환경에서도 일정하게 진행하는 동작은 Big O 표기법으로 O(1)이다.
예를 들어, 배열에 값을 .push()를 이용해서 넣는다고 생각해보자.
배열의 길이가 10이든 1000이든 상관없이, .push()는 항상 같은 속도의 연산을 실행할 것이다.
O(n)의 경우도 있다.
O(n)이 되는 경우는 보통 반복문을 사용할 때 이다.
만약 배열의 각 요소에 1씩을 더하는 작업을 해준다고 생각해보자.
그러면 배열의 처음부터 끝까지 한 번씩 순회해서 1을 더해주어야한다.
배열의 크기가 10이면 10번의 동작을 수행하고, 1000이면 1000번의 동작을 수행한다.
이렇듯 n의 크기가 증가할 수록, 일정하게 연산시간이 증가하는 경우 O(n)으로 표기한다.
O(n^2)도 있을 수 있다. 가장 쉽게 만나볼 수 있는 경우는 이중 반복문을 사용할 때다.
어떤 반복문 내에서 그 배열을 또 반복하게 되면은, 연산 동작이 제곱이 될 것이다.
예를 들어서 가장 대표적인 이중 반복문인 구구단을 예시로 생각해보자.
n인 숫자를 1단부터 n까지 n단 호출하라고 하면, 이렇게 해야할 것이다.
const timesTable = function (num) {
for (let i = 1; i <= num; i++) {
for (let j = 1; j <= num; j++) {
console.log(`${i} x ${j} = ${i * j}`)
}
}
}
timesTable(3); /* "1 x 1 = 1"
"1 x 2 = 2"
"1 x 3 = 3"
"2 x 1 = 2"
"2 x 2 = 4"
"2 x 3 = 6"
"3 x 1 = 3"
"3 x 2 = 6"
"3 x 3 = 9" */이렇게 이중반복문을 호출해서 말이다.
만약 n이 100이라면 10000번의 연산을 한다. 1000이라면? 1000000의 수행을 한다.
이렇게 n^2인 경우에는 n의 크기(여기서는 숫자의 크기, 아니면 배열의 길이도 될 수 있다)가 커질 수록 n이 급격하게 커진다.
그래서 코드를 작성할 때 주의해서 작성해야 한다.
그렇다고 해서 O(1)의 시간 복잡도를 가지는게 무조건 좋을까?
꼭 그렇지만은 않다.
시간 복잡도는 O(1)이지만, 연산하는데 굉장히 많은 코드가 들어간다고 생각해보자.
시간 복잡도는 분명 간단하게 O(1)로 가질 수 있지만, 애초에 구동 시간 자체가 큰 경우라면 오히려 다른 방법이 효율적일 수도 있다.
프로그래머는 상황에 맞는 적절한 시간 복잡도를 생각하고 구성하는 것이 중요하다.
자료구조의 시간 복잡도
이제 각 자료구조의 시간 복잡도를 생각해보자.
사실 자료구조에 시간 복잡도가 있는 것이 아니라, 자료구조에서 실행하는 동작의 시간 복잡도를 생각해보아야한다.
자료구조에서의 기본적인 동작인 삽입(insertion), 삭제(deletion), 검색(search) 작업의 각각의 시간 복잡도를 계산해보자.
Stack의 경우
우선 스택에 새로운 데이터를 추가하는 것은 자료 구조의 크기와 상관없이 항상 일정하다. 그래서 O(1)의 시간 복잡도를 가진다.
삭제하는 것도 마찬가지이다. 맨 마지막의 데이터 하나를 삭제하기만 하면 된다. 마찬가지로 O(1)의 시간복잡도를 가진다.
반면 검색을 하는 경우, 어떤 스택 내에 특정 데이터를 찾을 때 모든 요소를 한 번씩 찾게된다.
물론 검색 중에 일치하는 데이터를 찾은 경우가 있을 수 있다. 하지만 Big O 표기법은 최악의 경우의 시간 복잡도를 표기한다.
그래서 스택의 가장 마지막에 데이터가 있는 경우 혹은 없는 경우에는 스택을 전부 순회해야하기 때문에, 스택의 크기가 커질수록 동작이 많아지게 된다. 그래서 O(n)의 시간 복잡도를 가지게 되는 것이다.
Queue의 경우
큐도 마찬가지로 데이터를 추가하고 삭제하는데 항상 일정한 시간이 든다. 맨 뒤에 값을 추가하고, 맨 앞의 값을 삭제해주기만 하면 된다.
그래서 삽입과 삭제가 둘 다 O(1)의 시간 복잡도를 가진다.
그리고 큐도 스택과 마찬가지로, 검색을 할 때 전 요소를 순회해야만 한다. 그래서 O(n)의 시간 복잡도를 가지게 된다.
Linked List의 경우
연결 리스트에서 데이터를 삽입할 때는(위 그림처럼 E 노드를 삽입할 경우), B 노드의 다음 노드가 E노드를 가리키도록 한다. 그리고 E노드의 다음 노드는, B노드의 다음 노드였던 C노드를 가리킨다.
예시는 중간에 삽입하는 경우가 나왔지만, 사실 head에 삽입하는 것도 동일하다. 기존의 관계를 끊고, 새로운 데이터와의 관계를 추가해준다. 항상 동일하게 O(1)의 시간 복잡도를 가질 것이다.
데이터를 삭제하는 것도 비슷하다. 다음 노드를 그 다음 노드를 가리키게 한 후, 노드 데이터를 삭제하면 된다.
항상 동일하게 O(1)의 시간 복잡도를 가질 것이다.
검색하는 경우는 어떨까? 우선 head의 데이터와 비교해보고, 일치하지 않으면 다음 노드. 그 다음 노드도 일치하지 않으면 그 다음 노드.
이런 식으로 최악의 경우 가장 끝의 노드까지 탐색할 것이다. O(n)의 시간 복잡도를 가지게 된다.
셋 다 삽입과 삭제는 O(1), 검색은 O(n)이 나왔다.
앞으로 올릴 자료구조에서도 마냥 이렇게 같은 시간 복잡도가 나오지는 않는다.
우리가 평소에 코드를 짤 때에도, 시간 복잡도를 한 번 생각해보면서 짜보자.
그러면 어떤 방식이 조금 더 효율적일 수 있는 지 비교해볼 수 있다.
'자료구조' 카테고리의 다른 글
| Tree - 깊이 우선 탐색, 너비 우선 탐색, Binary Search Tree (0) | 2022.04.28 |
|---|---|
| Hash Table - Hash Table과 충돌, 충돌 해결 기법 (0) | 2022.04.27 |