1. Binary Search

저는 원래 알고리즘을 탐색부터 시작했었는데...

이제와서 생각해보면 사실 그건 조금 안좋은 순서라고 생각이 됩니다.

되도록이면 알고리즘 강의를 들으면서 그 커리큘럼에 맞춰 시작하시는게 좋지 않나 싶습니다.

물론 현재도 완벽하게 탐색쪽을 잘 푼다 이런건아니지만, 그런 이유를 떠나서 기본기가 가장 중요한 것 같아요.

개인 적으론 DP, 수학 쪽을 주로 공부하면서 생각하는 폭을 넓히고

탐색이나 그래프 파트에선 BFS, DFS 등을 접해보시는게 좋을거 같습니다.

그래서 수학이나 DP 부분을 먼저 건드려 보고싶습니다만

제가 잘 알지 못하고 또 이해 못한 부분도 많아 이는 나중에 정리하고

탐색과 그래프에서 그래도 꽤나 많이 쓰이는 알고리즘부터 정리를 해볼까 합니다.

---

Binary Search

---

이분 탐색, 이진 탐색

두 부분으로 나누어 탐색한다는 의미로 정렬된 데이터에서 특정한 값을 매우 빠른 속도로 찾기위해 사용하는 알고리즘.

---

기본 문제 자체는 정말 가볍게 개념만 간단히 알고가도 될 정도로 눈에 확 띄고 적용하기 쉽지만

저 같은 경우엔 난이도가 조금만 높아져도 '이 문제가 이분탐색인가?' 싶을정도로 어렵게 느껴집니다...

난이도가 꽤 있는 문제 같은 경우엔 저도 뭐.. 증명도 잘 못하고 접근도 잘못하는 경우가 많아서 기본 내용만 정리하고 넘어갈게요.

이분 탐색에서 가장 중요한 말은 '두 부분으로 나눈다', 그리고 '정렬된 데이터'라고 생각합니다.

즉 ,어떤 수를 공간적으로 2분할 하여 나누어 찾아 나가는데, 이때 공간적으로 나뉘는 이 데이터들은 정렬이 되어있어야합니다.

앞으로 말씀드릴 설명에서 다 나올 내용인데

'데이터가 정렬하는데 시간이 많이 걸린다거나, 정렬이 불가능한 데이터'라면 기본적으로 사용이 불가능하다 볼 수 있습니다.

물론 대부분의 문제가 데이터 정렬을 안해도 되는데 그것을 못알아채도록? 문제가 출제 됩니다.

아래 예시에서 어떤 방법으로 위에 색칠한 내용이 적용되는지 알아볼게요.

(아래에 같은색으로 색칠된 내용과 연관해서 읽으시면 됩니다.)

예시)

20세 이상의 성인분들은 술 게임 하면서 많이 해보셨을텐데, 술 병뚜껑의 숫자 맞추기 게임입니다.

어떤 술의 뚜껑엔 항상 숫자가 1 ~ 50 사이의 숫자가 적혀있다고 합니다. (사실 진위 여부는 모르겠습니다.)

그래서 술 게임 할 때 종종 이용하는데요.

우리가 이 게임을 할때 게임 주최자를 제외하고 숫자를 하나씩 어떤식으로 불렀나요?

아마 아래와 같이 게임을 진행해 나가셨을거라 생각합니다.

1. 1 ~ 50 사이에 존재하는 것이 분명하고
2. 1 ~ 50 사이라는 것은 이미 정렬되어있다고 볼 수 있겠죠.
3. 그리고 절반씩 줄여나가며 찾습니다.
4. 이때 답을 찾으면 게임이 종료되고 부른 숫자보다 답이 크다면 'up', 작다면 'down'을 외칩니다.

예를 들어 병뚜껑의 답이 '28'이었다면,

1번째 사람은 1과 50의 중간 값 25를 부르고 -> up

2번째 사람은 25와 50의 중간 값 37(또는 38)을 부르고 -> down

3번째 사람은 37과 25의 중간 값 31을 부르고 -> down

4번째 사람이 25와 31의 중간 값 28을 불러 게임이 종료됩니다.

1 ~ 50까지 숫자를 단 4회만에 찾아내었죠.

'단순 우연이 아닌가?'라고 생각 하실 수 도 있지만, 이 게임의 아이디어가 바로 이분 탐색의 기본 원리입니다.

그리고 색칠한 부분 이해 하셨나요? 

저런식으로 이미 탐색해야하는 부분이 x ~ (x + n)으로 주어졌다면 이미 정렬된 데이터에서 탐색한다고 생각하시면 됩니다. ㅎㅎ

이제부터 어떻게 이 알고리즘이 동작하는지 알아보죠.

간단히 숫자가 아래와 같이 8개 정도 있다고 가정해보겠습니다.

---

---

이 수는 우선 눈으로 보기에도 오름차순으로 잘 정렬 되어있습니다.

여기에 각 숫자마다 번호를 붙여줄게요. 배열처럼 말이죠.

그래서 배열 'int[] arr = new int[8]'로 잡고 0번의 값은 12 7번의 값은 1101으로 결정합니다.

값 자체로 비교해서 중간 값을 찾으려 하는 것도 나쁘지 않은 방법입니다.

다만, 이렇게 무작위로 떨어져있는 값들 사이에서 원하는 어떤 숫자를 찾는다는것은

