안녕하세요 Dibrary입니다. 이번에는 이분탐색을 사용해야 풀 수 있는 문제를 정리해보겠습니다.
저에게 이 문제는 처음에 이해하는데 굉장히 시간이 오래 걸린 문제여서.... 정리를 꼭 해둬야겠다 생각했죠.
먼저 문제를 보고 어떤 방법으로 이분탐색을 해야 하는지 감을 잡지 못했습니다.
정확히는 '다른 풀이를 보고서도 이해가 안되었다' 가 더 맞는 표현같네요.
지금은 다른 풀이를 이해한 부분만 정리해보면 아래와 같습니다.
1. 대부분 start = 1로 잡고, (문제에서 시작 인덱스가 1이라고 했죠) end 를 k로 잡습니다. 여기서 end를 k로 잡는 이유는 n은 반드시 1보다 큰데 그 말은 k번째 숫자는 k보다 클 수가 없다는 것이죠.
예를 들어 n이 1이면 k번째 숫자는 k가 됩니다.
n이 2라도 되면 k번째 숫자는 반드시 k보다 작습니다. (더 정확히는 작거나 같죠)
2. 그리고 mid값보다 작은 것의 갯수를 한 방에 세는 것이 중요합니다. 당연히 mid값은 (start+end)//2로 하겠죠. 이정도는 이분탐색을 공부하면 간단히 알 수 있습니다. 문제는, 이 mid값을 가지고 '어디에 써먹느냐'가 문제죠.
다른사람들의 수식 대부분은 아래와 같습니다.
제일먼저 보이는건, for문으로 n번째 숫자까지를 진행합니다. 왜일까요? 문제에서 n*n크기의 배열이라고 했으므로, 숫자는 n까지 있기 때문에 for문으로 n번째까지 진행하는 것입니다.
그 다음에 문제는 min(int(mid/i), n) 입니다. 다르게 int를 줄여서 min(mid//i, n)으로도 나타낼 수 있죠.
이게 가장 이해가 안 되었던 코드 부분인데 나름 설명해보자면, 예제 1번을 빗대어서 설명해보겠습니다.
3*3 배열이므로 아래와 같은 값으로 구성될 겁니다.
자 그럼, mid값은 (1+7)//2 인 4가 되겠네요. 위 코드대로 진행하면 cnt는
- i가 1일때 3이 더해집니다.
- i가 2일때 2가 더해집니다.
- i가 3일때 1이 더해집니다.
뭔가 감이 잡히시나요? 우선 i가 1일때 mid//i값은 4입니다. 그러나, 우리가 처음 문제에서 주어진 배열은 n행까지만 가능하므로 4는 n=3값보다 크죠. 그래서 min으로 n값이 cnt에 더해지는 것입니다.
i가 2일때 mid//i값은 2가 됩니다. 잘 보면 2행에서 4와 같거나 작은 값의 갯수는? 2개 입니다. 우연의 일치일까요?
i가 3일때 mid//i값은 1이 됩니다. 잘 보면 3행에서 4보다 작거나 같은 값의 갯수는 1개 입니다. 아하!
mid//i값은 각 i값에서 mid값보다 작거나 같은 숫자의 갯수를 의미하는구나! 를 알 수 있습니다.
그래서 이 갯수에 대해서 '이진탐색'을 진행하는 것입니다.
최종 코드는 아래와 같습니다.
생각보다 코드는 간단했는데, 이해하는데 꽤나 시간이 걸린 문제입니다.
'알고리즘 > 문제풀이' 카테고리의 다른 글
[BOJ][15651번] N과 M (3) (백트래킹) (0) | 2022.09.26 |
---|---|
[BOJ][3063번] 게시판 (0) | 2022.09.08 |
[BOJ][2108번] 통계학 (0) | 2022.09.07 |
[BOJ][2018번] 수들의 합 5 (0) | 2022.08.19 |
[BOJ][1516번] 게임개발 (0) | 2022.08.18 |