문제 17435번: 합성함수와 쿼리 (acmicpc.net) 17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 www.acmicpc.net 풀이 정의역과 공역의 범위가 같은 functional graph가 주어졌으므로 무한히 합성가능합니다. n번 합성한 경우의 함수값을 결정하기 위해 n번 반복을 한다면 Q * n 으로 최대 200,000 x 500,000 의 연산량이 발생해버립니다. 따라서 다른 방법을 사..
자료구조
문제 11505번: 구간 곱 구하기 (acmicpc.net) 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 배열이 주어지고 배열의 구간의 대한 값을 물어보는 문제입니다. 값을 가져오는 것 말고도 변경하는 작업도 해야하기 때문에 구간합과 같은 배열을 이용하기 보단, 세그먼트 트리를 이용해야 합니다. 세그먼트 트리의 구현에 대한 문제이므로 세그먼트 트리를 먼저 공부한 뒤 푸는것이 좋습니다. 이 문제에서 주의할 점은 구간의 곱을 구하기 때문에 구간..
세그먼트 트리 세그먼트 트리는 특정 구간의 최대값, 최소값, 합, 곱 등을 빠르고 간단하게 구할 수 있게 해주는 자료구조 입니다. 예를 들어 배열 arr = [1, 3, 2, 5, 7, 3, 5] 에서 3 ~ 7 번째 수 까지의 구간합을 구한다고 가정해봅시다. 가장 단순한 방법으로는 선형적으로 3번부터 8번까지의 수를 더하며 구할 수 있습니다. 하지만 이 방법은 $O(n)$으로 n = 1,000,000,000 처럼 크다면 상당히 부담되는 연산량입니다. 그래서 누적합을 미리 구해 구간합을 구하는 방법도 있습니다. prefixSum = [0, 1, 4, 6, 11, 18, 21, 26] 을 구한 뒤 prefixSum[7] - prefixSum[2]을 계산하여 구간합을 얻을 수 있겠죠. 문제는 배열의 값을 수..
