커피를 마시고 싶어서 카페를 찾으려고 한다. 그때 내가 가지고 있는 돈은 4천원뿐. 가장 가까운 카페에서 카페라테를 먹으려고 한다.
그렇다면 문제(?) 해결과정은 다음과 같을 것이다.
1. 가장 가까운 카페를 찾는다.
2. 카페를 찾았다면? 카페를 확인한다.
2-1 카페가 닫았다면? 다음 카페로..
2-2 카페가 열였다면? 들어간다.
3. 커피의 가격을 본다.
3-1 커피가격이 내가 가진 돈보다 비싸면? 가게를 나와서 다시 카페를 찾는다.
3-2 커피 가격이 맞으면 구매후 문제해결!이렇게 문제를 해결하기 위해서는 경우의 수를 생각하면서 방법을 고려하게 된다. 이렇게 문제해결을 위한 절차와 방법을 알고리즘이라고 한다.
컴퓨터공학에서의 알고리즘
컴퓨터는 사람보다 똑똑하지 않다. 우리는 간단하게 사고할 수 있는 것을 컴퓨터는 하나하나 알려줘야 작동할 수 있다.(심지어 이름을 짓는 것까지!)
따라서 컴퓨터한테 작업을 지시하기 위해서는 직접 컴퓨터의 언어로 절차를 만들어서 컴퓨터가 그 작업을 하도록 지시해야 한다.
또한 컴퓨터가 사람보다 못하다고 하는 것은 작업이 잘못 되어도 그 것을 실행한다는 것이다.
그 작업이 영원히 끝나지 않더라도, 1000개의 작업을 100만번 하라고 해도 그대로 시행하게 된다.
이 것을 방지하기 위해서는 작업은 끝날 수 있게, 또한 같은 방식도 작업을 최대한 줄일 수 있도록 하는 것이 중요하다.
알고리즘의 조건
컴퓨터 공학에서는 이러한 점들을 고려하여 알고리즘의 조건을 다음과 같은 정의하였다.
-
문제의 존재
알고리즘이 존재하려면 문제사항, 요구사항이 있어야 할 것이다. 또한 컴퓨터로 해결할 수 있는 문제여야 한다.1)입력
입력값은 0 또는 하나이상의 입력값이 주어지게 된다.2)출력
출력값은 알고리즘을 통과한 입력값에 대한 결과가 하나 이상 존재해야 한다. -
절차 설명
문제 해결에 있어서 방법과 절차가 명확해야 한다. -
유한성
알고리즘은 반드시 유한한 횟수 안에서 끝나야 한다. 컴퓨터의 처리능력의 한계와 메모리 성능 저하에 영향을 주면 안된다. -
효과성
알고리즘은 다른 사람이 보기에도 충분히 이해할 수 있도록 단순하고 간결해야 한다.
알고리즘의 평가 기준
어떤 알고리즘이라도 문제를 해결할 수 있는 방법은 많다. 1을 10번 더해서 10을 만드는 것과 1과 10을 곱해서 10을 만드는 것은 값이 같다.
하지만 1을 10번 더하는 것과 1*10만으로 문제를 해결하는 것은 효율성은 매우 다를 것이다.
컴퓨터 공학에서 알고리즘은 단순히 문제를 해결하는 것이 주제가 아닌 문제를 어떻게 하면 효율적으로 풀지를 고민하는 과정인 것이다.
시간복잡도
컴퓨터는 사람보다 똑똑하지는 못해도 처리속도는 매우 빠르다. 그래서 알고리즘의 속도를 측정하기 위해서 시간의 패턴을 대략적으로 계산하는 복잡도 계산법이 Big-O 계산법이다. O(n)은 n개의 데이터를 처리하기 위해서 최대 n번의 계산이 필요하다는 식이다.
O(1) : 문제 해결을 하는데에 단 한번의 계산만 필요
O(logn) : 문제를 해결하는데의 계산이 절차에 따라 감소(sort가 대표적인 예시)
O(n) : 문제 해결에서 필요한 n개의 데이터와 계산이 정비례
O(nlogn) : 문제 해결에 있어서 nlogn만큼의 시간이 필요(선형로그)
O(n^2) : 문제를 해결하는데 n개의 데이터에는 n^2의 계산이 필요(주로 for문 안의 for문, 즉 중첩 루프)
O(c^n) : 문제를 해결하기 위해서 필요한 것은 상수 c의 n제곱(최악의 시간효율성)
O(n!) : 문제 해결 불가능...
공간복잡도
최근 컴퓨터 메모리의 발달로 공간복잡도의 중요성은 낮아졌다. 하지만 여전히 고려를 해야 하는 이유는 불필요한 메모리 사용을 줄이기 위해서이다.
Big-O 표기법으로 사용하며 n의 데이터에서 n이 사용되는 횟수만큼 쌓일 때 공간복잡도는 O(n)이 된다.
예를 들어
const = arr[[],[],[],[],[],[],[]]
이런 배열이 있을 때는 배열안에 또 배열이 존재하므로 n*m = O(n^2)으로 표기하게 된다.
정리
알고리즘을 비전공자들이 보았을 때는 그저 문제를 푸는 과정만을 생각할 수 있다. 나도 그랬었다. 하지만 알고리즘을 위해서 나온 수많은 방법론들(퀵 정렬, BFS/DFS)은 어떻게 하면 효율적이고 효과적으로 문제를 해결할 수 있을지에 대한 컴퓨터 공학의 고민의 정수가 담겨있다.
다시 한번, 컴퓨터에서의 알고리즘은 문제를 해결할 수 있느냐 없느냐가 아닌, 어떻게 효율적이고 쉽게 문제를 해결할 수 있느냐의 총 집합니다.
