개발일지

www.acmicpc.net/problem/2449 2449번: 전구 입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전 www.acmicpc.net 접근 1) dp[left][right][color] 재귀함수로 구간에 특정 color로 색칠하는 방법을 고민했다. => 실패 이유는 모르겠다. 2) dp[left][right] 하지만 구간을 나누고 특정 color로 색칠할 필요가 없었다. => left의 색이나 right의 색으로 칠하는 것이 자명하기 때문이다. dp[left][right] = min(dp[left][i] + dp[i + 1][righ..

www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net 접근 처음에 Disjoint-Set과 LCA를 고민했다. Disjoint-Set을 고민한 이유는 간선을 추가할(샘플을 측정) 때 Disjoint-Set의 Union연산을 통해 하나의 Set으로 만들고, Find연산으로 쉽게 UNKNOWN인지 알 수 있기 때문이다. LCA를 고민한 이유는 무게차이를 구할 때 공통 조상 노드를 찾아서 거리를 구하면 logN만에 쉽게 거리를 찾을 수 있기..

개념 CCW 알고리즘을 이용하여 두 선분이 교차하는지 판별할 수 있다. 작동원리 위 예시를 보면 CCW(A, B, C)와 CCW(A, B, D)가 반대방향(곱이 음수)이면 두 선분은 교차한다고 볼 수 있다. 하지만 위 예시와 같은 반례가 존재한다. (직선이 아닌 선분이기 때문에 CCW의 방향이 반대여도 교차하지 않을 경우가 있다.) 그렇기 때문에 CCW(A, B, C)와 CCW(A, B, D)의 방향, CCW(C, D, A)와 CCW(C, D, B)의 방향 두 번을 검사하여 교차하는지 확인할 수 있다. 하지만 두 선분이 같은 직선에 있을 경우 CCW가 0이 나온다. 위와 같은 반례는 CCW(A, B, C) * CCW(A, B, D) == 0 && CCW(C, D, A) * CCW(C, D, B) == 0..

개념 유한 집합의 합집합의 원소의 개수를 세는 기법이다. 작동원리 즉 겹치는 부분이 홀수면 더하고, 겹치는 부분이 짝수이면 뺀다. 시간복잡도 집합의 갯수가 N일 때 O(2^N) 문제 www.acmicpc.net/problem/17436 17436번: 소수의 배수 첫째 줄에 N(1 ≤ N ≤ 10)과 M(1 ≤ M ≤ 1012)이 주어진다. 둘째 줄에는 N개의 소수가 주어진다. 입력으로 주어지는 소수는 100보다 작거나 같으며, 같은 소수가 두 번 이상 주어지지 않는다. www.acmicpc.net 코드 #include using namespace std; using Int = int; using Long = long long; int main() { ios::sync_with_stdio(false); c..

개념 오일러의 피 함수는 N이 주어 졌을 때 1 ~ N의 숫자중 N과 서로소인 숫자의 개수를 찾는 함수이다. 작동원리 1. p가 소수인 경우 소수인 경우 약수가 1과 자기 자신밖에 없으므로 자기 자신을 제외한 모든 수와 서로소이다. 2. 소수 p의 거듭제곱인 경우 소수 p의 거듭제곱과 서로소가 아닌 경우는 p의 배수일 경우이다. 즉 p, 2p, 3p .... p^(k-1) * p => p^k - p^(k-1)이다. 3. n과 m이 서로소인 경우 n과의 서로소의 곱과 m과 서로소의 곱은 n*m과 서로소이다. 결론 n을 소인수 분해했을 때 p1^a1 * p2^a2 * p3^a3 ... pn^an꼴이 나오면 다음이 성립한다. 문제 www.acmicpc.net/problem/11689 11689번: GCD(n,..

개념 위 그림은 911, 91125, 97625 저장했을 때 트리의 예시이다. 트라이는 문자열을 효율적으로 관리하기 위한 트리구조이다. 접두사를 노드에 하나씩 저장하고 접두사를 제외한 문자열을 자식 노드에 저장하는 트리구조이다. (접두사를 저장한다고 해서 Prefix Tree라고도 불림) 작동원리 문자열의 앞부터 차근차근 트리를 탐색하여 문자를 찾기 때문에 검색 속도는 빠르지만 각 노드별로 모든 문자를 저장할 배열이 필요하기 때문에 메모리가 많이 든다. * 메모리 크기 : 포인터 크기 * 배열의 길이(저장하는 문자의 수) * 총 노드의 개수 시간 복잡도 저장 : O(L) 검색 : O(L) 문제 www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 ..

개념 Segment Tree에서 구간의 Update를 빠르게 처리하기 위한 방법이다. Segment Tree에서 Update의 시간 복잡도는 O(logN)이기 때문에 구간의 길이가 L인 Update의 시간 복잡도는 O(LlogN)이기 때문에 쿼리의 수가 많은 경우 시간초과를 받을 수 있다. Lazy Segment Tree는 Update를 필요한 시기에 Update하도록 미루면서 Range Update를 O(logN)으로 수행할 수 있다. 작동원리 구간을 Update할 경우 Segment Tree에서 참조하는 Node만 Update를 진행하고, 자식 노드의 Update는 Lazy Tree에 기록하여 Update를 미룬다. 시간 복잡도 init : O(NlogN) update : O(logN) update_..

개념 각 노드에 구간의 정보를 저장하여 Query, Update를 빠르게 처리할 수 트리다. 작동원리 트리로 구간의 정보를 저장하여 최악의 경우 트리의 높이만큼 트리를 탐색하여 Query와 Update를 수행할 수 있다. 트리의 성질 왼쪽 자식노드 : index * 2 오른쪽 자식노드 : index * 2 + 1 Query 참조하는 범위가 구간을 완전히 벗어나면 0을 Return한다. 참조하는 범위가 구간에 완전히 겹치면 Tree에 저장된 값을 Return한다. 참조하는 범위가 구간에 걸치면 Tree에 더 깊은 Level을 참조한다. 3-6 구간의 정보를 얻으려면 5, 6을 참조한다. 1-7 구간의 정보를 얻으려면 2, 6, 14를 참조한다. 1-8 구간의 정보를 얻으려면 1을 참조한다. Update 참..