알고리즘

알고리즘

이번 포스트는 알고리즘들 중에서 정렬, BFS,DFS등에 대해서 진행해 보도록 하자.

재귀

재귀적 용법이라함은 어떠한 함수 A가 있을때, 함수 A 내부에서 다시 함수 A를 호출하는 방식을 말한다.

정확한 정의는 자신을 정의할 때 자기 자신을 재 참조하는 방법이다.

조그마한 문제를 해결하여 큰문제를 해결하는 방식으로 분할정복을 사용 하는 방법이기도 하다.

이때 주의해야 할것은 재귀함수들은 탈출조건을 반드시 명시해야 한다는것이다.

그렇지 않다면 불필요한 재귀용법으로 인해 프로그램 및 변수를저장 하는 콜스택에서 오버플로우가 일어나 프로그램이 실행되지 못한다.

재귀와 반복문

재귀와 반복문은 같은 목적으로 사용할 수 있다. 하지만 재귀는 함수를 호출하기 때문에, 새로운 변수를 할당하는등 추가적인 메모리를 사용해야 한다. 또한 N이 커질수록 그만큼 시간 복잡도는 반복문보다 증가한다.

그 예로 피보나치수열을 구하는 문제를 들수가 있는데, 피보나치 수열을 반복문으로 풀면 변수 2개를 사용하여 f(n-1), f(n-2)의 값을 저장했다가 다시 변수에 저장하는 방식으로 풀어내면 된다. O(n)의 시간이 소요된다.

하지만 재귀적 용법은 그렇지 않다.

f(n)을 구하기 위해 f(n-1), f(n-2)의 값을 알아야 하고, f(n-3)…f(1) 의 값을 알아야 한다.

이때 조금더 생각해 보면, f(1)은 n이 커지면 커질수록 기하급수적으로 호출되는 수가 증가한다. 따라서 피보나치수열을 재귀적용법으로 풀어내면 O(n^2)의 시간복잡도를 가지게 된다.

다만 연산결과를 메모리에 저장해두고 필요할때마다 사용하는 다이나믹 프로그래밍을 사용하면 반복문과 같은 시간복잡도를 가지게 된다.

정렬

머지소팅

애증의 관계이기도 하고, 대표적인 분할 정복 알고리즘인 머지 소팅 알고리즘은 O(NlogN)의 시간 복잡도를 가지게 된다.

사유는 분할하는것 자체는 O(logN)의 시간이 소요되지만, 분할된 배열을 정렬하면서 병합할때 분할된 배열들을 전부 하나하나 확인하면서 작업해야 하기 때문.

보통 재귀적 용법을 사용하여 작성하는 편이다.

동작방식은 다음과 같다.

1. 보통 배열의 절반을 나누어 왼쪽, 오른쪽 배열에 대해 함수를 호출한다. 1-1. 더이상 재귀적 용법을 사용하기 어려울때 까지 1번을 반복한다.
2. 만약 배열의 길이기 1이면 입력받은 배열을 리턴한다.
3. 리턴받은 배열들을 대상으로 하나의 정렬된 배열을 생성하고 리턴한다.

버블 소팅

버블 소팅알고리즘은 인접한것끼리 비교하여 정렬을 하는 방식이다. 그니까 n번의 요소와 n+1 번째 요소를 비교하여 정렬이 되지 않았으면 위치를 교체하는 방식.

O(n^2)의 시간복잡도를 가지게 된다.

인서션 소팅

버블과 비슷하지만, 위치가 바뀐것과 주변의것을 비교하여 정렬을 진행하게 된다. 이미 정렬된 배열을 대상으로 시도하는경우 O(N)의 시간복잡도를 가지게된다.

하지만 그렇지 않는경우 O(N^2)의 시간복잡도를 가진다.

일부 정렬 알고리즘에서는 알고리즘의 일부로 사용되기도 한다.

셀렉션 소팅

셀렉션소팅은 정렬이 되어있지 않는것중 가장 작은것을 선택하여 0번째, 1번째… 자리와 교환하는 방식

삽입정렬과 마찬가지로 O(n^2)의 시간복잡도를 가진다.

퀵소팅

배열의 요소들중 임의로 하나의 요소를 선택하여 피봇으로 지정하고 피봇보다 작은 배열 및 피봇보다 큰수의 배열로 분할한다.

이후 배열의 첫번째 요소를 피봇으로 삼아 위의 과정을 반복한다.

비록 시간복잡도는 머지소팅과 같은 O(NlogN) 이지만, 큰 규모를 정렬해야 할때 상당히 빠른속도를 자랑하는 방식이다.

하지만 피봇이 연속으로 가장 작은수/가장 큰수를 선택하는 경우라면 셀렉션소팅과 다를게 없어진다.

이런 최악의 케이스를 방지하고자

1. 임의의 난수를 이용하여 피봇을 선정한다.
2. 첫번째 요소, 끝요소, 중간의 요소의 평균의 값을 피봇으로 지정한다.
3. 삽입정렬과 혼용하여 크키가 200 이하인경우, 삽입정렬로 정렬한다.

세가지 방법이 고안되었다. 삽입정렬은 작은 규모에서는 다른 정렬 알고리즘에 비해 속도가 빠른편이다. 일반적으로 2번 3번을 같이 사용하는것이 매우 성능이 좋다.

라딕스 소팅

라딕스 소팅은 배열이 숫자인 경우에만 진행이 가능한걸로 알고 있다.

10개의 큐를 필요로 하며 다음 과정을 거친다.

1. 1의 자릿수에 해당되는 번호의 큐에 차례대로 추가한다.(1의 자릿수가 4이면 4번째 큐에 넣는다)
2. 10개의 큐중 0번째 큐부터 하나씩 디큐 하여 배열을 재구성한다.
3. 1번을 다시 진행하되, 대상 자릿수를 *10을 한다. (1의 자릿수대신 10의 자릿수를 대상으로 진행) 3-1 1-3번을 가장 큰수의 자릿수까지 반복. (가장큰수가 4자리 숫자이면 1000의 자릿수까지 진행)

시간 복잡도가 O(N)일 정도로 굉장히 빠른 알고리즘이지만

1. 숫자만가진 배열일 경우만 사용가능하다.
2. 큐를 위한 추가적인 메모리를 필요로 한다.

는 단점이 존재한다.

힙소팅

이전 포스트를 보충설명한다.

트리대신 큐을 이용하여 정렬한다. 이렇게 하는 이유는 큐에서 요소 하나를 제거해도 힙소트의 규칙이 유지되기 때문이다.

추가적인 메모리를 필요로 하지 않으면서, 항상 O(NlogN)이라는 시간복잡도를 가지는 효율적인 정렬법.