알고리즘의 기초 - 정렬

컴퓨터 과학이란 컴퓨터를 활용하여 문제 해결하는 것을 말한다.

"여기서 문제 해결을 어떤 방식으로 할 것인가"가 중점인데 이 절차, 방식이 알고리즘이다.

 

쉽게 생각하면 문제 해결을 위한 레시피라고 할 수 있다.

알고리즘의 단계적 처리 절차를 따르면 문제를 해결할 수 있다.

 

효율적인 알고리즘 생성을 위해서는 4개의 조건을 충족해야 한다.

 

1. 0개 이상의 외부입력 + 1개 이상의 출력 생성(입출력)

2. 각 명령은 모호하지 않고 단순 명확해야 함(명확성)

3. 한정된 수의 단계를 거친 후에는 반드시 종료해야 함(유한성)

4. 모든 명령은 컴퓨터에서 수행가능해야 함(유효성)

 

4개의 조건을 충족하는 알고리즘은 어떻게 생성될까?

 

1. 설계 : 어떤 방법을 사용할 것인가?(욕심쟁이 방법, 분할정복 방법 등)

2. 표현 : 프로그래밍 언어, flow 차트, 의사 코드 등으로 표현한다.

3. 정확성 검증 : 수학적 증명을 통해 정확성을 검증한다.

4. 효율성 분석 : 공간, 시간 복잡도를 이용하여 효율성을 분석한다.

 

물론 현시대에 우리가 알고리즘을 직접 개발할 일은 거의(99.999999%) 없다.

이미 너무나 똑똑하고 뛰어난 사람들이 많이 개발했고, 우리는 그것을 사용할 줄만 알면 되기 때문이다.

 

대표적인 알고리즘 설계 기법

대표적인 알고리즘 설계 기법에는 욕심쟁이 방법과 분할정복 방법이 있다.

 

- 욕심쟁이 방법(Greedy,  탐욕알고리즘)

내가 각 단계에서 가장 최선이라 여겨지는 것만 계속 고르는 것이다.

 

 

위와 같은 상태가 있다고 한다면 A로 갔을 때 가장 최고의 상태라면 A를 선택하는 것이다.

물론 A 다음에 선택할 수 있는 선택지가 B나 C에 비해 현저히 좋지 않는 경우가 발생할 수 있으며, 이것이 욕심쟁이 방법의 한계이다. 가장 간단하고 효율적인 알고리즘을 만들 수 있는 방법이다.

 

욕심쟁이 방법을 이용하여 해결하는 문제로는 우선 거스름돈 문제가 있다.

 

거스름돈 문제란? (동전문제)

거스름돈을 줄 때 동전의 수를 최소로 주는 문제이다.

액수를 초과하지 않으면서 액면가가 가장 높은 동전을 최대로 뽑으면 해결하는 문제이다.

그러나 동전의 액면가가 120원, 280원 등 일반적이지 않은 경우 해결할 수 없다.

 

두번째로는 배낭 문제가 있다.

최대 용량이 M인 하나의 배낭에 n개의 물체가 있다고 가정.

각 물체에는 무게(w)와 이익(p)가 부여된다. 이때 물체의 이익의 합이 최대가 되도록 가방에 넣어야 한다.

 

무게는 적으면서 이익이 가장 큰 물체(단위 무게당 이익이 높은)를 찾아서 최대한으로 넣으면 해결 된다.

단, 물체를 쪼갤 수 있다는 전제하에 해결되며 물체를 쪼갤 수 없다면(0/1 배낭 문제) 해결이 불가하다.

 

- 분할정복 방법

주어진 문제를 2개 이상의 문제들로 계속 분할한다.

분할된 문제들의 해결 합을 결합하여 원래 문제의 해를 구하는 방식이다.

이때 분할된 작은 문제는 원래 문제와 동일해야하며(입력값만 작아짐), 분할된 문제는 서로 영향을 주지 않고 독립적이여야 한다.

 

정렬

주어진 데이터를 값의 크기 순서에 따라 재배치하는 것.

 

정렬할 모든 데이터를 주기억장치에 저장한 후 정렬하는 내부정렬과 일부 데이터들만 반복적으로 주기억장치로 가져와서 정렬을 수행하는 외부정렬 두가지 방식이 있다.

 

내부정렬의 정렬방식은 두 데이터를 직접적으로 비교하면 정렬하는 비교 기반과 데이터 분포(데이터 이동 횟수 비교)를 이용한 데이터 분포 기반 알고리즘이 있다.

 

비교 기반 알고리즘에는 선택, 버블, 삽입, 셸, 퀵, 합병, 힙 정렬이 있으며 데이터 분포 기반 알고리즘에는 계수, 기수, 버킷이 있다.

 

정렬을 나누는 기준 중 다른 하나는 안정적(Stable), 불안정적이 있으며 안정적은 중복된 데이터 A, B가 있다는 가정하에 정렬 이후에서 A와 B의 순서가 유지되는 것을 말한다. 불안정적은 정렬 이후 A와 B의 순서가 바뀌는 것을 말한다.

 

제자리 정렬(In-Place)은 입력데이터가 아무리 증가해도 추가 저장 공간이 증가하지 않는 정렬을 말한다.

 

 

- 선택 정렬

입력 배열에서 가장 작은 값부터 순서대로 선택해서 나열하는 방법.

제자리, 불안정적 알고리즘이다. 데이터의 입력 순서에 영향을 받지 않고 항상 동일한 성능을 갖는다.

 

1. 정렬되지 않은 부분을 순회하며 가장 작은 값을 찾는다.

2. 찾은 최소값을 정렬되지 않은 부분의 가장 첫번째 원소와 교환한다.

3. 이후부터는 정렬된 배열의 가장 마지막 원소와 교환한다.

 

두 개의 반복문이 중첩되어 진행되는데.

정렬되지 않은 부분을 순회하며 가장 작은 값을 찾는 For 문(0부터 N-1까지)

정렬된 부분의 마지막 원소값을 찾는 For 문(N-1부터 1까지)

 

빅오 표기법에 따라 성능은 O(N^2)이다.

 

- 버블 정렬

모든 인접한 두 데이터를 비교하여 왼쪽이 더 큰 경우 서로 교환하여 정렬을 수행한다.

왼쪽에서 오른쪽으로 진행하며 큰 값을 오른쪽에 배치하는 방향 또는 오른쪽에서 왼쪽으로 진행하며 가장 작은 값을 왼쪽에 배치하는 방향 2개가 존재한다.

제자리,안정적 알고리즘이다.

 

두 개의 반복문이 중첩되어 진행되며 선택 정렬과 동일하게 For문이 순회한다.

 

빅오 표기법에 따라 성능은 O(N^2).

 

선택정렬보다 비효율적이나 두 개의 반복문을 개선하여 효율적으로 사용할 수 있다.

첫번째 반복문에서는 자리 바꿈이 발생하지 않으면 정렬된 상태이므로 바로 bool 변수를 사용하여 자리바꿈이 일어나는 지 체크하도록 한다.

두번째 반복문에서는 모든 데이터를 비교하는데 정렬된 부분까지 비교할 필요는 없으므로 단계가 증가함에 따라 특정 인덱스까지만 비교하도록 한다.

 

이와 같이 변경하면 O(N^2)라는 것은 동일하지만 비교적 빠른 성능을 갖게 된다.

또한, 변경된 알고리즘의 경우 입력된 데이터 상태에 따라 성능이 달라지게 되는데

 

50 40 30 20 10 역순일때 최악의 성능을 갖으며 10 20 30 40 50과 같이 정순일때 최고의 성능을 갖는다.