알고리즘이란?
문제를 풀기 위해 필요한 단계들의 집합이다.
간단하게, 문제를 어떻게 푸는지에 대한 것을 정리해놓은 것이 알고리즘이라는 것이다.
컴퓨터에서 알고리즘이란, 실행했을 때 컴퓨터가 확실하게 알아들을 수 있는 프로그램을 실행하는 과정의 집합이다.
알고리즘엔 여러가지 특성이 있는데, 다음과 같다:
명확성(Definiteness) : 각 명령어들이 모호하지 않고 정확해야 한다.
유한함(Finiteness) : 유한한 단계를 거쳐서 종료되어야 한다.
효과성(Effectiveness) : 각 명령어들은 기초적이고, 간단해야 한다.
알고리즘에서 가장 먼저 배웠던 것이 Sorting Problem, 정렬 알고리즘이다.
정렬 알고리즘이란?
말 그대로, 주어진 정보(숫자, 문자 등등)를 우리가 원하는 순서대로 나열하는 것을 뜻한다.
우리는 알파벳, 한글, 숫자 등등을 보았을 때, 직관적으로 숫자를 배열할 수 있다. 그러나, 컴퓨터는 이를 직관적으로 하지 못하기 때문에 이러한 과정을 거치게 해 줄 알고리즘이 필요하다.
정렬 알고리즘에는 여러가지가 있는데, 대표적으로는 삽입(Insertion) 정렬이 있다.
삽입 정렬이란?
손에 든 숫자 카드들을 정렬하는 것처럼, 앞에서부터 차례대로 카드를 순서대로 넣는 정렬을 의미한다. 예를 들어,
5 2 4 6 1 3
이라는 수열이 있다고 치자. 이를 오름차순, 즉 낮은 숫자부터 정렬한다고 한다면
- 한 숫자를 지정
- 그 숫자보다 앞의 숫자가 크면 위치를 바꾼다.
- 앞의 숫자가 작다면 다음 숫자를 지정한다.
이를 반복해서 작업하는 것이 삽입 정렬이다.
이와 함께 배우는 것이 시간 복잡도이다.
시간 복잡도란?
문제를 풀 때, 여러가지 알고리즘이 나올 수 있다. 각각의 알고리즘은 걸리는 시간이 다 다를 것이고, 그 중 최악, 최선, 평균을 구하는 것이 시간 복잡도이다. 이는 다음 번에 배우게 되었다.
그 다음으로 배운 것은 합병(Merge) 정렬이다.
합병 정렬이란?
큰 수열을 정렬할 때, 이 수열을 더 작은 수열로 나눈 후, 정렬하면서 합친다. 이는 D&C, 분할 정복(Devide and Conquer)로 이어진다.
그럼 분할 정복은 또 뭐냐?
분할 정복이란?
위의 합병 정렬처럼, 문제의 크기가 클 때는 보이지 않던 것이 작게 보면 보일 수도 있다. 이에서 착안해, 큰 문제를 작은 문제로 쪼갠 후 각 문제를 정복해 나간다는 알고리즘 중 하나이다. 이 또한 다음 번에 배우게 되었다.
