코딩성장스토리

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 100,000,000,000번 곱해야하는 문제이다 . 즉 시간복잡도가 O(log n)이 아니면 불가능 하다. 그래서 분할 정복을 생각하였다. 문제 풀이는 제곱수가 n이라 하고 행렬 a가 있다고 할 때, ex)n=10이라고 하자. 나는 재귀로 풀었기에 n은 1,2,4,5,10으로 올라가는 형태이다. 즉 n=1일때 A n=2일때 A*A=A^2 n=4일 떄 는 (A^2)*(A^2)=A^4 n=5일 때 는 ..

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 이 문제는 누적합 으로 접근해서 풀어야한다. 난 처음에 누적합으로 접근하는 건 알겠는데 (i,j)의 쌍들을 구하는 것을 구현하면 시간제한을 초과할 것 같았다. 즉 다른 방식으로 접근을 해야한다. 그 방법은 d[i]의 배열이 문제에서 주어진 배열의 누적합이라고 하고 A[i]를 문제에서 주어진 배열이라고 할 때 A[i]에서 A[j]의 구간합은 d[j]-..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제를 처음 접했을 떄 가장 떠오른 것은 백트래킹이었다. 아직 다이나믹프로그래밍을 모르는 것 같다...(dp문제 풀 떄마다 좌절감을 느끼는 중..) 아래 코드는 백트래킹으로 푼 코드이다 넘어가도 좋당... 나같은 행동은 하지 마세용.. (시간초과로 틀린 코드) #include #include #include using names..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍으로 푸는 것이다. 라고 생각해서 접근했지만 후...모르겠어서 다른 글을 참고했다.. 풀이는 말그대로 다이나믹 프로그래밍으로 푸는 것이다 두 문자열 ACAYKP CAPCAK 가 있다고 하였을 때, 맨 처음 부분 문자열 A,AC,ACA... 와 C,CA,CAP.. 로 비교해가면서 푸는 것이다. 즉 부분 집합에서 최적해를 찾아가..