Binary Search) 알고리즘 — Bolio

마지막 업데이트: 2022년 4월 10일 | 0개 댓글
  • 네이버 블로그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 트위터 공유하기
  • 카카오스토리 공유하기
Binary Search 과정

이분탐색(Binary Search) 알고리즘

k. k 번 비교할 때의 범위 n/(2^k)는 = 1 이고, k = log ₂ N 이다. 따라서 이진 탐색의 시간 복잡도는 O(logN)이 된다.

0 1 2 3 4 5 6 7 8 9
2 5 6 9 12 13 14 18 20 23

위와 같이 정렬되어 있는 배열이 있을 때, 20을 찾는다고 가정해보자. 만약 순차탐색을 하면 0번째 인덱스, 1번째 인덱스, 2번째 인덱스 . 를 순서대로 찾아가면서 9번째 탐색에서 원하는 값을 찾을 수 있을 것이다.

0 1 2 3 4 5 6 7 8 9
2 5 6 9 12 13 14 18 20 23

이분탐색을 이용한다면 제일 왼쪽 인덱스 0과 제일 오른쪽 인덱스 9를 이용하여 가운데 인덱스((0+9)/2 = 4)와 값(12)를 구한다. 이때 구하려는 값 20보다 12가 작으므로 왼쪽 인덱스를 5로 변경해준다.

0 1 2 3 4 5 6 7 8 9
2 5 6 9 12 13 14 18 20 23

마찬가지로 왼쪽 인덱스와 오른쪽 인덱스를 이용하여 가운데 인덱스((5+9)/2 = 7)와 값(18)을 구한다. 이때 구하려는 값 20보다 작으므로 또다시 왼쪽 인덱스를 8으로 변경해준다.

0 1 2 3 4 5 6 7 8 9
2 5 6 9 12 13 14 18 20 23

왼쪽 인덱스와 오른쪽 인덱스를 이용하여 가운데 인덱스((8+9)/2 = 8)와 값(20)을 구한다. 원하는 값을 찾았으므로 탐색을 종료한다.

이분탐색(Binary Search)

정수 배열 int[] array = 에서 int key = 8 이 몇 번째에 위치해 있는지 찾는다고 가정하자.

Binary Search 과정

가장 먼저 할 일은 탐색 범위를 정하는 것이다. 이 경우에는 주어진 정수 배열 전체를 기준으로 하므로 인덱스 0 ~ 7이 범위가 된다.

탐색 범위가 정해지면 해당 범위의 가운데에 위치한 값을 찾는다. 가운데 값은 탐색 범위의 마지막 인데스에서 첫 인덱스를 뺀 뒤 2로 나눈 수를 인덱스로 가지는 값이다. 이 경우는 (7 - 0) / 2는 3이므로 array[3]의 10이 가운데 값이 된다.

key값과 가운데 값(10)을 비교한다.
1) 값이 서로 같다면 해당 인덱스를 반환
2) key 값이 가운데 값보다 작다면 가운데 값 이후(가운데 값 포함)를 탐색범위에서 제외시킨다.
3) key 값이 가운데 값보다 크다면 가운데 값 이전(가운데 값 포함)를 탐색범위에서 제외시킨다.

8은 10보다 작으므로 위의 2)에 해당한다. 따라서 탐색 범위를 0 ~ 2로 변경한다.

원하는 값을 찾을 때 까지 2번, 3번, 4번의 과정을 반복한다. 만약 탐색 범위 내 원소의 개수가 하나가 될 때 까지 key 값을 찾지 못했다면 주어진 원소 배열에 key 값이 존재하지 않다고 결론 내리고 탐색을 종료한다.

위의 3번과정을 진행하기 위해서는 key 값이 중간 값 보다 작은 경우 key 값이 배열안에 존재한다면 반드시 중간 값보다 앞에 위치함을 보장해야한다. 반대의 경우도 마찬가지이다. 따라서 array는 정렬되어 있어야만 한다. 위의 경우는 이미 정렬된 배열을 사용했지만 그렇지 않은 경우 탐색을 진행하기 전에 먼저 원소 배열을 정렬해야 한다.

