3. 알고리즘 정리 [이분탐색]

이진탐색에 대한 공부를 시작한다.

이진탐색을 왜쓸까?

일단 이것부터 파악을 해야한다.

사실 순차 탐색 = 이진탐색 값을 구하는 건 동일하다.

결국 둘다 탐색을 해서 답을 도출해내는 건 동일하게 성공적으로 실행된다.

근데, 탐색해야되는 량이 엄청 많다면? 그때는 이진탐색을 실행한다.

 

우선 이진탐색에 대한 기초적인 구현을 시작한다.

아주 간단하게, 5개의 숫자를 입력받고, 그중에 target인 15를 찾는것이다.

mid를 시작과 끝점을 합한 /2 를 하고, 만약의 mid index가 타겟보다 크면, 최고를 mid -1 로 이동

반대라면 low를 mid +1로하게된다.

물론 이 것은 입력값이 순차적은 정렬 형태를 띈다는 가정이다.

 

이렇게 되면 순차 탐색 보다 훨씩 빠른 탐색을 할수있다.

탐색 대상이 많은 경우에 해당 알고리즘을 사용할수 있고, 이런 알고리즘 구현문제의 경우

순차 탐색으로 하면 실패되게끔 시간제한을 둔다.

 

자 그러면 백준 문제를 풀어보자

 

*수 찾기

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

 

이문제를 푸는 방법은 우선 배열 두개를 생각해야한다.

나는 target(있는지 체크하기 위한 배열) source (검사를 위한 배열)

이렇게 두개를 생각했다.

그리고, source의 원소 하나씩을 체크해서, target에 이분 검색을 하게 하였고

정답 배열에 담아서, 출력하였다.

int 배열은 초기화하여 크기를 정하면, 초기값이 자동으로 0이 된다는 것을 이용하여,

특정 맞을때만 1로 하고 break;를 했다.

 

 

정답 코드이다.

 

 

 

* 숫자카드 2

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

이문제는 어떻게 보면... 좀 이상하다..

출제가 잘못되었는지 자바 특성의 테스트케이스가 잘못된건지....

무튼 이문제는 이분탐색으로 풀면 타임아웃 실패 나고, 그냥 배열받아서, 하나씩 비교해가면서, 

해당 인덱스 ++ 해준다음에 print 해주는게 정답이다...이럴꺼면.. 이분탐색....이 아닌데...

 

근데 테스트케이스가 만약에, 엄청난 수의 배열일 경우, 시간이 늘어난다고 가정해서, 이분탐색이 정답이 될 것같다.

무튼

이분탐색의 소스는 아래와 같다.

우선 메인의 소스이다.

단순히 메인은, 숫자를 입력받아서, 각각 배열에 넣고,

첫번째 인덱스 마지막 인덱스를 각각 구해서 빼준다.

이때 조심해야할 것은, 1개가 존재하는 경우 뺀 값이 0이기 때문에,

value 에 대한 체크를 해서, +1 과 음수인 경우 그냥 0으로 리턴해준다.

 

 

첫번째, 마지막 인덱스 구하는 함수이다.

 

비슷해 보이지만, 차이가 있다면, start와 end를 이동시키는 조건이 = 의 유무이다.

이건 직접 그려보면서 하면 바로 이해가 될 것이다.

 

무튼 이렇게 하면 내 콘솔에서는 정답처리이다 ㅋㅋ..

 

* 랜선 자르기

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

정신 똑바로 안차려서 컴파일 에러에 오랫동안 헤맷던 문제이다.

역시 알고리즘은 빡집중할수있는 환경에서 해야하는듯 하다

꼼꼼하지않고 덤벙대면 자기가 놓친 부분이어디인지도 모르는 **같은 상황 ㅋ

 

이소스는 메인 함수이다.

 

 

 

쉽게 말해서 나는, 받은 랜선의 길이중 1~최대수 까지의 배열이 있고,

start 는 1 end 는 최대자리수 로해서, mid를 찾아가면서, ++ or -- 했다.

그리고, 해당 될때 max랑 비교해서 값을 넣었고,

최종 return int를 출력했다. 그리고 정답

 

정신좀 차리자 ㅋ