알고리즘 개념 정리 - 정렬

재직중이지만 관련 전공자가 아니라서 부족한 기초를 채우기 위해 방송통신대학교 컴퓨터과학과 수업을 들으며 성적을 만들고 있는데,

이번에는 알고리즘 수업을 들으며 내용을 정리해보았습니다.

알고리즘의 시간 복잡도

O(logn)  O()  O(n)   O()   O(1)   O()   O(nlogn) 를 비효율적인 것부터 효율적인 순서대로 나열해보자.

 

알고리즘의 시간 복잡도를 구할 때, 알고리즘의 모든 문장이 아닌 루프의 반복 횟수만을 조사하여 최고 차수를 시간 복잡도로 취하여 O(최고차수)와 같은 방법으로 계산해볼 수 있습니다.
빅오 함수에 따른 연산 시간의 증가를 표로 나타내보면 다음과 같습니다.

따라서, 비효율적인 것 부터 효율적인 순서대로 나열하면 아래와 같습니다.
O()  ＜  O()  ＜  O()  ＜  O(nlogn)  ＜  O(n)  ＜  O(logn)  ＜  O(1)

 

 

알고리즘 설계 기법 - 욕심쟁이 방법

개념

  해를 구하는 일련의 선택 과정에서 전후 단계의 선택과는 상관없이 각 단계마다 ‘가장 최선’이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법

 

특징

  각 단계에서 전후 단계의 선택에 대해 고려하지 않고 현재 상태에서만 만족하는 최적해를 선택하기 때문에 국부적인 최적해가 항상 전체적인 최적해를 만들지 못할 수도 있습니다. 최솟값/최댓값을 구하는 최적화 문제에 주로 사용하며, 간단하면서 효율적인 알고리즘을 만들 수 있는 강력한 기법입니다.

 

적용 알고리즘

거스름돈 문제, 배낭 문제, 최소 신장 트리(크루스칼 알고리즘, 프림 알고리즘), 단일 출발점 최단 경로(데이크스트라 알고리즘) 등이 있습니다.

• 거스름돈 문제 : 가게에서 고객에게 돌려줄 거스름돈이 T만큼 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제입니다. 동전의 액면가가 임의로 주어지는 일반적인 경우에는 욕심쟁이 방법으로 해결할 수 없습니다.
• 배낭 문제 : 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어있는 물체들의 이익의 합이 최대가 되도록 물체를 넣는 방법을 찾는 문제입니다. 물체를 쪼개서 넣을 수 있다고 가정하면, 단위 무게당 이익이 가장 큰 물체부터 최대한 가방에 넣을 수 있습니다. 물체를 쪼갤 수 없는 ‘0/1 배낭 문제’는 욕심쟁이 방법을 적용할 수 없습니다.

배낭 문제 예시

• 물체를 쪼갤 수 있는 배낭 문제에 대해서 욕심쟁이 방법을 적용해서 최대 이익을 구하시오.

  물체를 쪼갤 수 있다고 가정했으므로 단순히 물체의 이익을 취하기보다는 단위 무게당 이익을 계산하고, 이것이 최대가 되는 물체부터 최대한 배낭에 넣으면 최적해를 구할 수 있습니다. 단위 무게당 이익을 구하면 다음과 같습니다.

단위 무게당 이익이 다음과 같으므로, 단위 무게당 이익이 큰 순서인 물체 4, 물체 1, 물체 3, 물체 2 의 순으로 배낭에 물체를 넣습니다.

 [단위 무게 당 이익]

• 물체 4 : 6.25
• 물체 1 : 6
• 물체 3 : 4
• 물체 2 : 3

물체 4를 배낭에 넣으면 배낭의 용량은 10에서 물체 4의 무게 4만큼 줄어들어서 남은 배낭의 용량은 6이 됩니다. 

그 후에 무게가 3인 물체 1을 배낭에 넣으면 남은 배낭의 용량은 3이 됩니다. 

그 다음 물체 3을 배낭에 넣으면 남은 배낭의 용량 3과 물체 3의 무게 3이 같으므로 배낭이 꽉 차고 더 이상 물체를 넣을 수 없게 됩니다.

결국, 배낭에는 물체 4, 물체 1, 물체 3이 들어있으므로,

얻을 수 있는 최대 이익 = 물체 4의 이익 + 물체 1의 이익 + 물체 3의 이익 = 25+18+12 = 55 가 됩니다.

 

 

정렬 알고리즘 - 선택 정렬 / 버블 정렬 / 삽입 정렬 / 퀵 정렬

정렬할 데이터가 배열 A[]와 같이 주어졌을 때, 
1) 선택정렬, 2) 버블 정렬 (왼쪽에서 오른쪽으로 진행), 3)삽입 정렬의 수행 과정 각각을 단계별로 나타내보자.
                                                                                A[] = {2 5 6 3 4 1}

 

1) 선택 정렬

선택 정렬은 배열에서 최소값(혹은 최대값)을 찾아 선택하고, 해당 값을 배열의 맨 앞(혹은 맨 뒤)과 교환하는 과정을 반복합니다.

선택 정렬의 처리 과정을 순서도로 나타내면 아래와 같습니다.

이 과정은 아래 그림과 같은 단계로 수행됩니다.

 

2)    버블 정렬

버블 정렬은 모든 인접한 두 데이터를 차례로 비교하여 왼쪽 데이터가 더 큰 경우에는 오른쪽 데이터와 자리를 바꾸는 과정을 반복해서 정렬을 수행하는 방법입니다.

모든 인접한 두 데이터의 비교는 왼쪽에서 오른쪽 또는 오른쪽에서 왼쪽으로 진행하면서 수행합니다. 

 

왼쪽에서부터 오른쪽으로 이동하면서 처리하는 과정을 단계별로 나타내면 아래 그림과 같습니다.

 

3)    삽입 정렬

삽입 정렬은 주어진 데이터를 하나씩 뽑은 후 이미 나열된 데이터가 항상 정렬된 데이터를 유지하도록 뽑은 데이터를 바른 위치에 삽입해서 나열하는 방법입니다.

입력 배열을 정렬 부분과 미정렬 부분으로 구분해서, 미정렬 부분의 첫 번째 데이터를 뽑은 후 정렬 부분에서 뽑은 데이터가 위치할 자리를 찾아서 삽입하는 처리 단계를 반복적으로 수행해서 정렬합니다.

 

이 수행 과정을 단계별로 표현하면 아래 그림과 같습니다.

 

 

3)    퀵 정렬

주어진 배열에 대해서 퀵 정렬의 분할 함수 Partition()을 적용한 후의 결과 배열을 구해보자. (단, A[0]이 피벗이다.)
                                                                         A[] = {6 9 7 4 8 2 5 10 3 1}

 

 퀵 정렬은 특정 데이터를 기준으로 주어진 배열을 2개의 부분배열로 분할하고, 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식입니다.

분할 함수 Partition()을 한 번 적용한 후의 결과 배열은 {2 1 3 4 5 6 8 10 7 9} 입니다.

 

풀이 과정을 단계별로 설명한 그림은 아래와 같습니다.