인덱스 바이너리

이 BIT는
여러가지 최대 최소 문제에서 O(N) 시간복잡도를 O(lg N)으로 줄여 준 사랑스러운 자료구조입니다.

A Fenwick tree (also known as binary indexed tree) is a data structure that can be used to implement cumulative frequency tables. It was invented by Peter Fenwick in 1994.
(Wikipedia)
1994 년에 저 사람이 개발했다고 하네요.

흔히들 Index Tree로 쓰지만. 너무 길어서 하위 본문에서는 BIT를 쓰도록 하겠습니다.

Tip : 이 자료구조의 기초는 완전이진트리입니다만,
편리하게 사용하기 위해서는 포화이진트리로 바꾸어서 구축하는 편이 낫습니다.


기본 틀은 이렇습니다.
맨 루트 노드가 전체 범위를 담당하고 각 자식이 반씩 뜯어서 범위를 나눠가지고,
단말 노드가 되면 이제 각각의 값을 고유하게 가지는 간단한 개념입니다.

반대로 말하면, 부모 노드가 자식 둘의 범위를 합쳐서 (최대를 구한다면 둘 중 큰 것을) 저장합니다.
첫번째부터 네번째까지 중의 최대를 찾고 싶으면 굳이 1,2,3,4 다 안둘러봐도 1-4의 범위를 가지는 2번째 라인의 첫번째 노드의 값을 그대로 가져오기만 하면 됩니다. 저 1-4의 범위를 Binary Search) 알고리즘 — Bolio 가지는 노드는
'2'의 인덱스를 가지는데, 이 인덱스 부여 방법은 후에 설명하겠습니다.

또한 응용하여 만약 첫번째부터 여섯번째까지를 구한다면 1-4의 값과 5-6의 값을 비교하고
두번째부터 여덟번째까지의 최대를 구한다면 2-2, 3-4, 5-8 이중 제일 큰 값을 찾으면 되겠죠.

인덱스 부여는 다음과 같습니다. 그냥. 맨 위부터 그리고 맨 왼쪽부터 증가시켜주면 됩니다.
1,2,3,4,5,6,7,8,9. 이렇게요.
범위를 다 붙인 다음은 아래와 같습니다.


처음 보시는 분들은 잘 모르실지도 모르지만, 이진트리의 특성 중 하나인데,
왼쪽 자식의 노드는 부모의 인덱스 x2
오른쪽 자식의 노드는 부모의 인덱스 x2 +1
부모의 인덱스는 [자식의 인덱스 /2] (코딩할 때는 소수점 짤리니까 그냥 /2 하셔도 됩니다)

아까 특별히 말을 안했지만, 데이터 갯수에 따라서 트리의 사이즈가 바뀝니다.
N개일 때 일단 2의K로 표현되는 숫자 중 N보다 크거나 같은 녀석을 찾아줍니다.
그리고 사이즈를 각각 지정해 주는데,
그리고 그 구한 녀석을 M이라고 할 때, 단말 노드는 M개, 총 트리 사이즈는 M*2-1 입니다.

ex)
1 => 1
2 => 2
3~4 => 4
5~8 => 8
9~16 => 16

이 숫자가 N에 대한 M입니다. 그후 단말노드의 앞부터 차례대로 데이터를 넣어주면 세팅이 끝입니다.
i번째 데이터는 M+i-1 번방에 넣어주면 되는데, 예를 들면
데이터가 5개라면 M은 8이 될 테고, 단말 노드는 8개, 총 트리 사이즈는 15개가 되고,
i번 데이터를 넣을 때는 M+i-1 이니까 1번째 데이터는 8번 방. 이런 식으로

그리고 M-1부터 1로 줄여가면서 두 자식노드를 비교해서
더 크거나 작은 것을 넣는 방법으로 세팅이 끝납니다.

사실 영상으로 해보고 싶었는데 기술력이 없는 이유로 포기.

장황하네요. 역시 이건 말로 해야되는데, 글로 쓰면 어색합니다.
코드로 하는 게 더 편할지도 모르겠네요. 아. 범위 자르는 것도 설명 안했는디
설명이 어눌해서 그러니 코드 보고 이해하세요!


