알고리즘이란 무엇인가?
알고리즘(algorithm)이란 특정 작업을 수행하기 위해 순서대로 따라야 하는 유한한 명령어들의 집합으로 정의됩니다. 어떤 절차가 진정한 알고리즘이 되려면 다음의 다섯 가지 기준을 반드시 충족해야 합니다.
알고리즘이 충족해야 할 5가지 조건
- 입력(Input) : 지정된 객체 집합으로부터 가져오거나 수집한 0개 이상의 입력을 가집니다.
- 출력(Output) : 입력과 특정한 관계를 맺는 하나 이상의 출력을 반드시 생성해야 합니다.
- 명확성(Definiteness) : 각 단계는 분명하게 정의되어야 하며, 모든 명령어는 명확하고 모호함이 없어야 합니다.
- 유한성(Finiteness) : 유한한 횟수의 단계를 거친 후에는 반드시 종료되어야 합니다.
- 유효성(Effectiveness) : 수행해야 할 모든 연산은 충분히 기본적인 수준이어야 하며, 정확하게 그리고 유한한 범위 안에서 실행 가능해야 합니다.
알고리즘을 표현하는 3가지 방법
같은 알고리즘도 목적과 상황에 따라 여러 가지 방식으로 나타낼 수 있습니다.
- 자연어(Natural Language) : 영어와 같은 일상 언어로 알고리즘을 서술하는 방식입니다. 이해하기 쉽지만 길어지면 모호해질 수 있습니다.
- 순서도(Flowchart) : 도형과 화살표를 이용해 처리 흐름을 그래픽으로 표현합니다. 다만 알고리즘이 작고 단순한 경우에만 적합합니다.
- 의사 코드(Pseudo Code) : 대부분의 모호성 문제를 피할 수 있으며, 특정 프로그래밍 언어의 문법에 얽매이지 않아 가장 널리 사용됩니다.
예제 1 : 숫자의 팩토리얼 값을 계산하는 알고리즘
1단계: 숫자 n을 입력받는다 2단계: 변수 final을 1로 설정한다 3단계: final ← final × n 4단계: n을 1 감소시킨다 5단계: n이 0인지 검사한다 6단계: n이 0이면 8단계로 이동한다 (반복문 탈출) 7단계: 그렇지 않으면 3단계로 이동한다 8단계: 결과값 final을 출력한다
재귀 알고리즘(Recursive Algorithm)
재귀 알고리즘은 자기 자신을 다시 호출하는 알고리즘으로, 일반적으로 이전 호출의 반환값을 매개변수로 전달하며 호출을 반복합니다. 여기서 매개변수는 입력을, 반환값은 출력을 의미합니다.
재귀 알고리즘은 하나의 큰 문제를 동일한 성격의 하위 문제들로 나누어 단순화하는 방법으로 정의됩니다. 한 번의 재귀 호출 결과가 다음 재귀 호출의 입력으로 사용되며, 이러한 반복은 자기 유사(self-similar) 방식으로 진행됩니다. 즉, 알고리즘은 점점 더 작은 입력값으로 자기 자신을 호출하고, 그 작은 값들에 대한 연산을 통해 최종 결과를 얻습니다. 팩토리얼 계산과 피보나치 수열 생성이 재귀 알고리즘의 대표적인 예입니다.
재귀 알고리즘을 설계할 때는 무한히 호출되는 것을 막기 위해 반드시 종료 조건(base case)을 함께 정의해야 한다는 점에 유의해야 합니다.
예제 : 재귀를 이용한 팩토리얼 함수 작성
int factorialA(int n)
{
return n * factorialA(n-1);
}