Day.10 Binary Search(이진 탐색) - 백준 1920번(수 찾기)

오늘 들어야 할 알고리즘 강의 chapter가 이진탐색 (binary Search)였다.

 

이미 개념에 대해선 잘 알고있어서, 개념을 이해하는데 큰 어려움은 없었지만, 이 것을 구현하려고 하니 정말 시간이 많이 소모됐다. 기존에 진행하는 Python 알고리즘 강의의 방식대로 python으로 구현하는 것이 아니라 같은 내용을 java로 구현하려고 한다. (백준을 이용)

 

(구현 방식에 대해 생각하고, 직접 그 방식을 구현하려고 많은 시간을 썼지만, 이렇게 연습하다보면 구현 능률이 올라 갈 것이라 믿어 의심치 않는다...)

 

직접 구현을 하면서 강의를 따라가려고 하니 생각보다 강의 속도가 안나서 고민이다 어떻게 해야할지..

(팀원분이랑 이 부분에 대해서 이야기를 했는데, 그냥 잘 모르겠으면 해설보고 이해를 하는 편이 좋을지...)

그럼 본론으로 들어가보자

 

---

- Binary search (이진탐색)

 

우선 이진탐색의 정의를 짚고 넘어가자면 정렬된 배열에서 내가 원하는(특정한 값)을 찾아내는 방식의 알고리즘이다. 

배열 중간 값을 통해 내가 찾고자 하는 값과 비교하게 되고, 좌측 혹은 우측 배열에서 이와 같은 방식을 통해 내가 원하는 값을 찾는다. 

 

이진 탐색은 검색의 범위를 반으로 분할하고 검색하는 작업을 반복하기에 분할 정복 기법을 이용한 방법인데, 전제 조건이 정렬된 배열이어야 한다. 

 

그림으로 이해해보면 다음과 같다.

1

3

5

7

11

12

15

18

20

이러한 배열이 있다고 가정하고, 내가 찾을 숫자는 예를 들어 15라고하자.

 

우선 앞서 이진 탐색의 방식과 정의를 설명한 것처럼 배열의 중간값으로 접근 해야한다.

배열의 중간값은  11 

배열의 중간값과 내가 찾고자 하는 값을 비교한다   ==>

만약 중간값을 기준으로 찾고자 하는 값이 크면 우측 탐색, 작으면 좌측 탐색 (11<15)

11

12

15

18

20

동일한 방법으로 진행한다. -> 중간값을 찾는다 -> 15 

아쉽지만 이번 케이스는 내가 찾고자 하는 값과 같아서 종료..

 

이러한 방식으로 내가 찾고자 하는 값을 찾을 수 있고, 그 값이 없더라도 특정 이벤트를 만들어 낼 수 있다.

 

(내가 작성한 소스코드이다.)

https://github.com/jipang9/Java_Algorithm_Study/tree/master/src/Binary_Search

GitHub - jipang9/Java_Algorithm_Study

 

(확실히 Bufferedreader로 하는 것 보다 scanner로 하니까 성능이 안나오긴 함)

 

구현부

이 부분에서 애를 많이 먹었다.... 알고리즘을 공부를 많이 안해서 생각하는 능력이 후달리다는것을 오늘 한번 다시 느꼈다.

그래서 고민인게 새로운 알고리즘 자료구조 책을 사서 그 책을 완주할지. 아니면 지금처럼 챕터를 이용해서 백준을 풀어볼지..

(지금 백준 수준이 딱 실버 하위느낌인데...  그래도 실버 상위-골드까진 올라가야한다고 들었는데..)