[DS] 01. 자료구조가 중요한 이유

index

이 포스트 시리즈는 이 책을 기반으로 작성된다. 필요하다면 다른 문헌(아마 주로 CLRS같은 대학교재가 될 듯)도 참고해가며 작성될 것이다. 언어는 파이썬3을 위주로 쓴다.

코드의 품질을 평가하는데 있어 유지보수성과 같은 다양한 기준들이 있지만 또 다른 기준은 바로 효율성이다. 즉, 똑같은 동작을 수행하는 두 개의 코드가 있다하더라도 그 중 하나가 더 빠르게 실행될 수 있을 때, 그 코드는 효율성을 가진다고 우리는 얘기한다.

다음 예시는 2부터 100까지 모든 짝수를 출력하는 두 가지 함수다.

1
def print_numbers_version_one():
2
    number = 2
3

4
    while number <= 100:
5
        # If number is even, print it:
6
        if number % 2 == 0:
7
            print(number)
8

9
        number += 1
10

11

12
def print_numbers_version_two():
13
    number = 2
14

15
    while number <= 100:
16
        print(number)
17

18
        # Increase number by 2, which, by definition, is the next even number:
19
        number += 2

위 두 함수 중 어느 것이 더 빠르게 실행될까? 바로 두 번째다. 왜냐하면 첫번째 함수는 100에 이르기까지 루프를 100번 반복하는 반면, 두번째 함수는 50번만 반복하기 때문이다. 그러므로 두번째 함수가 더 효율적이다.

자료구조

데이터는 모든 유형의 정보를 지칭하는 광범위한 용어이며, 가장 기초적인 데이터로는 숫자와 문자열이 있다. 자료구조는 이러한 데이터를 구성하는 방식을 말한다. 한편, 우리가 알아야하는 것들 중엔 데이터를 구조화하는 방법(예컨대 주어진 데이터를 배열이나 해쉬맵에 저장하는 법 등)이 있겠지만, 그렇게 구조화된 데이터의 구성이 코드 실행 속도에 미치는 영향이 크다라는 것 또한 알아야한다. 왜냐하면 데이터를 어떻게 구성하느냐에 따라 프로그램의 실행속도가 좌우되고, 많은 데이터를 처리해야하는 프로그램이나 수천 명이 동시에 사용하는 웹 앱을 개발한다면 자료구조에 따라 처리가 수월하게 되거나 혹은 과부하가 일어나 다운되어버릴 수도 있기 때문이다. 따라서 자료구조를 깊게 알수록 소프트웨어 성능을 더욱 더 효율적으로 끌어낼 수 있는 빠르고 간결한 코드를 작성하는 노하우를 얻게 된다.

가장 기본적인 자료 구조: 배열

배열은 가장 기본적인 자료 구조 중 하나이며, 데이터 요소(element)로 이루어진 리스트다 (파이썬의 리스트와 유사하다). 배열의 용도는 여러가지이며 그만큼 다양한 상황에서 사용될 수 있다. 예컨대 어떤 자연어에 대한 정보들을 관리하는 애플리케이션의 소스코드를 보고있다면 이런 코드가 있을 거다.

1
language = ["name", "speakers", "location", "status", "area"]

위 배열은 5개의 값을 갖고 있으므로 크기가 5이고, 배열 내 데이터의 위치는 인덱스로 나타내며 이는 0부터 시작하며 영어로는 zero-based index라 한다. 예를들어 "location"의 인덱스는 2다.

자료 구조 연산

자료 구조는 기본적으로 다음 4가지 방식으로 사용되며 이를 연산(operation)이라 한다.

읽기(read): 자료 구조의 특정 지점에서 무언가를 조회하는 것. 배열의 경우 특정 인덱스에서의 값을 조회하는 것을 의미하며, 예컨대 위 예시에서 인덱스 2에 어떤 정보가 있는지 조회하는 것이 배열에서는 읽기에 해당한다.
검색(search): 자료 구조에서 특정 값을 찾는 것을 말한다. 기억해두자. 컴퓨터는 바보이기 때문에 단순 읽기는 조회만을 얘기하며, 이는 검색과는 분리된 거다. 배열에서는 특정 값이 배열 내에 있는지, 있다면 어느 인덱스에 있는지 확인하는 것을 의미한다. 위 예시에서 “status”가 있는지 배열에서 찾는 것은 해당 배열에서의 검색에 해당한다.
삽입(insert): 자료 구조에 새로운 값을 추가하는 것을 의미한다. 배열의 경우, 배열에 추가되는 슬롯에 새 값을 넣는 것을 의미한다.
삭제(delete): 자료 구조에서 값을 제거하는 것을 지칭한다. 배열에선 기존에 저장된 값 중 하나를 제거하는 것을 의미한다.

