자연수 k와 n에 대해, q, r을 다음 조건을 만족하는 정수로 정의합시다.
k = qn + r, 0 < r <= n
(q는 k-1을 n으로 나눈 몫, r은 k-1을 n으로 나눈 나머지에 1을 더한 수입니다.)
배열의 각 줄을 순서대로 이어붙였을 때, k번째 수는 (q+1) * r입니다. (k번째 칸이 정사각형의 q+1번째 행 r번째 열에 위치하기 때문)
(q+1)*r = qr + r <= qn + r = k 가 항상 성립합니다. (등호는 q=0 or r=n일때)

jungk0419 1년 전
이분탐색시에 상한선을 N^2 가 아니라 K로 설정할 수 있는 이유를 모르겠어요
어떤분께서
이분탐색의 상한을 k로 잡아도 된다는 것은 모든 k에 대해 배열에 있는 수 중 k번째로 작은 수가 k 이하라는 뜻이며, 이는 모든 k에 대해 배열에 k 이하인 수가 k개 이상 존재한다는 것과 동치입니다.
배열의 각 줄을 순서대로 이어붙였을 때(ex. n = 3일 경우 1, 2, 3, 2, 4, 6, 3, 6, 9), 모든 k에 대해 앞의 k개의 수가 k 이하이므로 위의 명제가 성립합니다. 엄밀한 증명은 직접 해 보시기 바랍니다.
라고 하셨는데 엄밀한 증명을 못하겠어서 질문올립니다 ㅜㅜㅜㅜ