[패스트캠퍼스][환급 챌린지]Chapter 2. 딥러닝을 위한 자료 구조 02-01 자료구조 개요

Chapter 2. 딥러닝을 위한 자료구조

통계와 관련된 이론은 지난 포스트에서 끝났고, 오늘부터는 컴퓨터공학과 관련된 내용이 주를 이룹니다. 개인적으로 머신러닝을 깊게 파고들기 시작하면서 가장 아쉬웠던 부분이, 학부 당시 수업에서 머신러닝 기법과 그 적용 위주로만 수업을 들은 탓에 정작 그 기법으로 다뤄야 하는 데이터가 어떤 특성을 가지고, 그래서 어떻게 다루는 것이 더 효율적이고 올바른지를 전혀 알려주지 않았다는 겁니다(데이터 전처리(preprocessing)가 아니라 오늘부터 다룰 자료구조, 그 외에는 데이터베이스 등의 정보를 말하는 겁니다). 그래서 더더욱 이 챕터가 저에게 중요하게 다가오는 것 같네요.

저한테 왜 그랬어요

02-01 Data Structure 개요

자료구조

def) 자료구조 (Data Structure): 다수의 자료(data)를 담기 위한 구조
현실 세계에는 다양한 자료가 존재합니다. 우리가 어떻게 그러한 자료를 저장하고 처리하는 지와 관련해 가장 효율적인 방법들이 정립되어 있습니다. 특히 데이터의 수가 많아질수록 더욱 효율적인 자료구조가 필요합니다. 예를 들어, 학생이 1백만명이 넘어가고, 학생에 대한 정보를 도합 1억회 이상 열람한다고 하면, 메모리 용량과 속도 향상을 위해서라도 효율적인 자료구조를 이용할 필요가 있습니다.
여기서 자료구조/알고리즘의 성능 측정 방법을 이해하고 넘어가야 합니다. 아래에 두 가지 자료구조가 있다고 해봅시다.

1. 삽입과 추출 모두 적당히 빠름.
2. 삽입은 느리지만 추출은 매우 빠름.

여기서 우리가 데이터를 삽입할 일이 많다면 두 알고리즘 중 1번 알고리즘을 쓰는 것이 좋습니다. 반대로, 삽입은 그다지 많이 하지 않지만 이미 구축된 데이터를 추출할 일이 많다면 2번 알고리즘을 쓰는 것이 적절하겠죠. 이와 같이, 어떤 알고리즘을 사용할 지는 주어진 상황에 맞게 취사선택하는 것이 좋습니다. 이론상으로는 그렇죠.
하지만, 일반적으로 실무에서는 삽입과 추출 둘 다 적당히 빠른 1번 알고리즘을 사용합니다. 왜일까요? 두 자료구조의 삽입과 추출 속도를 아래와 같이 표기할 수 있습니다.

1. 삽입: $O\left(\log N\right)$/추출: $O\left(\log N\right)$
2. 삽입: $O\left(N\right)$/추출: $O\left(1\right)$

이 표기법을 점근 표기법(asymptotic notation) 또는 Big-O 표기법이라고 부르는데, 수학적으로 엄밀한 정의는 함수가 얼마나 빨리 증가 또는 감소하는지를 나타내는 표기법입니다. 이를 컴퓨터에 적용해보면, 간단하게 말해 연산 속도의 척도로도 볼 수 있습니다. 입력 데이터가 $N$만큼 주어져있을 때, 걸리는 속도를 $O\left(N\right)$ 등으로 나타내는 겁니다. 자세한 건 아래에서 다시 살펴보도록 하죠.
문제는 일반적으로 $O\left(\log N\right)\sim O\left(1\right)$와 비슷한 정도로 충분히 빠르다는 겁니다. 반대로 $O\left(\log N\right) < O\left(N\right)$이므로 객관적으로 잘 짜여진 알고리즘이라고 단언하기가 어렵습니다. 그래서 실무적인 관점에서는 대부분 1번 알고리즘/자료구조를 사용하는 겁니다.
따라서 자료구조를 제대로 이해하지 못하면 불필요한 메모리 또는 연산 시간 낭비가 생길 수 있으므로, 자료구조를 적절히 사용할 필요가 있습니다.

자료구조의 필요성 예시

C언어를 기준으로 정수(int, integer의 준말) 형식의 데이터가 약 100만 개 존재한다고 가정해보겠습니다. 해당 프로그램을 이용할 때, 내부적으로는 하루에 약 1억 회의 데이터 조회가 일어난다고 합니다. 이때 원하는 데이터를 가장 빠르게 찾도록 해주는 자료구조로 트리(tree)라는 형태가 있다고 합니다. 트리에 대한 건 나중에 자세히 배울 테니 일단은 이런 게 있구나 하고 넘어갑시다.

자료구조의 종류

자료구조는 크게 봤을 때 선형성을 기준으로 두 그룹으로 나뉘며, 각각의 하위 분류가 존재합니다.

1. 선형구조(Linear Data Structure)
   • 배열 (array)
   • 연결 리스트 (linked list)
   • 스택 (stack)
   • 큐 (queue)
2. 비선형 구조 (Nonlinear Data Structure)
   • 트리 (tree)
   • 그래프 (graph)

