밤이 블로그

BOJ#3653 영화 수집 * 문제https://www.acmicpc.net/problem/3653 * 풀이저는 팬윅 트리를 완전히 마스터하지 못해서이 문제를 세그먼트 트리를 이용해서 풀었습니다. 따라서 코드가 상당히 길고 최적화된 솔루션이 아닙니다. 다음에 기회가 되면 팬윅 트리를 이용해서 다시 풀어보도록 하겠습니다. , 3 3 3 1 1답 : 2 1 0 위 예제를 보면 일단 최초에는 아래와 같이 영화가 쌓여 있을 것입니다.[1번 영화, 2번 영화, 3번 영화] 문제를 쉽게 풀기 위해서 위 배열을 다음과 같이 변형해봅시다.사이즈를 n에서 n+m으로 늘렸습니다.[0, 0, 0, 1, 2, 3] 1) 3번 영화를 꺼낼 때, 앞에 영화 2개가 쌓여있다[0, 0, 0, 1, 2, 3] -> [0, 0, 3, ..

BOJ#6549 히스토그램에서 가장 큰 직사각형 * 문제https://www.acmicpc.net/problem/6549 * 풀이세그먼트 트리 + 분할정복으로 풀었습니다.어려워서 많이 고생한 문제입니다. - 구하는 것 : 히스토그램에서 가장 큰 직사각형 - 히스토그램은 막대의 집합이고, 모든 막대 x에 대하여 막대 x의 높이로 하면서 만들 수 있는 가장 큰 직사각형들을 구해봅시다.- 어떤 막대 x에 대하여 양쪽으로 직사각형을 확장해나가면, 막대 x 높이로 만들 수 있는 가장 큰 직사각형을 구할 수 있습니다. - 우리는 그것들 중 가장 큰 직사각형을 구하면 됩니다. - 그렇다면 [2 1 4 5 1 3 3]의 히스토그램이 주어졌을 때, 어떤 순서로 막대를 검사하면 될까요- 가장 작은 막대부터 (높이가 작은 ..

BOJ#14438 수열과 쿼리 17 * 문제https://www.acmicpc.net/problem/14438 * 풀이Segment Tree - RMQ설명 : http://stack07142.tistory.com/216 * 나의 코드 (Java, Kotlin)https://github.com/stack07142/BOJ/blob/cd23ff130cc6e28b7f30aea5c4bc8932dad8688b/BOJ%2314438_SequenceQuery17/src/Main.java (Java)import java.io.*; import java.util.StringTokenizer; /** * 선데이코딩 베타라운드1 - E. 수열의 최소값 * BOJ#14439 수열과 쿼리 17 * https://www.acmic..

BOJ#2042 구간 합 구하기 * 문제https://www.acmicpc.net/problem/2042 * 풀이 http://stack07142.tistory.com/216 * 나의 코드 https://github.com/stack07142/BOJ/blob/48ba119dd11b7779be8b2d1e05a64b723e334d54/BOJ%232042_RangeSumQuery/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * BOJ#2042 구간의 합 구하기 * https://www.acmicpc.net/problem/2042 */ public class Main { static final int QUERY_CHANGE = 1;..