1-O 부연설명

1-O 부연설명

자 오늘은 1-O 부연 설명을 좀 해보도록 할텐데,

cnt = cnt x 10 + 1; 을 해주고 난 다음 모듈러 연산 n을 해주고 있죠. 그런데 이걸 보고 질문해주시는 분들이 있어요.

지금 else 문의 cnt %= n부터 시작해서 대입해보면,

'아니 선생님. 이렇게 해야 옳은 표현 아닌가요?'

그러니까 위의 코드가 이렇게 되어야 하는거죠. 물론 맞는 말씀입니다. 그런데

이것도 맞는 표현입니다.

왜일까요? 거기에 대해서 얘기를 해 보도록 할텐데, 자 봐요.

제가 강의에서 주장하는 건 이거죠.

그러면 제가 증명해야 될 것은 뭐죠?

이거겠네요. 오른쪽이 왼쪽과 같다는 걸 증명하면 되겠죠.

a 모듈러 연산 n이 가지는 숫자의 범위는 어느 정도가 되죠? (0 ~ n - 1)까지죠. 그걸 또 모듈러 연산 n 하면, 역시 (0 ~ n - 1)까지의 범위가 나와서 증명이 완료됩니다.

그 다음에는 왼쪽이 왜 오른쪽처럼 써도 되는지 증명해야죠.

그럼 밑에 식처럼 되고 결국 ( A * B ) mod n = (A mod n * B mod n) mod n이니까 증명이 되는 것을 볼 수 있습니다.

그래서 (a % n * b) % n == (a * b) % n 임을 알 수 있습니다.

---

자 그러면 실제로도 이게 되는지 코드를 돌려서 테스팅을 해보도록 할게요.

그러니까 저는 ret이 ret2과 같은 의미를 가진다고 주장하는 거죠. 아까 증명한 대로 같은지 돌려보면, 한번도 출력이 안되는 걸 볼 수 있습니다.

지금 보시는 것처럼 1-O에서의 이 코드가 성립되는 걸 볼 수 있습니다.