알고리즘 - 1 알고리즘의 정의와 필요성

목표

 실세계에서 해결하고자 하는 모든 문제들에 대한 최적의 해결 방법을 전산학 적으로 고찰하기 위해 최적의 알고리즘을 학습하고, 각종 알고리즘에 대한 복잡도와 성능 및 특성을 고찰해 실세계에 적용할수 있는 능력을 배양한다.

 

 

 

알고리즘이란?

1. 알고리즘의 기원

2. 알고리즘의 정의

3. 알고리즘의 특징

4. 알고리즘의 분류

 

 

알고리즘 단어 유래

- 페르시아 수학자인 무함마드 이븐 무사 알콰라즈미 라틴 이름인 라고리즈미로부터 유래

- 무하마드 이븐 무사 알콰리즈미는 대수학의 아버지라 불리며, 수학 뿐만아니라 천문학, 지리학 등에도 많은 업적을 남김

 

유클리드 호제법

- 가장오래된 알고리즘

- 기원전 300년경 유클리드에 의해 증명됨

- 2개의 자연수 사이의 최대 공약수를 구하는 알고리즘

 

입력 : 자연수 m, n 단 m >= n > 0
출력 : m, n의 최대 공약수

Euclid(m, n)
if n = 0
    return m
return Euclid(n, m mod n)

 

 

알고리즘

- 어떠한 문제를 해결하기 위한 여러 동작들의 모임을 기술한 것

- 컴퓨터 공학에서 알고리즘은 명확한 입력과 출력을 가지고 있어야 함

 

 

프로그램 작성

- 프로그램 = 자료구조 + 알고리즘

- ex. 최대값 탐색 프로그램 = 배열 + 순차 탐색

 

 

알고리즘을 공부하는 이유

- 문제를 해결하기 위한 효율적인 과정을 습득하기 위함

- 기존의 알고리즘을 분석하여, 체계쩍으로 생각하는 훈련을 수행하기 위함

 

 

알고리즘의 예시

1. 학생 100명의 성적을 입력받아 가장 최저 점수를 출력하는 작업

- 입력 : 학생 100명의 성적

- 출력 : 입력된 100개의 성적 중 최소 값

 

2. 숫자 카드 74, 58, 45, 100, 32, 88 중 32 숫자카드를 찾는 작접

- 입력 : 숫자카드 74, 58, 45, 100, 32, 88

- 출력 : 32 숫자카드의 위치

 

 

 

알고리즘이 가져야 하는 요건

1. 입출력 : 입력과 출력을 가져야 함

2. 정확성 : 주어진 입력에 대해 항상 올바른 답을 주어야 함

3. 유한성 : 유한 시간 내에 종료 되어야 함

4. 효율성 : 시간적, 공간적 효율성을 가져야 함

5. 수행성 : 컴퓨터로 수행 가능해야함

 

 

알고리즘 분석 기준

1. 정확 성

- 모든 유효 입력에 대해 유한 시간 내 올바른 해를 찾아내는가 판단

2. 기억 장소 사용량

- 해를 찾아내는 데 사용되는 기억 장소의 사용량

- 입력 개수에 따른 증가율이 중요함

3. 수행 시간

- 해를 찾아내는데 걸리는 시간

- 절대 시간보다는 입력 개수에 따른 증가율이 중요함

 

 

알고리즘의 분류

분류 방식	분류
문제 해결 방법에 따른 분류	1. 분할 정복 알고리즘 2. 그리디 알고리즘 3. 동적 계획 알고리즘 4. 근사 알고리즘 5. 백트래킹 알고리즘 6. 분기 한정법
문제에 따른 분류	1. 정렬 알고리즘 2. 그래프 알고리즘 3. 기하 알고리즘

 

 

1. 분할 정복 알고리즘

- 주어진 문제의 입력을 분할하여 문제를 해결하는 알고리즘

- 분할된 입력에 똑같은 알고리즘을 적용(재귀를 이용하는 경우가 많음)

- ex. 병합 정렬, 퀵 정렬, 선택 정렬 등

 

2. 그리디 알고리즘

- 가능한 해들 중에서 가장 좋은 해를 찾는 알고리즘

- 수행 시점에서 가장 좋은 해를 찾아 나감

 -> 근시안적인 최적해를 찾는다고 할 수 있으며, 근시안적인 최적해를 모아서 문제의 최적해를찾음

- ex. 동전 거스름 문제, 최소 신장 트리 문제, 최단 경로 찾기 문제, 부분 배낭 문제

 

3. 동적 계획 알고리즘

- 최적회 문제 해결 알고리즘

- 입력 크기가 작은 부분 문제를 해결하고, 이를 이용해서 보다 큰문제를 해결하여, 최종적으로 주어진 입력크기의 문제를 해결하는 방법

- ex. 모든 쌍 최단 경로, 연속 행렬 곱셈, 배낭 문제, 동전 거스름돈 문제

 

4. 근사 알고리즘

- 지수 시간이 걸리는 문제(NP 문제)에 대한 근사해를 찾는 알고리즘

