1-N

틀림

---

1-N

자 오늘은 곱셈 문제를 풀어 보도록 할텐데요. 이 문제는 정말 단순하죠.

A를 B번 곱해서 C로 나눈 나머지를 구하는 문제죠.

'선생님 곱하기니까 그냥 for 문을 통해가지고 곱하면 되지 않을까요?'

이런 식으로 곱하기를 다 끝난 다음에 이렇게 모듈 연산 C를 하면은 되지 않을까요? 라고 생각할 수가 있어요.

자 근데 여기서 문제를 봤을 때 가장 먼저 뭐부터 보라고 했죠? 문제의 최대 최소 범위를 보라고 말씀을 드렸죠.

A, B, C는 모두 2,147,483,647 이하의 자연수, 즉 20억 이하네요. 이걸 for 문으로 하게 되면 시간 복잡도가 20억 이하가 된다는 거예요.

그러면 이거는 for 문으로 하면 안 되겠구나 라는 결론이 나와야 됩니다.

자 그러면 이거를 어떻게 풀어야 될까? 어떻게 매번 곱하는거에 대한 시간복잡도를 줄일 수 있을까? 사실 이 1-N, 1629 곱셈 문제는 굉장히 유명한 문제입니다.

그래서 좀 유명한 풀이긴 한데 일단 한번 보도록 할게요.

자 제가 한번 예시를 한번 들어볼게요.

2의 4승은 뭐죠? 2의 4승은 2를 4번 곱한 거지만 2의 2승 곱하기 2의 2승이네요?

2의 8승도 마찬가지입니다.

그러면 이거를 어떻게 하면 줄일 수 있을까?

그러니까 매번 2를 4번 곱하는 게 아니라, 2의 2승, 즉 2를 2번 곱한 거를 변수에다가 담아놓고, 그 변수를 곱하면 여기에 대한 연산에 드는 cost는 줄일 수가 있겠죠.

자 2의 8승은 2의 4승 곱하기 2의 4승이죠.

자 그러면 2의 4승을 어떤 변수 A에다가 담아놔요. 그리고 나서 그냥 A 곱하기 A를 하게 되면, 2를 4번 곱할 필요는 없다는거죠.

그러니까 2의 8승이 이런데, 곱하기 하나 자체가 하나의 cost 잖아요. 그래서 곱하기를 하나 할 때마다 연산양, cost가 증가한다는 거예요.

그래서 2 x 2 x 2 x 2를 하나의 변수 A라고 놓으면, 2 x 2 x 2 x 2를 곱해줄 필요가 없죠. 그냥 A 곱하기 A 하면, 저 긴 연산과 동일한 효과가 나는 거죠.

그러니까 우리가 곱한 것들을 어떠한 변수에다가 담아놓고, 그 변수를 활용하는 방법을 통해서 이걸 한번 풀어볼 거예요.

자 우리는 go 라는 함수를 정의할 거에요.

go(2, 64) 하면 2를 64번 곱한다라는 거예요. 그러면 이게 어떻게 되냐?

go(2, 32)를 2번 곱한 것이 되죠. 즉, 2의 64승 = 2의 32승 곱하기 2의 32승이니까, 2의 32승을 변수에 넣어야 겠다는 생각이 들죠. 그 다음에

이건 또 go(2, 16)을 2번 곱한 게 되죠. 즉 2의 32승 = 2의 16승 곱하기 2의 16승이니까 이번에는 2의 16승을 변수에 넣어야 겠네요.

그래서 쭉쭉쭉 가면 이렇게 됩니다. 최종적으로 2의 32승 값만 구하면 이걸 2번 곱하면 2의 64승을 구할 수 있습니다.지금까지  A X A, 곱하기 연산을 몇 번 했을까요?

지금 보면 이게 몇 번 일어났어요? 총 6번 일어났어요. 즉 log2의 64번이 되어버린거죠.

선생님 그냥 이렇게 for 문으로 곱하면 안되나요? 안되죠. 이렇게 하면 시간 복잡도가 20억입니다.

그래서 앞서서 설명한 방법, 곱한 것들을 변수에다가 집어넣고 그 변수를 이용해서 하게 되면,

곱하기 연산이 20억번에서 log2의 20억이 된다라는 거예요. 확 주는 거죠.

그래서 이러한 재귀적인 함수로 어떤 값들을 집어넣고 계속해서 반으로 나누면서 그러한 값들을 이용해가지고 곱하는 방법을 이용하면 이런 식으로 시간 복잡도를 줄일 수 있다라는 겁니다.

그러면 이 문제는 사실은 또 하나의 개념이 들어가요. 이거는 모듈러 연산에 관한 건데 이거는 교안에 설명이 되어 있습니다.

(a + b) % c = ((a % c) + (b % c)) % c

(a * b) % c = ((a % c) * (b % c)) % c 

입니다. 즉, 좌변과 우변이 같습니다.

이건 정수론의 개념이에요. 이거를 이용할텐데 자 이 개념을 왜 이용할거냐면 우리가 해야 되는건 뭐죠?

20억을 최대, 최대치로 계산했을 때 20억을 20억번 곱해야 되는 거예요. 그런데 20억 곱하기 2만 해도 int의 범위를 벗어나죠.

그러니까 이 곱하는 것 자체 때문에 일단 범위는 무조건 long long을 써야 돼요. 그런데 20억을 20억번 곱하는데 long long을 당연히 벗어날 거 아니에요. long long으로도 부족하죠.

그래서 얘를 어떻게 계산하냐면 20억이라는 숫자를 곱할 때마다 모듈러 연산을 해줘요.

이렇게 하면 값이 너무 커져서 overflow가 되잖아요. long long으로도 담을 수 없는 값이 되어버린다는 거예요.

그렇기 때문에 곱하기를 할 때마다 이렇게 조금 조금씩 미리미리 이렇게 나눠준다 라는 겁니다.

자 우리 첫번째 뭐라고 했죠? 곱한 것을 어떤 변수에다가 집어넣는다고 했죠. 그걸 기반으로 해가지고 반씩 나누면서 재귀함수를 구현한다고 했어요.

그리고 두번째는 뭐라고 했죠? 모듈러 연산 값이 오버플로우가 되기 때문에 그걸 방지하기 위해서 이렇게 한다고 했죠.

---

자 이 두 가지의 개념을 잡고 코드를 보도록 할게요. 엄청나게 간단합니다.

일단 int형 선언은 안 됩니다. 왜냐하면 곱하는 것 자체가 한 번만 곱해도 20억이 이제 초과되어 버리기 때문에 이거는 long long으로 시작하고 들어가야 합니다.

이 go 라는 재귀함수를 보면, 일단 재귀함수는 기저사례가 있어야된다고 했죠.

그런데 이건 뭐죠? 홀수 승 때문에 그렇습니다.

만약에 홀수 승이라면 한번 더 곱해줘야 되기 때문이죠.

c++은 0은 false 값을 가지고, 0 이외의 값들은 전부 true 값을 가집니다. 언어마다 다르긴 한데, 그렇기 때문에

이게 실행되는 거죠. 그리고 (ret * (a % c)) % c 가 아닌 이유는 아래와 같습니다.