공작소

문제 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, ST도 올바른 괄호 문자열이다. 모든 올바른 괄호 문자열은 위의 3개 규칙으로만 만들 수 있다. '('와 ')'로 이루어진 괄호 문자열 S = s1s2...sN과 M개의 쿼리가 주어진다. 쿼리는 두 정수 i, j (1 ≤ i ≤ j ≤ N)로 이루어져 있고, 쿼리가 의미하는 것은 다음과 같다. S의 부분 문자열 SiSi+1...Sj가 올바른 괄호 문자열이면 1, 아니면 0 모든 쿼리를 수행하고, 쿼리의 결과를 누적한 값을 구해보자. 입력 첫째 줄에 문자열 S가 주..

문제 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v: Ai = v로 변경한다. 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다. 입력 첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 1,000,000) 셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 넷째 줄부터 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. 1번 쿼리의 경우 1 ≤ i ≤ N, 1 ≤ v ≤ 1,000,000 이고, 2번 쿼리의 경우 1 ≤ i ≤ j ≤ N이고, 0 ≤ k ≤ (쿼리가 주어..

문제 N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오. 버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다. 입력 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |..

문제 그래프 G는 정점의 집합 V와 간선의 집합 E로 이루어져 있고, G = (V, E)로 나타낸다. 대부분의 경우에 V와 E는 명시되어 있다. 일부 그래프의 경우에는 집합이 명시되어 있지 않다. 예를 들어, 순열 그래프는 간선의 집합이 명시되어 있지 않다. {1, 2, 3, 4, 5}로 이루어진 두 순열 (2, 5, 4, 1, 3)과 (1, 5, 3, 2, 4)가 있다. 평행선을 그리고, 그 위에 순열에 적힌 숫자 순서대로 정점을 그린다. 그 다음 같은 숫자끼리 선분을 연결한다. 아래 그림과 같이 교차하는 선분의 쌍은 총 여섯 개라는 것을 알 수 있다. 교차하는 쌍은 순열 그래프의 간선이 된다. 순열 그래프의 정점은 숫자가 되고, 간선은 교차하는 쌍이 된다. 위의 예를 이용해 순열 그래프를 만들면 V ..

문제 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, ST도 올바른 괄호 문자열이다. 모든 올바른 괄호 문자열은 위의 3개 규칙으로만 만들 수 있다. '('와 ')'로 이루어진 괄호 문자열 S = s1s2...sN과 M개의 쿼리가 주어진다. 쿼리는 정수 하나 index로 이루어져 있고, 쿼리가 의미하는 것은 다음과 같다. S의 i번째 문자가 '('면 ')'로, ')'면 '('로 변경한다. 쿼리의 수행은 누적되며, i번째 쿼리는 i-1번째 쿼리가 수행된 결과에 수행되어야 한다. 각 쿼리를 수행한 결과가 올바른 괄호 문..

문제 중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 수열의 중앙값이다. 예를 들어, {1, 2, 6, 5, 4, 3}에서는 3이고, {11, 13, 12, 15, 14}에서는 13이다. 오세준은 1초에 온도를 하나씩 재는 온도계를 만들었다. 이 온도계에는 작은 디스플레이 창이 하나 있는데, 이 창에는 지금부터 최근 K초 까지 온도의 중앙값을 표시해 준다. (온도를 재기시작한지 K초부터 표시한다. 그 전에는 아무것도 출력되지 않는다.) 오세준은 온도를 N초동안 쟀다. 그 시간 동안 온도계의 디스플레이 창에 뜨는 숫자의 합을 구하는 프로그램을 작성하시오. 다른 말로 하면, 길이가 N인 수열이 주어진다. 이 수열은 N-K+1 개의 길이가 K인 연속된 부분..

문제 자연수를 저장하는 데이터베이스 S에 대해 다음의 쿼리를 처리합시다. 유형 1 : S에 자연수 X를 추가한다. 유형 2 : S에 포함된 숫자 중 X번째로 작은 수를 응답하고 그 수를 삭제한다. 입력 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니다. (1 ≤ X ≤ 2,000,000) T가 2라면 X는 S에서 삭제해야 할 몇 번째로 작은 수인지를 나타냅니다. S에 최소 X개의 원소가 있음이 보장됩니다. 출력 유형 2의 쿼리 개수만큼의 줄에 각 쿼리에 대한 답을 출력합니다. 풀이 과정 구간 합 세그먼트 트리를 만들어 들어오는 수 자..

문제 수정이는 어린 동생을 달래기 위해서 사탕을 사용한다. 수정이는 평소에 여러 개의 사탕을 사서 사탕상자에 넣어두고, 동생이 말을 잘 들을 때면 그 안에서 사탕을 꺼내서 주곤 한다. 각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕을 의미하며, 1,000,000은 가장 맛없는 사탕을 의미한다. 수정이는 동생이 말을 잘 들은 정도에 따라서, 사탕상자 안에 있는 사탕들 중 몇 번째로 맛있는 사탕을 꺼내주곤 한다. 예를 들어 말을 매우 잘 들었을 때에는 사탕상자에서 가장 맛있는 사탕을 꺼내주고, 말을 조금 잘 들었을 때에는 사탕상자에서 여섯 번째로 맛있는 사탕을 꺼내주는 식이다. 수정이가 보관하고 있는 사탕은 매우 많기 때문에 매번 사탕상자를 뒤져서 ..

문제 민호가 관리하는 천나라에는 N개의 집이 있다. 민호는 집을 쉽게 관리하기 위해 각각의 집을 1번, 2번, … N번으로 부르기로 했다. 어느 날 미적 감각에 눈을 뜬 민호는 특정 구간의 집들의 색들을 새롭게 칠하거나, 특정 구간의 집들에 존재하는 색의 수를 알고 싶어졌다. 작업은 다음과 같은 두가지로 이루어 진다. “C x y z” : x번과 y번, 그리고 그 사이에 있는 모든 집을 z번 색으로 색칠한다. “Q x y” : x번과 y번, 그리고 그 사이에 있는 모든 집에 존재하는 색의 가짓수를 출력한다. 민호가 사용할 색의 종류는 (1번, 2번, … T번) 이라 하고 처음 모든 집은 1번으로 색칠되어 있다고 생각한다. 민호가 해야하는 작업을 시뮬레이션 해보는 프로그램을 작성하자. 입력 첫 번째 줄에 ..

문제 각각 N(1 ≤ N ≤ 2,000)개의 쌍으로 이루어진 2N개의 정점과 M(1 ≤ M ≤ N×(N-1)/2)개의 간선으로 구성된 이분그래프가 주어질 때 서로 교차하는 총 개수를 구하는 것이다. 교차 조건 : 한 독립 집합 A와 다른 독립 집합 B가 연결된 두 개의 간선을 (A1, B1), (A2, B2)라 한다면 A1 B2 또는 A1 > A2, B1 < B2를 만족한다면 두 간선을 교차한다고 한다. 예를 들어 위에 예에서 (3, 2)는 (1, 5)와 (5, 1)과 교차한다. 이 문제를 해결하는 프로그램을 작성하시오. 입력 첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j..