// Start
// 아아. 참고로 밑 소스는 최소값 찾는 소스입니다.
// 최대 찾고 싶으시면 INF 넣는 부분을 -INF로 해주시고 부등호들 반대로 해주시면 됩니다.

자바 [JAVA] - 이진 삽입 정렬 (Binary Insertion Sort)

이번 포스팅의 경우 삽입 정렬을 토대로 하기에 반드시 삽입 정렬을 먼저 보고 오시기를 바란다.

만약 필자의 정렬 알고리즘을 시리즈로 보았다면 왜 퀵 정렬 다음에 이진 삽입 정렬을 다루지? 싶을 수도 있다. 일단 왜 그런지부터 말하자면 원래 포스팅 순서대로라면 팀 정렬(Tim Sort)를 다루어야 한다.

그러나 팀 정렬의 경우 Merge Sort(합병 정렬), Insertion Sort(삽입 정렬)이 혼용 된 하이브리드 정렬 알고리즘이다.

여기서 좀 더 구체적 설명해보자면 Insertion Sort의 메커니즘은 같으나, 원소가 들어 갈 위치를 선형 탐색이 아닌 이분 탐색(이진 탐색)을 이용한 방법으로 Binary Search) 알고리즘 — Bolio 구현한다.

삽입 정렬의 메커니즘이 무엇이었는지 생각해보자.

정렬 해야 할 target 원소에 대해 target 원소의 인덱스를 기점으로 타겟이 이전 원소보다 크기 전 까지 반복하면서 반복을 멈춘 위치가 target 원소가 들어갈 위치가 되는 것이다.

문제는 선형 탐색이다보니 한 원소에 대해 비교 작업이 최대 N번이 일어난다.

그렇기 때문에 탐색 과정을 이분탐색을 통해 logN 의 탐색 시간 복잡도를 갖도록 하는 방식이 바로 이 번 정렬의 핵심이다.

(전체적인 시간 복잡도 자체는 O(N 2 )으로 같다. 이 부분은 뒤에서 설명하도록 하겠다.)

먼저 구현을 하기전에 차이점에 대해 잠깐 더 구체적으로 들여다 보자.

일단 기존의 삽입 정렬 과정은 아래 그림을 참고하면 되고, 코드를 중심으로 보자.

위에서 보면 비교 탐색과 동시에 원소를 뒤로 밀어내는 작업을 같이 while문을 통해 이루어지고 있다.

여기서 while 조건문을 보면 j >= 0 과, target < a[j] 이렇게 두 개의 조건이 매 번 반복되고, j >= 0 은 비교 가능한 최대 하한 인덱스인 0까지 탐색이 이루어질 수 있다는 의미이며, target < a[j] 는 배치해야 할 target 원소가 탐색하면서 이전 원소가 target보다 작을 때 까지 반복한다는 것이다.

그러면 이분 탐색을 활용한 정렬은 어떻게 될까? 일단, 이분 탐색을 구현했다고 가정하에 코드를 작성하자면 다음과 같다.

[이진 삽입 정렬 코드]

다만, 0 ~ i (현재 target의 위치) 사이 이분탐색을 통해 target 원소가 위치 할 곳을 찾아낸 뒤, target 원소가 해당 위치에 삽입되기 위해 원소들을 한 칸씩 뒤로 밀어주는 것으로 변경되었을 뿐이다.

그럼 일단 구현 메커니즘을 보자.

이진 삽입 정렬의 전체적인 과정은 이렇다. (Binary Search) 알고리즘 — Bolio 오름차순을 기준으로 설명)

1. 현재 타겟이 되는 숫자에 대해 이전 위치에 있는 원소들에 들어 갈 위치를 이분 탐색을 통해 얻어낸다. (첫 번째 타겟은 두 번째 원소부터 시작한다.)

2. 들어가야 할 위치를 비우기 위해 후방 원소들을 한칸 씩 밀고 비운 공간에 타겟을 삽입한다.

