[백준] [이분탐색] 기타 레슨 : 2343 Python

아직 각 알고리즘에 대한 이해 및 활용능력이 부족한 것 같아서, 기출에 나온 구현 문제보다는 알고리즘 연습을 할 것 같다.

첫 번째 알고리즘은 바로 이분 탐색이다. 이분 탐색은 학교 예제에서도 다뤄본 적 있는 알고리즘이라 비교적 쉽다고 생각했었는데 최근 프로그래머스 중 이분 탐색 문제(입국심사)를 풀어보고 정말 쉬운 게 없구나 느끼게 됐다.

사실 모든 알고리즘 문제들이 그렇겠지만, 이 문제를 어떤 알고리즘으로 풀지?라는 생각만 잡히게 된다면 어느 정도 쉽게 풀 수 있다. 특히 나는 알고리즘을 연습할 목적으로 백준의 이분 탐색 문제집을 풀었기 때문에 어떤 알고리즘으로 풀지라는 고민의 시간 없이 문제를 풀었기 때문에 그나마 쉽게 풀 수 있었다. 

문제에 대해 설명하자면, 총 N개의 강의를 녹화할 때, M장의 CD를 사용한다고 한다. 이때 CD를 M자 사용하려고 할 때, 필요한 CD의 최소용량을 구하는 것이다.

아직 이분 탐색 문제를 많이 풀어보지 못해서인지, 아니면 이분 탐색문제들이 다 비슷한 것일지는 모르겠지만, 프로그래머스의 입국심사와 문제가 거의 비슷한것 같다.

일단, 나는 이분탐색 풀 때, 인덱스(문제가 찾고자 하는 값)와 그 범위(최소, 최대)를 찾는 것이 가장 중요하고, 이것만 찾으면 쉽게 풀지 않을까? 생각하고 있다.

이 문제에서도 문제가 묻는 것은 CD의 용량의 최솟값이다. CD의 용량은 연속인 자연수이고, 가능한 범위는 1부터 무한대까지이다. 이 수들 중 중간값 검증을 통해서 모든 강의를 다담을 수 있는 수를 찾는 것이 이 문제의 목표이다.

이미 CD가 가능한 용량의 범위는 찾아버렸고, 그다음은 이 용량(middle) 값으로 모든 강의를 담을 수 있는지 검증하는 과정만 구현한 후 이진 탐색 코드를 짠다면 문제가 완성일 것이다.

나는 중간값 검증하는 과정을 함수로 구현하였다. 중간값으로 문제에서 요구한 조건대로 CD를 담을 때 CD의 개수가 M보다 크다면 용량을 늘려야 할 것이고, 작거나 같다면 용량을 줄여봐야 할 것이다(최솟값 검증을 위함)

이를 코드로 구현한다면,

이렇게 된다. 함수로 중간값을 검증하는 코드를 완성한다면 그다음은 중간값 검증 결과를 토대로, 이진 탐색을 구현하는 것이다.

사실 이 부분은 사람들마다 코드가 조금씩 다른 것을 확인할 수 있다. 크거나 같다로 짤 것인지, 또는 right나, left를 조정할 때 -1을 할지 안 할지에 차이가 있었다.

왜 다른지에 대해 이해하고 싶었지만, 나에게는 너무 어려웠기에 나는 교수님이 알려주신 코드로 이분 탐색을 계속 구현할 것 같다. (다행히 아직 이렇게 구현해서 막힌 적은 없다.)

위에는 이분 탐색 코드이다. 정말 이분 탐색 문제는 아 이거 이렇게 이분 탐색하면 되겠네! 만 깨우치면 코드는 정말 쉬워지는 것 같다. 물론 저렇게 깨닫는 경지가 되려면 연습이 엄청 필요할 것 같다...

문제출처 : 백준 https://www.acmicpc.net/problem/2343

2343번: 기타 레슨