선형 자료구조

def) 선형 자료구조 (Linear Data Structure): 하나의 데이터 뒤에 다른 데이터가 한 개 존재하는 자료구조
선형 자료구조는 데이터가 일렬로 순차적으로 연결되어 있다는 특징이 있습니다. 한 데이터 뒤에는 다른 데이터가 오직 하나만 뒤따릅니다.

비선형 자료구조

def) 비선형 자료구조 (Nonlinear Data Structure): 하나의 데이터 뒤에 다른 데이터가 여러 개 존재할 수 있는 자료구조
반대로 비선형 자료구조는 데이터가 굳이 순차적으로 연결되지 않아도 됩니다. 아래의 트리 그림을 보더라도, 한 데이터 뒤에 다른 데이터 2개가 뒤따르므로 일렬로 정렬되지 않습니다.

 

자료구조와 알고리즘

또한 효율적인 자료구조 설계를 위해서는 알고리즘 지식이 필요합니다. 자료구조 자체가 일종의 코드, 논리 구조로 볼 수 있기 때문입니다. 역으로 효율적인 알고리즘을 작성하기 위해서 문제 상황에 맞는 적절한 자료구조가 사용되어야 합니다. 따라서 ML 스크립트 내지는 프로그램을 짤 때 자료구조와 알고리즘 둘 모두를 고려해야 합니다.

저는 두 쪽의 지식 모두 부족해서 X고생했습니다...

프로그램의 성능 측정 방법

프로그램의 성능은 시간 복잡도와 공간 복잡도라는 2개의 척도를 이용해 나타냅니다.
def) 시간 복잡도 (time complexity): 알고리즘에 사용되는 연산 횟수
공간 복잡도 (space complexity): 알고리즘에 사용되는 메모리의 양

한편 공간을 많이 사용하더라도 시간을 단축하는 알고리즘도 흔하게 채택됩니다. 실질적으로는 시간과 메모리 둘 모두를 적절히 사용하는 알고리즘을 짭니다.

Big-O 표기법

위에서 잠시 삽입/추출 시간을 표시할 때 대문자 $O$를 이용한 표기를 Big-O 표기법이라고 한다고 언급했습니다. 이 표기법은 시간 복잡도를 표현할 때 주로 사용되는 표기법으로, 특정 알고리즘이 얼마나 효율적인지 수치적으로 나타낼 수 있는 장점이 있습니다. 참고로 Big-O 표기법에서는 가장 빠르게 증가하는 항(term)만을 고려하는 표기법입니다. 무슨 얘긴고 하면 예를 들어서...
$$연산 횟수\left(n\right)=2n^3+3n^2+1$$
과 같이 연산 횟수가 주어진다면, 이 알고리즘의 시간 복잡도는 가장 높은 항인 삼차항만을 고려해서 $O\left(n\right)$로 표기하게 됩니다. 참고로 현실에서는 보통 동작 시간이 1초 이내인 알고리즘을 설계할 필요가 있습니다.
그럼 몇 가지 코드 예시를 통해 각 알고리즘의 시간 복잡도를 알아보겠습니다. 첫째로 아래의 예시는 0부터 9까지의 정수를 모두 더하는 알고리즘으로 $O\left(n\right)$의 시간 복잡도를 갖습니다.

n = 10
summary = 0
for i in range(n):
    summary += i

print(summary)

두 번째 예시는 구구단 알고리즘입니다. 두 개의 정수를 곱하므로 이 알고리즘은 $O\left(n^2\right)$의 시간 복잡도를 갖습니다.

n = 9
for i in range(1, n+1):
    for j in range(1, n+1):
        print(f"{i} x {j} = {i * j}")

오늘날 사용되는 컴퓨터에 탑재되는 CPU는 최소 GHz 단위의 연산 속도를 가지며, 이는 1초에 최소 10억 회의 연산을 할 수 있다는 얘기입니다. n이 1000일 때의 시간 복잡도에 따른 연산 횟수는 다음과 같습니다.

시간 복잡도	연산 횟수
$O\left(n\right)$	1,000
$O\left(n\log N\right)$	10,000
$O\left(n^2\right)$	1,000,000
$O\left(n^3\right)$	1,000,000,000

그 외의 몇 가지 경우에 대한 시간복잡도를 그래프로 나타내면 아래 그림과 같습니다. 거의 1에 가까울 정도로 속도의 변화가 없는 부류도 있는 반면, 매우 빠른 속도를 자랑하는 경우도 있습니다.

마지막으로 공간을 나타낼 때는 MB(메가바이트) 단위로 표기합니다.

int a[1000]: 4KB
int a[1000000]: 4MB
int a[2000][2000]: 16MB

18일차 후기

네, 서론에서도 말했지만 이 부분부터는 거의 처음 배우는 파트입니다. 거의 미지의 영역이네요. 다시 생각해봐도 '그 때 이 내용들을 조금이라도 알고 있었다면 대학원 때 내 연구도 조금이나마 수월했을까?' 싶은 부분이네요. 피가 되고 살이 되는 내용들입니다.

http://bit.ly/3Y34pE0

패스트캠퍼스 [직장인 실무교육]

* 본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.