좋은 알고리즘 분석 기준과 재귀 호출, 병합정렬, 알고리즘의 IT 기기 활용

좋은 알고리즘 분석 기준과 재귀 호출, 병합 정렬, 알고리즘의 IT 기기 활용에 대해 정리해보도록 하겠습니다. 

 

알고리즘 분석 기준

먼저 알고리즘을 분석하는 것의 필요성에 대해 알아보자면 알고리즘이 있을 때 이 것이 시간을 얼마나 소모를 하는가를 아는 것이 굉장히 중요합니다. 최악의 경우나 평균적인 경우 어느 정도가 소요가 되는지를 살펴봐야 하며, 입력한 데이터의 양이 얼마나 되는지에 따라 어느 정도의 시간이 걸릴지 예측 가능해야 합니다. 그래서 같은 문제라고 할지라도 선택을 하는 알고리즘에 따라 효율에 아주 큰 차이를 가져올 수 있습니다. 알고리즘은 명확하고 효율적이어야 합니다. 이해가 쉬워야 하며 명확성을 해치지 않는 범위 내에서 일반적인 언어로 기술을 해도 됩니다. 효율적이야 한다는 것은 같은 문제 해결을 하는데도 수행 시간에 큰 차이를 가져오기 때문에 좋은 알고리즘을 선정하여 사용하거나 좋은 알고리즘을 개발해야 합니다. 

 

 

재귀 호출의 개념적 이해

재귀 호출의 개념이 있는데, 재귀 호출은 귀납적 사고를 활용하여 알고리즘의 시간 평가를 많이 합니다. 재귀 호출은 Recursive function이나 Recusive call이라고 부릅니다. recursion, 재귀 호출의 개념은 어떠한 문제 안에 크기만 다르고 같은 문제들이 포함되어 있는 경우가 많습니다. 어떤 문제 안에 크기만 다른 똑같은 문제가 있을 때는 자기를 다시 호출을 하면 된다는 말입니다. 이런 것은 수학에서 수열의 점화식에서 활용이 되는 경우가 많습니다.

 

 

 

피보나치수열과 같은 것이 대표적인 재귀 호출의 개념이라고 할 수 있습니다. 이런 수열의 점화식에 해당하는 재귀 호출 분석에는 특히 정렬 부분이 많이 활용이 됩니다. 귀납적 사고를 활용을 하게 되는데 귀납적 사고나 구학적 귀납법은 작은 문제에 대한 결론이 옳다고 가정을 하고 지금 현재 작은 문제와의 관계를 볼 때 자신에게도 결론이 옳다는 것을 증명하면 되는 것입니다. 수학적 귀납법을 통해 재귀 호출을 하는 것에 대한 시간을 평가하는 것이 가능해집니다. 

 

 

병합 정렬과 재귀 호출

이러한 방법을 사용하게 되면 병합 정렬이라는 알고리즘이 재귀 호출을 이용하여 일어나게 됩니다. 병합 정렬은 MergeSort라고 말하는데 배열의 시작과 끝을 주고 배열을 주게 되면 병합 정렬에서는 1에서 중간 지점을 계산하고 배열을 반으로 나누게 됩니다. 배열을 반으로 나눠 위치를 q에 넣게 되고 첫 번째 전반부와 배열의 반의 앞쪽, 배열의 반의 뒤쪽을 다시 mergeSort 하게 됩니다.

 

 

그래서 전반부 정렬과 후반부 정렬을 한 뒤 4번에서 병합을 하게 됩니다. 그래서 2번과 3번을 보면 반으로 나뉘어 있는 것을 볼 수 있는데, 반 지점에서 시작부터 반과 반 다음부터 끝까지로 나눌 수 있습니다. 그렇게 되면 한번 재귀 호출을 할 때마다 반씩 줄어드는 상황이 됩니다. log_2n번 호출이 되었다고 할 수 있습니다. 반대로 지수적으로 늘어나게 될 경우 2배, 4배, 8배로 늘어나게 됩니다. 그래서 merge까지 합쳐 전체적으로 소요 시간이 어떻게 되는가 하는 부분에 대해서는 병합 정렬에 대한 이해를 통해 계산을 할 수 있습니다. 

 

모든 IT의 기초인 문제를 해결하는 과정을 묘사하는 알고리즘

모든 IT의 기초인 문제를 해결하는 과정을 묘사하는 알고리즘

 

알고리즘의 IT 기기 활용

이러한 알고리즘은 실생활에서 다양하게 응용이 되어 사용되는데, 길 찾기나 ATM 기계의 위치가 어느 정도에 설치가 되어야 하는지, DNA 염기서열 분석이나 비행기 스케쥴링, 신용카드 정보 데이터 분석 등 다양한 실생활의 문제 해결을 위해 알고리즘이 활용이 되는 것을 볼 수 있습니다. 간단한 알고리즘의 개념이 이렇게 많은 IT 기기들에서 활용이 될 수 있는 것이 놀랍습니다.