본문 바로가기
728x90

세그먼트 트리

[백준알고리즘] 2104번: 부분배열 고르기-C++ 2104번: 부분배열 고르기 (acmicpc.net) 2104번: 부분배열 고르기 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱 www.acmicpc.net 문제를 푸는데 되게 오래걸렸다. 처음에는 세그먼트 트리를 오랜만에 공부하려고 시작한 거라, 공부하는데 시간이 소요됐다. 그러고 나서는 어떻게 적용되면 좋을지 고민하느라 시간이 소요됐다. 마지막으로, 알 수 없는 '틀렸습니다'의 늪에서 헤어나오지 못했다. 게다가 하루에 30분 저도씩 밖에 시간을 못 쓰는 바람에 며칠이 걸.. 더보기
[백준알고리즘] 6549번: 히스토그램에서 가장 큰 직사각형-C++ 6549번: 히스토그램에서 가장 큰 직사각형 (acmicpc.net) 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 보니까 2년 전에 풀다가 말았던 문제인 것 같다. 파이썬으로 풀려고 시도했던 흔적이 남아있다. 플레티넘 5라고 해서 너무 쉬운 방법은 안 풀릴 거 같았다. 조금 생각해서 스택을 이용해 푸는 방법을 생각했고, 약간 지저분해 보여 조금 아이디어를 가다듬고 문제를 풀었다. 사실 바로 풀릴지 모르고 했는데 돼서 놀랬다. 해당 문제에 대한 게시판.. 더보기
[백준알고리즘] 1168번: 요세푸스 문제 2 -C++ [백준알고리즘] 1168번: 요세푸스 문제 2 -C++ 1168번: 요세푸스 문제 2 (acmicpc.net) 1168번: 요세푸스 문제 2 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000) www.acmicpc.net 예전에 Python으로 코테 문제를 풀었을 때 \(O(NK)\) 만에 통과하는 코드로 풀었다. 아래가 해당 글의 링크다. [백준알고리즘] 1158, 1168번: 요세푸스 문제, 요세푸스 문제 2 -Python (tistory.com) [백준알고리즘] 1158, 1168번: 요세푸스 문제, 요세푸스 문제 2 -Python [백준알고리즘] 1158, 1168번: 요세푸스 문제, 요세푸스 문제 2 -Python https://www.acmic.. 더보기
728x90

티스토리툴바