알고리즘(Algorithm) 요약
1. 알고리즘 소개
1.1. 기본개념
- 알고리즘: 주어진 문제를 해결하기 위한 일련의 단계적 처리 과정
- 최소값 찾기 알고리즘
A[] = {80, 70, 40, 20, 30, 10, 60, 50} 1. 배열의 첫번째 데이터를 최솟값으로 지정 2. 배열에서 다음 데이터를 읽고 최솟값과 비교 3. 작은 값을 최솟값으로 지정 4. 배열에 비교할 값이 존재하면 **2**로 이동하고 없으면 최솟값을 출력- 오일러 경로 문제
- 그래프의 모든 간선을 오직 한번씩만 지나가는 경로를 찾는 문제 - 주어진 그래프에 대해 임의의 한 점에서 출발하여 모든 선분을 한번씩만 지나는 경로의 존재 여부를 확인(단, 각 점은 여러번 방문 가능) - 각 정점의 차수가 홀수인 정점이 없거나, 2개이면 오일러 경로가 존재 - 만약 차수가 홀수인 정점이 2개인 경우, 출발점과 도착잠이 같은 오일러 경로가 되며 이를 오일러 회로라고 함.- 서울에서 부산까지 가장 짧은 거리를 갖는 경로 찾기
- 데이크스트라 알고리즘 활용 - 임의의 두 도시간의 최단 경로를 찾는 문제는 플로이드 알고리즘 적용 - 프로그램: 문제풀이 과정인 알고리즘을 적절한 프로그래밍 언어로 표현해서 컴퓨터가 이해하고 실행할 수 있도록 만든 명령어의 모임
- 알고리즘의 성립 요건
- (조건1) 입출력: 외부에서 0개 이상의 입력을 받아서 하나 이상의 출력을 생성
- (조건2) 명확성: 각 단계는 모호하지 않고 단순하고 명확
- (조건3) 유한성: 한정된 수의 단계를 거친 후에는 반드시 종료
- (조건4) 유효성: 모든 명령은 컴퓨터에서 수행이 가능
1.2. 알고리즘 설계
- 정렬되지 않는 10장의 카드에서 특정 카드 찾기 - 순차탐색
SequentialSearch (A[], n, key) # A[0..n-1] 입력배열, n 배열크기, key 찾으려는 값
출력: key가 배열내에 존재하면 해당 인덱스, 아니면 n 반환
{
i = 0;
while(i<n && A[i]!=key)
i = i + 1;
return (i);
}
- 정렬된 10장의 카드에서 특정 카드 찾기 - 이진탐색
BinarySearch (A[], key, Left, Right) # A[Left..Right] 입력배열, key 탐색 키
출력: key가 A[]내에 존재하면 해당 인덱스, 아니면 -1 반환
{
if(Left > Right) {
return (-1);
}
Mid = [(Left + Right) / 2]; //[x]는 소수점 버림(floor 연산)
if(A[Mid] == key) {
return (Mid);
}
else if (key < A[Mid]) {
BinarySearch(A, key, Left, Mid-1);
}
else {
BinarySearch(A, key, Mid+1, Right);
}
}
1.2.1. 욕심쟁이 방법
- 정의: 각 선택 단계마다 정해진 기준에 따라 가장 최선이라고 여겨지는 국부적인 최적해를 선택하다보면, 결국 전체적인 최적해를 구할 수 있을 것이라는 낙관적 전략
- 사례: 크루스칼 알고리즘, 프림 알고리즘, 데이크스트라 알고리즘
- 거스름돈 문제
- 문제1 거스름 돈이 780원 일때, 동전의 최소 개수(500·100·50·10원권 사용가능)
- 7개 = 5001, 1002, 501, 103
- 문제2 거스름 돈이 650원 일때, 동전의 최소 개수(500·120·100·50·10원권 사용가능)
- 5개 = 5001, 1201, 10*3
- 3개 = 5001, 1001, 50*1
- 문제1 거스름 돈이 780원 일때, 동전의 최소 개수(500·100·50·10원권 사용가능)
- 배낭 문제1
- 문제1 배낭용량 M=10, 물체개수 n=4, 물건이 분할 가능 가정, 용량 내 최대 이익
구분 이익 무게 무게1당 이익 물건1 18 3 6 물건2 15 5 3 물건3 12 3 4 물건4 25 4 6.25 해답 55 = (25×1)+(18×1)+(12×1)
- 문제2 배낭용량 M=10, 물체개수 n=4 물건이 분할 가능 가정 용량 내 최대 이익
구분 이익 무게 무게1당 이익 물건1 15 3 5 물건2 20 5 4 물건3 9 3 3 물건4 14 4 3.5 해답 42 = (15×1)+(20×1)+(14/2)
- 문제1 배낭용량 M=10, 물체개수 n=4, 물건이 분할 가능 가정, 용량 내 최대 이익
1.2.2. 분할정복 방법
- 정의: 주어진 문제의 입력을 더이상 나눌 수 없을 때까지 2개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할한 문제들을 각각 해결한 후, 해를 결합하는 하향식 접근 방법
- 분할: 주어진 문제의 입력을 작은 문제로 분할
- 정복: 작은 문제들을 순환적으로 분할하되 분할 불가시 해를 계산
- 합병: 작은 문제의 해를 결합하여 원래 문제의 해를 계산
- 순환알고리즘을 통한 문제해결
배열 A[] = {10, 15, 20, 25, 30, 35, 40, 45, 50} 에서 탐색키 key=20의 이진탐색
- A[], key=20, Left=0, Right=8을 사용하여 중앙위치(Mid)를 계산 및 Mid값(30)과 key(20)을 비교 수행 → 값이 같지 않고 작으므로 Mid의 좌측에 해당하는 부분배열을 대상으로 이진탐색 순환 호출
- A[] = {10, 15, 20, 25}, key=20, Left=0, Right=3을 사용하여 이진 탐색 다시 호출 → Mid(15)와 key(20) 비교한 결과 값이 같지 않고 크므로 Mid의 우측에 해당하는 부분배열을 대상으로 이진탐색 순환 호출
- A[] = {20, 25}, key=20, Left=2, Right=3을 사용하여 이진 탐색 다시 호출 → Mid(20)와 key(20) 비교한 결과 값이 같으므로 Mid=2를 반환하고 탐색 종료
- 순환알고리즘을 분할 정복 방법 3단계에 적용
- 분할: 배열의 가운데 원소를 기준으로 좌우로 분할하고, 탐색키가 가운데 원소와 같으면 가운데 원소에 해당하는 배열의 인덱스 반환 후 종료
- 정복: 탐색키가 가운데 원소보다 작으면 좌측 부분배열을, 크면 우측 부분배열을 대상으로 이진탐색 순환호출. 이진탐색 수행시 절반의 부분배열이 처리 대상에서 제외
- 결합: 부분배열에 대한 탐색곃과 바로 호출되므로 결합 불필요
1.2.3. 동적 프로그래밍 방법
- 정의: 입력의 크기가 가장 작은 부분 문제부터 해를 구해 저장해 놓고, 이를 이용하여 입력 크기가 보다 큰 문제의 해를 점진적으로 만들어 가는 상향식 접근 방법
- 이용: 최솟값 및 최댓값을 구하는 최적화 문제에 사용
1.3. 알고리즘 분석
1.3.1. 정확성 분석
- 정의: 유효환 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성할 수 있는지 평가
1.3.2. 효율성 분석
- 정의: 알고리즘을 수행하는데 얼마나 많은 자원(공간복잡도=메모리의 양, 시간복잡도=수행시간)이 필요한지 평가
- 공간복잡도: 컴파일 과정에서 고정적으로 결정되는 정적 공간과 동적할당이나 함수 호출 등을 통해 동적으로 결정되는 공간
- 시간복잡도: 알고리즘의 기본연산의 수행 횟수를 세는 방법으로 측정
####### 알고리즘 수행시간: 3n+5 SumAverage(A[], n) Input: A[0..n-1], n // 입력배열과 데이터 개수 Output: 데이터의 합과 평균 { sum = 0; //1회 수행 i = 0; //1회 수행 while(i<n) { //n+1회 수행 sum = sum + A[i]; //n회 수행 i = i+1; //n회 수행 } average = sum / n; //1회 수행 print sum, average; //1회 수행 }####### 알고리즘 수행시간: 2n^2+2n+3 DoubleIteration(n) Input: n 반복횟수 Output: 이중루프의 총 반복횟수 { count = 0; //1회 수행 for(i=0; i<n; i++) //n+1회 수행 for(j=0; j<n; j++) //n(n+1)회 수행 count ++; //n^2회 수행 print count; //1회 수행 }