3. 그 다음 타겟을 찾아 위와 같은 방법으로 반복한다.

즉, 그림으로 보면 다음과 같은 과정을 거친다.

삽입 정렬과 마찬가지로 첫 번째 원소는 타겟이 되어도 비교 할 원소가 없기 때문에 Binary Search) 알고리즘 — Bolio 처음 원소부터 타겟이 될 필요가 없고 두 번째 원소부터 타겟이 되면 된다.

그러면 삽입정렬 과정은 알았으니 이를 적용 할 이분 탐색을 구현하는 부분이 관건이겠다.

일단 이분 탐색 과정을 이해해보자면, '정렬 된 상태의 구간' 내에서 중간에 위치한 원소와 비교하여 중간 원소보다 작다면 왼쪽 구간으로, 크다면 오른쪽 구간으로 다시 나누어 탐색하는 과정을 말한다.

쉽게 그림으로 이해하자면 다음과 같다.

위와 같은 메커니즘으로 구현을 하면 된다. 이분 탐색만 따로 떼어서 코드로 구현하자면 다음과 같다.

생각해보자. 우리가 이진탐색하는 범위는 이미 정렬되어있는 상태다. 그리고 우리는 범위에서 key값이 삽입 될 위치를 찾는 것이 관건이다.

이 때 이진 탐색의 범위가 정렬 되어있다는 것은 이미 왼쪽 원소부터 순차적으로 삽입 정렬이 이루어져있다는 의미다.

쉽게 말해 이진 탐색 범위 내에 어떤 원소 a가 key값이랑 동일한 값이더라도 a원소가 key보다 선행원소였기 때문에 안정정렬을 위해서는 key가 a원소 뒤에 위치해야 한다. 즉, key에 대한 중복원소가 존재 할 때, key가 '가장 오른쪽 위치'로 가도록 하기 위함이다.

이에 대한 참고 글은 아래에서도 잘 보여주고 있으니 한 번 확인해보는 것도 좋을 것 같다.

Binary search algorithm - Wikipedia

From Wikipedia, the free encyclopedia Jump to navigation Jump to search This article is about searching a finite sorted array. For searching continuous function values, see bisection method. Search algorithm finding the position of a target value within a

※그리고 중요한 점이 있다.

여기서는 이해를 돕기 위해 중간 값을 구할 때 mid = (lo + hi) / 2 로 표기하고 있지만, 사실 값의 범위가 클 경우에는 int overflow가 발생할 수 있다.

쉽게 가정해서 lo = 1, hi = 2147483647 (= Integer.MAX_VALUE) 이렇다면,

(lo + hi) 과정에서 overflow가 발생하여 -2147483648 가 되고, 여기에 2를 나누게 되어 -1073741824 라는 잘못된 값을 반환할 수 있다.

이러한 경우 어떻게 해결하냐면, 결국 lo와 hi의 중간 값이라는 것은 lo 로부터 hi까지의 거리를 2로 나눈 값을 더한 값이라는 것이다.

lo = 3, hi = 7 이라 할 때, 중간 값은 (3 + 7) / 2 = 5 일 것이다.

이렇게 위와 같이 표현 할 수 있지만, 사실 생각해보면, 3 ~ 7까지 거리라는 건 결국 3을 기준으로 7이 얼만큼 떨어져 있는가이다.

즉, 3으로부터 4만큼 떨어져있는 지점은 7이라는 것이고, 만약 두 지점의 중간 값이라면, 떨어진 거리의 절반이라는 것이다.

그러면 다음과 같이 표현 할 수 있다.

중간 지점 = 시작점 + (거리 차) / 2

이를 수식으로 표현하면 다음과 같다.

mid = lo + ((hi - lo) / 2)

즉, overflow를 고려했을 때 위와 같이 두 거리의 차에 대한 값을 토대로 중간 값을 구하는게 좋다.

설명은 이해를 돕기 위해 (lo + hi) / 2로 일단 진행을 하고, 코드 작성 부분에서만 lo + ((hi - lo) / 2) 로 작성하도록 하겠다.

