7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제 읽기 처음 문제를 읽었을 때는 시간 제한이 6초이고, T의 범위가 나와있지 않아서 좀 당황했었다.. 어쨌든 문제를 해결하려는데, 저번에 IOIOI를 풀었을 때처럼 한 번에 연산이 되는 게 아니라서 생각을 좀 했었다. 문제 풀이는 다음과 같은 과정을 통해 이루어졌다. ArrayList 1개와 이진 삽입 정렬 - 시간 초과 우선순위 큐 2개와 Map - OK TreeMap 사용하기 - Good 문제 풀기 ArrayList 1개와 이진 삽입 정렬 - 잘못된 ..

11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 읽기 이 문제는 앞서 풀었던 세그먼트 트리를 활용한 문제이다. 구간 합 구하기와 크게 다를 건 없다. 세그먼트 트리를 이용하면 된다. 세그먼트 트리, Segment Tree 세그먼트 트리, Segment Tree ❓ 세그먼트 트리, Segment Tree 세그먼트(Segment)는 영어 뜻 자체로는 분할, 단편, 구분 등의 의미를 가진다. 이는 특정 구간 내 데이터에 대한 연산 또는 쿼리를 빠르게..

6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 문제 읽기 확실히 어려웠다! 플레 문제는 역시 뭔가 다르다. 일단 처음에 이 문제를 봤을 때는 감이 전혀 오지 않았고, 일단 패스했었다. 입력 값이 너무 커서 엄두가 나지 않았다.. 그 당시에는 입력 값이 크면 DP?라는 생각밖에 없었기 때문에 풀지 못했다. 시간이 좀 지나고 다시 풀어봐야 겠다는 생각을 했고, 다시 봤지만, 역시나 잘 모르겠더라. 그래서 해당 알고리즘을 먼저 공부하고 해야겠다 싶어 알고리..

2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 문제 읽기 이번 문제는 어떤 자료구조를 사용하는지 알고 푸는 것이기 때문에 어렵지 않았다. 세그먼트 트리 자료구조를 공부했고, 이를 적용하면 쉽게 해결할 수 있는 문제이다. 세그먼트 트리에 관한 자세한 설명은 다음 포스팅에서 알아볼 수 있다. 세그먼트 트리, Segment Tree 세그먼트 트리, Segment Tree ❓ 세그먼트 트리, Segment Tree 세그먼트(Segment)는 영어 뜻 자체로는 분할, 단편, 구분..

세그먼트 트리, Segment Tree ❓ 세그먼트 트리, Segment Tree 세그먼트(Segment)는 영어 뜻 자체로는 분할, 단편, 구분 등의 의미를 가진다. 이는 특정 구간 내 데이터에 대한 연산 또는 쿼리를 빠르게 구할 수 있는 트리이다. 보통 특정 구간 합, 최솟값, 최댓값, 평균값 등을 구할 때 활용한다. [시간 복잡도] 데이터 변경 : O(logN) 연산 : O(logN) 데이터 변경할 때마다 연산하기 M번 : O((logN + logN) * M) = O(MlogN) 선형 탐색을 이용한 구간 합 구하기 ‘특정 구간의 합을 구해라’는 말을 보면 가장 단순하게 생각할 수 있는 방법은 바로 선형 탐색이다. 다음과 같은 배열 {1, 2, 3, 4, 5}에서 2번 구간부터 4번 구간까지의 합을 ..

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 읽기 문제를 읽어보면 결국 사람은 두 분류로 나뉘게 된다. 지민이의 (진실을 아는 사람 + 알게 될 사람 / 전혀 모를 사람) 이 두 분류만 확실하게 구분하면 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티의 최대 개수를 구할 수 있을 것이다. 진실을 아는 쪽이 하나라도 포함되어 있는 파티에서는 거짓말을 치지 못할 것이고, 그 외에 전혀 모를 사람에게는 거짓말을 칠 수 있을 것이다. 이러한 부분을 봤을 때, 유니온 파인드를 쓰면 빠르게 해결할 수 있..