자료구조와 알고리즘

자료구조란?

사람들이 사물을 정리하는 것과 마찬가지로 프로그램에서 자료(Data)들을 정리하는 여러가지 구조

컴퓨터 프로그램은 논리적으로 따져보면 '자료구조'와 '알고리즘'으로 구성되어있다.

#define MAX_ELEMENTS 100

int score[MAX_ELEMENTS]; //자료구조
int main(){

int i,tmp;
tmp=score[0];

for(int i=1;i<n;i++){ //알고리즘
	if(score[i]>tmp){
    tmp=score[i];
    }

}

printf("%d\n",tmp);

return 0;
}

자료구조와 알고리즘은 밀접한 관계가 있고 자료구조가 결정되면 그 자료구조에서 사용할 수 있는 알고리즘이 결정된다.

컴퓨터가 복잡한 자료들을 빠르게 저장, 검색, 분석, 전송, 갱신하기 위해서는 자료구조가 효율적으로 조직화되어 있어야 하며 응용 프로그램에서 가장 적합한 자료구조와 알고리즘을 선택해야 한다.

알고리즘이란?

컴퓨터로 문제를 풀기 위한 단계적인 절차, 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것(명령어들의 집합)

모든 명령어들의 집합이 알고리즘이 되는 것은 아니고 다음과 같은 조건들을 만족하는 집합만이 알고리즘으로 정의된다.

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

따라서 알고리즘에는 입력은 없어도 되지만 출력은 반드시 하나 이상 있어야 하고 모호한 방법으로 기술된 명령어들의 집합은 알고리즘이라고 할 수 없다.

또한 컴퓨터가 실행할 수 없는 명령어(ex.몫이 0인 나눗셈)를 사용하면 알고리즘이 아니고, 무한히 반복되는 명령어들의 집합도 알고리즘이 아니다.

알고리즘을 기술하는 가장 많이 쓰이는 방법은 유사 코드(pseudo-code)와 프로그래밍 언어이다.

추상 데이터 타입

데이터(Data)란? 처리의 대상이 되는 모든 것 ex.정수, 문자열, 실수 등

데이터 타입(Data type)이란? 데이터의 집합과 이러한 데이터에 적용할 수 있는 연산의 집합

추상 데이터 타입(Abstract data type)이란? 데이터 타입의 정의가 그 데이터 타입의 구현으로부터 분리된 데이터 타입

알고리즘의 성능 분석

컴퓨터는 예전에 비하여 엄청난 계산 속도와 방대한 메모리를 자랑하지만 여전히 프로그램(알고리즘)의 효율성은 중요하다.

첫 번째 이유 : 최근 상용 프로그램의 규모가 이전에 비해서는 엄청나게 커지고 있기 때문, 즉 처리해야 할 자료의 양이 많음.

두 번째 이유 : 사용자들은 여전히 빠른 프로그램을 선호하기 때문.

따라서 프로그래머는 하드웨어와는 상관없이 소프트웨어적으로 최선의 효율성을 갖는 프로그램을 제작하도록 노력해야 함.

효율적인 알고리즘이란? 알고리즘이 시작하여 결과가 나올 때까지의 실행 시간이 짧으면서 컴퓨터 내에 있는 메모리와 같은 자원을 덜 사용하는 알고리즘이다.

일반적으로 실행 시간이 메모리 공간보다 더 중요하게 고려되기 때문에 '알고리즘의 실행 시간'을 효율적인 알고리즘의 기준으로 삼는다.

실행 시간 측정 방법

알고리즘을 구현하여 실행 시간을 측정하는 방법은 정확하고 확실한 방법이다.

하지만 하드웨어나 소프트웨어 환경에 영향을 많이 받기 때문에 구현하지 않고 알고리즘의 효율성을 따지는 기법이 필요하다.

알고리즘의 복잡도 분석 방법

만약에 여러가지 알고리즘 중에서 가장 효율적인 알고리즘을 선택해야 하는 경우, 직접 구현하지 않고도 대략적인 알고리즘의 효율성을 비교하는 방법이 복잡도 분석(Complexity analysis)이다.

알고리즘 복잡도 분석은 구현하지 않고도 모든 입력을 고려하는 방법이고 실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.

시간 복잡도 함수

알고리즘 분석에서는 실행 시간 분석을 시간 복잡도(Time complexity)와 기억 공간 분석을 공간 복잡도(Space complexity)라고 한다.

우리가 알고리즘의 복잡도를 이야기할 때 대개는 시간 복잡도를 말한다.

시간 복잡도는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아니라 알고리즘을 이루고 있는 연산들이 몇 번이나 실행되는지를 숫자로 표시한다.

알고리즘의 복잡도를 분석할 때는 산술, 대입, 비교, 이동 등의 연산의 실행 횟수를 사용한다.

즉, 어떤 알고리즘이 수행하는 연산의 개수를 계산하여 두 개의 알고리즘을 비교할 수 있다.

연산들의 수행 횟수는 보통 프로그램에 주어지는 입력의 개수 n에 따라 변하게 된다. 따라서 일반적으로 연산의 실행 횟수는 고정된 숫자가 아니라 n에 대한 함수가 된다.

연산의 개수를 입력의 개수 n의 함수로 나타낸 것을 '시간 복잡도 함수 T(n)'라고 한다.

빅오(Big-O) 표기법

시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법, n의 값에 따른 함수의 상한 값을 나타내는 방법

자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있다.

입력의 개수가 큰 경우에는 차수가 가장 큰 항이 전체의 값을 주도하므로 보통 시간 복잡도 함수에서는 최고차 항만을 고려하면 충분하다.

따라서 기본 연산의 횟수가 다항식으로 표현되었을 경우 다항식의 최고차 항만을 남기고 다른 항들과 상수항을 버리고 궁극적으로는 최고차 항의 계수도 버리고 최고차 항의 차수만을 사용한다.

O(1) > O(logn) > O(n) > O(n logn) > O(n^2) > O(n^3) > O(2^n) > O(n!)

최선, 평균, 최악의 경우

똑같은 알고리즘도 주어지는 입력의 집합에 따라 다른 실행 시간을 보일 수 있다.

알고리즘의 효율성은 주어지는 자료 집합에 따라 최악/평균/최선의 경우로 나누어서 평가할 수 있는데, 대부분 최악의 경우의 실행 시간이 알고리즘의 시간 복잡도의 척도로 많이 쓰인다.