[알고리즘] 알고리즘 설계

[알고리즘] 알고리즘 설계

 

1. 알고리즘의 설계 방식

-알고리즘은 일련의 과정을 거쳐 생성된다.

-주어진 문제의 입출력 조건/처리 조건등을 고려해 문제 분석 -> 이를 바탕으로 알고리즘 설계 -> 적절한 방식으로 표현 및 기술

-알고리즘 분야에서는 문제를 푸는 방법과 절차 뿐만이 아니라, 그 방식의 정확성/효율성을 분석하는 과정도 함께 이루어진다.

 

 

2. 최솟값 찾기 알고리즘

-예를 들어, 아래의 두 방식 중에서 어떤 것이 더욱 효율적인 방식인지 찾아내야 한다고 치자. 아래의 사진은 여러 개의 숫자들 중에서 가장 작은 최솟값을 찾아내는 알고리즘이다. 아래의 두 가지 방법 외에도 여러 방법들이 존재한다.

-이렇게 동일한 문제에 대해서도 여러 알고리즘이 존재할 때에는, 적절한 알고리즘을 선택해야 한다. (효율성)

 

 

3. 탐색 문제

-아래와 같이 뒤섞인 카드 10장 중, 원하는 숫자를 가진 카드를 찾는다고 생각해보자. 

-순차 탐색(Sequential Search): 가장 간단한 방법은 카드를 하나씩 집어 펼쳐가며 찾는 것이다. 이 방법을 순차 탐색(Sequential Search)라고 한다.

-이진 탐색(Binary Search): 만약 10장의 카드가 숫자를 기준으로 오름차순 정렬이 되어있다고 생각해보자. 입력 데이터가 정렬되어 있다면 순차 탐색보다는 이진 탐색이 더 효율적일 수 있다. 

=> 사용하려는 데이터의 정렬 여부에 따라서도 사용할 알고리즘이 달라질 수 있다.

 

*이진 탐색 방법

(1) 주어진 배열에서 중앙 위치 계산

(2) 중앙 위치의 값과 탐색 키를 비교해, 원하는 값이라면 탐색을 종료

(3) 원하는 값과 일치하지 않는다면 탐색 키와 중앙 값의 크기를 비교해, 이진 탐색을 순환 호출한다.

(4) 탐색 키가 중앙의 값보다 작다면, 탐색 키는 정렬된 입력 배열의 왼쪽 절반 부분에 존재할 수 있기 때문에 배열의 왼쪽 절반을 다시 입력 배열로 사용한다. 만약 탐색 키가 중앙의 값보다 크다면 그 반대로 수행한다. (오른쪽을 입력 배열로 사용)