꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/8903 장비를 5개 이상 이용할 경우에는 그리디하게 접근하여 각 장비 당 최대 점수를 갖고 있는 장비를 5개 고르면 되지만, 장비가 1개 이상 4개 이하일 경우 위와 같은 그리디한 접근은 옳지 않은 것을 알 수 있습니다. N이 최대 10,000이기 때문에 모든 경우를 그대로 완전탐색해버리면 TLE가 나는 까다로운 문제였습니다.따라서, 각 장비를 K개의 그룹으로 나누어 해당 그룹에 속한 능력치들의 합이 최대인 장비를 고르는 쪽으로 접근하면 되는 문제였습니다. *학회 슬랙을 통해 같은 학교 학우이신 Green55님이 많은 힌트를 주셨습니다. #include #include #include using namespace std; con..

문제 링크입니다: https://www.acmicpc.net/problem/1672 왜 DP 문제로 분류되어있는지 잘 모르겠는 문제입니다.길이는 최대 백만이기 때문에 O(N)으로 충분히 해결할 수 있는 문제였습니다. #include #include #include using namespace std; int N; string change = "ACAGCGTAATCGGAGT"; char func(char a, char b) { int idx = (a == 'A' ? 0 : a == 'G' ? 1 : a == 'C' ? 2 : 3); int idx2 = (b == 'A' ? 0 : b == 'G' ? 1 : b == 'C' ? 2 : 3); return change[idx * 4 + idx2]; } int ..

문제 링크입니다: https://www.acmicpc.net/problem/1351 범위가 long long인 것만 조심하면 간단히 풀 수 있는 DP 문제였습니다. #include #include using namespace std; long long N, P, Q; map cache; long long func(long long N) { if (cache.count(N)) return cache[N]; else return cache[N] = func(N / P) + func(N / Q); } int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> P >> Q; cache[0] = 1; cout

문제 링크입니다: https://www.acmicpc.net/problem/15685 Algospot DRAGON(https://jaimemin.tistory.com/357)과 개념은 비슷했지만 훨씬 쉬운 문제였습니다. 알고리즘은 아래와 같습니다.1. 시작 방향을 토대로 g 세대까지 방향들을 미리 구성합니다.2. 구성한 방향들을 토대로 (y, x)를 움직이며 visited 배열에 표시합니다.3. N개의 입력에 대해 1, 2번을 모두 완성하고 정사각형의 개수를 파악합니다. #include #include #include using namespace std; const int MAX = 100 + 1; typedef struct { int y, x; }Dir; //right, up, left, down Di..

문제 링크입니다: https://www.acmicpc.net/problem/1436 N의 범위가 작기 때문에 브루트 포스 기법을 이용하여 답을 찾아내면 됩니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; //첫 번째 종말의 숫자 int num = 666; int turn = 1; //완전 탐색 while (1) { //해당 숫자를 찾았다면 if (turn == N) break; num++; //해당 숫자를 저장하고 int copyNum = num; string s; while (copyNum) { s += (copyNum % 10 + '0');..

문제 링크입니다: https://www.acmicpc.net/problem/11866 N과 M의 범위가 작기 때문에 그대로 시뮬레이션을 돌리면 AC를 받을 수 있는 문제였습니다.시간복잡도는 O(N^2)입니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N, M; cin >> N >> M; queue q; for (int i = 1; i

문제 링크입니다: https://www.acmicpc.net/problem/3673 배열을 입력받으면서 부분합을 D로 모듈러 연산을 한 결과의 개수를 visited 배열에 저장합니다.$$이후,\; _{visited[i]}C_2의\; 누적합을\; 구해주면\; 됩니다.$$ #include #include #include using namespace std; const int MAX = 1000000 + 1; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; for (int t = 0; t > D >> N; vector visited(MAX, 0); int sum = 0; vi..

문제 링크입니다: https://www.acmicpc.net/problem/6597 아래와 같은 두 성질을 이용하면 쉽게 풀 수 있는 문제였습니다.1. 전위 탐색을 했을 때 제일 앞에 있는 노드가 해당 서브트리의 노드입니다.2. 중위 탐색을 했을 때 루트를 기준으로 왼쪽에 나오는 노드들은 왼쪽 서브트리, 오른쪽에 나오는 노드들은 오른쪽 서브트리에 속한 노드들입니다. #include #include #include using namespace std; void postOrder(string preOrder, string inOrder) { //기저 사례 if (!preOrder.length()) return; //트리에 포함된 노드의 수 int num = preOrder.size(); const char ..

문제 링크입니다: https://www.acmicpc.net/problem/15805 전위 순회 탐색을 생각해보면 쉽게 풀 수 있는 문제였습니다.한번도 방문하지 않은 노드는 (해당 노드가 등장하기 전 노드)의 자식입니다. #include #include using namespace std; const int MAX = 200000 + 1; int A[MAX]; int parent[MAX]; set tree; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; for (int i = 0; i > A[i]; parent[A[0]] = -1; tree.insert(A[0]); for (int i = ..

문제 링크입니다: https://www.acmicpc.net/problem/1517 배열을 반으로 나누어서 탐색하며 접근해야했던 문제였습니다. 버블소트는 해당 인덱스를 기준으로 다음 인덱스를 비교했을 때, 해당 인덱스에 위치한 값의 우선순위가 더 작다면 swap하는 정렬 기법입니다. 알고리즘은 아래와 같습니다.1. 배열을 반으로 쪼개며 inversion 즉, 해당 인덱스보다 다음 인덱스의 우선순위가 작은 지점을 탐색합니다.2. 탐색을 하는 과정에서 머지 소트처럼 다른 배열에 값을 업데이트합니다.i) 순서가 맞다면 그대로 넣어줍니다.ii) 우선순위가 반전되있는 상태라면 반전되어있는 길이를 결과에 더해주고 순서에 맞게 넣어줍니다.3. 2번에서 업데이트한 배열을 토대로 기존 배열을 업데이트해줍니다. #incl..