속도 측정

그렇다면 연산 속도는 어떻게 측정할까? 컴퓨터에서 연산이 얼마나 빠른지 측정하려면 이는 단순히 물리적 경과 시간을 측정하는 것이 아니라 위 연산들이 몇 단계에 걸쳐 수행하는지를 논해야한다. 왜 물리적 시간이 아닌 단계를 갖고 측정할까? 그 이유는 간단하다. 누구도 어떤 연산이 고정적으로 특정 시간이 걸린다고 단정할 수 없기 때문이다. 어떤 함수를 실행시킬 때 1940년대에 개발된 애니악 컴퓨터에서 5초가 걸렸다면 오늘날 데스크탑에선 그보다 훨씬 더 빠른 시간이 걸릴 가능성이 높을 거며, 미래에 개발될 컴퓨터는 그것보다 더 빠른 시간 내에 함수를 실행시킬 수 있다. 즉, 하드웨어에 따라 물리적 소요 시간이 달라지므로 연산 속도를 단순 소요시간을 기준으로 삼을 수가 없다는 것이다.

그러나 대신 필요한 계산 단계 갯수로 연산 속도를 측정할 수 있다. 예컨대 위에 맨 처음 파이썬 코드에서 동일한 동작을 하는 두 개의 함수 비교가 바로 그 경우다.

읽기

기본적으로 컴퓨터는 단 한 번의 단계를 통해 배열 내 특정 인덱스 값이 어떤 것이 조회할 수 있다. 위 자연어 배열 예시는 사실 인덱스 정보 외에 또 다른 중요한 정보를 갖고 있다. 아래 예시를 보자.

1
language = ["name", "speakers", "location", "status", "area"]
2
# memory address: 1010, 1011, 1012, 1013, 1014
3
# index: 0, 1, 2, 3, 4

즉, 메모리 주소가 있다는 것인데, 이를 통해 컴퓨터는 특정 인덱스에서의 값을 읽을 때 해당인덱스로 바로 이동할 수 있다. 그리고 이 과정은 다음과 같이 꽤나 복합적으로 작용한다.

컴퓨터는 모든 메모리 주소에 한 단계만에 이동할 수 있다.
- 예컨대 메모리 주소 1063에 있는 값을 찾으라는 요청을 받으면 검색 과정을 거치지 않고 바로 해당 주소에 접근 가능하다. 이는 마치 오른쪽 새끼손가락을 들어보라고 했을 때 굳이 모든 손가락을 들어볼 필요 없이 바로 해당 손가락을 볼 수 있는 거랑 비슷하다.
컴퓨터는 배열을 할당할 때 마다 배열이 시작되는 메모리 주소도 기록한다.
- 예컨대 컴퓨터에 배열의 첫 번째 요소를 찾으라고 요청하면 컴퓨터는 즉시 적합한 메모리 주소로 이동하여 해당 요소를 찾아낸다.

그리고 위와 같은 과정은 배열의 첫 번째 값을 어떻게 한 단계만에 찾는지를 설명한다. 그러나 컴퓨터는 그 어떠한 임의의 인덱스 값도 간단한 덧셈으로 찾을 수 있다. 예컨대 인덱스 3의 값을 찾으라 요청하면 단순히 인덱스 0의 메모리 주소를 가져와 3을 더 한다는 거다 (메모리 주소는 순차적이기 때문이다). 위 자연어 배열을 예시로써 다음을 살펴보자.

자연어 배열은 인덱스 0부터 시작하며, 해당 인덱스의 메모리 주소는 1010이다.
인덱스 3은 인덱스 0에서 정확히 세 슬롯 뒤에 있다.
이는 1010 + 3, 즉 1013이므로 인덱스 3은 메모리 주소가 1013이다.
따라서 인덱스 3의 값을 읽는다.
인덱스 3이 메모리 주소 1013에 있다는 것을 알아냈으므로 그곳으로 이동하여 “status”라는 문자열 값이 있는 걸 알 수 있다.

설명을 위해 쪼개어 놓았지만 위 과정들 자체는 한 번에 이루어진다고 보면 된다. 이렇듯 컴퓨터에게 있어 읽기라는 연산이 가장 효율적인 경우는 바로 배열이다. 앞서 말했듯 한 단계만 소요되기 때문이다.

검색

