(알고리즘 -4) 알고리즘의 설계

 

알고리즘을 설계할 때 당연히 최대한 효율적인 알고리즘을 구현하고 싶을 것입니다. 

어떠한 문제를 해결하기 위한 알고리즘은 여러개 존재하는데 그중에서 최대한 효율적인 알고리즘이란 값들의 비교 횟수가 적은 알고리즘입니다. 

 

예를 들어 최댓값을 구하는 알고리즘을 구현하고자 할 때 다음과 같은 방식을 써봅시다. 

 

 

위 예시같은경우 맨 처음에 25랑 15랑 비교를 해서 25라는 결괏값을 얻었습니다. 그다음 25랑 35랑 비교를 해서 35라는 결괏값을 얻었습니다. 이렇게 서로 다른 두 값을 비교해서 총 7번의 비교연산을 수행했습니다. 즉 8개의 숫자 중에서 7번의 연산을 수행했으니 n개의 숫자가 있었다면 n-1개의 연산을 수행하는 거라고 보면 되겠네요 최댓값 찾는 알고리즘이 n-1번의 연산을 수행하였다면 이건 효율적인 알고리즘입니다. 

 

 

토너먼트형식도 마찬가지로 n-1번의 비교연산을 수행합니다. 

 

이 경우도 똑같이 n - 1번 비교연산을 합니다. 

 

다음으로 주어진 데이터 중에서 원하는 값을 가진 데이터를 찾는 탐색 문제 알고리즘을 설계해봅시다. 

뒤섞여 있는 10개의 카드 중에서 원하는 숫자를 가진 카드를 찾는 문제를 생각해봅시다. 

대부분 사람들은 그냥 하나씩 뒤집어 가면서 원하는 카드를 찾을것입니다. 이런 경우 운이 좋으면 한 번에 찾을 수 있지만 운이 나쁘면 마지막까지 카드를 뒤집는 경우도 생깁니다. 

 

c언어로 표현해봅시다. 

 

순차 탐색 알고리즘 

반복문을 이용하여 하나씩 원하는 숫자를 찾는 코드입니다. 

9라는 숫자가 8번째 있으므로 출력결과도 8이 뜨는걸 확인할 수 있습니다. 

 

한편 임의의 숫자들이 오름차순으로 나열된후 뒤집어져 있는 경우에 숫자 9 카드를 찾는 문제를 생각해 봅시다. 

이 경우에도 물론 순차탐색 알고리즘을 적용할수 있습니다. 다만 이진 탐색을 사용하면 보다 효율적으로 찾을 수 있습니다. 

 

간단히 예를들어 1부터 100까지 숫자가 있다고 해봅시다. 오름차순으로 정렬될 경우 1 2 3 4... 98 99 100 이런 식으로 차례대로 있습니다. 여기서 흔히 많이 아는 업다운을 적용해 봅시다. 이게 이진트리 개념인데 76이라는 숫자를 찾을 때 순차 알고리즘을 적용하면 76번 연산을 해야 됩니다. 하나 이진트리를 적용하면 3번이면 되죠 

 

50 업하면 50~100이라는거고 

75 업 다운하면 75~100이라는거고 여기서 

다시 88 업 다운하면 다운이 되서 75부터 87 사이 일 테고 여기서 

80 업다운 하면 다운이 돼서 75부터 80이 됩니다. 여기서 다시 77 업다운하면 

다운이 되서 75 76일 테고 그냥 75 76 순차적으로 뒤집으면 76이 됩니다.