자료구조란? (feat. 시간복잡도, 공간복잡도)

목차
1. 자료구조(Data Sturcture)란?
  1-1. 자료구조의 종류
2. 시간복잡도와 공간복잡도
  2-1. 시간복잡도(Time complexity)
  2-2. 공간복잡도(Space complexity)
    2-2-1. 빅오표기법(Big Oh)

1. 자료구조 (Data Structure)란?

자료구조(Data Structure)를 알아보기 앞서, 우선 자료(Data)는 무엇일까요? 우리가 학교에서 조별과제를 한다고 가정해보겠습니다. 그러면 발표를 하기 위해 자료조사를 해야겠죠? 조별과제를 할 때, 발표자와 PPT담당자를 제외한 나머지 팀원들은 보통 자료조사를 하여 PPT담당자에게 보내줍니다. 그러면 PPT담당자는 자료들을 취합해서 보기 좋게 정리한 뒤에 발표자료를 만들죠.

 

보노보노 PPT.. 눈이 아프시다면 빠르게 스크롤을 내려주세요...

 

결국 '자료(data)'라는 것은 문자, 숫자, 소리, 그림, 영상 등 현실세계에서 수집한 아직 가공되지 않은 사실이나 개념을 의미하죠. 그리고 컴퓨터 세계에서는 이러한 것들이 전부 다 컴퓨터 언어로 변환이 가능한 특정 값 또는 이들의 집합으로 이루어져있습니다.

 

그렇다면, 이렇게 수집한 자료(data)를 실생활에 활용을 하려면, 위에서 PPT를 만든 것처럼 일정한 규칙이나 규격을 적용해서 조직적, 체계적으로 나열하고, 구분을 해야겠죠? 컴퓨터 세계에서는 이렇게 가공되어있지 않은 자료(data)들을 목적에 맞게 활용할 수 있도록, 형태를 구분하고, 분류할 수 있는 구조(Structure)들있습니다. 그 구조들은 프로그래밍 언어를 통해 다 구현이 되어있죠.

 

(여기서부터는 편의상 '컴퓨터 세상의 자료(data)'를 '데이터'라고 말하겠습니다.)

 

그 구조가 바로, 자료구조(Data Structure)입니다. 즉, 자료구조란 컴퓨터가 데이터를 효율적으로 구성, 저장하고, 처리, 조작을 하기 위한 방법을 의미하는 것이죠. 예를 들어, 만약에 우리가 숫자를 컴퓨터에 저장하려고 한다면, 자료구조를 사용해서 이 숫자를 어떤 방식으로 저장하고 처리할지를 정할 수 있습니다. 

 

 

1-1. 자료구조의 종류

자료구조의 종류는 대표적으로 배열(Array), 링크드 리스트(Linked List), 스택(Stack), 큐(Queue), 트리(Tree), 그래프(Graph)가 있습니다.

 

가장 기본적인 자료구조는 배열입니다. 배열은 같은 종류의 데이터를 연속적인 메모리 공간에 저장하는 방법입니다. 예를 들어, 만약에 1,2,3,4,5라는 다섯개의 숫자를 저장하려면, 배열을 사용해서 1,2,3,4,5의 숫자를 입력순으로 순서대로 저장할 수 있습니다. 

 

링크드 리스트는 기차와 같이 한칸한칸 연결된 형태로 만들어진 구조입니다. 그래서 1,2,3,4,5 숫자가 순서대로 들어와도 내 마음대로 중간에 있는 '3'이라는 숫자를 빼고, 다시 넣고를 할 수 있죠. 스택은 박스 안에 책을 차곡차곡 쌓고, 뺄 때는 위에서부터 뺄 수 있는 것처럼, 데이터를 한쪽 끝에서만 넣고 뺄 수 있는 구조입니다. 큐는 놀이동산 대기줄 처럼, 데이터를 한쪽 끝에서는 넣고, 반대쪽 끝에서는 뺄 수 있는 구조입니다. 트리는 나무 줄기처럼, 데이터를 계층 구조로 저장하는 구조입니다. 마지막으로 그래프는 거미줄 형태로 각 데이터마다 서로 연결할 수 있는 형태로 만들어진 구조입니다.

 

이처럼 여러가지 종류의 자료구조를 선택하여 데이터를 저장하고, 처리할 수 있죠. 이러한 자료구조들을 사용하면 컴퓨터에서 데이터를 더욱 빠르고 효율적으로 처리할 수 있고, 어떤 자료구조를 사용하느냐에 따라 프로그램의 성능이 크게 달라질 수 있습니다. 

 

컴퓨터공학에서의 자료구조를 배울 때 목표는 스택, 큐, 트리, 그래프 총 4개의 자료구조를 충분히 이해하는 것입니다. 이 글부터 시작해서 앞으로 총 4개의 파트에 걸쳐서 자료구조를 설명드리겠습니다.

1) 자료구조 개념 및 고려사항(시간복잡도, 공간복잡도)

2) 어레이, 링크드리스트, 스택, 큐 자료구조

3) 알고리즘: 정렬 알고리즘, 서칭 알고리즘

