C언어로 쉽게 풀어쓴 자료구조 — 1장 자료구조와 알고리즘
1. 자료구조와 알고리즘
@자료구조
일상생활에서 사물들을 여러 방식으로 정리하듯이 프로그램도 자료들을 보관하기 위해서 여러 구조들을 가지고 있다. 이때, 프로그램이 자료를 정리하기 위한 구조를 자료정리라고 정의한다.
@자료구조의 종류
대표적인 자료구조로는 크게 스텍과 큐로 나눌 수 있다.
스택(Stack) : 접시를 쌓는 것처럼 정보를 쌓아서 정리하는 자료구조로 맨 위에서만 데이터를 추가하거나 제거할 수 있다.
큐(Queue) : 계산대의 줄과 같이 들어온 순서대로 연산이 처리되는 방식의 자료구조로 맨 처음 들어온 데이터가 가장 먼저 처리된다.
그 외에도 그래프, 트리, 사전, 리스트 등의 자료구조가 존재한다.
@프로그램의 구성
프로그램 = 자료구조 + 알고리즘
대부분의 프로그램에서 자료를 처리하고 있고 이들 자료는 자료구조를 사용하여 저장된다. 또한 프로그램이 문제를 해결하기 위해서는 어떠한 절차, 알고리즘에 따라 자료구조를 이용해 문제를 해결한다.
컴퓨터가 복잡한 자료를 빠르게 저장, 삭제, 전송, 검색, 분석, 갱신하기 위해서는 자료구조가 효율적으로 조직화되어야 하며 가장 적합한 알고리즘을 선택해야 한다.
@알고리즘
어떠한 문제를 해결할 때, 첫번째로 할 것은 문제를 해결할 수 있는 방법을 구현하는 것이다. 방법을 구현하는 것은 대부분 프로그래밍 방식이나 사용 언어에 구애받지 않는다.
두번째로 구현한 방법을 컴퓨터가 수행할 수 있도록 단계적인 절차를 자세히 기술하는 것이다. 이때, 컴퓨터가 문제를 풀기 위한 단계적인 절차를 알고리즘(Algorithm)이라고 하고 두번째 단계는 알고리즘을 짜는 것으로 볼 수 있다.
더 자세히 말하자면 알고리즘은 문제가 주어진 상태에서 컴퓨터가 문제를 해결할 수 있는 방법을 장치가 이해할 수 있는 언어로 자세히 기술한 것, 즉 특정한 일을 수행하는 명령어들의 집합이라고 정의할 수 있다.
#단, 알고리즘에는 특정 조건을 만족하는 명령어만 포함된다.
@알고리즘의 정의
● 입력 : 0개 이상의 입력이 존재해야 함
● 출력 : 1개 이상의 출력이 존재해야 함
● 명백성 : 각 명령어의 의미가 모호하지 않고 명확함
● 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 함
● 유효성 : 각 명령어들은 종이와 연필, 컴퓨터로 실행 가능한 연산이여야 함
알고리즘은 위의 5가지 조건이 모두 만족해야만 성립한다.
@알고리즘의 기술방법
● 한글이나 영어같은 자연어
->자연어의 경우 약간의 모호성이 존재하기 때문에 명령어를 확실하게 정의해야 한다.
● 흐름도
->흐름도의 경우 도형을 사용하여 초심자에게는 쉽지만 알고리즘이 복잡해지면 기술하기 어렵다.
● 의사 코드
프로그래밍 언어와 함께 가장 많이 사용되는 기술방법으로 자연어보다는 체계적이고 프로그래밍 언어보다는 덜 엄격한 특징을 가져 알고리즘을 구현하는 데만 사용된다.
#의사코드의 경우 c언어와 비슷하나 대입연산자가 ‘=’이 아닌 ‘<-’이다.
● 프로그래밍 언어
프로그래밍 언어의 예약어들은 모두 명백한 의미를 가지고 있기 때문에 알고리즘을 기술하기에 적합하다.
2. 추상 자료형
@자료형
자료형(data type)이란 데이터의 종류를 말한다. 대표적인 자료형의 종류는 정수, 실수, 문자열 등 다양하며 이러한 자료형들은 프로그래밍 언어에서 기본적으로 제공한다.
@자료형의 분류
● 기초 자료형 : char,int,float,double 등
● 파생 자료형 : 배열, 포인터
● 사용자 정의 자료형 : 구조체, 공용체, 열거체
자료형을 작성할 때에는 실행 가능한 연산에도 신경써야 하며 이는 곧 자료형을 고려할 때, 데이터뿐만 아니라 데이터 간의 연산도 고려해야 한다는 것을 의미한다.
#복잡한 자료형의 연산은 주로 함수로 정의한다.
@추상자료형
추상자료형(ADT : abstract data type)이란 추상적, 수학적으로 자료형을 정의한 것이다.
소프트웨어 개발과 유지보수에 있어서 가장 중요한 이슈는 소프트웨어의 복잡성을 관리하는 것이다. 이러한 복잡성에 대처하기 위해 많은 알고리즘과 프로그래밍 언어가 개발되었고 이러한 알고리즘과 프로그래밍 언어는 추상화를 핵심으로 개발되었다.
#추상화(abstraction) : 어떤 시스템의 간략화된 기술 또는 명세로서 시스템의 정말 핵심적인 동작과 구조에만 집중하는 것
좋은 추상화는 사용자에게 중요한 정보는 강조하고 세세한 것들은 제거하는 것이다. 이를 위하여 정보은닉기법(information hiding)가 개발되었고 추상자료형(ADT)의 개념으로 발전하였다.
@추상자료형의 구현
추상자료형은 실제적인 구현으로부터 분리되어 정의된 자료형으로 데이터나 연산이 무엇(what)인 것은 정의되지만 어떻게(how) 구현될지는 정의하지 않는다.
추상자료형 안에는 객체와 함수들이 정의되고 객체는 주로 집합의 개념을 사용하여 정의된다. 그후 함수가 구현되며 함수의 이름,매개변수, 반환형, 수행 기능의 문장 등이 포함된다.
#’::=’의 경우 ‘~으로 정의된다’를 의미한다.
추상자료형을 구현할 때는 주로 세부사항을 알리지 않고 외부와의 인터페이스만을 제공한다. 따라서 구현방법을 언제든 안전하게 변경할 수 있다. 이는 곧, 인터페이스만 안전하다면 추상자료형을 여러 방법으로 구현할 수 있다고 볼 수 있다. 이러한 것은 정보은닉기법에서 가장 기본적인 명제이고 추상자료형의 중심 아이디어이다.
프로그래밍 언어에 따라 추상자료형은 여러 방법으로 구현된다. 객체지행언어(c++, java 등)에서는 클래스 개념을 통해 구현된다. 추상 자료형의 객체는 클래스 속성으로 구현되고 연산은 클래스의 맴버함수로 구현된다. 또한 private와 protected를 통해 내부 접근을 제한할 수 있다. 또한 클래스는 계층구조로도 구성될 수 있다.
3. 알고리즘의 성능 분석
@효율적인 알고리즘
컴퓨터는 계속해서 발전하여 계산속도와 메모리 용량이 나날이 발전하고 있다. 그럼에도 불구하고 프로그램의 효울성은 아직도 중요한 요소로 뽑히고 있다. 이러한 이유는 크게 2가지로 볼 수 있다.
- 상용 프로그램의 규모가 이전에 비해 매우 커져 처리해야 할 자료가 많아져 효율성이 중요해졌다.
- 사용자들이 빠른 프로그램을 선호하여 효율성이 떨어지면 경쟁에서 살아남기 어렵다.
효율적인 알고리즘이란 결과가 나올 때까지 수행시간이 짧으면서 자원을 적게 사용하는 알고리즘을 말한다.
@수행시간 측정방법
프로그램의 효율성을 측정하는 가장 간단한 방법은 알고리즘을 프로그래밍 언어로 작성하여 실제 컴퓨터상에서 실행시킨 후, 그 수행시간을 측정하는 것이다.
c언어에서는 2가지의 방법이 있다.
- clock()함수를 통하여 호출 프로세스에 의해 사옹된 CPU 사용시간을 계산
->clock()함수는 시스템 시각을 CLOCKS_PER_SEC 단위로 반환하기 때문에 수행기간을 측정하기 위해서는 알고리즘 실행 전에 clock()함수를 실행하여 변수1에 저장하고 끝나면 다시 clock()함수를 호출하여 변수2에 기록한다. 그후 (변수1 — 변수2)의 값을 CLOCKS_PER_SEC으로 나누어 주어야 한다.
2. time()함수를 사용하여 측정
->알고리즘 시작과 종료 시점에서 time()함수를 호출하고 difftime()함수를 통해 시간을 측정한다.
그러나 이러한 방법은 몇가지 문제점을 가지고 있다.
- 알고리즘을 구현하고 테스트하는 것이 필요하기 때문에 복잡한 알고리즘의 경우 구현이 부담될 수 있다.
- 반드시 똑같은 하드웨어를 사용하여 알고리즘의 수행시간을 측정해야 한다. 하드웨어마다 수행기능이 다르기 때문에 다른 하드웨어로 측정을 할 경우, 정확한 시간을 측정할 수 없을 수 있다.
- 실험되지 않은 입력에 대해서는 수행시간을 주장할 수 없다.
@알고리즘 복잡도 분석
알고리즘 복잡도 분석은 구현을 하지 않아도 알고리즘의 효율성을 따져볼 수 있는 기법으로 여러 알고리즘 중 하나를 선택해야 하는 경우 알고리즘 복잡도 분석이 사용된다. 알고리즘 복잡도 분석은 구현되지 않아도 모든 입력을 고려할 수 있는 방식이며 하드웨어나 소프트웨어 환경과 관계없이 수행시간을 측정할 수 있다.
알고리즘 분석에서는 2가지 측면을 고려할 수 있는데 수행시간과 알고리즘이 필요로 하는 기억공간의 양이다. 수행시간 분석을 시간 복잡도라고 하고 기억공간 분석을 공간 복잡도라고 한다. 대부분의 알고리즘의 복잡도는 시간 복잡도를 말하는데 이는 대부분 필요한 공간보다는 걸리는 시간에 더 관심을 가지기 때문이다.
시간복잡도는 절대적인 수행시간을 나타내는 것이 아닌 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 측정하여 표시한다. 즉, 알고리즘이 수행하는 연산의 수를 측정하여 시간 복잡도를 측정한다고 할 수 있다.
예를 들어 동일한 조건에서 같은 일을 할 때, A는 20번의 연산을, B는 100번의 연산을 수행한다면 A가 더 효율적인 알고리즘이라고 할 수 있다.
그러나 연산의 수행횟수는 입력에 따라 변하기 때문에 상수가 아니다. 그러므로 일반적으로 연산의 수행횟수는 고정된 숫자가 아니라 입력의 개수에 대한 함수라고 할 수 있다. 이러한 함수를 시간 복잡도 함수라고 하며 T(n)이라고 한다.
#n이 커질수록 수행시간은 늘어나며 덧셈보다 곱셈에서 비약적으로 상승한다.
@빅오 표기법
일반적으로 입력의 개수와 시간 복잡도 함수의 관계는 상당히 복잡하다. 그러나 자료의 개수가 많을 경우 차수가 가장 큰 항이 가장 영행을 미치고 다른 항들은 상대적으로 무시될 수 있다.
예를 들어 t(n) = n의 제곱 + n + 1이라고 가정하면 n이 1000일 때, n의 제곱 값은 전체의 99.9%를 차지하고 나머지는 0.01%를 차지한다. 따라서 입력값이 크다면 가장 차수가 큰 항이 대부분의 영향력을 가져감을 볼 수 있다.
보통 복잡도 함수에서 중요한 것은 n이 증가하였을 때, 연산의 총 횟수가 n에 비례하여 증가하는지, 아니면 n의 제곱에 비례하여 증가하는지, 아니면 다른 증가추세를 가지는지가 중요하다.
시간복잡도 함수에서 불필요한 정보를 제거하고 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표시법이라고 한다. 빅오 계산법은 O(n)으로 나타내며 n의 값에 따른 함수의 상한값을 나타내는 방법이다.
#빅오 표기법 : 두 함수 f(n)과 g(n)이 주어졌을 때 모든 n>n0에 대하여 |f(n)| <= c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=O(g(n))이다.
빅오 표기법을 사용하면 시간 복잡도 함수의 증가에 별로 기여하지 못하는 항을 생략함으로써 시간 복잡도를 간단하게 표시할 수 있다. 빅오 표기법을 얻는 간단한 방법은 기본연산의 횟수가 다항식으로 표현되었을 경우 다항식의 최고차항만을 남기고 다른 항들과 상수항을 버리는 것이다. 최고차항의 계수도 버리고 단지 최고차항의 차수만을 사용한다. 단, logn은 차수를 가지고 있으므로 버리면 안된다.
@빅오 표기법의 표시방법
● O(1) : 상수형
● O(logn) : 로그형
● O(n) : 선형
● O(nlogn) : 선형로그형
● O(n의 제곱) : 2차형
● O(n의 세제곱) : 3차형
● O(2의 n제곱) : 지수형
● O(n!) : 팩토리얼형
빅오 표기법은 결국 입력의 개수에 따른 기본 연산의 수행 횟수를 개략적으로 나타낸 것이므로 이것을 이용하여 알고리즘의 대략적인 수행기간을 측정할 수 있다.
O(1) < O(logn) < O(n) < O(nlogn) < O(n의 제곱) < O(2의 n제곱) < O(n!)
여기서 주의할 점은 상수항이나 계수가 큰 경우, 수행시간에 영향을 준다는 것이다. n이 작을 때는 상수항이나 각항의 계수도 영향을 준다.
알고리즘이 지수형이나 팩토리얼형의 시간 복잡도를 가지면 사실상 사용할 수 없다. 이는 입력의 개수가 30이 넘을 경우 슈퍼 컴퓨터를 통해도 우주 탄생에서 지금까지의 시간보다 더 긴 시간이 걸리기 때문이다.
빅오 표기법 이외의 표기법
빅오 표기법의 문제는 f(n) = 2n + 1일 경우 f(n) = O(n)이라 하지만 사실은 f(n) = O(n의 제곱)이라는 것이다. 그 이유는 n0 = 1, C =2로 잡으면 n>1에 대하여 2n + 1 <= 2*n의 제곱이기 때문이다.
빅오 표기법은 최소 차수 함수로 표기되었을 때만 의미가 있다. 이를 보완한 것이 빅오메가와 빅쎄타 표기법이다.
빅오메가 표기법은 어떤 함수의 하한을 표시하는 방법이다. 예를 들어 f(n) = 2n + 1이면 n>1에 대하여 f(n)=Ω(n)이다.
빅세타는 동일한 함수로 상한과 하한을 만들 수 있는 경우, 즉, f(n) = O(g(n))이고 f(n)=Ω(g(n))인 경우 f(n) = Θ(g(n))이다.
3개의 표기법 중 가장 정밀한 것은 빅세타이다. 그러나 통상적으로 비공 표기법을 가장 많이 사용한다. 단 그때는 최소차수로 상한을 표시한다고 가정한다.
@최선, 평균 ,최악의 경우
최선, 평균, 똑같은 알고리즘도 주어지는 입력의 집합에 따라 다른 수행 시간을 보일 수 있다. 즉, 특정한 자료 집합이 주어지면 다른 자료 집합보다 더 빨리 수행될 수 있다.
알고리즘의 효율성은 주어지는 자료집합에 따라 다음의 3가지 경우로 나누어서 평가할 수 있다.
1. 최악의 경우 자료집합 중에서 알고리즘의 수행시간이 가장 오래 걸리는 경우이다.
2. 최선의 경우 수행시간이 가장 적은 경우이다.
3. 평균적인 경우 알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려하여 평균적인 수행시간을 의미한다.
3가지 중 평균적인 수행시간이 가장 좋아 보인다. 그러나 평균 수행시간을 산출하기 위해서는 광범위한 자료 집합에 대하여 알고리즘을 적용시켜서 평균값을 계산해야 해서 구하기 힘들 수도 있다. 최악 수행시간은 시간 복잡도 척도로 많이 쓰이는데 입력 자료 집합을 알고리즘에 최대한 불리하도록 만들어서 얼마만큼의 시간이 소모되는 지를 분석할 수 있기 때문이다. 이 때문에 어떤 의미에서는 최악 수행시간이 평균적인 수행시간보다 중요하다고 볼 수 있다. 최선의 경우는 별 의미 없는 경우가 대부분이다.
