한빛출판네트워크

자료구조(Data Structure)는 개발자가 데이터를 효율적으로 사용할 수 있도록 정리하는 방법을 말합니다. 각각의 자료구조에는 장단점이 있으므로 어떤 자료구조가 최선일지는 해결하고자 하는 문제의 종류와 어떤 부분을 우선적으로 최적화할지에 따라 달라질 수 있습니다. 

✅자료구조의 큰 그림

자료구조^{data structure}는 이름 그대로 어떠한 구조로 데이터를 다룰지에 대해 학습하는 과목입니다. 자료구조란 무엇인지, 그와 연관된 과목인 알고리즘이란 무엇인지, 자료구조와 알고리즘을 판단하는 척도인 시간 복잡도와 공간 복잡도가 무엇인지 확인해 보겠습니다. 

• 자료구조와 알고리즘

컴퓨터 구조와 운영체제에 대해 공부를 해보셨다면 자료구조를 직간접적으로 살펴보셨을텐데요, 메모리 내에 존재하는 스택 영역의 ‘스택’과 스케줄링 큐의 ‘큐’도 자료구조의 일종입니다.

자료구조와 더불어 함께 학습하면 좋은 과목이 있습니다. 바로 알고리즘입니다. 알고리즘^algorithm은 어떠한 목적을 이루기 위해 필요한 일련의 연산 절차를 의미합니다. 자료구조가 데이터를 효율적으로 저장하고 관리하기 위한 방법을 다룬다면, 알고리즘은 어떤 목적을 이루기 위한 효율적인 연산 방법을 다룬다고 볼 수 있습니다. 이트리의 순회, 깊이 우선 탐색, 너비 우선 탐색, 최단 경로 알고리즘과 같이 중요한 알고리즘 개념은 알아두면 좋습니다.

자료구조와 알고리즘은 전혀 다른 개념처럼 보이지만, 둘 사이에는 깊은 연관성이 있습니다. 어떤 자료구조가 사용되었느냐에 따라 사용 가능한 알고리즘이 달라질 수 있기 때문입니다. 알고리즘의 일종인 너비 우선 탐색과 깊이 우선 탐색은 그래프, 스택 등의 자료구조를 알고 있어야만 온전히 이해할 수 있습니다.

• 시간 복잡도와 공간 복잡도

개발자는 프로그램을 만드는 과정에서 소스 코드를 통해 다양한 데이터를 다루고(자료구조), 그 데이터를 활용해 특정 목적을 이루기 위한 연산(알고리즘)을 구현합니다. 따라서 자료구조와 알고리즘을 고려하며 작성한 코드는 훨씬 더 품질 좋은 코드가 될 가능성이 높습니다. 실제로 같은 목적을 위한 코드라 하더라도 자료구조와 알고리즘을 고려했는지 여부에 따라 극명한 성능의 차이를 보일 수 있습니다.

그렇다면 자료구조와 알고리즘의 고려 여부에 따른 성능의 차이는 어떻게 판단할 수 있을까요? 바로 시간 복잡도와 공간 복잡도를 통해 알 수 있습니다. 시간 복잡도와 공간 복잡도는 소스 코드나 프로그램이 얼마나 효율적인지를 판단하는 척도입니다.

시간 복잡도^{time complexity}란 입력의 크기에 따른 프로그램 실행 시간의 관계를 의미합니다. 프로그램의 실행 시간과 입력의 크기는 서로 밀접한 관계가 있습니다. 가령 ‘서로 다른 N개의 데이터가 있을 때, 앞에서부터 차례대로 하나씩 검사하여 특정 데이터를 찾는 프로그램’이 있다고 가정해 봅시다. 데이터가 하나(N=1)라면 프로그램의 실행 시간이 길지 않겠죠. 그러나 데이터가 100개(N=100)라면 일반적으로 조금 더 오랜 시간이 소요될 것입니다. 나아가 N이 10,000이라면 실행 시간이 평균적으로 훨씬 더 오래 걸릴 것입니다.

이때 실행 시간은 연산의 횟수에 비례한다고 간주합니다. N이 1일 때보다 100일때 일반적으로 더 많은 연산이 필요할 것이고, N이 100일 때보다 10,000일 때 더 많은 연산이 필요할 테니까요. 따라서 시간 복잡도는 입력의 크기에 따른 프로그램 실행 시간이라고 할 수도 있고, 입력의 크기에 따른 연산 횟수라고 할 수도 있습니다.

그럼 이번에는 소스 코드로 시간 복잡도를 이해해 보겠습니다. 예를 들어 다음과 같은 코드에서 ‘1+1’이 ‘한 번의 연산'을 의미한다고 생각해 볼게요. 그럼 다음 코드에는 몇 번의 연산이 필요할까요? 너무 쉽습니다. 다섯 번의 연산이 필요하겠죠.

1+1
1+1
1+1
1+1
1+1

