Algorithm (43) 썸네일형 리스트형 [백준 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, .. 이전 1 ··· 3 4 5 6 다음