이분 탐색을 구현하긴 했는데.. 선형 탐색과는 뭐가 다른거지?

바로 시간복잡도가 O(logN) 이라는 것이다.

N개의 요소를 갖고있는 리스트가 주어졌다고 해보자. 그리고 우리가 이분 탐색에서 N/2 씩 쪼개가면서 탐색을 한다.

즉, K번 반복한다고 할 때, (1/2)K * N 이 된다는 의미다.

이 때, 위 이미지에서 보면 결국 최악의 경우인 마지막 탐색 범위가 1인 경우가 있을 것이다. K번 반복 했을 때 쪼개진 크기가 1이라고 가정한다면, 결국 K만큼 반복한다고 했으니 K에 대해 풀어보면 다음과 같다.

즉, N개의 리스트에서 어떤 수를 찾는 과정에 대한 시간 복잡도는 O(logN)이라는 것이다.

분명 기존의 삽입정렬은 while()문으로 한 번 순회했고, 이진 삽입 정렬은 이분탐색 과정과 원소들을 밀기 위한 순회 과정을 거쳐야 하는데, 오히려 이진 삽입 정렬이 느린 것이 아닌가?

기본적으로 Insertion Sort나, Binary Insertion Sort나 N개의 각 원소들은 삽입시 N개의 원소를 밀어내는 시프트 작업이 발생하기 때문에 O(N 2 ) 의 시간 복잡도를 갖는 것은 같다.

그리고 위에서 말했던 것처럼 while문으로 한 번 순회하는 일반적인 Insertion Sort가 별도의 이진탐색 과정을 거친 뒤 얻은 위치에 원소를 삽입하기 위한 시프트 작업이 발생하는 Binary Insertion Sort보다 빠르게 보이기도 한다.

그러면 왜 이진 삽입 정렬이 필요한 것인가? 이를 이해하기 위해서는 이분 탐색부터 이해해야 한다.

이분 탐색 자체는 앞서 설명했듯, 탐색 비용이 O(logN)의 시간 복잡도를 갖는다. 그리고 우리는 이진 삽입 정렬에서 원소가 들어갈 위치를 찾는 비교작업으로 사용을 하고 있다.

즉, 일반적인 삽입 정렬과의 차이라면 삽입 정렬은 탐색과 시프팅 작업을 동시에 하지만, 이진 삽입 정렬은 탐색을 이분 탐색으로 따로 구한 뒤 시프팅 작업을 거친다.

그럼 이진 삽입 정렬이 빠른 경우는 어떤 경우일까?

바로 '비교 작업 비용'이 '시프팅(스왑) 비용'보다 클 때 이진 삽입 정렬이 좀 더 빠르다는 것이다.

무슨말인가 싶을 수도 있으니 좀 더 구체적으로 설명해보겠다.

위처럼 일반적인 삽입 정렬의 경우 각 반복문 단계마다 j >= 0 과 target < a[j] 조건을 검사를 하면서 순회를 한다.

즉, target 이 들어갈 위치를 찾아가면서(target < a[j]) 동시에 시프팅 작업을 한다.

반면에 위처럼 이진 삽입 정렬의 경우 비교 작업을 이분탐색을 통해 사용되며, 그 다음 while문에는 j ~ location 까지 시프팅 작업이 이루어진다.

여기서 가장 큰 차이는 바로 '비교작업'의 차이라는 것이다.

앞선 예시에서는 우리가 두 원소를 비교할 때, 모두 int 형으로 '단일 비교'를 전제로 했지만, 사실 해당 타입만 존재하는 건 아니다. 특히 사용자가 만든 클래스 객체에서 비교작업을 하는 경우 대개 단일 비교로 이루어지지 않고 다양한 변수들의 비교를 통해 Comparable 혹은 Comparator을 구현하여 정렬을 할 것이다.

위 처럼 일반적인 primitive 타입의 배열의 경우 단일 값에 대한 비교를 하기 떄문에 비교 비용이 크지 않지만, 만약 다음과 같은 상황이라면 어떻겠는가?