코드를 반복문으로 일반화하여 표현해 보겠습니다. 다음과 같은 코드에서 n은 입력으로 주어진 데이터라고 가정할게요. 어떤 프로그래밍 언어인지는 중요하지 않습니다. 주석으로 남긴 의미만 파악해 보기 바랍니다. 다음 코드에는 몇 번의 연산이 필요할까요? n번의 연산이 필요할 것입니다.

for _ in range(n):    # 입력으로 주어진 값은 n; n회 반복하며
    1 + 1                         # 한 번씩 연산

같은 맥락에서 다음 코드에는 2n번의 연산이 필요합니다. 입력으로 주어진 n에 2를 곱한 만큼 반복하며 ‘1+1’을 연산하기 때문입니다.

for _ in range(2 * n):    # 입력으로 주어진 값은 n; 2n회 반복하며 
    1 + 1                                # 한 번씩 연산

다음 코드에는 n²번의 연산이 필요합니다. 2개의 반복문이 겹쳐 있기 때문입니다. 다시 말해, ‘n번씩 반복하며 한 번씩 연산하는 것’을 n번 반복하기 때문입니다(n × n). 마찬가지로 3개의 반복문이 겹쳐 있다면 n³번의 연산이 필요하겠죠.

for _ in range(n):        # 입력으로 주어진 값은 n; n회 반복하며
    for _ in range(n):    # 각각의 반복을 n회씩 반복하며
        1 + 1                         # 한 번씩 연산

마지막으로 다음 코드에서는 몇 번의 연산이 필요할까요? 답은 (n² + 3n + 2)번입니다.

for _ in range(n):        # 입력으로 주어진 값은 n; n회 반복하며
    for _ in range(n):    # 각각의 반복을 n회씩 반복하며
        1 + 1                         # 한 번씩 연산
                
for _ in range(3 * n):    # 입력으로 주어진 값은 3; 3n회 반복하며
    1 + 1                                # 한 번씩 연산
    
1 + 1                                 # 한 번씩 연산
1 + 1                                 # 한 번씩 연산

지금까지의 예제에서는 n의 값이 결정되면 코드의 연산 횟수 및 실행 시간도 함께 결정되었습니다. 하지만 현실 속 대부분의 프로그램은 예제처럼 입력의 크기가 결정된다고 해서 연산 횟수와 실행 시간이 무조건적으로 결정되지는 않습니다. 실제로는 입력하는 n이 같다고 하더라도 프로그램의 연산 횟수와 실행 시간이 달라질 수 있죠.

앞에서 가정했던 ‘서로 다른 N개의 데이터에서 특정 데이터를 찾는 프로그램’을 다시 생각해 봅시다. N이 100이라면 ‘일반적으로’, N이 10,000이라면 ‘평균적으로’ 더 오랜 실행 시간이 소요된다고 설명했습니다. ‘일반적으로’, ‘평균적으로’라는 사족을 붙인 이유는 그렇지 않은 경우도 있기 때문입니다. N이 10,000이더라도 ‘최선의 경우’, 운 좋게 단번에 원하는 데이터를 찾아낼 수도 있고, N이 100이더라도 ‘최악의 경우’, 데이터를 찾는 모든 연산을 끝내야만 원하는 데이터를 찾아낼 수도 있습니다.

그러나 상황에 따라 동일한 입력에 대한 프로그램의 실행 시간이 들쑥날쑥해서는 곤란하겠죠. 제대로 된 성능 판단 척도로서의 기능을 할 수 없을 것입니다. 그래서 시간 복잡도를 표현할 때에는 대중적으로 빅 오 표기법^{big O notation}이 사용됩니다. 빅 오 표기법은 함수의 점근적 상한을 표기하는 방법입니다. 시간 복잡도를 표현하기 위해 빅 오 표기법을 사용한다면 ‘입력에 따른 실행 시간의 점근적 상한’을 의미하는 것입니다. 그렇다면 점근적 상한이란 무엇일까요?

입력하는 n이 점점 증가하여 무한대로 커진다고 생각해 보세요. n에 따라 일반적으로 실행 시간도 점점 증가할 것입니다. 이때 실행 시간이 증가하는 데에도 한계가 있습니다. 이 한계를 점근적 상한이라고 합니다. 입력의 크기 n에 대한 빅 오 표기법은 흔히 실행 시간의 O(상한(n)) 형태로 표현되며, 이는 쉽게 말해 입력하는 n이 점점 증가해 무한대로 커진다고 하더라도 실행 시간이 대략 이 이상(상한)은 커지지 않을 것이라는 의미입니다. 예를 들어, 시간 복잡도에서 빅 오 표기법으로 표현된 O(n2)은 입력값 n이 증가하더라도 실행 시간의 증가율이 n²보다는 작다는 것을 표현합니다.