12 에서 1101의 중간값을 찾고 우리가 찾으려는 숫자보다 큰지 작은지, 그리고 이 값들 내에 존재하는 값인지 이러한 불필요한 소모가 발생하기 때문에, 배열을 사용한다고 생각하시면 될 것 같습니다.

우선 우리가 122(target)라는 값을 찾으려 한다 가정합시다.

아래에서 설명드리는 start, end, mid는 모두 배열의 index를 의미하며 target은 찾으려는 값 자체를 의미합니다.

가장 작은 수 0번(12)와 7번(1101)을 시작과 끝 값으로 정의합니다.

---

---

여기서 부턴 위에서 말씀드린 술 게임과 같은 방식입니다.

0과 N - 1의 중간 값: (0 + (N - 1)) / 2: 중간 값 (이라는 의미로 mid로 잡고)

mid의 값이 122와 같은지 확인합니다.

mid = (0 + (N - 1)) / 2 = 3: 즉, 3번의 값은 77 이고 77 < 122 입니다. 

따라서 arr[mid] < target 입니다.

---

---

up의 경우니까 시작 점에 mid값을 저장하고, 다시 mid와 끝의 중간 값을 찾아야겠죠.

즉, mid가 start로 바뀌는 경우입니다. 그런데 이미 mid의 값은 확인을 했고 아니란 것을 알았어요.

그렇기 때문에 start = mid + 1;을 저장합니다.

그리고 다시 mid를 start와 end 중간 값으로 설정 후 mid = (4 + 7) / 2 = 5;

값을 비교해 봅시다.

---

---

mid == 122로 우리가 찾으려던 값을 찾았네요.

이렇게 비교 2회 만에 빠르게 원하는 값을 찾을 수 있었습니다.

(단, down이 발생하는 경우는 arr[mid] > target인 경우니까 end = mid - 1;로 설정해주시면됩니다.)

이를 코드로 옮겨 볼게요.

BinarySearch.java

public class Main {
    public static void main(String[] args) {
        int[] nums = {12, 26, 31, 77, 85, 122, 430, 1101};
        int targetValue = 122;
        
        int target = binarySearch(nums, targetValue);
        System.out.println(target);            // 찾으려던 값의 index 출력
    }
    
    private static int binarySearch(int[] arr, int target) {
        int start = 0, end = arr.length - 1;
        
        while(start <= end) {
            int mid = (start + end) / 2;
            
            if(arr[mid] > target) end = mid - 1;            // down
            else if(arr[mid] < target) start = mid + 1;        // up
            else return mid;                                // correct
        }
        
        return -1;            // 찾지 못한 경우
    }
}

BinarySearch.java 결과

아까 우리가 찾던 방식이랑 똑같이 돌면서 결국 답을 찾아냈습니다.

그리고, 위 코드에서 배열에 없는 값을 입력한다면, 결과는 -1이 출력 될 겁니다.

이것도 한번 해볼게요.

BinarySearch.java 결과 (값이 존재하지 않는 경우)

의도한 대로 결과가 잘 출력되는 것 같아요.

이분 탐색은 정말 여러 방면으로 많이 쓰이겠지만, 쓸 수 있는 조건 꼭 확인하시고 접근 하시길 바랍니다.

이분 탐색은 단조증가 또는 단조감소 함수일 때 쓸 수 있다고 정의됩니다.

'f(x) = x' 이러한 경우가 가장 대표적입니다.

• 반드시 정렬되어 있어야 하고
• 어떤 값 x가 증가 또는 감소함에 따라 이에 영향받는 함수 값 f(x) 또한 증가하거나 감소하는 경우라 생각하시면 됩니다.

(함수의 값이 증가/감소의 여부가 변하는 진동하는 값이면 대부분 적용 불가능하다 생각하시면 됩니다.)

이분 탐색의 시간 복잡도는 O(logN) 입니다.

계속 절반으로 나누면서 N의 크기가 2로 나누어지면서 결국 1이 되었을때 끝나니까요.

이해가 안되신다면 직접 어떤 수를 2로 계속 나눠 보시면 알게됩니다.

ex)

N = 1567의 경우

1번 행은 2를 나눈횟수, 2번 행은 그때의 값입니다.

1	2	3	4	5	6	7	8	9	10
783	391	195	97	48	24	12	6	3	1

10번만에 1이 나왔죠? 즉, 최악의 경우라도 '10 ~ 11'회 정도면 원하는 값을 찾을 수 있다는 뜻입니다.

그리고 2^10(1024) < 1567 < 2^11(2048)이니까 위에서 말씀드린 시간 복잡도를 만족하네요.

이렇게 탐색해야하는 N이 매우 크더라도(10억 정도..) 그 값들이 정렬된 상태라면, 꽤나 유용하게 쓰일 수 있습니다.

10억이라해도 log(1_000_000_000)이면 결국 3 * log(2^10) = 약 O(30) 정도 되니까요.

(당연히 아시겠지만 로그는 밑이 2입니다.)

최근 문제를 풀면 풀수록 부분부분에 정말 많이 활용되고 있는 알고리즘이라고 느낍니다.

잘못된 정보나 빠진 정보, 또는 의문점이 있으시다면 댓글 부탁드려요.

보완하도록 하겠습니다.