개발자꿀꿀이

문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 1, 2, 3, 4, 5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 곱을 구하라고 한다면 240을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 곱을 구하라고 한다면 48이 될 것이다. 풀이 구간합 세그먼트 트리를 구간 곱으로 바꿔주는 것으로 풀었다. 1,000,000,007 로 나눈 나머지를 구하는 것이 문제기 때문에 구간 곱을 구할때 미리 modular 연산을 통해서 값을 구해 놓는다. 값을 update 할 때에도 같은 방식으로 modular 연산을 통해 미리 값을 1,000,000,007로 나눈 나머지..

문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다. 풀이 시간복잡도를 최소한으로 하기 위해서 segment tree(세그먼트 트리) 를 이용해서 풀었다 1. 부모노드의 값을 두개의 자식노드의 값중 작은 값으로 하는 것 ..

문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 풀이 세그먼트트리를 이용한 문제를 이해하는데 오래걸렸다. 1 ~ n 까지중 아직 제거되지 않은 수를 1로 두고 제거된 수를 0으로 둔 뒤 그 수들의 구간합을 세그먼트 트리로 구현한 트리를 이용해 문제를 푼다. 아..