4) 트리, 그래프 자료구조

 

---

2. 시간복잡도(Time complexity)와 공간복잡도(Space complexity)

위에서 어떤 자료구조를 사용하느냐에따라 프로그램의 성능이 크게 달라진다고 했었죠? 자료구조를 선택해야할 때 가장 크게 고려해야할 사항이 있습니다. 바로, 시간복잡도(Time complextity)와 공간복잡도(Space complexity)입니다. 이 두 가지의 개념이 가장 중요한 이유는 코드의 효율성을 수치화하여 가장 잘 나타낼 수 있는 지표이기 때문이죠.

 

1) 시간 복잡도(Time complexity): 프로그램이 실행되고, 완료되는데 걸리는 시간(이론적으로 계산할 수 있는)

2) 공간 복잡도(Space complexity): 프로그램이 실행되고, 완료되는데 필요한 메모리

 

실행 시간과 메모리 사용량은 프로그래밍이 있어서 한정적 자원(computing resource)입니다.(물론 하드웨어의 발전으로 인해 옛날 보다는 한정적이지 않긴 합니다.) 때문에 이를 효율적으로 활용해야하죠. 

 

 

2-1. 공간 복잡도(Space Complexity)

공간 복잡도는 코드의 효율성을 수치화할 수 있는 지표라고 말씀드렸습니다. 프로그램을 실행하면, 데이터들이 RAM이라는 메모리에 올라가게 되는데, 이때 메모리의 크기는 고정이 되어있습니다. 즉, 메모리를 최대한 덜 잡아먹을 수 코드를 설계해야할 텐데요. 그렇게 설계한 코드의 공간복잡도를 계산하는방법은 고정공간 요구량과 가변공간 요구량의 덧셈으로 구할 수 있습니다.

 

1) 고정 공간 요구량(Fixed space requirements): 자료구조가 사용하는 고정된 메모리 공간을 의미합니다. 고정된 크기를 갖는 변수(int, double)가 여기에 포함되며, 크기가 정해진 배열의 경우에도 고정 공간 요구량에 속합니다.

2) 가변 공간 요구량(Variable space requirements): 필요에 따라 동적으로 할당, 해제되는 메모리의 공간을 의미합니다. 특정 instance에 따라서 사이즈가 달라지는 변수들이 여기에 속합니다.

 

 

2-2. 시간 복잡도(Time Complexity)

시간 복잡도는 컴파일타임(Complie Time)과 러닝타임(Excution&Running Time)으로 나뉩니다. 실행시간은 컴퓨터 사양이나, 네트워크 환경 등에 따라서 달라질 수 있는 부분이기 때문에 변수가 너무 많습니다. 그래서 우리는 컴파일 시간의 복잡도만 계산하면 됩니다.

 

for문으로 구구단을 1단부터 9단까지 나오게끔 코드를 짜면, 코드가 9 x 9 = 81번, 즉 9의 2승 만큼 실행이 됩니다. 그럼 N단이 나오는 코드를 짜면 어떤 값이 나올까요? N^2의 값이 나올 겁니다. 이렇게 사용하는 데이터 개수(N)에 의해서 시간복잡도가 정해집니다. 

 

2-2-1. 빅오 표기법(Big Oh)

빅오 표기법은 알고리즘을 수학적으로 표기해주는 표기법입니다. 알고리즘의 시간과 공간 복잡도를 표현할 수 있죠. 빅오 표기법은 알고리즘의 실제 러닝타임을 표기하는 것이라기 보다는 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 게 목표이기 때문에 상수와 같은 숫자들은 모두 1이 됩니다. 

 

이 때, 최대로 걸릴 수 있는 상한시간, 즉 최악의 경우(worst case)를 가장 먼저 고려하는 경우가 대부분인데요. 이 때, 최악의 경우를 Big Oh라고 나타냅니다.(Big Ω는 최선의 경우, Big Θ은 평균의 경우. 사실상 Bih Oh만 쓴다고 보면 됨.)

 

기본적으로 알아두어야할 빅오 표기법의 예(best case -> worst case 순)

 

• O(1): 데이터가 증가함에 따라 성능의 변화가 없다.
• O(log N): 데이터가 증가해도 처리시간이 딱히 늘어나지 않는다. 
• O(N): 입력 데이터의 크기에 비례해서 처리시간이 늘어난다. 
• O(N^2): 데이터가 늘어남에 따라 N x N ,즉 N 값의 정사각형 면적 수치만큼 늘어난다. 처음에는 조금씩 상승하다가 나중에 가면 데이터를 하나 추가할 때마다 처리시간이 수직상승한다. 
• O(N^3): 데이터가 늘어남에 따라 N x N x N, 즉 N 값의 큐빅 부피만큼 처리시간이 늘어난다. N^2와 비슷한 양상이지만, 데이터가 추가될 때마다 훨씬 빠르게 처리시간이 늘어난다. 
• O(2^N): 데이터가 늘어남에 따라 피포나치 수열만큼 처리시간이 늘어난다. 데이터의 즈악에 따라 처리시간이 N^3보다도 훨씬 빠르게 들어난다