[C언어로 쉽게 풀어쓴 자료구조] 1.1 자료구조와 알고리즘

자료구조 복습

 

교재 : c언어로 쉽게 풀어쓴 자료구조 (개정 3판) - 청인국, 공용해, 하상호 지음

 

 

1.1 자료구조와 알고리즘

 

자료구조란?

 

컴퓨터 프로그램 구성 : 

"프로그램 = 자료구조 + 알고리즘"

 

- 자료 구조 (data structure) : 프로그램에서 자료들을 정리하여 보관허는 여러 가지 구조들 

- 알고리즘 (algorithm) : 주어진 문제를 처리하는 절차

 

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

 

예 : 

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

ing 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;
}

자료구조 : 배열 scores

알고리즘 : 변수 largest를 첫 번째 요소로 초기화하고 나머지 요소들과 순차적으로 비교하는 것

 

 

알고리즘이란?

알고리즘 (algorithm) :

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

* 명령어 : 컴퓨터에서 수행되는 문장들을 의미

 

 

알고리즘 정의 : 

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

즉, 입력은 없어도 되지만 출력은 반드시 하나이상 있어야 하고 모호한 방법으로 기술된 명령어들의 집합은 알고리즘이라 할 수 없으며 실행할 수 없는 명령어를 사용해도 알고리즘이 아니며 무한히 반복되는 명렁어들의 집합도 알고리즘이 아님

 

 

알고리즘 기술 방법 : 

1. 한글이나 영어 같은 자연어
2. 흐름도 (flowchart)
3. 의사 코드 (pseudo-code)
4. 프로그래밍 언어

1. 한글이나 영어 같은 자연어

자연어를 사용하기 때문에 약간의 모호성이 존재함.

모호성을 제거하기 위하여 명령어로 사용되는 단어들을 명백하게 정의해야만 알고리즘이 될 수 있음.

 

2. 흐름도 (flowchart)

도형을 사용하여 알고리즘을 기술하는 방법.

초심자에게 좋은 방법이지만 알고리즘이 복잡해질수록 기술하기 힘듦.

 

3. 의사 코드 (pseudo-code)

가장 많이 쓰이는 방법1

자연어보다는 더 체계적이고 프로그래밍 언어보다는덜 엄격한 언어.

알고리즘을 기술하는 데만 사용되는 코드를 의미.

대입 연산자가 '=' 가 아닌 '←'을 주의

 

4. 프로그래밍 언어

가장 많이 쓰이는 방법2

프로그래밍 언어의 예약어들은 모두 명백한 의미를 가지고 있음.

알고리즘을 기술하는데 안성맞춤.

 

 

배열에서 최댓값을 찾는 알고리즘을 의사 코드로 표현한 예 : 

ArrayMax(list, N):
	largest←list[0];
    for i←1 to N-1 do
    	if list[i]>largest
        	then largest←list[i]
    return largest

 

 

Quiz

01. 문제를 풀기 위한 단계적인 절차는   알고리즘   이다.

02. 알고리즘을 기술하기 위한 방법에는 자연어, 흐름도,   의사 코드   , 프로그래밍 언어가 있다.

03. 알고리즘이 되기 위한 조건이 아닌 것은?

• 출력
• 명백성
• 유효성
• 반복성