공부공간

https://www.acmicpc.net/problem/12846 12846번: 무서운 아르바이트 성화는 악독하기로 유명한 편의점 사장이다. 그의 편의점에는 특이한 임금 체계를 가지고 있다. 각 날마다 일의 차이때문에 일마다 급여가 정해져 있다. 돈은 당일에 주지 않고 퇴직을 할 때 한 www.acmicpc.net 연속한 수열에서 가장 최솟값을 기준으로 얻을 수 있는 총합의 가장 큰 값을 고르는 문제이다. 문제상황을 잘 읽어보면, https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,00..

https://www.acmicpc.net/problem/1306 1306번: 달려라 홍준 첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 www.acmicpc.net 길이가 N인 수열에서, 내가 현재있는 index 에서 [index-(M-1) , index+(M-1)] 에서 가장 큰 값을 찾으면 된다. N = 100만 이므로, N^2의 풀이보다는 NlogN의 풀이인 세그먼트 트리를 이용하여, N개의 쿼리를 처리해주자, 위문제는 O(NlogN+N) 에 처리가 가능하다. 즉, 구간의 최댓값을 저장하는 배열을 세그먼트 트리로 만들면 된다. i..

www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net N이 10만이기때문에 일반적인 모든구간을 탐색하는 N^2풀이시 시간초과를 만나게된다. 복잡도를 줄이기위해 어떤 직사각형을 생각해보면 그 높이는 입력으로 들어온 것들중 한개일 것이다. 너비는 적당한 구간일 것이고, 따라서 높이를 N개 탐색하는데, 구간에 대해서 최솟값을 반환해주는 함수가있다면, 높이를 최소부터 최대까지 탐색할수 있을것이다. 그러면 구간 점 ..

https://www.acmicpc.net/problem/2268 2268번: 수들의 합 첫째 줄에는 N(1≤N≤1,000,000), M(1≤M≤1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는지를 �� www.acmicpc.net 세그먼트트리의 기본꼴인 연속합을 구하는 문제이다. 세그먼트트리는 O(NM)의 시간복잡도를 O(LogN)으로 줄여주는 자료구조이다. 기본예제를 충분히 연습하고 Fenwick 트리로 넘어가야겠다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; ..

https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net https://algorithmstudy-mju.tistory.com/128 BOJ - 2357 ) 최솟값과 최댓값 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 구간쿼리대 점갱신에 대표적인 예로, 구간에서 최댓값 최솟값 누적합.. 등등을 물어보는 쿼리에 대해 LogN에 처리하기위해 전처리를 해준다. 사실 딱히 설명할게없다.. 세그먼트트리 응용과 구간쿼리 구간갱신을 위한 Lazy Propagation을 공부해야겠다. import java.io.BufferedReader; import java.io.InputStreamR..

https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합� www.acmicpc.net 주말에 할게 없어서 세그먼트 트리를 복습하며 문제를 풀었다.. ( 사실할게많은데 안하는것뿐 ) 세그먼트 트리는 Divide and Conquer를 기반으로 자료를 관리하는 자료구조이다. 적절한 Query에 대해서, 그노드가 해당되었는지의 여부를 한판하고 재귀함수를통해 처리해준다. import java.io.BufferedReader; import java.io.In..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 www.acmicpc.net 연속 합을 구하는 문제에서 Segment Tree 와 Fenwick Tree를 자주 사용하는데, Segment Tree로 위 문제..