Tip - 바닥함수와 천장함수의 관계

천장함수를 바닥함수로 표현하는 법

$n \ge 0, k > 0$ 라 할 때,

$\dfrac{n}{k}$ 에 대해서 $\left\lfloor \dfrac{n}{k} \right\rfloor$는 단순히 코드로 n / k 로 표현할 수 있다.

$\left\lceil \dfrac{n}{k} \right\rceil$는 $\left\lfloor \dfrac{n+k-1}{k} \right\rfloor$ 로 흔히 쓰여 코드에선 (n+k-1)/k 로 얻는 것이 흔하다.

이걸 좀 더 그림과 함께 보자.

흔히 이 영역에 $n$이 있다면 $\left\lfloor \dfrac{n}{k} \right\rfloor$ 는 $1$ 이 된다. 이 때의 구간은 $[k, 2k-1]$ 이다.

천장함수(올림 연산)을 보자

$\left\lceil \dfrac{n}{k} \right\rceil=2$ 가 되려면 구간은 $[k+1,2k]$ 이고, 다음과 같다.

여기에 $k-1$ 를 더한 구간은 $[2k,3k-1]$ 로, 올바르게 천장함수의 역할을 수행하게 됨을 알 수 있다.

따라서 $\left\lceil \dfrac{n}{k} \right\rceil=\left\lfloor \dfrac{n+k-1}{k} \right\rfloor$ 이다.

0번째 인덱스부터 K씩 증가하는 수의 포함 개수

어떤 수가 $k-1,2k-1,3k-1,\dots$ 처럼 되면 구간 길이 $n$에서 이 수가 표시되는 개수는 $\left\lfloor \dfrac{n}{k} \right\rfloor$ 로 깔끔하게 표현된다.

당연히 코드는 n/k 이다.

하지만 어떤 수가 $0, k, 2k, 3k,\dots$ 처럼 늘어나며 표시된다고 하자.

그럼 $[0, n]$ 구간에서 위 수가 표시되는 개수는 얼마일까?

$n=3k$ 라 하자. 그럼 다음과 같이 총 $4$개가 포함된다.

이를 천장함수의 표현으로 표현하면 $\left\lceil \dfrac{n+1}{k} \right\rceil$ 개가 포함된다고 할 수 있다.

이는 바닥함수로 $\left\lfloor \dfrac{n+k}{k} \right\rfloor=\left\lfloor \dfrac{n}{k} \right\rfloor+1$ 이다.