Part 1. 데이터 구조 - 데이터 구조와 알고리즘, 자료형, 빅 오 표기법

1. 데이터 구조와 알고리즘, 자료형, 빅 오 표기법

  1장에서는 데이터 구조와 알고리즘이 무엇인지 살펴보고 기본 자료형과 빅 오(O) 표기법에 대해 간단히 설명한다. 본 도서의 목적은 프로그래밍 코드 없이 간단한 설명만으로 알고리즘을 이해하는 것이므로 프로그래밍 언어의 문법을 다루지 않고 알고리즘적 사고에 중점을 두고 설명이 진행된다. 해당 알고리즘에 대해 더 깊은 사고를 하기 위해서는 알고리즘을 더 상세하게 소개한 다른 도서를 찾는 것을 추천한다. 1장을 소개하기 전, 간단히 데이터가 무엇인지 짚고 넘어가도록 하겠다. 데이터는 직업이나 관심 분야에 따라 단어가 뜻하는 의미가 다양하지만, 본 도서에서 언급하는 데이터는 컴퓨터에 저장되어 있거나 컴퓨터가 가공 및 처리하는 모든 것을 뜻한다. 여기서 정보는 가공이나 처리가 끝난 데이터를 의미하는 말이므로 데이터와 정보의 개념을 혼동하지 않도록 주의한다.

 

데이터 구조

  데이터 구조는 데이터를 구성하고 저장하는 방법을 설명하며, 데이터를 식별하는 방법을 제공, 데이터의 관계를 보여주는 개념이다. 하나의 도형이 하나의 데이터라고 할 때, 도형의 종류와 배열되어있는 상태를 식별하는 것 자체를 데이터 구조라고 하며, 데이터 구조는 아래의 그림과 같이 ○와 △를 구분하여 데이터를 구성하고 저장하는 메커니즘을 제공할 수 있다.

  데이터 구조는 각 요소(○,△)에 접근할 수 있으며, 아래 그림과 같이 각 요소에 식별자(숫자 등)을 지정할 수 있다. 이를 통해 2번째 도형이 필요한 경우 해당 "2번째"라는 의미가 왼쪽으로부터의 2번째인지, 오른쪽으로 부터의 2번째인지를 고민하지 않고 식별자가 2인 도형을 바로 전달할 수 있게 된다.

 

 

알고리즘

  알고리즘은 문제를 해결하기 위해 사용하는 일련의 단계로, 정해진 순서대로 문제를 해결하는 방법, 즉 '절차'라 말할수있다. 알고리즘의 의미는 다양하게 해석할 수 있지만 모든 해석의 공통점은 문제를 해결하는 논리적 단계라는 뜻을 포함한다는 것이다. 문제를 해결하기 위해서는 알고리즘은 단순해야 하지만 명확하고 모호하지 않아야 한다.

  알고리즘에서 데이터구조가 필요한 이유는 "과일을 접시에 담는다"라는 행위를 수행하는 로봇에게서 찾을 수 있다. 로봇의 앞에 토마토가 놓여 있다고 가정하였을 때, 로봇이 토마토가 과일인지 채소인지 알지 못하는 상태라면 접시에 담아야 할지, 담지 말아야 할지 모르게 된다. 이때 토마토가 채소라 명시된 데이터 구조를 로봇이 가지고 있었다면, 로봇은 토마토가 과일이 아니기 때문에 접시에 담지 않을 것이다.

 

데이터 구조와 알고리즘의 관계

  데이터 구조와 알고리즘은 서로 다른 개념이지만 상호 보완적이다. 데이터 구조는 알고리즘이 다루는 데이터를 구성하며, 알고리즘이 데이터를 처리하고 사용자가 원하는 완전한 정보를 산출하는 과정에서 필요한 부분을 제공한다. 이를 위에서 설명하였던 과일을 접시에 담는 로봇을 예로 들자면, "과일 보관함에서 과일을 꺼내 접시에 담는 일련의 과정(알고리즘)을 수행하는 로봇이 과일이 무엇인지를 정의해 둔 데이터 구조의 구성원에 토마토가 있는지 확인함으로써 눈 앞에 있는 토마토가 과일인지 확인할 수 있는 것"이라 설명할 수 있다. 즉, 데이터 구조는 알고리즘이 결과를 산출하는 과정에서 처리하는 데이터를 저장하고 구성하는 것이다.

 

