알고리즘 오답노트 (~23.7.12)
이 글은 풀이를 스스로 찾아내지 못한 문제들을 정리해놓은 글이다. 오답노트가 으레 그렇듯 나중에 다시 찾아와서 풀어볼 생각이다.
Baekjoon Online Judge - 1629. 곱셈
자연수 A 를 B 번 곱한 수를 C로 나눈 나머지를 구하는 문제다. 주의할 점은 A, B, C 모두가 2,147,483,647 이하의 자연수라는, 엄청나게 넓은 범위를 자랑한다는 것이다.
처음에는 반씩 나눠서 재귀로 풀었다.
function dnq(count) {
const mod2 = count % 2;
const half = Math.floor(count / 2);
return (dnq(half) * dnq(half + mod2)) % BigInt(c);
}
하지만 이 풀이로는 시간 초과가 나서 캐시도 사용했다. 캐시를 사용하니 채점을 통과했다.
푼 것 자체는 만족스럽지만, 이 문제의 분류는 "수학"과 "분할 정복"이라고 표시된다. 분류를 봐서는 캐시를 사용하지 않는 방법이 있을 것 같았기에 풀이를 찾아봤다. 확실히 내 풀이보다 더 간단한 풀이가 있었다.
function dnq(count) {
const half = Math.floor(count / 2);
const res = dnq(half);
return count % 2 === 1 ? (res * res * a) % c : (res * res) % c;
}
풀이 참고
Baekjoon Online Judge - 11401. 이항 계수 3
무려 "나머지 연산의 역원"과 페르마의 소정리에 대해 알고 있어야지만 풀 수 있는 문제. 페르마의 소정리를 사용해 도출해낸 식 중 N 제곱 부분을 분할 정복으로 해결하면 된다. 한마디로 그냥 수학 문제다.
풀이 참고
Baekjoon Online Judge - 11444. 피보나치 수 6
어찌 알았겠는가.. 이 문제가 행렬의 N 제곱을 사용해 풀 수 있는 문제라는 것을.. 바로 전 문제로 푼 게 행렬 제곱이었건만 전혀 몰랐다. 솔직히 피보나치 수열을 2x2 행렬을 사용해 풀 수 있다는 사실을 기존에 알고 있던 사람이 아니라면, 이 문제를 풀 수 있는 사람이 정말 있을까? ...있을 것이다. 세상은 괴물 투성이니까.
풀이 참고
Baekjoon Online Judge - 6549. 히스토그램에서 가장 큰 직사각형
옛날에 비슷한 문제를 푼 기억이 있어서 찾아봤는데 leetcode 에 푼 흔적이 있었다. 하지만 해당 문제는 이 문제만큼 제한이 크지 않아서 거의 브루트포스 비슷한 방법으로 풀었다.
분할 정복으로 풀 수 있다는 걸 알고 있음에도 풀이가 도저히 떠오르지 않아서 결국 풀이를 찾아봤다. 솔직히 말하자면 풀이를 맨 처음 봤을 때는 와닿지가 않았다. "정말 이 풀이로 풀린다고? 이게 반례가 없다고?" 하지만 천천히 잘 생각해보니 제대로 된 풀이란 걸 알 수 있었다.