- ex. 여행자 문제, 정점 커버 문제, 통 채우기 문제, 클러스터링

 

5. 백트래킹 기법

- NP 완전 문제의 해를 탐색하기 위한 알고리즘

- ex. 여행자 문제, 체스 퀸 배치 문제

 

6. 분기 한정 기법

- 큰 입력에 대해 백트래킹 기법이 갖는 단점을 보완하기 위해 고안된 기법

- ex. 여행자 문제 등

 

 

알고리즘 분석

1. 알고리즘을 분석하는 이유

2. 알고리즘의 수행 시간

3. 알고리즘의 공간 사용량

 

알고리즘을 분석하는 이유

1. 정확성 확인(무결성 확인)

- 모든 유효한 입력에 대해 유한 시간 내에 올바른 해를 찾아내는가 판단하기 위함

2. 효율성 확인

- 한정된 자원(기억 장소 사용량, 수행 시간)에서 효율적으로 작동하는지 확인하기 위함

3. 궁극적으로 알고리즘을 분석하여 얻는 이점

- 알고리즘 분석 -> 체계적이고 효율적으로 생각하는 훈련을 할 수 있음

- 문제를 해결하기 위해 중요한 것과 중요하지 않은 것을 판단할 수 있음

- 문제를 단순화 하여 생각 할 수 있음

- 다른사람의 아이디어에 대한 효율성을 판단 할 수 있음

 

 

알고리즘 수행 시간

1. 알고리즘의 효율성을 분석하는 방법은 다양하지만 많은 경우 알고리즘의 수행시간을 이용하여 효율성 분석

2. 시간 복잡도

 - 입력 크기에 비례하여 작업시간이 어떠한 비율로 증가하는지 확인함.

3. 시간 복잡도를 사용하는 이유

- 실측으로 시간을 측정하는 경우 프로그래밍 언어, 컴퓨터 성능, 프로그래머의 실력 등의 다양한 변수에 따라 달라질 수 있음

 

 

수행 시간 분석 방법

- 최선 경우 분석

- 최악 경우 분석

- 평균 경우 분석

 

 

 

 

가짜 동전 찾기 알고리즘

- 문제 : 많은 수의 동전 중에서 1개의 동전이 가짜 동전인 경우 가짜 동전을 어떻게 찾을까?

- 가짜 동전의 크기와 모양은 진짜 동전과 동이랗며 무게만 약간 가벼움

- 무게의 차이를 감지 할 수 있는 양팔의 저울만 주어짐

 

알고리즘 1

- 해결 방법 : 한쪽에 1개의 동전을 올려놓고 나머지 동전을 하나씩 바꾸어 가면서 무게를 잼

- 수행시간 분석

 -> 최선 경우 분석 : 운이 좋은 경우 1번만에 찾을 수 있음

 -> 최악 경우 분석 : 운이 나쁜 경우 즉, n - 1번 수행해야함

 

알고리즘 2

- 해결방법 : 동전을 2개씩 선택하여 2개의 동전을 양팔 저울에 올려놓고 무게를 잰 후 가벼운 동전을 찾아냄

- 수행 시간 분석

 -> 최선 경우 분석 : 운이 좋은 경우 1번 만에 찾을 수 있음

 -> 최악 경우 분석 : 운이 나쁘면 모든 경우 즉, n/2번 수행해야함

 

알고리즘 3

- 해결 방법

 -> 동전을 똑같은 개수로 반으로 나누어 두 무리를 만들고 무개를 잰 후 가벼운 쪽을 찾고, 나머지를 다시 반으로 나누어 가벼운 쪽을 찾음

- 수행 시간 분석

 -> 일반적인 n에 대해서 log_2 n번 수행해야함.

 

알고리즘 분석 - 동전 개수가 1024개 인 경우

방법	분석 내용
알고리즘1	- 최악의 경우 : 1023번 수행 - 평균의 경우 512번 수행 - 최선의 경우 : 1번 수행 (큰 의미없음)
알고리즘2	- 최악의 경우 : 512번 수행 - 평균의 경우 : 256번 수행 - 최선의 경우 : 1번 수행
알고리즘3	- 최악의 경우 : 10번 수행 - 평균의 경우 : 10번 수행 - 최선의 경우  10번 수행

=> 알고리즘 3은 동전의 개수가 n인 경우 어떠한 경우에도 log_2 n번의 수행으로 동전을 찾을수 있기 때문에 가장 효율적

 

 

알고리즘의 공간 사용량

- 알고리즘의 공간 사용량도 알고리즘의 효율성을 분석하는 방법 중 하나

- 공간 복잡도 : 입력 크기에 비례하여 작업 공간이 어떠한 비율로 증가하는지 분석하는 것

- 공간 복잡도를 시간 복잡도와 함께 사용하는 이유

 -> 실측으로 공간 사용량을 측정하는 경우 프로그래밍 언어, 프로그래머 실력 등 다양한 변수에 따라 달라질 수 있음.