안녕하세요 CODER_JH입니다.
제가 가장 좋아하는 알고리즘 파트네요 ㅎㅎ
알고리즘이 뭘까요?? 위키백과의 말을 빌리도록 하겠습니다.
알고리즘 : 어떠한 문제를 해결하기 위한 여러 동작들의 모임이다. 유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있다.
이렇다고 하네요..
그렇다면 본격적으로 잘 알려진 알고리즘을 하나씩 알아보도록 하겠습니다.
먼저 가장 기본적인 탐색 알고리즘의 순차탐색과 이진탐색에 대해 알아보겠습니다.
<순차탐색>
순차탐색이란 말그대로 앞에서 부터 순차적으로 하나하나 탐색해 나가는 것입니다.
찾고자 하는 값이 앞쪽에 있다면 짧은 시간에 찾아낼 수 있지만 뒤쪽에 있다면 오래 걸리겠죠?(비효율적이란 얘기입니다.)
그림으로 알아 보도록 하겠습니다.
참쉽죠? ㅎ
코드로 작성해 보겠습니다.
-> 매우 간단하내요 arr[0] ~ arr[9] 까지 for문을 돌려 만약 찾고자하는 값가 같으면 탐색을 멈추는 소스 입니다.
-> 순차탐색의 시간복잡도는 탐색리스트가 n개라면 O(n)이 되겠내요.
다음은 이진탐색에 대해 알아보도록 하겠습니다.
<이진탐색>
이진탐색이란 이름에서 뭔가 느껴지지 않나요? 탐색할 때 마다 탐색 범위가 반으로 줄어들기 때문입니다.
이진탐색을 하기위해선 탐색 리스트가 정렬되어 있다는 전제가 있어야 합니다.
10억개의 데이터 리스트를 순차탐색으로 탐색할 때 평군 5억번의 비교를 해야됩니다. 그러나 이진탐색으로 탐색할 경우 최대 33번의 비교로 값을 찾아낼수있습니다. 이 수치만 보더라도 이진탐색이 매우 효율적이라는 것을 알수있습니다.
그림으로 알아 보도록 하겠습니다.
-> 정렬된 데이터셋에서 중간값을 구합니다. 후에 찾고자 하는 값과 비교합니다. 찾고자 하는 값이 더 크므로 5보다 작은 값은 버리고 6~10을 보게됩니다.
->6~10사이의 중간값인 8과 찾고자 하는 값을 비교합니다. 찾고자하는 값보다 크므로 8이하는 버리고 9~10을 보게됩니다.
->이렇게 9와10이남아버리면 값을찾게 됩니다.
->3번의 탐색만에 값을 찾게됬내요~
코드로 작성해 보겠습니다.
->소스도 그렇게 어려운 부분은 없는 것같내요 ㅎㅎ
->이해안가는 부분있으면 댓글 달아주세요~
탐색의 2가지 알고리즘에 대해 알아봤습니다. 기본적인 것이므로 충분히 이해하고 가시기 바랍니다.
다음 시간에는 정렬 알고리즘에 대해 하니씩 파헤쳐 보도록 하겠습니다.