기본 자료형 - 불, 문자, 정수, 부동 소수점 수

  데이터는 컴퓨터에 저장되어 있거나 컴퓨터가 처리 중인 모든 것을 뜻한다. 데이터는 자료형을 통해 분류되며, 자료형이란 처리할 데이터의 속성이 무엇인지, 데이터로 수행하려는 작업이 무엇인지를 컴퓨터에 알려주는 것이다. 기본 자료형(원자 자료형)은 불(boolean), 문자(character), 정수(integer), 부동 소수점 수(floating-point number) 4가지로 구분되며, 이는 가장 기본적인 프로그래밍 언어인 C언어에 기반으로 만들어진 자료형이다.

  불(boolean)은 논리 자료형으로 참(true)과 거짓(false)으로 이루어져 0과 1, 켜기와 끄기 같은 전통적인 컴퓨터 환경을 구성하는 상태를 표현한다. 산술 논리장치나 명령 레지스터 등 이진 데이터를 사용하는 장치에서는 불 자료형을 이용하여 표현하는 것이 쉽고 간편하다. 한편 양자 컴퓨팅 분야에서는 큐비트(qubit)라는 양자비트가 존재하는데, 이 자료형은 0과 1을 포함하여 0과 1이 아닌 어느 쪽도 확정할 수 없는 상태도 함께 표현한다.

  문자(character)는 사람이 사용하는 자연어를 처리하기 위한 자료형이다. 컴퓨터는 이진 숫자를 기반으로 프로그램을 이해하지만, 사람은 이진 숫자를 한번에 파악하기 어렵기 때문에 사용하며, 컴퓨터마다 사용하는 인코딩 방식이 서로 다를 수 있다. 

  정수(integer)는 자연수, 0, 음수를 함께 부르는 말이며, 컴퓨터의 숫자처리를 위해 사용되는 자료형이다. 컴퓨터에서 정수는 CPU 아키텍처와 메모리 용량의 한계, 프로그래밍 언어에 정해져 있는 정수 범위의 제한으로 인해 무한한 숫자는 아니다. 상황에 따라 직접 원하는 범위의 정수를 다루는 자료형을 만들어야 하는 경우도 있을 수 있다.

  부동 소수점 수(floating-point number)는 소수점을 포함한 소수를 표현하는 자료형으로, 작은 점(.)의 위치가 움직이며 숫자를 표현하기 때문에 부동점(floating point)라는 이름이 붙었고, 이를 한국어로 번역하는 과정에서 부동 소수점이라는 이름이 붙게 되었다. 부동 소수점의 정밀도는 단정도(single precision)와 배정도(double precision)로 나뉘게 되는데, 단정도는 32비트를 1 워드로 표현하고 배정도는 64비트를 1 워드로 표현한다. 따라서 단정도 부동 소수점 수를 표현하는 자료형은 float(32비트), 배정도 부동 소수점을 표현하는 자료형을 double(64비트)로 구분한다.

 

함수 - 함수, 메소드, 프로시저, 서브루틴

  함수(function)는 컴퓨터 과학과 밀접하게 관련된 수학적 개념으로, 프로그래밍에서의 함수는 특정 동작을 수행하는 코드 덩어리를 뜻한다. 즉, 어떤 처리 과정을 수행한 후 출력을 제공하는 상자와 같은 개념이다. 프로그래밍에서의 함수는 매개변수(파라미터) 또는 인수라고 하는 데이터를 입력으로 사용하며 때로는 결과를 반환한다. 이때, 결과를 반환하지 않는 함수를 void함수(C 기반)라고 부른다. 여기서 매개변수란 함수를 정의할 때 사용하는 변수이며 인수는 함수를 호출하며 전달하는 매개변수의 실제 값을 말한다.

  객체지향 프로그래밍 언어에서는 청사진 역할을 하는 특수한 코드를 클래스라고 부르며, 클래스 내부에 있는 함수를 메소드라 부른다. 근본적으로 메소드는 클래스의 객체 이름을 이용해 호출하는 함수를 뜻한다. 일부 프로그래밍 언어에서는 이러한 함수를 프로시저, 또는 서브루틴이라고 칭하며 일부 프로그래머 사이에서는 값을 반환하지 않는 함수를 프로시저라 칭하기도 한다.

  함수, 메소드, 프로시저, 서브루틴은 프로그래밍 언어에 따라 지칭하는 용어가 달라질 뿐 모두 의미와 사용하는 목적이 같다. 이들은 모두 커다란 프로그램 내에서 호출될 수 있는 작은 프로그램 또는 하위 프로그램이다.

 