이번엔 반대로 생각해보자. 즉, 인덱스 3에 어떤 값이 들어있는지 묻는 대신, 어떤 인덱스를 봐야지만이 ‘dates’를 찾을 수 있는지 묻는 것이다. 이 연산이 바로 검색 연산이다.

헷갈릴 수도 있으니 읽기와 검색의 차이를 간단히 다시 살펴보자.

읽기: 컴퓨터에 인덱스를 제공하고 그 안에 있는 값을 반환하도록 요청하는 것!
검색: 컴퓨터에 값을 제공하고 해당 값의 위치 인덱스를 반환하도록 요청하는 것!

얼핏 보면 두 연산은 비슷해보이나, 효율성 측면에서 큰 차이가 난다. 읽기의 경우, 컴퓨터는 제공된 인덱스를 보고선 그곳에 즉시 이동해 그 안에 포함된 값을 찾을 수 있어 빠른 반면, 검색은 컴퓨터가 특정 값으로 바로 이동할 수 있는 방법이 없기 때문에 시간이 걸린다. 그리고 이는 중요한 컴퓨터의 특징 중 하나다!

즉, 컴퓨터는 모든 메모리 주소에 즉시 접근할 수 있지만, 각 메모리 주소에 어떤 값이 포함되어 있는지는 바로 알 수 없다.

다시 자연어 예시 배열로 가보자. 컴퓨터는 각 셀의 실제 내용을 즉시 볼 수 없고, 단순히 인덱스 정보만을 배열이 최초에 제공해준다. (대충) 아래와 같다는 것이다.

1
language = [?, ?, ?, ?, ?]

이 배열에서 예컨대 “status”라는 정보를 검색하려면 컴퓨터는 각 셀을 한 번에 하나씩밖에 검사할 수 없으며, 이는 아래와 같은 방식으로 된다.

1
language = ["name", ?, ?, ?, ?]
2
               0    1  2  3  4
3
              ⬆️

우선 인덱스 0부터 시작한다. “name”이 니나다. “status”가 아니므로 다음 인덱스로 이동한다.

1
language = ["name", "speakers", ?, ?, ?]
2
               0         1      2  3  4
3
                        ⬆️

“speakers”가 나왔다. “status”아 아니므로 다음 인덱스로 넘어간다. 이 과정을 반복하다보면…

1
language = ["name", "speakers", "location", "status", ?]
2
               0         1           2           3    4
3
                                                ⬆️

원하는 값인 “status”를 찾았으니 검색을 마친다.

위 검색 연산은 총 4단계가 소요되어있다. 이와 같이 각 셀을 한 번에 하나씩 확인하는 가장 기본적인 검색 과정을 선형 검색(linear search)라고 한다.

만약 검색하고자 하는 값이 “area”였다면, 총 단계는 곧 최대 단계이자 모든 셀의 갯수만큼의 단계로 검색해야한다. 따라서 셀이 5개인 배열 혹은 N-array에서 최대 단계수는 5이고, 500개인 배열이라면 500단계가 될 것이다. 즉, N-array의 선형 검색은 최대 N단계가 걸린다는 것이다.

삽입

배열에 새로운 데이터를 삽입할 때의 효율성은 배열 내 어디에 데이터를 삽입하느냐에 따라 달라진다. 예컨대 위 자연어 정보 배열에서 “family”라는 정보를 배열 맨 끝에 추가한다고 한다면, 한 단계의 삽입 단계만 필요하다. 그러나 맨 끝이 아닌 다른 곳(예: 중간 어딘가)이라면 얘기가 달라진다. 그 이유는 컴퓨터의 또 다른 특징, 즉 배열을 할당할 때 컴퓨터가 항상 배열의 크기를 기록하고 관리한다는 특징 때문이다.

“family”라는 정보 배열의 시작이나 중간에 삽입하는 걸 생각해보자. 단순이 맨 끝에 삽입하는 경우엔 셀을 하나 추가하면 되지만 시작과 중간의 경우엔 얘기가 달라진다. 예컨대 인덱스 2에 “family”를 삽입을 하는 과정은 컴퓨터는 다음과 같이 진행한다. 파이썬으로 표현하면 다음과 같다. (파이썬에선 셀이 선언되어있지만 그 값은 비어있는 Null을 None으로 표현한다.) 참고로 아래 과정은 어디까지나 시각화를 위한 표현이다.

1
# initlaize the array
2
language = ["name", "speakers", "location", "status", "area", None]
3

4
# step 1 - move
5
language = ["name", "speakers", "location", "status", None, "area"]
6

