자료 구조 및 알고리즘

자료구조와 알고리즘은 프로그래밍을 위한 기본이다. 여기서 자료구조는 프로그래밍시 메모리의 효율적 사용과 빠른 실행 속도 및 정확한 처리를 궁극적인 목표로 하고 있고 알고리즘은 자료구조가 추구하는 목표에 기반하여 문제 해결을 위한 일련의 절차나 방법을 공식화된 형태로 표현한 것이다.

 

자료 구조

 

우리는 일상생활에서 사물들을 여러 가지 방법을 사용해서 정리한다. 예를 들어 버킷 리스트에는 평생에 걸쳐 이루고자 하는 목표를 차례대로 기록한다. 식당에서는 그릇들을 쌓아서 보관한다. 마트에서는 계산할 때 차례대로 줄을 서기도 한다. 영어사전에는 단어들과 단어들의 설명이 표기되어 있다. 컴퓨터는 계층구조를 이루고 있는 디렉토리를 이용하여 파일들을 저장한다. 지도에는 도시들과 도시들을 연결하는 도로가 표시되어 있다.

 

이처럼 사람들이 사물을 정리하여 저장하는 방법에는 여러 가지가 있다. 프로그램에서도 이와 마찬가지로 자료들을 정리하여 보관하는 여러 가지 구조들이 존재한다. 이를 자료 구조(data structure)라 부른다. 몇 가지의 예를 들어보면 식당에 그릇을 쌓는 것처럼 자료들을 쌓아서 정리하는 구조를 컴퓨터에서는 "스택"이라고 부른다. 스택에서는 맨 위에서만 자료를 추가하거나 제거할 수 있다. 마트 계산대의 줄에 해당하는 자료 구조를 큐라 부른다. 큐에서는 먼저 도착한 자료가 먼저 빠져나간다. 

 

흔히 "프로그램=자료구조+알고리즘"이라고 한다. 대부분의 프로그램에서 자료(data)를 처리하고 있고 이들 자료는 자료 구조를 사용하여 저장된다. 또한 주어진 문제를 처리하는 절차가 필요하다. 이것은 알고리즘(algorithm)이라고 불린다.

 

예를 들어 시험 성적을 읽어 들여서 최고 성적을 구하는 프로그램에 대하여 생각하여 보자. 외부에서 성적이 입력되면 이 성적들을 처리하여 좋게끔 프로그램의 어딘가에 저장시켜야 한다. 우리가 가장 쉽게 사용할 수 있는 것은 아마도 배열일 것이다. 이 경우, 배열이 자료를 저장하는 구조, 즉 자료 구조가 된다. 다음으로 필요한 것은 배열에 저장된 점수들 중에서 가장 큰 값을 찾는 절차이다. 여러 가지 방법으로 할 수 있겠지만 가장 간단하게 변수를 하나 만들고 배열의 첫 번째 요소 값을 변수에 저장한 다음, 이 변수와 배열의 요소들을 순차적으로 비교하여, 만약 배열의 요소가 더 크면 배열 요소의 값을 변수에 저장한다. 이런 식으로 배열의 끝까지 진행하면 최고 성적을 찾을 수 있다. 이렇게 문제를 해결하는 절차를 알고리즘이라고 한다. 

 

최고 성적을 구하는 프로그램을 C언어를 이용하여 작성하여 보면 다음의 프로그램롸 같다. 여기서 배열 scores가 자료구조에 해당되고 변수 largest를 첫 번째 요소로 쵸기화하고 나머지 요소들과 순차적으로 비교하는 것이 알고리즘에 해당한다.

 

#define MAX_ELEMENTS 100
int scores[MAX_ELEMENTS];  // 자료구조

int get_max_score(int n)  // 학생의 숫자는 n
{
    int i, largest;
    largest = scores[0];  // 알고리즘
    for (i = 1; i<n; i++) {
        if (scores[i] > largest) {
           largest = scores[i];
         }
     }
     return largest;
}

 

자료구조와 알고리즘은 밀접한 관계가 있어서 자료구조가 결정되면 그 자료구조에서 사용할 수 있는 알고리즘이 결정된다. 컴퓨터가 복잡한 자료들을 빠르게 저장, 검색, 분석, 전송, 갱신하기 위해서는 자료구조가 효율적으로 조직화되어 있어야 한다. 또한 각 응용에 가장 적합한 자료 구조와 알고리즘을 선택하여야 한다.

 