재귀와 반복

  재귀함수란 프로그램이 실행되는 도중 자기 자신을 호출하는 함수이다. 이러한 재귀 함수는 보통 특정 조건을 충족할 때까지 끊임없이 동작하게 된다. 이러한 재귀 함수가 중단되지 않고 지속적으로 호출되게 되면 컴퓨터의 가용 메모리 공간이 점점 줄어들어 결국 자기 자신을 호출하는 횟수의 한계인 최대 재귀 깊이(maximum recursion depth)를 초과해 스택 오버플로 에러(stack overflow error)가 발생할 수 있다.

  반복은 재귀와 혼동해서는 안되는 다른 개념이다. 알고리즘 내부에서 반복이란, 특정 조건이 충족될 때까지 코드 덩어리의 실행이 되풀이되는 것을 뜻한다. 반복에서 유의할 점은, 재귀와 마찬가지로 컴퓨터 가용 메모리의 한계 때문에 반복의 종료 조건을 지정하지 않으면 프로그램 에러가 발생한다는 것이다.

 

알고리즘의 세 가지 유형

  알고리즘은 분할 정복 알고리즘(divide and conquer algorithm), 탐욕 알고리즘(greedy algorithm), 동적 프로그래밍(dynamic progromming= 동적 계획법) 알고리즘 3가지가 있다. 분할 정복 알고리즘은 큰 문제를 여러 개의 작은 문제로 나눠 해결하고, 결과를 결합해 하나의 해결 방법을 얻는 알고리즘이다. 하나의 나무에서 모든 이파리를 떼어내야 하는 문제에 분할 정복 알고리즘을 적용한다면, 한 사람이 모든 이파리를 떼어내는 것이 아닌 수천 명의 사람이 각자 하나씩 이파리를 떼어내어 이파리를 모으도록 해결 절차를 정하게 된다. 분할 정복 알고리즘은 이처럼 큰 목표를 작게 나누어 쉽게 목표를 달성할 수 있도록 하는 것이다.

  탐욕 알고리즘은 실행되는 순간(특정 순간)마다 최상의 결정(가장 적합한 동작)을 내리는 알고리즘이지만, 해당 결정이 문제 전체를 해결할 수 있는 최적의 방법인지는 장담할 수 없다. 방문 판매원 문제를 통해 알고리즘의 동작 방향을 알아보자면, n개의 도시를 방문하는 최적경로를 찾는다고 할 때, 탐욕 알고리즘은 현재 위치한 도시에서 가장 가까운 다음 도시를 찾아 움직이게 된다. 이것이 전체적으로 보았을 때 최단 경로인지는 장담하지 못하지만, 지금 순간의 최적 경로가 되는 것이다.

  동적 프로그래밍 알고리즘은 탐욕 알고리즘과 대조적으로, 과거에 내린 결정이 앞으로의 결정에 영향을 주게 되는 알고리즘이다. 탐욕 알고리즘은 특정 순간에 최적인 해결방법을 찾지만 동적 프로그래밍 알고리즘은 문제를 해결하는 다양한 해결방법을 찾아 저장하여 재사용을 한다. 해당 알고리즘은 음성인식 또는 연쇄 행렬 곱셈에 주로 사용하며, 두 알고리즘을 간단히 정리하자면 탐욕 알고리즘은 근사치를, 동적 프로그래밍 알고리즘은 최적 값을 구하는 것이라고 할 수 있다.

 

알고리즘 분석

  알고리즘을 설계하는 것과 분석하는 것은 별개의 과정이다. 알고리즘을 설계한 뒤에는 알고리즘의 성능을 분석할 필요가 있다. 문제를 해결하기 위해 사용하는 단계가 적을수록 더 효율적인 알고리즘이라고 할 수 있는데, 이러한 알고리즘의 효율성을 분석할 때는 시간 복잡도(time complexity)와 공간 복잡도(space complexity)의 두 가지 방법을 이용한다.

 

