주녘공부일지

https://www.acmicpc.net/problem/2468핵심 아이디어 및 정답 코드- 특정 높이 이상의 인접한 영역을 묶었을 때 가장 많은 영역으로 쪼개지는 경우를 구하는 문제- 깊이 우선 탐색(DFS) 알고리즘을 이용하여 최소 ~ 최대 범위에서 가장 많은 영역이 생기는 경우를 구함+ BFS로 풀어도 무관해보이지만, 모든 경우를 구해야 하므로 DFS가 더 유리할 수 있음 + Memo) Find-Union 알고리즘 + a 로 한번 풀어볼 것 ( 시간 복잡도를 많이 줄일 수 있음 ) -> 20ms -> 0ms DFS 풀이 정답 코드https://godgjwnsgur7.tistory.com/47 [Algorithm C#] BFS, DFS ( + Back Tracking )1. BFS(Breadth F..

https://www.acmicpc.net/problem/2870핵심 아이디어 및 정답 코드- 주어진 문자열 중에 정수들을 찾아내어 오름차순으로 정렬해 출력하는 문제- 문제에서 최대 100자리를 가진 숫자가 나올 수 있기 때문에 정수형이 아닌 문자열로 받아옴 - 000 -> 0 - 001 -> 1 - 100 -> 100 + 문자열은 길이가 같을 경우 비교하면 더 큰 숫자가 크게 나옴 정답 코드#include #include #include #include using namespace std;vector strVec;void FindNumStr(string str){ for (int i = 0; i 0) strVec.push_back(temp); } }}..

https://www.acmicpc.net/problem/17070핵심 아이디어 및 정답 코드- 파이프를 옮길 수 있는 경우의 수를 구하는 문제- 접근 방식에 따라 DFS, DP로 풀 수 있음 맨 위에부터 DP, DFS(도착지에서 탐색), DFS(출발지에서 탐색)1. DFS 풀이https://godgjwnsgur7.tistory.com/47 [Algorithm C#] BFS, DFS ( + Back Tracking )1. BFS(Breadth First Search) - 너비 우선 탐색최단 경로, 임의의 경로를 찾고 싶을 때, 등에 사용- 큐(FIFO) 사용 // 큐를 이용 public void BFS(int index) { Node root = nodes[index]; Queue queue = new ..

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 ..

https://www.acmicpc.net/problem/9375핵심 아이디어 및 정답 코드- 해당 옷을 입지 않은 경우의 수를 같이 구하면 한번에 구할 수 있음- 의상 종류 개수 + 1을 전부 곱하면, 아무것도 입지 않은 경우의 수가 포함되므로 마지막에 1을 빼줌 + 처음에 DFS로 접근했다가 시간 초과를 경험함ㅠ; 정답 코드#include #include using namespace std;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int totalCount; cin >> totalCount; for (int i = 0; i m; int count; cin >> count; for (int j = 0; j > str..