알고리즘이란

 

어떤 문제가 주어져 있고 이것을 컴퓨터로 해결하려고 한다고 가정하자. 첫 번째 해야 할 일은 문제를 해결할 수 있는 방법을 고안하는 것이다. 예를 들면 컴퓨터를 이용하여 전화번호부에서 특정한 사람의 이름을 찾는 문제를 생각하여 보자. 한 가지 방법은 전화번호부의 첫 페이지부터 시작하여 한 장씩 넘기면서 특정한 사람을 찾는 것이다. 이 방법은 엄청난 시간이 걸리는 방법이고 보통 이런 식으로 찾는 사람은 거의 없을 것이다. 또 하나의 방법은 전화번호부의 이름들이 정렬되어 있음을 이용하는 방법이다. 즉 찾고자 하는 이름이 "박철수"라고 하자. 전화번호부의 중간에 있는 이름과 "박철수"를 비교한다. 중간에 있는 이름보다 앞에 있다면 앞부분만 검색한다. 그렇지 않다면 뒷부분만 검색하면 된다. 이러한 과정을 박철수란 이름을 찾을 때까지 되풀이 한다. 이 방법은 굉장히 효율적인 방법이고 일반적인 사람들이 사용하는 방법이다. 이러한 방법들은 보통 프로그래밍 스타일이나 프로그래밍 언어와는 무관하다. 즉 C언어를 사용하건, Java를 사용하건, 사용되는 방법은 동일하다.

 

두 번째로 해야 할 일은 이들 방법에 따라 컴퓨터가 수행하여야 할 단계적인 절차를 자세히 기술하는 것이다. 컴퓨터로 문제를 풀기 위한 단계적인 절차를 알고리즘(algorithm)이라고 한다. 엄밀하게 이야기하면 알고리즘이란 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것이다. 따라서 알고리즘은 특정한 일을 수행하는 명령어들의 집합이다. 여기서 명령어란 컴퓨터에서 수행되는 문장들을 의미한다. 모든 명령어들의 집합이 알고리즘이 되는 것은 아니고 알고리즘의 되기 위한 조건들을 만족하는 집합만이 알고리즘으로 정의된다.

 

정의 - 알고리즘

- 입력 : 0개 이상의 입력이 존재하여야 한다.
- 출력 : 1개 이상의 출력이 존재하여야 한다.
- 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.
- 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다.
- 유효성 : 각 명령어들은 종이와 연필, 또는 컴퓨터로 실행 가능한 연산이어야 한다.

 

따라서 알고리즘에는 입력은 없어도 되지만 출력은 반드시 하나 이상 있어야 하고 모호한 방법으로 기술된 명령어들의 집합은 알고리즘이라 할 수 없다. 또한 실행할 수 없는 명령어들(예를 들면 0으로 나누는 연산)를 사용하면 역시 알고리즘이 아니다. 또한 무한히 반복되는 명령어들의 집합도 알고리즘이 아니다.

 

알고리즘을 기술하는 데는 다음과 같은 4가지의 방법이 있다.

① 한글이나 영어 같은 자연어

② 흐름도(flowchart)

③ 의사 코드(pseudo-code)

④ 프로그래밍 언어

 

①의 방법은 자연어를 사용하기 때문에 약간의 모호성이 존재한다. 이 모호성을 제거하기 위하여 명령어로 사용되는 단어들을 명백하게 정의해야만 알고리즘이 될 수 있다. ②의 방법은 도형을 사용하여 알고리즘을 기술하는 방법으로 초심자에게 좋은 방법이지만 알고리즘이 복잡해질수록 기술하기 힘들게 될 것이다. 따라서 가장 많이 쓰이는 방법은 ③, ④와 같은 의사 코드나 프로그래밍 언어를 사용하는 방법이다. 프로그래밍 언어의 예약어들은 모두 명백한 의미를 가지고 있어서 알고리즘을 기술하는데 안성맞춤이다. 의사 코드는 자연어보다는 더 체계적이고 프로그래밍 언어보다는 덜 엄격한 언어로서 알고리즘을 기술하는 데만 사용되는 코드를 말한다.