포털:고등학교/정보·통신 계열 전문 교과(2015)/컴퓨터 시스템 일반/알고리즘 설계
알고리즘은 빠른 시간안에 결과를 도출한다!
알고리즘 설계
[편집]알고리즘 설계란?
[편집]알고리즘 설계는 문제를 해결하는 수학적인 과정을 만들어내는 특정한 방법이다.
알고리즘 설계의 이용
[편집]우선, 알고리즘 설계는 알고리즘 공학에 적용되고 웹 크롤링 검색 과정, 패킷 라우팅 및 캐싱 등에서 사용된다.
알고리즘 설계의 종류
[편집]분할정복 알고리즘
[편집]1.분할정복 알고리즘이란? (Divide and Conquer)
분할정복 알고리즘은 문제를 나눌 수 없을 때까지 계속 나눠 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘이다.
2.설계하는 방법
1).주어진 문제가 분할이 가능하다면 2개 이상의 문제로 나눈다. (Divide)
2).나누어진 문제들이 여전히 분할이 가능하다면, 다시 분할을 하고 분할이 안된다면 문제를 푼다.(Conquer)
3).정복(Conquer)한 문제들을 통합하여 원래 문제의 답을 얻는다.(Combine)
3.분할 정복의 응용
1). 병합 정렬 알고리즘
과정
1.정렬한 데이터 집합의 크기가 0또는 1이면 이미 정렬된 것으로 보고, 그렇지 않으면 데이터의 집합을 반으로 나눈다.
2.원래 같은 집합에서 나뉘어져 나온 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다.
(단, 병합할 때 데이터 집합의 원소는 순서에 맞춰 정렬한다.)
다음과 같은 데이터 집합이 있다.
7 2 5 9 6 4 1 3 8
아까 설명한 '과정 1'을 반복한다
7 2 5 9 6 4 1 3 8
↙ ↘
7 2 5 9 6 4 1 3 8
↙ ↘ ↙ ↘
7 2 5 9 6 4 1 3 8
↙ ↘ ↙ ↘ ↙ ↘ ↙ ↘
7 2 5 9 6 4 1 3 8
↙ ↘
7 2
이제 '과정 2'의 방법을 수행한다.
1 2 3 4 5 6 7 8 9
↗ ↖
2 5 6 7 9 1 3 4 8
↗ ↖ ↗ ↖
2 5 7 6 9 1 4 3 8
↗ ↖ ↑ ↑ ↑
2 7 5 9 6 4 1 3 8
↑
7 2
이렇게 데이터 집합을 정렬해가면서 병합하고 결국 완전히 정렬된 데이터 집합을 얻는 알고리즘이다.
2). 합병정렬 알고리즘
과정
1. 두 데이터 집합의 크기의 합만큼의 크기를 가지는 빈 데이터 집합을 만든다.
2. 두 데이터 집합의 첫 번째 요소들을 정확히 비교하여 작은 요소를 빈 데이터 집합헤 추가한다. 그리고 원래 데이터 집합에서 삭제한다.
3.원래 두 데이터 집합의 요소가 모두 삭제될 때 까지 2를 반복한다.
다음과 같은 집합 A B와 A + B의 크기의 합만큼의 집합을 가진 빈 데이터 집합 C가 있다.
A | 1 | 3 | 5 | 7 | 9 | B | 2 | 4 | 6 | 8 | C | | | | | | | | | |
A | 1 | 3 | 5 | 7 | 9 |
↕ // A에서 1 과 B에서 2를 비교 후 1이더 작으므로 C 첫 번째 구간에 1을 추가하고 A에서 1을 제거
B | 2 | 4 | 6 | 8 |
C | 1 | | | | | | | | |
A | | 3 | 5 | 7 | 9 |
↗
↙
B | 2 | 4 | 6 | 8 |
C | 1 | 2 | | | | | | | |
A | | 3 | 5 | 7 | 9 |
↕
B | | 4 | 6 | 8 |
C | 1 | 2 | 3 | | | | | | |
A | | | 5 | 7 | 9 |
↗
↙
B | | 4 | 6 | 8 |
C | 1 | 2 | 3 | 4 | | | | | |
A | | | 5 | 7 | 9 |
↕
B | | | 6 | 8 |
C | 1 | 2 | 3 | 4 | 5 | | | | |
A | | | | 7 | 9 |
↗
↙
B | | | 6 | 8 |
C | 1 | 2 | 3 | 4 | 5 | 6 | | | |
A | | | | 7 | 9 |
↕
B | | | | 8 |
C | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | |
A | | | | | 9 |
↗
↙
B | | | | 8 |
C | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
A | | | | | 9 |
B | | | | |
C | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
주의점
1). 문제를 제대로 나누기만 하면 해결하는 것은 쉽기 때문에 분할을 제대로 하는 것이 제일 중요하다.
2). 분할정복 알고리즘은 일반적으로 재귀 알고리즘 사용 되므로 효율성이 쉽게 떨어진다.
탐욕 알고리즘
[편집]탐욕 알고리즘이란? 탐욕 알고리즘은 가장 최적이라고 생각되는 것을 계속 선택하는 방식으로 진행하여 해답에 도달하는 알고리즘을 말한다.
(순간마다 하는 선택은 그 부분에서는 최적한 방법이지만, 그것들만 선택해서 최종적인 해답을 만들었다고 해서, 꼭 최적이라는 보장은 없다.)
탐욕 알고리즘의 활용
1). 거스름돈 거슬러 주기
편의점에서 돈을 거슬러 줄 때에는 되도록이면 동전 개수를 적게 거슬러 주는게 좋다. 거스름돈이 2000원인데 10원 짜리 200개를 주면 손님은 매우 불만을 갖을 것이다. 이 문제의 해답은 동전의 개수가 최소가 되게 찾는 것이다.
출처
무작위 대입 기법(Brute Force)
[편집]무작위 대입 기법이란? 무작위 대입 기법이란 주어진 문제의 해답을 찾기 위해 모든 가능한 경우를 전부 다 시도해보는 것을 말한다. 이론적으로 모든 가능한 수를 점검하기 때문에 실수가 없다.
무작위 대입 기법의 단점 자원이 가장 큰 문제이며, 무작위 대입 기법은 문제의 복잡도에 매우 민감하다. 문제 해답의 경우의 수가 기하급수적으로 증가할 경우, 문제를 해결하기 위해 필요한 자원 또한 기하급수적으로 증가한다. 그래서 복잡한 문제의 해답을 찾는데는 매우 비효율적이다.