알고리즘 소개

알고리즘은 주어진 문제를 해결하기 위한 단계적 절차 또는 방법이다.

 

알고리즘은 명확하게 기술되어야 하고 유한한 시간 내에 모든 유효한 입력에 대해 올바른 해를 주어야 한다.

 

주어진 문제를 해결하는 여러 개의 알고리즘들 중 시간적으로 효율적인 알고리즘을 선택해야 한다.

 

문제를 알고리즘으로 해결하는 단계별 과정들은 다음과 같다.

1. 문제 이해: 주어진 문제를 완전히 이해해야 한다.

2. 알고리즘 설계: 주요 알고리즘 설계 기법을 참고하여 알고리즘을 설계햐야 한다.

3. 정확성 증명: 알고리즘이 정확하다는 것을 증명해야 한다.

4. 알고리즘 분석: 알고리즘의 시간(혹은 공간) 효율성을 분석해야 한다.

5. 알고리즘 구현: 알고리즘은 컴퓨터 프로그램으로 구현해야 한다.

 

알고리즘은 자연어나 의사 코드로 표현한다. 알고리즘은 특정 프로그래밍 언어로 구현한다.

 

문제를 해결하는 주요 알고리즘 설계 기법들은 분할 정복, 동적 계획, 탐욕 기법, 되추적, 분기한정과 근사 알고리즘이 있다.

 

알고리즘을 문제 유형에 따라 정렬, 탐색, 문자열 처리, 그래프, 조합, 기하하적이나 수치 알고리즘으로 분류할 수 있다.

 

수학적 귀납법에 의한 이진 탐색 알고리즘의 정확성 증명

가정:N(>=1)-탐색 벙위에 있는 정렬된 정수들의 수 

      x - 찾는 정수

 

1. 기본 단계

N=1일 때 x를 목록에 있는 하나뿐인 정수와 한 번만 비교하면 x가 목록에 있는지 여부를 알 수 있으므로 이진 탐색은 맞다.

 

2. 귀납적 가설

N <= k(양의 정수)일 때 이진 탐색은 x가 목록에 있는지 여부를 알려 준다고 가정하자.

 

3. 귀납적 단계

N=k+1일 때 이진 탐색은 x가 목록에 있는지 여부를 알려 준다는 것을 증명하자. 이진 탐색은 먼저 x를 N개의 정수들의 중간 요소와 비교한다. 비교 결과는 다음과 같이 세 가지 경우가 있다.

 

경우 1 x가 중간 요소와 같다. 이 경우는 x를 찾았으므로 이진 탐색은 맞다.

 

경우 2 x가 중간 요소보다 작다. 이 경우는 x를 목록의 왼쪽 반에서 찾아야 한다. 목록의 왼쪽 반의 크기 N'는 N/2 보다 크거나 같다. N' <= k 이므로 귀납적 가설에 의해 이진 탐색은 x가 목록에 있는지 여부를 알려 준다. 따라서 이진 탐색은 맞다.

 

경우 3 x가 중간 요소보다 크다. 이 경우는 경우 2와 비슷한 논리로 맞다. 

 

따라서 이진 탐색은 N=k+1일 때 맞다.

 

출처: 이충기 , 자바로 쉽게 배우는 알고리즘, 배움터