코딩스토리

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 일반적인 Prefix Sum으로 구하면 query로 인해 시간 초과가 발생한다. 따라서 Binary Index Tree(펜윅 트리)를 사용하여 구해야 하는 문제이다. 아래는 BIT에 대한 설명이다. https://kimtaehyun98.tistory.com/112 Binary Index Tree(BIT, Fenwick Tree) # 아래 ..

확장 유클리드 호제법 기말 기간이라 밀렸던 문제 해결 기법 강의를 듣고 있는데 확장 유클리드 호제법이 나왔다. 유클리드 호제법을 알고 있었고 가끔씩은 백준 푸는 데 사용했었기 때문에 어렵지 않게 이해하고 넘어가야지 했는데 뭐지? 이해가 안가네? 옛날 같았으면 그냥 에라이 모르겠다 하고 넘어갔을 텐데 뭔가 시험에 나올 것 같다는 강렬한 촉이 와서 정리해봤다. (개인적인 이해를 바탕으로 작성했기 때문에 완벽하진 않아요!) 확장 유클리드 호제법을 이해하려면 먼저 유클리드 호제법을 이해해야 한다. 일명 GCD 알고리즘이라고도 불리며 "수학"이란 카테고리에서는 가장 처음 접하는 알고리즘 다운 알고리즘이다. 자세하게 설명하는 건 생략하고 요약하자면 결국 유클리드 호제법을 간단히 말하면 "log 시간안에 최대공약수를..

https://www.acmicpc.net/problem/14289 14289번: 본대 산책 3 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 결국 정보대에서 정보대까지 d번만에 가는 경우의 수를 구해야 하는 문제였다. 이를 일반화해보면 "A 노드에서 B 노드까지 d번만에 가는 경우의 수"를 구해야 한다. 이 부분에 dp 스럽게 생각해보면 "A노드에서 B와 연결된 모든 노드까지 d-1번 만에 도착하는 경우의 수들의 합"과 같다. 즉 식으로 나타내면 다음과 같다. dp [i][j][k] = i 노드에서 j 노드까지 k번 만에 도착하는 경우의 수라고 가정해보자. 그렇다면 dp[i][j][k]는 아래와 같이 구할 수 있다. for(int a = 1; a i..

https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 본격적인 행렬 제곱 DP를 사용한 문제이다. 피보나치 수를 구하는 문제는 다이나믹 프로그래밍의 전형적인 문제 유형이다. 대부분 DP를 시작하는 사람들은 피보나치 수를 처음 접하면서 시작한다. 이 문제 역시 피보나치 수를 구하는 문제이다. 다른 점은 n 제한 하나이다. 이 문제의 n제한은 "1,000,000,000,000,000,000"이다. 이번에도 이 숫자가 내 통장잔고였으면.. 하지만 이번 건 스케일이 좀 남다르다. 내 통장잔고의 문제가 아니라 몇 년치 국가 예산보다 크지 ..

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬 제곱 DP를 공부하기 위해 먼저 이 문제를 풀어보았다. 주어진 조건 중 "1 ≤ B ≤ 100,000,000,000"을 보고 저게 내 통장 잔고였음 좋겠다... 뻘 생각 한번 해주고 시간 복잡도는 O(logN)으로 구해야겠다 싶었다. 내가 문제를 보고 생각했던 logN 풀이는 반드시 (A^2)*(A^2) = A^4를 만족해야 했다. 나는 행렬을 고등학교때 배우고 온 세대가 아니기 때문에(나름 신생아^^) ..