본문 바로가기

전체 글

 (207)
[백준 16975] 수열과 쿼리 21 세그먼트 트리 응용문제 www.acmicpc.net/problem/16975 www.acmicpc.net/problem/2042 구간 합 세그먼트 트리를 처음 접한다면 위 문제를 먼저 푸는 것을 권장합니다. [문제 풀이] 수열이 주어지면 최대 100,000개의 쿼리를 처리하는 문제입니다. 쿼리는 두 종류입니다. 1. 특정 범위에 k를 더함 2. 수열의 특정한 위치의 값 출력 1번 쿼리 때문에 느리게 갱신되는 세그먼트 트리 문제처럼 보입니다. 실제로 느리게 갱신되는 세그먼트 트리로 풀 수 있습니다. 하지만 2번 쿼리를 잘 보면 구간의 합을 구하는 것이 아닌 특정한 값을 찾는 문제입니다. 2번 쿼리마저 구간의 합을 구하는 문제였다면 이 문제는 빼도 박도 못하고 느리게 갱신되는 세그먼트 트리 문제였겠지만, 2..
[붕어빵 꼬리먼저 팀] 1회차 - 학습 마무리 2021/01/05 동계 모각코 1회차 오늘 학습하고자 했던 분야인 Two pointer와 Meet in the middle에 대한 문제를 각각 하나씩 골라서 풀이하려 했습니다. 생소한 내용을 바로 코딩하다보니 모각코 활동 시간으로는 부족하여 Meet in the middle에 대한 문제는 풀이하지 못했습니다. 풀이한 부분까지 코드로 올리겠습니다. [Two pointer] www.acmicpc.net/problem/1644 에라토스테네스의 체를 응용한 두 포인터 문제입니다. 배열의 연속합 중 특정값 S와 같아지는 경우의 수를 구하는 문제입니다. 그러나 일반적인 배열이 아닌 소수로만 이루어진 배열입니다. N의 범위가 작으므로 에라토스테네스의 체를 사용하여 소수의 리스트를 구한 뒤, 해당 리스트에 두 포인터..
[붕어빵 꼬리먼저 팀] 1회차 - 학습 계획 2021/01/05 동계 모각코 1회차 알고리즘 모각코답게 백준 온라인 저지에서 알고리즘 문제를 풀면서 공부할 생각입니다. 같이 시작한 다른 팀과 함께 AVL트리를 공부할 생각이었으나, 개인 주제를 통해 실력을 향상시키고자 서로 개인 주제를 골라 공부하고 학습한 내용을 공유하는 방향으로 모각코를 진행할 계획입니다. 오늘 공부할 내용은 Two pointer와 Meet in the middle로 하겠습니다.
[백준 2629] 양팔저울 다이나믹 프로그래밍 문제 www.acmicpc.net/problem/2629 www.acmicpc.net/problem/5557 위 문제와 접근 방식이 비슷하므로 위 문제를 먼저 해결할 것을 권장합니다. [문제 풀이] 추가 N개 주어져 있을 때, 각 구슬에 대해 양팔저울의 수평을 맞출 수 있는가에 대한 문제입니다. 굳이 모든 추를 사용하지 않아도 되고, 구슬과 추의 위치에 대한 제한은 없습니다. 추의 개수가 30이고, 구슬의 개수가 7개이므로 제한이 작아 보입니다. 지금부터 구슬은 무조건 왼쪽으로 고정시킨다고 생각하겠습니다. 수평을 맞춰야 하므로 오른쪽에 추를 올리는 경우는 왼쪽의 무게를 -시키는 과정이라 생각할 수 있고 왼쪽에 추를 올리는 경우는 당연히 왼쪽의 무게를 +시키는 과정이라 생각할 수 있습니..
[백준 17435] 합성함수와 쿼리 희소 배열 문제 www.acmicpc.net/problem/17435 희소 배열 기초입니다. www.acmicpc.net/problem/11438 응용을 원한다면 위 문제도 풀어보는 것을 권장합니다. [문제 풀이] 1부터 m까지의 수에 대해 f(x)가 주어졌을 때, n번 합성한 합성함수를 구하는 문제입니다. 걸핏 보면 간단한 문제처럼 보입니다. m개의 f(x)를 알고 있으니 n번만큼 x = f(x)를 반복하면 가볍게 해결이 가능합니다. 그러나 쿼리의 개수가 200000개, 거슬러 올라가야 하는 n의 제한이 500000이므로 단순히 x = f(x)만 반복한다면 O(nQ)의 시간 복잡도가 나오게 되고, 당연히 시간 초과가 나게 됩니다. 즉, 푸는 방법은 간단하지만 시간 복잡도를 향상시켜 풀어야 하는 문제입니..
[백준 13352] 석양이 진다... CCW 문제 www.acmicpc.net/problem/13352 www.acmicpc.net/problem/11758 CCW에 대해 모른다면 위 문제를 먼저 푸는 것을 권장합니다. [문제 풀이] N개의 점들이 주어졌을 때 점들이 두 개 이하의 직선을 이루는지 판별하는 문제입니다. 이 문제가 어렵게 느껴지는 이유는 어떻게 점들을 두 직선에 넣는지에 대한 생각이 어렵기 때문입니다. 점을 기준으로 생각한다면 모든 점을 탐색하면서 직선이 두 개 이하로 나오는지 검사하는 방법 말고는 떠오르지 않습니다. 그리고 단순히 완전 탐색을 하려 한다면 N의 최대 제한이 100이어도 통과하기 어려워 보입니다. 그렇다면 점이 아닌 직선을 기준으로 생각해봅시다. 두 직선을 만들어 놓고 점들이 직선에 포함되는지 확인만 한다면, ..
[백준 19577] 수학은 재밌어 오일러 피함수 문제 www.acmicpc.net/problem/19577 www.acmicpc.net/problem/11689 오일러 피함수를 모른다면 위 문제를 먼저 푸는 것을 권장합니다. [문제 풀이] n이 주어졌을 때 xφ(x) = n를 만족하는 가장 작은 x를 출력해야 합니다. n보다 작은 x(1 1: e //= cur; e *= cur - 1 return e N = int(input()) if N == 1 or N == 2: print(N) elif N % 2 == 1: print(-1) else: arr = [1, 2] for i in range(3, int(N**(1/2)) + 1): if (N % i == 0): arr.append(i) for i in range(len(arr) - 1, ..

티스토리툴바