1) 시간복잡도 : 주어진 입력에 따라 알고리즘이 문제를 해결할 때 걸리는 시간을 뜻하며, 알고리즘의 성능이 얼마나 효율적인지 알 수 있는 가장 일반적인 방법 2) 공간 복잡도 : 알고리즘이 문제를 해결할 때 점유하는 컴퓨터의 메모리 공간을 뜻하며, 널리 사용되는 방법은 아니지만 자원이 제한된 시스템에서 동작하는 프로그램을 구현하는 것과 같이 특별한 경우에 사용된다.

 

  효율성을 분석할 때 사용되는 두 가지 방법 중 일반적으로 자주 사용되는 시간 복잡도를 분석하는 방법 또한 실제적인 방법, 수학적인 방법 두 가지로 분류된다. 실제적인 방법은 입출력 데이터의 양이 알고리즘 동작에 미치는 영향을 관찰하고 기록하여, 이를 바탕으로 알고리즘이 얼마나 효율적인지 판단한다. 하지만 이러한 방법은 정확성이 떨어지고 사용범위가 제한적이라 수학적인 방법을 주로 사용한다. 수학적으로 판단하는 방법은 점근적 분석(asymptotic analysis)이라고도 부른다. 이 분석방법은 수학적으로 알고리즘 성능의 한계를 증명하여 실제적인 방법보다 많은 시간을 절약할 수 있는 방법이기도 하다. 구체적으로 수학적 분석 방법은 알고리즘의 성능이 최악이 되는 경계를 판단하거나 알고리즘의 평균 성능을 찾는다. 이때, 점근적 증가율(시간 효율성/데이터 양이 많을 때 얼마나 오래 걸리는지)을 비교하기 위해 빅 오(O) 표기법을 사용한다. 

 

빅 오 표기법

  알고리즘의 효율성을 수학적으로 판단하는 방법은 몇 가지 범주로 구분할 수 있다. 1) 알고리즘을 실행하는 데 걸리는 시간이 가장 긴 최악의 경우를 측정하는 것(빅 오/O, 리틀 오/o) 2) 실행하는 데 걸리는 시간이 가장 짧은 최상의 경우를 측정하는 것(빅 오메가/Ω, 리틀 오메가/ω) 3) 최악의 경우와 최상의 경우를 모두 측정하는것(세타/Θ) 4) 알고리즘을 실행하는데 걸리는 시간의 평균을 측정하는 것 등이다.

  이러한 여러 측정법과 표기법 중 점근적 분석에 가장 많이 사용되는 것은 빅 오 표기법이며, 빅 오의 대문자 O는 시간 복잡도의 정도를 나타내는 표기법인 차수(order, order of complexity)를 뜻한다. 

 

[빅 오 표기법의 실행 시간 표기 방법]

구분	설명
O(1)	상수형 알고리즘이며, 데이터 입력량과 무관하게 실행 시간이 일정하다.
O(n)	선형 알고리즘이며, 데이터 입력량에 비례하여 실행시간이 늘어난다.
O(logn)	로그형 알고리즘이며, 시간이 선형적으로 증가하면 n이 기하급수적으로 증가한다. 이는 데이터 입력량이 늘어날수록 단위 입력당 실행 시간이 줄어든다는 뜻이다.
O(nlogn)	선형-로그형 알고리즘이며, 데이터 입력량이 n배 늘어나면 실행시간이 n배 조금 넘게 늘어난다.
O(n²)	2차 알고리즘이며, 데이터 입력량의 제곱에 비례하여 실행시간이 늘어난다.
O(2ⁿ)	지수형 알고리즘이며, 데이터 입력이 추가될 때마다 실행 시간이 2배로 늘어난다.
O(n!)	계승(팩토리얼)형 알고리즘이며, 데이터 입력이 추가될 때마다 실행시간이 n배로 늘어난다.

  빅 오 표기법에서 성능이 좋은 순서대로 나열하면 O(1), O(logn), O(n), O(nlogn), O(n²), O(2ⁿ), O(n!)와 같다. 상수형 알고리즘인 O(1)의 성능이 가장 좋고, 계승(팩토리얼) 형 알고리즘인 O(n!)의 성능이 가장 나쁘다. O(n!)은 실제로 컴퓨터 과학이 해결해야 하는 복잡한 문제의 시간 복잡도이며, 대표적으로 앞서 살펴봤었던 방문 판매원 문제가 여기 속한다.