앞서 살펴본 ‘서로 다른 n개의 데이터에서 특정 데이터를 찾는 프로그램’에 적용해 보겠습니다. 프로그램에서 데이터를 한 번 찾아보는 것을 한 번 연산한 것으로 가정할 때 n이 점점 커져서 무한대로 향하더라도 대략 n번 이상으로 연산하지는(n번 이상으로 찾아보지는) 않을 것입니다. 즉, 이 프로그램의 시간 복잡도를 빅 오 표기법으로 표현하면 O(n)이 됩니다.

빅 오 표기와 관련해 유의해야 할 점이 있습니다. 점근적 상한을 표현할 때에는 최고차항의 차수만 고려한다는 점입니다. 즉, 입력값 n에 대한 실행 시간의 점근적 상한을 수식으로 표현할 때는 최고차항의 차수만 고려합니다. 앞서 설명한 코드 예제를 상기해 봅시다. 입력값 n에 대한 연산 횟수를 n에 대한 식으로 표현했었죠. 이때, n이 점점 증가하여 무한대로 커진다면 계수와 낮은 차수의 항이 끼치는 영향은 무시할 수 있게 됩니다. 따라서 빅 오 표기법으로 점근적 상한을 표기할 때는 입력값 n에 대한 연산 횟수에서 계수와 낮은 차수의 항을 제외시키고, 다음과 같이 최고차항의 차수만 고려하게 됩니다.

빅 오 표기법으로 표현되는 시간 복잡도 중에서도 자주 언급되는 표기들은 어느 정도 정해져 있습니다. 대표적인 시간 복잡도는 다음과 같은 그래프로 표현할 수 있습니다.

이 중 입력값 n이 충분히 클 때 가장 성능이 좋지 않은 시간 복잡도는 O(n!)입니다. 그렇다면 n이 충분히 클 때 O(n²)의 복잡도를 갖는 알고리즘과 O(1)의 복잡도를 갖는 알고리즘 중 더 성능이 좋은 알고리즘은 무엇일까요? 당연히 후자입니다. O(1)은 입력값이 10개, 1억 개가 주어지든 상관없이 항상 알고리즘의 실행 시간이 일정하다(상수 시간이 소요된다)는 의미이고, O(n²)은 n이 증가함에 따라 n의 제곱만큼 실행 시간이 증가한다는 것을 의미하니까요.

동일한 목적을 수행하는 알고리즘이라도 성능이 다를 수 있습니다. 일례로, 다음 표에 제시된 서로 다른 정렬 알고리즘들은 모두 정렬을 수행한다는 점은 동일하지만, 성능이 다를 수 있기 때문에 빅 오 표기법으로 표현된 시간 복잡도가 다릅니다.

특정 자료구조를 구성하는 데이터에 대한 접근, 검색, 삽입, 삭제 연산의 시간 복잡도를 빅 오 표기법으로 나타낼 수 있습니다. 자료구조를 통한 다양한 연산이 가능하며, 각 연산에 대한 성능은 빅 오 표기법으로 표현 가능하다는 점에 유의해 주세요.

지금까지 알고리즘의 성능을 판단하기 위해 살펴본 시간 복잡도와 유사한 공간 복잡도라는 개념도 있는데요. 공간 복잡도^{space complexity}는 프로그램이 실행되었을 때 필요한 메모리 자원의 양을 의미합니다. 시간 복잡도가 입력에 따른 실행 시간의 척도라면, 공간 복잡도는 입력에 따른 메모리 사용량의 척도라 할 수 있습니다.

모든 프로그램은 실행을 위해 메모리에 적재되어야 합니다. 같은 동작을 하는 프로그램이라고 하더라도 실행 과정에 많은 메모리가 필요한 경우가 있고, 그렇지 않은 경우가 있습니다. 이때 메모리의 사용량에 따라 많은 메모리가 필요한 경우는 공간 복잡도가 크고, 그렇지 않은 경우는 공간 복잡도가 작다고 할 수 있습니다. 

흔히 공간 복잡도는 시간 복잡도처럼 빅 오 표기법으로 표현됩니다. 공간 복잡도를 빅 오 표기법으로 표현하면 입력에 따라 필요한 메모리 자원의 양에 대한 점근적 상한을 표현하게 되겠죠. 다만, 오늘날 알고리즘의 성능 판단에 사용되는 척도는 주로 공간 복잡도보다는 시간 복잡도인 경우가 많기 때문에 특별한 언급이 없는 한, 빅 오 표기법으로 표현된 알고리즘의 성능은 모두 시간 복잡도를 표현한 것이라고 이해하시면 됩니다.

• 자료구조 지도 그리기

자료구조의 개념과 자료구조의 성능을 판단할 수 있는 시간 복잡도와 공간 복잡도를 살펴봤습니다. 핵심적인 자료구조(배열과 연결 리스트, 스택, 큐, 해시 테이블, 트리, 그래프)를 학습하기 전에 다음과 같이 한눈에 정리된 지도를 보면서 학습의 흐름을 정리해 보기 바랍니다.

위 콘텐츠는 『이것이 취업을 위한 컴퓨터 과학이다 with CS 기술 면접』의 내용을 재구성하여 작성되었습니다.