알고리즘 ⚙
넓은 의미로 자료구조와 함께 컴퓨터 프로그램을 구성하는 한가지 요소이다. 컴퓨터 명령어들의 집합이라고도 볼 수 있다.
프로그램이 자료와 연산으로 구성되어 있다면 알고리즘은 자료구조와 함께 프로그램을 구성하는 한가지 요소로 볼 수 있다.
좁은 의미로는 어떠한 문제를 해결하기 위한 절차이다.
공부중인 알고리즘은 좁은의미로 사용되는 알고리즘을 의미한다.
예를 들면, 1부터 100까지 합을 구하는 문제가 있다.
가장 간단한 방법은 1부터 차례대로 더하는 방법이 있을 것이다.
// 의사 코드(Pseudo Code)
CalcSum(n){
sum <- 0
for(i <-1; 1<= n; i<- i +1) {
sum <- sum + i;
}
return sum;
}알고리즘의 필수 5가지 특성
- 입력(input) : 외부에서 제공되는 자료가 0개 이상 있어야 한다. (입력값이 없는 경우도 있다.)
- 출력(output) : 적어도 1개 이상의 결과를 만들어야 한다.
- 명백성(definiteness) : 각 명령어는 의미가 모호하지 않고 명확해야 한다.
- 유한성(finiteness) : 한정된 수의 단계 뒤에는 반드시 종료된다. 무한히 동작해서는 안 된다.
- 유효성(effectiveness) : 모든 명령은 실행 가능한 연산이어야 한다. 예를 들어 0으로 나누는 연산과 같이 실행할 수 없는 연산을 포함해서는 안된다.
알고리즘과 자료구조와 관계
알고리즘의 성능은 자료구조에 종속된다.
같은 자료라 하더라도 어떻게 표현되고 저장되느냐에 따라 사용 가능한 알고리즘이 달라지기 때문이다.
자료구조의 기본적인 연산을 구현하기 위해서 알고리즘이 사용된다.
알고리즘 표현 방법
| 종류 | 내용 | 특성 |
|---|---|---|
| 자연어 | 사람이 표현하는 일반적인 언어로 표현 | 알고리즘 표현으로는 부적절하다. 기술하는 사람에 따라 일관성과 명확성이 달라진다. |
| 순서도 | 알고리즘을 그림으로 도식화해서 표현 | 알고리즘 각 단계를 직관적으로 표현할 수 있으나, 복잡한 알고리즘을 나타내기에는 비효율적이다. |
| 의사 코드(유사코드, 슈도코드) | 특정 프로그래밍 언어가 아닌 가상의 유사한 언어로 표현 | 프로그래밍 언어보다는 덜 엄격한 문법, 자연어보다는 더 체계적으로 기술이 가능하다. 슈도코드라고 불린다. |
| 프로그래밍 언어 | C와 같은 프로그래밍 언어로 표현 | 알고리즘을 구현 소스를 통해 나타내기 때문에 추가 구현 단계가 필요하지 않다.(알고리즘이 바로 구현 소스를 통해 나타나기 때문) 너무 엄격하게 기술하여 비효율적인 경우가 있다. |
자연어와 정반대되는 것이 프로그래밍 언어이다.
프로그래밍 언어의 경우 구현 소스를 통해 바로 알고리즘이 나타나지만 알고리즘을 표현하는 것이 힘들다는 단점이 있다.
일반적으로 알고리즘을 표현하는 가장 대표적인 방법이 순서도와 의사 코드 두가지 방법이 있다.
보통의 경우 의사코드를 사용해서 많이 표현한다.
순서도와 의사 코드
- 시작(start) 혹은 종료
- 처리 (특정 연산 실행)
- 판단 (주어진 조건 비교 후 조건에 따라 흐름 결정)
- 자료의 입력 및 출력
- 흐름선 (실행 순서 표시)
의사 코드 (Pseudo Code)
-
지정문
변수에 특정 값을 대입하는 명령
-
조건문
조건식을 만족하는지에 따라 흐름이 결정되는 명령
- 반복문
특정 명령을 여러 번 반복적으로 수행하는 구조
for 또는 while문이 해당한다.
알고리즘 성능 분석
주어진 문제를 해결하기 위해 여러 개의 다양한 알고리즘이 가능한데 어떤 알고리즘을 사용해야 할까?
- 알고리즘의 성능 분석 필요
여러개의 알고리즘이 있을 때 그 중에서 가장 효율적인 알고리즘을 선택해야 한다. 성능 검증을 통해서 가장 효율적인 알고리즘을 선택한다.
예를 들어, 1부터 100까지 합을 구하는 문제가 있다고 하자.
1. 1씩 100번 증가시키는 방법 (100번의 덧셈 연산)
2. 수열 공식으로 문제를 푸는 방법 100 * (1 + 100) / 2
수열 공식으로 문제를 푸는 방법은 덧셈 1번, 곱셈 1번, 나눗셈 1번의 총 3번의 연산으로 해결된다.
알고리즘 성능 분석 기준
-
공간 복잡도 (Space Complecity)
- 메모리 혹은 저장공간이 필요한가
-
시간 복잡도 (Time Complexity)
시간 복잡도를 측정하는 방법에는 2가지가 있다.
- 실제 걸리는 시간을 측정
- CPU 등 여러 환경에 따라 수행되는 시간 차이가 발생 - 실행되는 명령문의 개수를 계산 (시간 복잡도 함수는 입력 값에 따라서 수행되는 실행 연산의 빈도수를 나타냄)
- 대부분의 경우 사용하는 방법. 얼마나 성능이 우수한지 측정한다. 시간 복잡도 함수를 사용해서 알고리즘의 성능을 비교, 분석한다.
요즘에는 대부분 알고리즘 분석 기준은 시간 복잡도를 가지고 성능을 분석한다.
알고리즘 시간 복잡도 비교
1부터 n까지의 합을 구하는 알고리즘 2가지 사례를 살펴보자.
// 1번 알고리즘 (의사 코드)
CalcSum( n ){
i <- start; // 1번
sum <- 0; // 1번
for ( ; i <= n ; i <- i+1 ) { // 1번 + 1번
sum <- sum + i; // 1번
}
return sum;
}
1번 알고리즘의 연산 빈도수 2 + n * 3 = 3n+2
초기화를 위해서 2번의 연산이 필요하다. (i와 sum)
이후 반복문을 돌면서 비교 연산 1번, 더해주는 연산 1번, sum으 더해주는 연산 1번
초기 2번의 연산과 n번만큼 루프를 돌면서 각각 3번의 연산이 필요하다.
2번 알고리즘도 살펴보자.
// 2번 알고리즘 (의사코드)
clacSum ( n ) {
count <- n; // 1번
sum <- 1 + n; // 1번
sum <- sum * count; // 1번
sum <- sum / 2; // 1번
return sum;
}2번 알고리즘의 연산 빈도수 : 4
초기 값 설정(2번), 곱셈 1회, 나눗셈 1회 총 4회
입력값 n에 따라서 1번 알고리즘은 3n + 2 2번 알고리즘은 4에 해당하는 시간 복잡도가 나왔다.
시간복잡도 (Big-O 표기법)
시간복잡도 함수를 어떻게 비교할 수 있을까?
시간 복잡도 함수를 비교할 때(알고리즘 성능 분석) 보통 Big O 표기법을 많이 사용한다.
빅오 표기법
시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시한다.
계수(Coefficient)는 생략하여 표시한다.
예시 1
O(3n + 2) = O(3n) = O(n)
▲ 최고차항 (3n)만 선택 후 계수 3 제거최고 차항 3n을 선택 후 계수를 생략한다.
위에서 살펴본 첫번째 알고리즘의 시간 복잡도 함수는 3n+2였지만 Big-O 표기법에 의해 O(n)으로 나타낼 수 있다.
예시 2
O(4) = O(1)n의 대한 값이 아닌, 상수값 하나만 있을 때는 빅오 표기법에서 1로 나타낼 수 있다. 즉, N에 대한 항이 상수일 때는 1이 된다.
빅오 표기법에 대한 수학적 정의
시간 복잡도에서 많이 사용되는 최고 차항들
- O(1) : 상수
- O(logn) : 로그
- O(n) 1차, 선형
- O(n logn) : 선형로그
- O(n²) : 2차
- O(n³) : 3차
- O(2ⁿ) : 지수(Exponential)
- O(n!) : 계승(Factorial)
상수의 성능이 가장 우수하다.
