본문 바로가기

Algorithm/Data Structure10

BOJ G4 7662 이중 우선순위 큐 JAVA 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제 읽기 처음 문제를 읽었을 때는 시간 제한이 6초이고, T의 범위가 나와있지 않아서 좀 당황했었다.. 어쨌든 문제를 해결하려는데, 저번에 IOIOI를 풀었을 때처럼 한 번에 연산이 되는 게 아니라서 생각을 좀 했었다. 문제 풀이는 다음과 같은 과정을 통해 이루어졌다. ArrayList 1개와 이진 삽입 정렬 - 시간 초과 우선순위 큐 2개와 Map - OK TreeMap 사용하기 - Good 문제 풀기 ArrayList 1개와 이진 삽입 정렬 - 잘못된 .. 2024. 3. 26.
BOJ G1 11505 구간곱 구하기 JAVA 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)는 영어 뜻 자체로는 분할, 단편, 구분 등의 의미를 가진다. 이는 특정 구간 내 데이터에 대한 연산 또는 쿼리를 빠르게.. 2024. 3. 4.
BOJ P5 6549 히스토그램에서 가장 큰 직사각형 JAVA 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 문제 읽기 확실히 어려웠다! 플레 문제는 역시 뭔가 다르다. 일단 처음에 이 문제를 봤을 때는 감이 전혀 오지 않았고, 일단 패스했었다. 입력 값이 너무 커서 엄두가 나지 않았다.. 그 당시에는 입력 값이 크면 DP?라는 생각밖에 없었기 때문에 풀지 못했다. 시간이 좀 지나고 다시 풀어봐야 겠다는 생각을 했고, 다시 봤지만, 역시나 잘 모르겠더라. 그래서 해당 알고리즘을 먼저 공부하고 해야겠다 싶어 알고리.. 2024. 3. 3.
BOJ G1 2357 최솟값과 최댓값 JAVA 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 문제 읽기 이번 문제는 어떤 자료구조를 사용하는지 알고 푸는 것이기 때문에 어렵지 않았다. 세그먼트 트리 자료구조를 공부했고, 이를 적용하면 쉽게 해결할 수 있는 문제이다. 세그먼트 트리에 관한 자세한 설명은 다음 포스팅에서 알아볼 수 있다. 세그먼트 트리, Segment Tree 세그먼트 트리, Segment Tree ❓ 세그먼트 트리, Segment Tree 세그먼트(Segment)는 영어 뜻 자체로는 분할, 단편, 구분.. 2024. 3. 1.

티스토리툴바