7
# step 2 - move
8
language = ["name", "speakers", "location", None, "status", "area"]
9

10
# step 3 - move
11
language = ["name", "speakers", None, "locatoin", "status", "area"]
12

13
# step 4 - insert
14
language = ["name", "speakers", "family", "location", "status", "area"]

총 4단계가 이루어졌다. (만약 기존 배열에서 새로운 셀(=위의 경우 None)을 추가하는 단계까지 포함하면 5단계다). 그리고 우리는 이를 통해 자연스레 삽입에 대해 한가지 사실을 알 수 있다. 바로, 배열의 맨 앞에서 데이터를 삽입하는 것이 효율성 측면에서 최악의 시나리오란 것이다. 이는 N+1단계가 걸리는데, 배열 내 N개의 요소를 모두 이동한 다음 마지막으로 실제 삽입 단계를 플러스 원 해야하기 때문이다.

삭제

배열에서 삭제는 특정 인덱스의 값을 제거하는 연산이다. 다시 자연어 예시의 최초 배열 상태로 가서, 인덱스 2의 값을 삭제하는 연산을 살펴보자.

1
# initlaize
2
language = ["name", "speakers", "location", "status", "area"]
3

4
# step 1 - delete
5
language = ["name", "speakers", None, "status", "area"]

물론 여기서 끝낼 수도 있지만, 배열 중간에 사용하지 않는 빈 셀이 있으므로 이를 그대로 내비두는 것은 비효율적이다. 따라서 나머지 요소들을 옮겨야 한다. 즉, 배열에서 삭제 과정은 단순히 삭제만 있는 것 아니라, 이후 사용하지 않는 셀을 처리하는 추가과정이 있는 것이다 (나같으면 단순히 그냥 삭제 했으니깐 끝이라 생각했지만, 컴퓨터는 바보라는 점을 상기하자.).

1
# step 2 - move
2
language = ["name", "speakers", "status", None, "area"]
3

4
# step 3 - move
5
language = ["name", "speakers", "status", "area", None]

배열 끝에 None, 즉, 빈 셀만 남겨두었다. 배열 중간에 있는 것이 아니기에 까다로운 것이 아니므로 (필요없다면 빈 셀 자체를 그냥 삭제만 하면 끝이니깐) 그냥 내비두어도 된다. 이로써 컴퓨터가 배열에 대한 삭제 연산 예시를 살펴보았다.

위 단계는 삭제 1단계 + 이동 2단계 = 총 3단계가 진행되었다. 삽입과 마찬가지로 삭제 연산의 최악의 시나리오는 배열의 첫번째 요소를 삭제하는 것이다. 즉, 인덱스 0을 비우고 그 뒤의 인덱스들에 있는 모든 요소들을 왼쪽으로 하나하나 옮겨서 빈 셀이 되어버린 인덱스 0을 메워야 한다. 요소 5개로 구성된 배열이라면 인덱스 0, 즉, 첫번째 요소를 삭제하는데 1단계, 나머지 4개의 요소를 이동하는데 4단계가 걸린다. 500개의 경우, 마찬가지로 삭제하는데 1단계, 이동하는데 499단계가 걸린다. 즉, 배열의 경우 최악의 시나리오에서 삭제 연산은 최대 N단계인 것이다.

집합: 단일 규칙이 효율성에 미치는 영향

수학에서 집합의 원소는 두 번 이상 표현될 필요가 없듯 컴퓨터에서 자료구조로서의 집합 또한 그 안에 값은 중복을 포함하지 않는 자료 구조로서 표현된다.

다양한 집합이 있지만 여기서 다룰 건 배열 기반 집합이니 이걸 갖고 얘기해보자. 이 집합의 값들, 즉, 원소는 리스트로 이루어졌으므로 배열과 비슷하지만 집합의 특성을 지니고 있기에 원소(=요소)의 중복을 허용하지 않으며, 따라서 중복된 데이터를 방지하고자 할 때 유용한 자료구조로서 사용될 수 있다. 예컨대 화자가 항상 완벽하고 문법적이며 redundant하지 않는 문장만을 발화한다고 가정했을 때, 그 화자는 어떤 문장을 얘기할 때 강조와 같은 특별한 경우가 아니면 되도록이면 동일한 단어나 조사정보 혹은 구(phrase)를 반복하지 않으려고 한다고 생각해볼 수 있다. ‘봇치는 기타를 좋아한다’와 같은 문장이 있다고 하자, 이를 공백을 기준으로 해서 집합으로 표현하면 다음과 같다.

