[CS] 4-1. 자료구조 - 개요

"이것이 취업을 위한 컴퓨터 과학이다 with CS 기술면접" 책을 참고했습니다.

1. 자료구조 개요

자료구조는 말 그대로 데이터를 어떻게 효율적으로 관리하고 저장할지에 대해서 다루는 부분이다. 다양한 자료구조가 있겠지만, 대표적인 자료구조 위주로 학습할 예정이며 자료구조와 연관된 개념인 알고리즘, 그리고 시간, 공간 복잡도에 대해서도 차근차근 확인해보자.

1-1 자료구조와 알고리즘

앞에서 컴퓨터 구조와 운영체제를 학습하면서 자료구조에 대해서 간접적으로나마 다루었던 내용이 있었다. 예를 들어 메모리 내에 존재하는 스택 영역의 스택이나 CPU 스케줄링에 대해서 설명하면서 스케줄링 큐 같은 개념이 자료구조의 일종이었다.

그렇다면 알고리즘은 무엇일까? 알고리즘은 간단하게 말하면 어떤 목적 달성을 위해 필요한 일련의 연산 절차를 의미한다. 자료구조가 앞에서 말했던 것처럼 데이터를 효율적으로 저장하고 관리하기 위한 방법을 다룬다면, 알고리즘은 그걸 활용해서 어떤 목적 달성을 위해 효율적으로 연산하는 방법을 다룬다고 생각하면 된다. 다만 오늘의 목표는 자료구조이기 때문에 별도로 적지는 않겠지만, 자료구조를 학습하는 과정에서 필요한 알고리즘 개념은 차근차근 설명할 예정이다.

1-2 시간 복잡도와 공간 복잡도

(1) 시간 복잡도

위에서 설명했던 것처럼 자료구조와 알고리즘을 고려해서 코드를 작성한다면 그렇지 않은 코드보다 훨씬 효율적이고 성능이 좋은 코드가 작성될 확률이 높다. 다만 어떤 자료구조와 알고리즘이 현재의 목적에 따라 효율적이고 성능이 좋은지를 판단하는 기준이 뭘까? 그게 바로 시간 복잡도와 공간 복잡도이며, 이 두 복잡도는 소스 코드, 혹은 프로그램이 얼마나 효율적으로 동작하는지를 판단하는 기준이 된다.

 

시간 복잡도란 입력의 크기에 따른 프로그램 실행 시간의 관계를 의미한다. 프로그램의 실행 시간과 입력의 크기는 밀접한 관계가 있는데, 예를 들어보자. 만약 서로 다른 N개의 데이터를 하나씩 검사해서 특정 데이터를 찾는 프로그램이 있다고 한다면, 입력이 1 ~ 10개라면 금방하겠지만, 만약 10억개가 넘는 N개가 있다면 훨씬 오래걸릴 것이다.

시간 복잡도를 표현할 때, 대중적으로는 빅오 표기법이 사용된다. 빅오 표기법은 아래와 같이 사용된다.

O(N) => 입력의 크기 N에 대한 빅오 표기법

빅오 표기법은 함수의 점근적 상한을 표기하는 방법이다. 여기서 점근적 상한은 '입력에 따른 실행 시간의 점근적 상한'을 의미하는데, 점근적 상한은 구체적으로 뭘 의미하는걸까? 예를 들어 입력하는 n 자체가 앞으로 무한히 커진다고 가정할 때, 시간 복잡도의 정의에 따라 실행 시간 역시 점진적으로 증가할 것이다. 하지만 실행 시간의 증가에도 한계가 있을텐데 이를 점근적 상한이라고 한다. 위에 작성한 것처럼 N이라는 입력값에 대해서 그 값이 커지더라도 실행 시간이 대략 이 상한보다는 커지지 않을 것이다 라는 뜻이다. 예를 들어 O(N^2) 이라는 빅오표기법이 있다면 이는 "입력값 N이 증가하더라도 실행 시간의 증가율은 N^2보다는 작다" 라는 뜻으로 해석된다.

