Problem Solving43 Educational Codeforces Round #122 늦었지만 올리는 후기 A. Div. 7 어떤 수 n 이 주어졌을 때, 숫자를 최소한으로 바꾸어 7으로 나뉘는 수를 구하는 문제. 바뀐 숫자는 0으로 시작하면 안된다. n과 자리수가 같은 7으로 나누어지는 수를 iteration하며 숫자가 다른 횟수를 센 후, 횟수가 가장 작은 수를 구하였다. 어차피 n이 최대 999라 brute force로도 충분했다. B. Minority 0과 1으로만 구성된 string이 주어졌을 때, substring의 minority의 최대 갯수를 구하는 문제. 여기서 minority란 substring 안에서 1의 갯수가 0보다 더 많으면 0, 0이 더 많으면 1이다. 갯수가 같은 경우 minority는 없다. 가장 큰 substring은 결국에 string 그 자체이다. 그래.. 2022. 2. 8. Graph Depth-First Search (DFS) Backtracking 전에 가능한한 시작점으로부터 깊은 노드들을 먼저 탐색한다. 보통 재귀나 stack을 사용하여 구현. Breadth-First Search (BFS) 시작점으로부터 같은 깊이의 노드들을 먼저 탐색한 후 더 깊은 노드들을 탐색한다. queue를 사용하여 구현. Lowest Common Ancestor (LCA) 트리 구조에서 height가 가장 낮은 공통 ancestor을 LCA라 부른다. Euler tour를 순회하는 방법 - sqrt decomposition (O(n) for preprocessing, O(n^(1/2)) for query) - segment tree (O(n) for preprocessing, O(log n) for q.. 2022. 1. 25. Merge / Quick Sort & Binary Search Merge sort Sorting 방법 중 하나. 배열을 반으로 쪼개어(divide), 더 이상 나눌 수 없을 때 다시 합치면서(conquer) 배열을 정렬한다. Complexity: O(n log n) 으로 안정적이다. Quick sort Sorting 방법 중 하나. 하나의 pivot을 잡아 왼쪽에 pivot보다 작은 수들을, 오른쪽에 pivot보다 큰 수들을 놓은 다음, 좌, 우로 나누어 다시 pivot을 잡고 위의 과정을 진행한다. Complexity: O(n log n), O(n^2) (worst case) Binary search 정렬되어 있는 배열에서 원하는 원소를 O(log n)만에 찾는 방법. int binary_search(int num[], int from, int to, int ta.. 2022. 1. 23. 그리디 & 완전 탐색 & DP 그리디 마주하는 모든 문제들이 그리디로 풀리는 문제인지 일일이 증명할 수 없으므로 직관 + 판수로 감각을 익혀야겠다. 문제를 푸는 방법이 바로 떠오르지 않을 때 한 번쯤은 혹시 그리디로 풀리나? 하고 의심하는 것도 좋은 방법일 듯. 완전 탐색 개인적으로 문제를 접근함에 있어 가장 우선돼야 하는 방법이라고 생각한다. 완전 탐색으로부터 시작하여 규칙을 찾아내든, dp를 이용하여 연산 횟수를 효과적으로 줄이던지 문제를 이해하기 가장 좋은 접근 방법이다. DP 까다로운 문제가 있었다. state를 나타내기에 필수적으로 필요한 정보들을 잘 생각해봐야겠다. + 같은 상태를 나타내더라도 어떤 정보를 사용하는가에 따라 메모리 크기 차이가 날 수 있다. 잘 고려해주자. P (Polynomial) All decision .. 2022. 1. 21. 이전 1 ··· 4 5 6 7 8 9 10 11 다음
