알고리즘이란?
알고리즘을 간단하게 말하자면 '문제 해결 방법'이고,
조금 더 자세히 말하자면 '문제 해결을 위한 단계적 절차' 라고 할 수 있다.
이때, 프로그래밍에서 문제란 입력과 출력으로 정의될 수 있으므로
문제를 푼다는 것은 입력을 출력으로 변환하는 것을 의미한다.
그리고 이러한 방법을 정의한 것이 바로 알고리즘이다.
알고리즘을 어떻게 정의하냐에 따라 소모되는 시간과 메모리가 달라지므로
효율적인 프로그래밍을 위해선 알고리즘을 공부해야 한다.
돈을 넣고 버튼을 누르면, 과자와 거스름돈이 나온다.
이때 돈과 버튼이 입력, 과자와 거스름돈이 출력이고,
입력을 출력으로 변환을 해주는 '방법'이 바로 알고리즘이다.
알고리즘의 성능이란?
알고리즘에서의 성능은 아래와 같이 정의된다.
1) 수행 시간(= 러닝타임) 2) 사용된 데이터
이를 각각 '시간 복잡도', '공간 복잡도'로 나타낼 수 있다.
시간 복잡도와 공간 복잡도가 낮을 수록 좋은 알고리즘이라고 할 수 있다.
문제 해결 절차
알고리즘으로 문제를 해결하는 일반적 절차는 아래와 같다.
1. 문제 정의
input, output으로 해결하고자 하는 문제를 정의한다.
ex. 정수 배열을 입력받아 오름차순으로 정렬된 배열을 출력(리턴)한다.
2. 전략 세우기
ex. divide and coquer
3. 알고리즘 정의
input과 output을 정의하고 명령어를 이용해 input을 output으로 바꾸는 절차를 정의한다.
ex. 순차 탐색 알고리즘
input - 정수 배열, 키 / out - 키에 해당하는 인덱스 or -1
입력받은 배열을 0번 인덱스부터 하나씩 조사한다.
배열이 끝날 때까지 키를 찾지 못하면 -1을 리턴한다.
4. 알고리즘 분석
correctness : 알고리즘이 문제를 정확하게 해결하고 있는가?
efficiency : 시간, 공간 복잡도로 알고리즘의 효율성을 분석
optimality : 문제를 해결하기 위한 최적의 알고리즘인가?
5. 구현
6. 증명
cf. 1-4번은 이론적, 5-6은 실험적(직접 실행해 보는 것)
실험적 분석 vs 이론적 분석
- 실험적 분석 (Experimental studies)
알고리즘을 구현하고 실행하여 경험적으로 수행시간을 측정하는 방법 - 실험적 분석의 한계
1. 알고리즘을 구현해야 하고, 실행하기 위해 오류가 없어야 한다.
2. 모든 사이즈에 대한 수행시간이 아니므로 실험에 포함되지 않은 입력에 대해 일반화의 오류가 생긴다.
3. 컴퓨터의 성능에 좌지우지된다. - 이론적 분석 (Theoretical studies)
수도코드를 분석하여 Primitive Operation(or Basic Operation)을 기준으로
입력 n에 대한 함수를 만든 후 Big-O 표기법으로 표현한다. - 이론적 분석의 장점
1. 알고리즘을 직접 구현하지 않고 high-level에서 분석할 수 있다.
2. 입력 n에 대한 함수로 나타내므로 모든 크기의 입력에 대해 적용된다.
3. 실행 환경에 영향을 받지 않는다.
시간복잡도
입력 데이터의 크기가 커지면 연산의 실행횟수도 커지므로
연산의 실행횟수를 입력 데이터의 크기에 관한 함수로 표현한 것이다.
예를들어, 정수 5개가 있는 배열에 대해 10번의 연산이 필요하고,
정수 10개가 있는 배열에 대해 20번의 연산이 필요하면 이를
'크기가 n인 배열에 대해 n*2번 연산이 필요하다'로 설명하는 것과 같다.
(물론 이는 엄청 나이브하게 설명한 것이므로 참고만 하시길!)
실행 횟수 계산은 수도코드를 참조하여 카운트한다.
이때 최악의 경우에 대한 시간복잡도를 주로 사용한다.
생명과 직결된 자동차 사고 등에서는 반드시 최악의 상황을 가정해야 하고,
알고리즘이 복잡해질수록 평균 수행시간을 구하기 여렵기 때문에 보통은 최악의 경우를 가정한다.
예를들어, 크기가 n인 배열에 대한 순차 탐색 알고리즘의 시간 복잡도는
키가 마지막(n-1번째) 인덱스에 있거나, 키가 존재하지 않는 경우일 때의 실행 횟수를 시간 복잡도로 갖는다.
빅오 표기법 (Big-O)
앞서 입력 n에 대한 primitive operation을 함수로 나타내어 시간복잡도를 계산하는 것을 배웠다.
이렇게 만든 함수의 증가율을 수학적으로 표현한 것이 빅오 표기법이다.
이는 선형 분석 즉, Asymptotic Analysis 이라고 칭하기도 한다.
빅오 표기법을 수학적으로 정의하면 아래와 같다.
💡 어떤 함수 f(n)의 Big-O notation이 O(g(n))라는 것은
충분히 큰 n에 대해 f(n)<=c*g(n)을 만족하는 상수 c가 존재한다는 뜻이다.
하지만 위 수학적 정의는 잘 쓰이지 않는다. (이산수학 시간에나 사용되는 정도)
대부분 최고차항의 차수만 표기하는 방법을 사용한다.
Ex. $3n^3 + 20n^2+5 => n^3$
빅오 표기법의 의미
1. 상한
빅오 표기법은 입력이 아무리 크더라도, 수행시간이 특정 값 이상이 될 수 없음을 의미한다.
즉, 알고리즘 수행시간의 상한을 표현한다.
2. 함수 분류
빅오 표기법을 통해 함수를 분류할 수 있기 때문에 집합의 역할을 한다.
cf. 집합의 의미이므로 영어에서는 'is'나 속한다는 의미의 ⊂ 표현을 쓰기도 한다.