알고리즘 공부 <1> - 알고리즘이란? 정렬의 예 (삽입,병합)

Posted by oimb
2018. 9. 1. 20:18 알고리즘

그림 출처: https://www.inflearn.com

 

 

알고리즘은 간단히 말해 어떤 값이나 값의 집합을 입력으로 받아 또 다른 값이나 값의 집합을 출력하는

잘 정의된 계산 절차를 말한다.

그리고 모든 입력 사례에 대해 항상  올바른 출력을  내고 종료할 경우 이를 '타당하다'고 하며 , 그 타당한

알고리즘이 주어진 계산 문제를 푼다고 말한다.

지금 부터 이러한 알고리즘에 대해서 간단한 예를 설명 하겠습니다.

 

2. 정렬

2.1) 삽입 정렬

하나의 storage에 비교할 값을 넣고 바로 전 인덱스 부터  대소를 비교하며 차례대로 이동하는 형식이다.

따라서 기준점(*)을 기준으로 왼쪽은 정렬이 되어져 있고 오른쪽은 정렬되지 않았다. 

의사코드를 보면

이러한 값이 된다.

여기서 잠깐 이 의사코드가 맞는지 확인 하기 위하여 루프 불변셩에 대해서 알아보자

루프 불변성은 알고리즘이 타당한 이유를 쉽게 이해할 수 있도록 하기 위해 사용된다. 

이 루프 불변성을 보이려면 세 가지 특성을 만족하면 되는데

 

초기 조건 - 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다.

유지 조건 - 루프의 반복이 시작되기  전에 루프 불변성이 참이었다면 다음 반복이 시작되기 전까지도

계속 참이어야 한다.

종료 조건 - 루프가 종료될 때 그 불변식이 알고리즘의 타당성을 보이는데 도움이 될 유용한

특성을 가져야 한다.

 

여기서 앞의 두 조건을 만족하면 루프가 반복을 시작할 때 루프 불변성은 항상 참이다.

삽입 정렬을 예로 들면

1. 루프의 첫 반복 j=2일때 루프 불변성이 성립하는지 보자.

간단하가 처음일 때 A[1] 만 존해고 이는 정렬 되었다고 볼수 있으므로 루프 불변성이 성립한다.

 

2. 다음으로 매번 반복 시 루프 불변성이 유지되는지를 보자

이 역시 간단하다. 의사 코드를 보면 A[j] (key) 값이 올바른 위치를 찾을 때 까지 j-1,j-2,j-3...을

오른쪽으로 한 자리 씩 움직이게 된다.( A[i+1] = A[i]) 그리고 마지막에는 같은 

원소이지만 정렬 된 값을 가지게 되므로 루프 불변성이 유지된다.

 

3. 3은 2와 같다 종료 상황시 루프 불변성이 유지됨을 보이면 된다. 범위는 1~n이 될것이다.

지금 의사코드는 맞는지를 확인 해봤으니 이 알고리즘을 분석해 보자.

알고리즘을 분석할 때는 수행시간을 입력 크기의 함수로 표현 한다( T(n)

이를 위해 수행시간과 입력크기를 알아야 하는데

 

입력 크기는 일반적으로는 입력 항목의 개수 이다. 또 이진수의 비트(bit) 인 경우 필요한 총 비트수가 될수 있다.

수행 시간은 실행된 단계의 횟수를 말한다. 의사코드의 각 행을 수행하는 데 상수 시간이

소요 된다고 생각 하면된다. 보통 상수시간(c)와 횟수(times)로 계산한다.

 

알고리즘의 수행시간은 각 명령문 수행시간의 합이다. 이를 주의하자

수행시간이 ci 단계 만큼 걸리는 명령문이 n번 실행된다면 총 수행시간은 ci n 이 된다

이를 T(n)에 대해 정리 하면

이 된다

그리고 여기서 c(5,6,7) 의 식에 대해서 best&worst case 로 나뉘어게 된다.

best case의 경우 while문이 조건식 비교의 순간 단 한번 돌게 되므로 c(6,7)은 0이 되어진다.

그리고 worst case는 전부 도는 경우로 1 ~ j-1 까지 모두 돌게 되어진다.

vWorst case

 빅오는 O(n^2)이 된다.

 
2.2) 병합정렬
 
이번에는 앞서 설명한 삽입정렬 다음으로 병합정렬을 설명하겠습니다.
삽입정렬은 점진적인 방법을 사용하는데 하나씩 검사하는 형태라고 생각하면됩니다.
 
이어 병합정렬은 분할정복 형태로 이루어진다. 
분할정복 형태는 재귀적 구조를 가진 유용한 알고리즘입니다.
이를 적용할 병합 정렬은
 

따라서 이에 대응하는 의사코드를 보면

 

그리고 분할정복 방법론의 시간 복잡도 함수 로 나타내면

 

 

이는  원래 문제의 1/b 인 a개의 부분 문제로 분할된다고 보면 된다  즉 병합 정렬에서는
원래 문제의 1/2 인 2개로 나눠진다고 볼수 있다.
즉 분할정복 방법론의 병합정렬의 시간 복잡도 함수를 나타내면

 

분할 단계는 부분 배열의 중간 위치를 계산 하므로 상수 시간 이 걸린다 즉 O(1)
정복 단계는 문제의 1/2를 재귀적으로 풀게 되므로 2T(n/2)이 된다.
결합 단계는 이미 n개의 원소를 나누는데 worst case가 n이므로 O(n)이 된다.
 
 
알고리즘은 정말로 어려운것 같다 ... 이해 해도 다시 하나씩 증명하며 정리하려니 되게 고됬다..
오늘은 여기까지 다음 알고리즘 공부까지..

 

이 댓글을 비밀 댓글로