1-2. 알고리즘이란?

자료구조를 정리하면서 알고리즘(Alhorithm)을 왜 얘기하냐고 생각할 수도 있다.

하지만 자료구조와 알고리즘은 밀접한 관련이 있다.

알고리즘을 잘 다루려면 그 알고리즘에 잘 어울리는 자료구조를 선택해야 하고,

자료구조를 잘 다루기 위한 알고리즘도 자료구조마다 다르다.

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

대부분의 프로그램은 데이터를 처리하고, 이 자료들은 자료구조를 사용해 표현되고 저장된다.

또한 주어진 문제를 처리하고, 자료구조를 다루는 절차가 알고리즘으로 구현된다.

알고리즘은 다음과 같은 조건들이 만족되어야 한다.

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

알고리즘을 기술하는 방법은 크게 4가지가 있다.

1. 자연어(한국어, 영어 등)
2. 흐름도(flowchart)
3. 유사 코드(pseudo-code)
4. 특정 프로그래밍 언어(C, C++, Java 등)

n개의 정수를 저장하고 있는 배열에서 최댓값을 찾는 알고리즘을 위 4가지 방법으로 알아보자.

• 자연어
  • 자연어는 사람에게 익숙한 언어이기 때문에 기술이 편리하지만 모호성을 확실하게 제거해야 한다.

ArrayMax(A, n)

1. 배열 A의 첫 번째 요소를 변수 temp에 복사한다.
2. 배열 A의 다음 요소들을 차례대로 temp와 비교해, 더 크면 그 값을 temp에 복사한다.
3. 배열 A의 모든 요소를 비교했으면 temp를 반환한다.

 

• 흐름도(flowchart)
  • 흐름도는 알고리즘을 명확하게 표현할 수 있다는 장점이 있어 명세서 등에서 많이 사용된다.
  • 알고리즘이 복잡해지면 흐름도가 매우 복잡해지는 단점이 있다.

• 유사 코드(pseudo-code)
  • 자연어보다는 더 체계적이지만 프로그래밍 언어보다는 덜 엄격한 언어
  • 알고리즘의 표현에 흔히 사용되는 방법이다.
  • 유사 코드의 문법은 프로그래밍 언어와 비슷하지만 특정한 언어에 국한되지 않는다.

ArrayMax(A, n)

temp ← A[0];
for i←1 to n-1 do
	if temp < A[i] then
    	temp ← A[i];
return temp;

• 특정한 프로그래밍 언어
  • 특정한 프로그래밍 언어를 사용해 알고리즘을 기술하는 방법
  • 알고리즘의 가장 정확한 표현이지만, 구현을 위해 특정한 프로그래밍 언어에 대한 구체적인 사항들을 알고 있어야 한다.

int ArrayMax(int score[], int n) {
	int temp = score[0];
    
    for (int i = 1; i < n; i++) {
    	if (score[i] > temp)
        	temp = score[i];
    }
    
    return temp;
}