1. 자료구조

학교에서 강의를 들은지는 꽤 됐지만 중간고사 공부도 할 겸 다시 정리하는 시간을 갖고자 글로 정리를 하게 되었다.

첫번째 내용은 자료구조와 알고리즘의 정의에 관한 것이다.

참고로, 이 책은 2019년 생능출판사에서 나온 천인국, 공용해, 하상호 저의 C로 쉽게 풀어쓴 자료구조 책과 강의자료를 토대로 작성되었다.

 

자료구조는 우리의 일상생활에서 유사성을 찾을 수 있다.

그릇을 쌓아서 보관하는 것은 스택, 마트 계산대의 줄은 큐, 버킷 리스트는 리스트, 영어사전은 사전, 지도는 그래프, 컴퓨터의 디렉토리 구조는 트리와 같다.

 

쌓인 그릇은 가장 마지막에 얹은 그릇을 가장 먼저 뺄 수 있으므로 스택의 특성과 같다. 마트 계산대의 줄은 먼저 온 사람이 먼저 계산할 수 있으므로 큐의 특성과 같다.

 

이처럼 자료구조는 프로그램에서 자료들을 정리하여 보관하는 여러가지 구조를 의미한다. 

 

그럼 자료구조를 배워야 하는 이유는 뭘까

컴퓨터 프로그램은 자료구조와 알고리즘이 합쳐진 구조로 이루어져 있다.

흔히 "프로그램=자료구조+알고리즘"이라고 한다. 대부분의 프로그램에서 자료를 처리하고 있고 이들 자료는 자료구조를 사용하여 저장된다. 

 

보통 가장 많이 사용하는 자료구조는 배열이다. 배열에 자료를 저장하고 필요에 따라 각각의 자료를 꺼내서 비교한다.

그리고 이러한 자료를 다루는 절차가 바로 알고리즘이다.

 

다음은 최고 성적을 찾는 알고리즘이다.

 

largest<-scores[0]

for i<-1 to N-1 do

  if scores[i]>largest

     then largest<-scores[i]

return largest

 

간단히 동작설명을 하자면, largest를 scores의 첫 번째 요소로 초기화한다.  그리고 나머지와 순차적으로 비교하게 된다.

그리고 아래는 위의 알고리즘을 C언어를 이용하여 작성한 프로그램이다.

cal_scores.c

#define MAX ELEMENTS 100 
int scores[ MAX_ELEMENTS ]; // 자료구조 
int get_max_score( int n) // 학생의 숫자는 n 
{
	int i, largest;
	largest = scores[0]; // 알고리즘 
	for (i = l; i<n; i++) { 
        if (scores[i] > largest) { 
                largest = scores[i];
        }
    } 
	return largest; 
}

100만큼의 크기를 가진 정수형 배열 scores를 선언한다. 여기서 배열 scores가 자료구조에 해당한다.

학생의 숫자를 매개변수인 n으로 넘겨받고 largest를 scores배열의 첫번째 값으로 초기화한다. 그리고 i가 1부터 입력받은 학생의 수까지 돌면서 현재 배열의 값과 이전에 저장된 largest와 비교하게 된다.

 

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