[WEEK02] 13일차 이분 탐색 & 분할 정복

2470 두 용액

https://bladejun.tistory.com/97

위 링크를 참고하였다.
로직 자체는 비슷하게 짰다고 생각했는데
target = min(target, abs(l + r))
이런 식으로 타겟과 abs(l + r) 중에 작은 값으로 타겟을 업데이트를 하는 방식으로 구현하려고 했으나 실패하였다.
분석해보니 모든 값이 양수로 나올때도 있어서 abs(l + r)이 타겟보다 작을 때만 타겟을 abs(l + r)로 업데이트하는 방식이 옳은 방식이었다.

16564 히오스 프로게이머

이분 탐색은 l, r 최소 최댓값을 잘 설정한 다음
최소 최댓값의 중간값인 mid 값을 이용해서 코드를 작성하는 경우가 많은 것 같다.

작성한 코드

mid 값을 어떻게 활용해서 코드를 작성할 것인가가 핵심인 듯 하다. 이해하면 쉬운듯 하면서도 아직은 결코 쉽지가 않다. 계속 분석하고 풀어보면서 익숙해져야할 듯 하다.

1629 곱셈

지수 법칙

A^m+n = A^m * A^n

나머지 분배법칙

(A * B) % C = ((A % C) * (B % C)) % C

위를 적용하면

10^11%12

= ((10^5%12)*(10^5%12)*10)%12

= ((((10^2%12)*(10^2%12)*10)%12)*(((10^2%12)*(10^2%12)*10)%12))%12

이런 식으로 된다.

지수가 짝수일 때는 아래처럼.

10^10%12

= ((10^5%12)*(10^5%12))%12

즉, 지수가 홀수일때는,

(B//2 * B//2 * A)

짝수일 때는,

(B//2 * B//2)

이렇게 나온다.
이제 재귀함수를 써서 분할 정복 코드를 작성하면 된다.

작성한 코드