11. Binary Search & Parametric Search(1)

안녕하세요. 최근 포스팅을 한 기억이... 기록을 보니 포스팅을 안 한지 6일정도 되어가네요. 최근 네이버 커넥트재단에서 부스트코스 인공지능 기초 코칭스터디 1기를 모집해서 신청했는데 7일 스터디 부스터로 선발되었다는 메일이 날아오고나서 그것 준비하는 거랑 온라인 프로그래밍 과외 문의가 들어와서 시강 준비때문에 바빴다는 변명아닌 변명을 해봅니다.(제 고등학교 후배, 영재고 고2 학생, 국제학교 학생 이렇게 3명이나 시강을 요청하셔서 바빴습니다. 어떤 영재고에서는 pandas를 필수과목 중 하나로 가르친다고 하더라고요. 역시 영재고는 앞서나가는 곳이구나 생각하게 되었습니다.)

 

이쯤 제 근황을 전해드리고 온라인 프로그래밍 과외랑 네이버 커넥트재단의 부스트코스 인공지능 기초 코칭스터디 1기는 제가 다른 포스팅에서 더 자세히 소개해드리겠습니다. 오늘의 주제는 Binary Search, 이분탐색입니다. 사실 이분탐색은 분할정복을 다룬 포스팅에서 소개해드린 바 있습니다.

 

 

11.01. Divide and Conquer Review

2021.11.18 - [학부공부/Algorithm_알고리즘] - 07. Divide and Conquer(1)

07. Divide and Conquer(1)

2021.11.21 - [학부공부/Algorithm_알고리즘] - 08. Divide and Conquer(2)

08. Divide and Conquer(2)

 

 

11.02. Binary Search

Binary Search는 앞서 링크를 걸어둔 포스팅을 참고하셔도 되지만 간단하게 설명드리자면 배열을 반으로 분할하면서 원하는 값을 탐색해나가는 알고리즘입니다. 물론 배열이 정렬된 상태여야 합니다.

 

반복문으로 원하는 값이 있는지 찾을 때는 시간복잡도가 O(N)이지만 이분탐색은 한 번 탐색할 때 탐색범위를 반으로 줄이기 때문에 반복문보다 효율적입니다. 시간복잡도는 O(logN)입니다.

 

 

11.03. Parametric Search

Parametric Search 방법 중 하나로 Binary Search를 사용합니다. 물론 Ternary Search, 삼분 탐색도 있습니다. 삼분 탐색은 볼록함수에서 극값, 최소/최댓값을 찾을 때 사용하는 알고리즘인데 다음에 기회가 있다면 소개해드리겠습니다. 이분탐색은 바로 문제의 답을 구하는 것이 아니라 범위를 계속 좁혀나가며 답을 구하는 알고리즘입니다. 어릴 때 Up/Down 놀이를 해보셨다면 더 익숙하시겠군요. 어떤 문제를 만족 vs 불만족으로 판별할 수 있는 문제로 바꾸는 것이 핵심입니다.

 

매개변수 탐색 문제의 대부분은 어떤 값의 최대값이나 최소값을 찾는 문제인 경우가 많습니다. 이런 문제들은 아래의 순서대로 풀 수 있습니다.

• 문제를 만족 or 불만족으로 바꾸기
• 구하고자 하는 값의 범위가 주어질 때 하나의 값을 잡고 조건을 만족하는지 묻기
• 범위를 좁혀서 원하는 값을 얻을 때까지 반복하기

 

이때 범위를 좁히는 과정에서 이분탐색을 사용합니다. 범위가 주어질 때 평균값을 선택한다는 것이죠. 당연히 시간복잡도는 이분탐색과 같고 이때 하나의 값을 잡고 조건을 만족하는지 묻는 과정에서 시간복잡도가 최종적으로 결정됩니다.

 

LEFT = MIN VALUE, RIGHT = MAX VALUE;

WHILE(LEFT <= RIGHT){
	MID = (LEFT + RIGHT) / 2;
    
    CHECK;
    
    UPDATE : LEFT = MID + 1 OR RIGHT = MID - 1;
    
    STORE TEMP RESULT;
}

 

 

사실 문제는 비슷비슷합니다. 보통 Sequential test 알고리즘으로 해결할 수 없겠구나하는 느낌이 드실겁니다. 추가로 tip을 드리자면 MID value를 계산하는 과정에서 오버플로우가 발생하지 않도록 long long 자료형을 사용하시는 것을 추천드립니다. 문제를 풀 때 UPDATE를 어떻게 할건지 신경써주시면 되고 가장 중요한 것은 CHECK과정입니다. 이 CHECK과정에서 얼마만큼의 시간복잡도와 공간복잡도를 사용하느냐가 문제해결의 중요 포인트입니다. 추가적으로 삼분탐색에 대해서 잠깐만 언급하자면 이분탐색은 항상 방향이 증가 or 감소 뿐입니다. 즉, 함수에서 최소/최댓값을 찾는다면 항상 단조 감소/증가인 경우만 이분탐색이 유효하게 적용될 수 있다는 거죠. 삼분탐색은 좀 더 넓은 범위를 가능하게 해줍니다. 

 

추가로 검색을 용이하게 해드리기 위해서 Binary Search와 Parametric Search와 관련된 모든 글은Binary Search와  Parametric Search tag를 사용하였습니다. 도움되시길 바라겠습니다.

https://ku320121.tistory.com/tag/binary%20search

https://ku320121.tistory.com/tag/parametric%20search

SONGANG