비교 작업마다 Custom 클래스의 a, b, s 를 모두 비교를 하여 어떤 원소가 더 우선순위가 높은지를 판단해야 한다. 즉, 일반적인 Binary Search) 알고리즘 — Bolio 단일 변수에 의한 비교보다 훨씬 비교작업 비용이 크다.

이렇게 여러 변수에 의해 우선순위가 결정되는 객체의 경우에는 결국 삽입정렬처럼 선형 탐색을 하게 된다면 시프팅작업과 탐색 작업이 한 반복문 내에 이루어진다 하더라도 N번의 비교 작업 자체가 비용(Cost)이 비싸진다.

그렇기 때문에 위와 같은 경우에는 별도의 이분탐색을 거치더라도 logN 시간 복잡도를 갖는, 즉 비교 비용을 줄일 수 있는 이분 탐색을 활용하는 것이 더욱 빠르다.

실제로 그럴까? 필자가 테스트 한 것을 보면 이렇다. (테스트는 Java를 통해 실험했고, 얻어온 결과를 파이썬의 plot으로 표현한 것 뿐이다.)

참고로 빨간색 이 일반적인 삽입 정렬(Insertion Sort) 이고, 파란색이진 삽입 정렬(Binary Insertion Sort)이다.

먼저 무작위로 생성 된 원소들을 갖는 int배열을 각각의 정렬 방식을 통해 얻어진 시간(밀리초) 그래프다.

보면 엄청 큰 차이는 아니더라도 분명하게 빨간색 선인 삽입정렬이 좀 더 빠른 걸 볼 수 있다.

그러면 객체를 정렬하는 경우는 어떨까?

위와 동일하게 Custom 클래스를 사용하여 Custom 배열 내의 Custom 원소들의 변수들도 랜덤으로 생성하여 각각 정렬을 했을 때의 어떻게 나타나지는지 보자.

보면 위 그래프와는 달리 이진 삽입 정렬이 더 빠른 것을 볼 수 있다.

위 결과처럼 비교 비용이 비싸질 수록 이진 삽입 정렬은 삽입 정렬에 비해 빠를 것이다.

정리하자면 이진 삽입 정렬이 항상 빠른 것은 아니지만, 비교비용이 스왑비용보다 비싸질 수록 상대적으로 효율이 좋아질 수 있으며 각 원소에서의 이분 탐색은 매우 작은 비용이더라도 작은 logN 비용은 분명 유의미한 차이를 낼 수 있다는 것이다.

그러면 굳이 왜 삽입 정렬을 안쓰고 이진 삽입 정렬을 쓰는가?

자바에서 기본적으로 정렬하는 클래스는 Arrays 클래스의 sort에 의해 이루어진다. (Collections.sort의 경우도 List를 배열로 변환하여 Arrays.sort로 내보낸다.)

그리고 크게 정렬 방식은 두 가지로 나누어지는데 하나는 dual-pivot Quick Sort이고, 다른 하나는 Tim Sort다.

그럼 어느 때 어떤 정렬을 쓰는가를 따져보아야 하는데, 기본적으로 primitive type 일차원 배열의 경우 dual-pivot Quick Sort에 의해 정렬이 된다. (참고로 2차원 배열(ex. int[][])같은 다차원 배열은 Object 타입으로 간다. 쉽게 생각해서 2차원 배열 int[][]의 경우 int[] 타입의 객체가 배열로 된 형태라고 이해하시면 된다.)

Tim Sort는 객체(Object)를 정렬하고자 할 때 쓰인다. 대개 여러 변수에 의해 비교 될 가능성이 높은 타입이 바로 객체이기 때문이지 않을까 싶다. 그리고 실제로 우리가 객체를 정렬하는 경우가 단순히 Wrapper클래스만 있는 것이 아닌 실제 현실 데이터를 반영한 class를 구현하여 이를 리스트로 만들어 다루는 경우가 많다.

그렇기 때문에 오히려 비교 횟수가 많을수록 오버헤드가 커지게 되므로 이럴 때엔 이진 삽입 정렬처럼 비교 횟수를 최소화하는 것이 더욱 효율적일 것이다.


0 개 댓글

답장을 남겨주세요