알고리즘 개요

1. 알고리즘이란?

주어진 문제를 해결하거나 함수를 계산하기 위해 따라야 할 명령어들을 단계적으로 나열한 것이라고 할 수 있습니다.

 

2. 알고리즘을 만족하기 위한 조건

1. 입출력 : 0개 이상의 외부입력과 1개 이상의 출력을 생성해야 합니다.

2. 명확성 : 각 명령은 모호하지 않고 단순 명확해야 합니다.

3. 유한성 : 한정된 수의 단계를 거친 후에는 반드시 종료해야 합니다.

4. 유효성 : 모든 명령은 컴퓨터에서 수행할 수 있어야 합니다.

5. 효율성 : 효율성은 알고리즘을 만족하기 위한 필수 조건은 아닙니다. 그러나 실용적관점에서는 효율성도 상당히 중요합니다. 왜냐하면 알고리즘을 구성하더라도 무한한 시간이 걸린다면 문제해결을 할 수 없다고 볼 수 있기 때문입니다.

3. 알고리즘의 생성단계

1) 설계

일반적/ 범용적인 설계기법은 존재하지 않습니다. 왜냐하면 주어진 문제와 조건등이 매우 다양하기 때문입니다.

그러나 많이 사용되는 알고리즘 설계기법은 3가지가 존재합니다.

 

1] 욕심쟁이 방법(탐욕알고리즘, 그리디 알고리즘) :

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

이 방법은 주로 최소값이나 최대값 등을 구하는 최적화문제에 사용됩니다.

 

장점: 이 방법은 간단하면서 효율적인 알고리즘을 만들 수 있는 기법입니다.

단점: 희망적이라고 쓰여있듯이 각 단계마다 선택한 국부적인 최적해가 항상 전체적인 최적해를 만들지 못할 수도 있습니다.

대표적인 응용 문제에는 아래 케이스가 있습니다.

 

a. 거스름돈 문제 : 가게에서 고객에게 돌려줄 거스름돈이 T만큼 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제

 

기본 해결방법: 거스름돈의 액수를 초과하지않으면서 동전의 액면가가 단순히 큰 것부터 욕심을 부려서 최대한 뽑아서 거스름돈을 만드는 방법

ex) 거스름돈의 액수 : 970원

첫번째 : 500원 동전 1개 , 나머지 470원

두번째 : 100원 동전 4개, 나머지 70원

세번째 : 50원 동전 1개, 나머지 20원

네번째 : 10원 동전 2개, 나머지 0원 → 총 동전의 개수 8개

 

ex2) 새로운 120원 동전 생성되고, 거스름돈의 액수 : 650원일 경우

일반적인 방법:

첫번째 : 500원 동전 1개, 나머지 150원

두번째 : 120원 동전 1개, 나머지 30원

세번째 : 10원 동전 3개, 나머지 0원 → 총 동전의 개수 5개

 

효율적 방법

첫번째 : 500원 동전 1개, 나머지 100원

두번째 : 100원 동전 1개, 나머지 50원

세번째 : 50원 동전 1개, 나머지 0원 → 총 동전의 개수 3개 (효율적)

 

※ 따라서 동전의 액면가가 일반적인 경우에는 욕심쟁이 방법으로 해결이 불가능합니다.

 

b.배낭문제 

 

가정 : 최대 용량M인 하나의 배낭과 n개의 물체가 있습니다. 각 물체 i에는 물체의 무게 w와 해당 물체를 배낭에 넣었을 때 얻을 수 있는 이익 p가 부여됩니다. 또한 물체를 쪼개서 넣을 수 있습니다.

 

문제 : 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어있는 물체들의 이익의 합이 최대가 되도록 물체를 넣는 방법, 또는 최대이익을 찾는 문제입니다.

 

기본해결방법 : 물체의 무게는 적으면서 이익이 가장 큰 물체부터 골라서 욕심을 내어 최대한 넣는 과정을 반복하는 방법

즉 단위 무게당 이익이 가장 큰 물체부터 최대한 넣는 과정을 반복함, 또한 물체를 통째로 넣을 수 없다면 물체를 쪼개서 넣음

 

ex) M=10, n=4, (물체1,물체2,물체3,물체4) → (p1,p2,p3,p4) = (15,20,9,14), (w1,w2,w3,w4) = (3,5,3,4)

단위 무게당 이익 = (p1/w1, p2/w2, p3/w3, p4/w4) = (5, 4, 3, 3.5)

첫번째 : 물체1(w1 = 3) 통째로 넣음, 나머지 공간 7 , 이익 15

