알고리즘(algorithm)
정의
문제를 해결하기 위한 절차나 방법.
컴퓨터 프로그램은 정교한 알고리즘들의 집합이라고 간주할 수 있다. 수학이나 컴퓨터 과학에서 말하는 알고리즘은, 보통 반복되는 문제를 풀기 위한 작은 프로시저(진행절차)를 의미한다. 컴퓨터 시대 이후로는 알고리즘이라고 하면 컴퓨터를 통해 실행되는 것이라고 여겨지는 경향이 있으나, 사실 알고리즘 자체는 컴퓨터가 등장하기 이전부터도 존재했다. 즉, 사람이 수동으로 종이를 사용해 일정한 절차로 문제를 풀더라도 알고리즘에 해당한다. 다만, 컴퓨터의 등장과 함께 알고리즘 역시 급속도로 발전하게 된 것은 사실이다.
https://namu.wiki/w/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
알고리즘의 조건
알고리즘은 총 5가지의 요건을 만족해야 한다.
입력, 출력, 명확성, 유한성, 효과성
입력
알고리즘은 0 또는 그 이상의 외부에서 제공된 자료가 존재한다.
출력
알고리즘은 최소 1개 이상의 결과를 가진다.
명확성
알고리즘의 각 단계는 명확하여 애매함이 없어야 한다.
유한성
알고리즘은 단계들을 유한한 횟수로 거친 후 문제를 해결하고 종료해야 한다. 알고리즘의 한 단계 이후 m의 값은 n 보다 작으며, m != 0이면 n의 값은 다음 번 단계에서 줄어든다.
효과성
알고리즘의 모든 연산들은 사람이 종이와 연필을 이용하여 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다.
알고리즘의 평가
알고리즘은 수행하는 데 걸리는 시간을 보여주는 시간복잡도와 메모리를 차지하는 정도를 나타내는 공간복잡도로 평가할 수 있다.
시간복잡도
시간복잡도는 input으로 주어지는 자료(n개)에 따라 총 몇 번의 연산을 수행해서 알고리즘을 끝마치는지를 측정한다.
예를 들어 n개의 데이터를 버블 정렬로 정렬할 경우 모든 원소를 모든 원소끼리 한번씩 비교하기 때문에 O(n^2) 의 시간복잡도로 측정된다.
하지만 퀵 정렬로 정렬할 경우 원소의 범위로 정렬하기 때문에 O(nlogn)의 시간복잡도로 측정된다.
공간복잡도
공간복잡도 역시 앞서 언급한 시간복잡도처럼 Big-O 표기법(Big O notation)을 주로 사용한다. 현실에서는 시간 복잡도보다 중요도는 떨어지는데, 시간이 적으면서 메모리까지 지수적으로 증가하는 경우는 없기 때문이고, 다항 시간 내에서 나타나는 메모리 문제들은 보통 알고리즘 자체보다는 알고리즘의 구현에서 발생하는 문제이기 때문이다. 다만 동적 계획법의 경우에는 메모리를 상당히 많이 필요하기 때문에 (즉, 공간복잡도가 크기 때문에) 입력 값의 범위가 넓으면 사용하지 못하는 경우가 많다. 또한 임베디드, 펌웨어 등 하드웨어 환경이 극도로 한정되어 있을경우 공간복잡도도 상당히 중요하게 보게된다. 이론적으로는 n에 대한 다항식만큼의 공간으로도 해결이 안 되는 정말 어려운 문제들을 생각하기도 한다.
알고리즘 종류
정렬
집합으로 주어진 데이터를 정렬하여 순서대로 만드는 알고리즘
탐색
DFS, BFS, 이진탐색 등이 존재하며 집합에서 특정 원소를 찾아내는 알고리즘
백트래킹
경로를 가능한 끝까지 탐색하고 다시 재귀적으로 돌아가는 알고리즘
분할정복
문제를 나눌 수 있는 데까지 분리하고 정복(실행) 하고 다시 조합하면 문제가 해결되어있는 알고리즘
동적계획법
다른 책에선 기억하며 풀기로 번역하는 경우도 있다. 작은 문제를 풀었을 경우 그 방법이 큰 문제에서도 적용되어 전체적인 답까지 유도해내는 방법이다.
그리디 알고리즘
문제를 해결할 때는 현재의 최선이 전체의 최선이라는 보장이 없다. 4개의 수 중 2개의 수를 고르는데 가장 큰 합이 되어야 할 경우 내가 지금 고른 랜덤의 두 개의 수가 최대를 보장할 수 없다. 그렇기 때문에 모든 조합을 찾아야되는데, 내가 지금 고른 랜덤의 수가 최대를 보장한다고 전제하고 시작하는 알고리즘이다.
그래프 알고리즘
경로를 탐색하는 방법을 구하는 알고리즘이다. 보통 최단경로를 구하는데 사용한다.