빅오 표기법 이외에도 빅 세타 표기법, 빅 오메가 표기법 등이 있는데, 간략히 설명하면 빅 세타는 입력에 대한 평균적인 실행 시간, 빅 오메가는 입력에 대한 실행 시간의 점근적 하한을 의미한다. 예를 들어 θ(N^2) 이면 입력값 N이 증가해도 실행 시간의 증가율은 N^2와 같다라는 뜻이 되고, Ω(N^2) 이면, 입력값 N이 증가하더라도 실행 시간의 증가율은 N^2보다는 크다는 뜻이다.

 

앞에서 설명했던 예시를 기반으로 빅오 표기법에 대해 설명해보자. 앞에서 서로 다른 N개의 데이터를 하나씩 검사해서 특정 데이터를 찾는 프로그램이 있다고 했었는데, 이걸 빅오 표기법으로 작성하면 O(N)이 될 것이고, 이는 데이터를 하나씩 탐색해서 계산한다고 가정할 때 N이 아무리 커진다 하더라도 탐색 과정이 N번 이상을 넘어가지는 않을 것이다. 

빅오 표기법으로 점근적 상한을 표현할 때는 최고차항의 차수만 고려한다. 즉 입력값 N에 대한 실행 시간을 수식으로 작성하면 그 중 최고 차항에 대해서만 고려한다. 이걸 감안하고나서 빅오 표기법으로 표현되는 시간 복잡도 중 자주 표현되는 표기는 다음과 같다.

위 표의 특징과 각각의 시간 복잡도의 특징을 보게 되면 다음과 같다.

• 실행 속도 : O(1) < O(log N) < O(N) < (O(N log N) < O(N^2) < O(2^N) 로 우측일수록 효율이 떨어짐
• O(1) : 입력값이 증가해도 실행 시간은 동일한 경우로, index로 접근해서 바로 처리할 수 있는 연산 과정이 해당한다.
  • stack의 push, pop 같은 기능이 해당.
• O(log N) : 연산이 한 번 수행될 때, 데이터의 크기가 절반 감소하는 알고리즘
  • 이진탐색이나, 트리 형태 자료구조의 탐색이 해당.
• O(N) : 입력값에 따라 실행 시간도 선형적으로 증가하는 경우
  • 1중 for문
• O(N log N) : 입력 데이터가 많아질수록 처리 시간이 로그 배만큼 더 늘어나는 경우로, 데이터가 만약 10개 늘면 처리 시간은 20배가 늘어난다.
  • 퀵, 병합, 힙 정렬이 이에 해당
• O(N^2) : 입력 데이터가 많아질수록 처리시간이 기하급수적으로 늘어남.
  • 이중 for문, 삽입 정렬, 버블 정렬, 선택 정렬 등이 이에 해당.
• O(2^N) : 입력 데이터가 많아질수록 동일하게 처리시간이 기하급수적으로 늘어나는 형태.
  • 피보나치 수열, 재귀의 역기능 등이 이에 해당.

(2) 공간 복잡도

앞에서 알고리즘의 성능 파악을 위한 2가지 대표적인 지표 중 시간 복잡도에 대해 설명했었다. 공간 복잡도는 이름 그대로 프로그램이 실행되었을 때, 필요한 메모리 자원의 양을 의미한다. 어떤 프로그램이더라도 결국 실행되기 위해서는 메모리에 적재되어야 하며, 사용량에 따라 필요한 메모리에 양이 많다면 공간 복잡도가 크다라고 표현한다.

공간 복잡도 역시 시간 복잡도와 동일하게 빅오 표기법을 기반으로 표현하는데, 앞에서는 입력값에 따른 함수의 실행 시간이었다면 공간 복잡도에서의 빅오 표기법이 의미하는 바는 입력에 따라 필요한 메모리 자원의 양에 대한 점근적 상한을 의미한다.

 

주로 알고리즘의 성능을 판단할 때는 시간 복잡도가 프로그램을 수행할 때 더 많이 고려되는 것이 일반적이며, 시간 복잡도와 공간 복잡도는 서로 반비례하는 경향이 있다.

---

여기까지가 자료구조에 대해서 학습하기 위해 필요한 정보들을 간략하게 정리해봤다. 좀 더 깊게 학습해야 될 내용은 별도로 학습하기로 하고, 다음 시간부터는 이제 차근차근 구체적인 자료구조들에 대해서 하나씩 알아보자.

---

참고

[알고리즘] 시간 복잡도와 Big O 표기법