주녘공부일지

https://www.acmicpc.net/problem/1103핵심 아이디어 및 정답 코드- 게임을 진행하면서 최대로 이동할 수 있는 횟수가 몇인지 구하는 문제 -> 모든 경우의 수를 구해야 하므로, 깊이 우선 탐색(DFS)를 이용  -> 단, 이미 왔던 좌표라면 무한 루프를 돌 수 있으므로 -1를 리턴 (BackTracking) - 모든 경우의 수를 구하다보면 중복 연산이 많아질 수 있음 -> 동적 계획법(DP)을 통해 중복되는 연산을 줄임 즉, DP + DFS BackTracking 문제 + 영역을 벗어거나 구멍에 의해 동전이 떨어지는 좌표로 이동하는 것도 이동횟수 https://godgjwnsgur7.tistory.com/109 [Algorithm C#] 동적 계획법(DP) / Memoizatio..

https://www.acmicpc.net/problem/4375핵심 아이디어 및 정답 코드- 큰 수를 대상으로 % 연산 시, 많은 수를 나눠야 하므로, 대상의 크기를 줄임 -> 모듈러 성질 이용 : (A * B) % C = (A % C) * (B % C)  -> 자료형 크기를 벗어나는 것도 방지할 수 있음 + 출력할 때, 개행 문자를 추가하지 않으면 출력 양식에 맞지 않아 실패 정답 코드#include using namespace std;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int target; while (cin >> target) { int num = 1; // 타겟으로 나..

https://www.acmicpc.net/problem/1629핵심 아이디어 및 정답 코드범위를 쉽게 벗어날 수 있으므로, 유의 -> 모듈러 성질 이용 : (A * B) % C = (A % C) * (B % C) 1) O(N) 계산 : 시간 초과- O(log N) 이하의 시간 복잡도로 풀어야 함 -> 지수 법칙 이용 : A^(N+M) = A^N * A^M 2) dp로 저장 : 메모리 초과- B / 2 만큼의 연산을 dp에 미리 담아두어 dp[B/2] * dp[B/2] * dp[B%(B/2)]로 계산하려고 시도 -> 재귀를 이용하여 연산량을 줄임 3) 재귀를 사용 : 통과- 재귀를 이용해 현재 넘어온 B 값이 짝수, 홀수인지에 따라 연산 -> 짝수 : A^B % C / 홀수 : A^(B + 1) % C ..