1
sentence1 = {"봇치는", "기타를", "좋아한다"}
2
sentence2 = {"봇치는", "봇치는", "기타를", "좋아한다"}
3

4
print(sentence1, sentence2) # {'봇치는', '좋아한다', '기타를'} {'봇치는', '좋아한다', '기타를'}

위 파이썬 예시에서 보이듯 “봇치는”이 sentence2 변수에 두 번이 들어가도 집합으로 표현이 되면 한 번밖에 표현되지 않는 걸 알 수 있다. 이러한 중복을 허용하지 않는 제한은 유용하지만, 이 조건에 의해 앞서 말한 읽기, 검색, 삽입, 삭제 연산 중 하나의 연산의 효율성이 크게 달라진다. 연산 별로 정리하면 다음과 같다.

집합에서의 연산

읽기
- 배열과 동일하다. (그 원리도 똑같다.)
검색
- 마찬가지.
삭제
- 마찬가지.(1)
삽입
- 다르다. 먼저 배열을 생각해보자. 최선의 시나리오인 배열의 맨 끝에 새로운 값을 삽입을 하는 것은 집합에서는 1차적으로 먼저 그 새로운 값이 기존의 값과 중복이 되는지를 살펴봐야 한다. 컴퓨터는 멍충하므로 인간과 달리 바로 알 수 없다. 즉, 먼저 검색부터 해야한다. 집합에 새 값이 기존에 존재하지 않아야지 해당 값을 삽입을 할 수 있기 때문이다. 따라서 집합에서의 모든 삽입은 먼저 검색을 거친다. 앞서 자연어 예시에서 “family”를 집합 자료구조에 추가하는 것을 예시로 생각해보자.

1
# initlaize the set
2
language = {"name", "speakers", "location", "status", "area"}
3

4
# step1 - search "family"
5
language = {"name", "speakers", "location", "status", "area"}
6
              ⬆️
7

8
# step2 - search "family"
9
language = {"name", "speakers", "location", "status", "area"}
10
                        ⬆️
11

12
# step3 - search "family"
13
language = {"name", "speakers", "location", "status", "area"}
14
                                    ⬆️
15

16
# step4 - search "family"
17
language = {"name", "speakers", "location", "status", "area"}
18
                                                ⬆️
19

20
# step5 - search "family". we found there's no "family" that already exists in the set.
21
language = {"name", "speakers", "location", "status", "area"}
22
                                                        ⬆️
23

24
# step6 - insert "family"
25
language = {"name", "speakers", "location", "status", "area", "family"}

위 예시는 집합 자료구조로서 정의된 language 변수에 “family”라는 값을 삽입하는 과정이다. 이미 설명했듯 “family”가 이미 존재하는지 검색하는 과정을 거친 후, 없음을 확인한 뒤에서야 “family”가 새로운 값으로 삽입된 걸 알 수 있다.

이는 다른 말로 하자면, 요소 N개에 대해 최대 N+1단계가 소요된다는 것이다. 왜냐하면 삽입될 값이 있는지 확인하기 위해 N단계의 검색이 필요하고, 이후 삽입을 위해 1단계가 더 필요하기 때문이다. 여기까지만 보면 배열의 삽입에서 최악의 시나리오인 맨 앞에서 데이터를 삽입하는 것과 동일한 단계가 걸리는 것처럼 보인다.

그러나 최악의 시나리오가 집합에 적용될 땐 얘기 달라진다. 먼저 컴퓨터는 집합에 삽입하려는 값이 이미 존재하는지 N개의 셀을 검색하고, 존재하지 않는다면 집합의 모든 원소(=값)을 오른쪽으로 옮기는 또 다른 N단계, 이후 마지막으로 새 값을 삽입하는 마지막 1단계를 거쳐야한다. 그러므로 집합 자료구주에서 삽입은 최악의 시나리오에선 2N+1단계가 걸리며, N+1인 배열과는 다르다.

맨 처음에 우리는 코드의 품질을 평가하는데 있어서 효율성, 즉, 처리의 단계가 중요한 기준이라고 얘기했고 단계가 적으면 적을수록 좋다고 하였다. 그렇다면 삽입 연산에서 집합보다는 배열이 반드시 선호되어야 하는 걸까? 아니다. 만약 중복 데이터가 없는지 확인해야할 때는 집합이 배열보다 효율적이다. 그렇지 않다면 배열을 갖고 삽입을 하는 것이 효율적이다. 즉, 상황(정확히는 구현하려는 애플리케이션 및 프로그램)에 따라 어떤 자료구조가 더 효율적인지는 늘 바뀐다는 것이다.

끝.