두번째 : 물체2(w2 = 5) 통째로 넣음, 나머지 공간 2, 이익 20

세번째 : 물체4(w4 = 4) 반으로 쪼개서 넣음, 나머지 공간 0, 이익 7 → 총 이익 42

 

ex2) 물체를 쪼갤 수 있다는 가정을 삭제 (0/1 배낭문제)

M=10, n=4, (물체1,물체2,물체3,물체4) → (p1,p2,p3,p4) = (15,20,9,14), (w1,w2,w3,w4) = (3,5,3,4)

단위 무게당 이익 = (p1/w1, p2/w2, p3/w3, p4/w4) = (5, 4, 3, 3.5)

기본 해결방법

첫번째 : 물체1 넣음, 나머지 공간 7 이익 15

두번째 : 물체2 넣음, 나머지 공간 2 이익 20

세번째 : 공간이 2밖에 남지않아 물체3, 물체4를 넣을 수 없음 → 총 이익 35

 

효율적 해결방법

배낭의 무게에 맞춰서 물체1(w1=3), 물체3(w3=3), 물체4(w4=4)를 배낭에 넣음

총 이익 : 15+9+14 = 38(효율적)

 

※ 따라서 0/1 배낭문제는 욕심쟁이 방법으로 해결할 수 없습니다.

 

최소신장트리 → 크루스칼 알고리즘, 프림 알고리즘

단일 출발점 최단 경로 → 데이크스트라 알고리즘

 

2] 분할정복 방법 :

주어진 문제의 입력을 더이상 나눌 수 없을 때까지 2개 이상의 작은 문제들로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방법입니다.

 

분할정복 방법의 특징으로는 아래 두가지가 있습니다.

1. 분할된 작은 문제는 원래 문제의 동일합니다.

즉, 입력의 크기만 작아진 것입니다.

2. 분할된 문제는 서로 독립적입니다.

순환적인 분할 및 결과의 결합이 가능합니다.

 

분할정복방법은 각 순환 호출마다 세단계의 작업을 수행합니다.

1. 분할 : 주어진 문제의 입력을 여러개의 작은 문제로 분할합니다.

2. 정복 : 작은 문제들을 순환적으로 분할하며 작은 문제가 더이상 분할되지 않을 정도의 크기라면 순환 호출없이 작은 문제에 대한 해를 구합니다.

3. 결합: 작은 문제의 정복된 해를 결합하여 원래 문제의 해를 구합니다. 

 

이러한 분할정복 방법이 적용된 문제에는 퀵정렬, 합병정렬, 이진탐색 등이 있습니다.

 

 

3] 동적 프로그래밍 방법

입력의 크기가 가장 작은 부분 문제부터 해를 구하여 테이블에 저장해 놓고, 이를 이용하여 입력크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근방법입니다.

 

이 방법의 특징으로는 아래와 같습니다.

1. 각각의 작은 문제는 원래의 문제와 동일하며 입력의 크기만 작습니다.

2. 작은 문제들은 서로 독립일 필요가 없습니다.

 

이러한 동적 프로그래밍 방법이 적용된 문제로는 플로이드 알고리즘, 행렬의 연쇄적 곱셉문제, 최장 공통 부분 수열 문제 등이 있습니다.

 

2) 표현/기술

1. 일상언어 : 단계별로 우리가 흔히 사용하는 언어로 의사표현을 하는 것을 말합니다.

예를 들면 여러개의 숫자 모음에서 최소값 찾기 문제가 있다고 한다면 아래와 같이 구성할 수 있습니다

[1] 첫번째 데이터를 최소값으로 저장한다.

[2] 다음 숫자를 보고 해당 숫자와 최소값을 비교한다.

[3] [2]의 결과로 해당 숫자가 최소값보다 작다면 해당 숫자를 최소값으로 저장한다.

[4] 다음 숫자가 있다면 [2]~[3]을 반복한다.

[5] 최소값을 출력한다

 

2. 의사코드

프로그래밍언어를 사용하면서도 일상언어를 섞어서 사용하는 방법입니다.

A = 숫자 리스트

i=1;

min = A[0];

while(i < n){

A[i] 가 min보다 작으면 min = A[i];

i++;

}

min 출력

 

3. 순서도 : 순서도는 알고리즘을 표현할때 나타나는 그림입니다.

 

 

3) 정확성 검증

수학적 증명으로 정확성을 검증합니다.

4) 효율성 분석

공간 복잡도, 시간 복잡도 등으로 효율성을 분석합니다.