알고리즘/세그먼트 트리
-
BOJ 2243 사탕상자알고리즘/세그먼트 트리 2021. 11. 29. 08:37
https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net solved의 class 6에 속해있는 문제이다. 생각보다 금방 풀려서 난이도 기여를 해볼까 했는데 스탠다드였다. 플레5 치고는 쉽게 풀리는 문제이니 도전해보면 좋을 듯 하다. 문제를 딱 읽어보면 이분탐색이라는 느낌이 확 온다. 현재 보유하고 있는 사탕중 n번째로 맛있는 사탕을 꺼내면 되기 때문이다. 하지만 문제는 보유하고 있는 사탕의 현황이 계속 바뀐다. 따라서 사탕의..
-
BOJ 6549 히스토그램에서 가장 큰 직사각형알고리즘/세그먼트 트리 2021. 11. 24. 23:53
소마 코테 이후로 거의 8달 가까이 놓고있던 알고리즘 문제풀이를 다시 시작했다. 기억을 되살리기 위해서 템플릿을 보지 않고 기억에 의존해서 코드작성을 했는데, 생각보다 많은것을 아직 기억하고 있어서 다행이다. https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 이 문제는 사실 군복무 전인 2018년 쯤부터 알고 있던 문제였으나, 접근방법을 몰라서 손도 대지 않고 있던 문제였다. 이후에도 몇번..
-
BOJ 1395 스위치알고리즘/세그먼트 트리 2021. 3. 22. 10:31
www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 레이지 프로퍼게이션을 공부한지 한달 조금 안되었다. 구간합을 구하는 것에 더해서 구간 업데이트까지 가능하다고?? 정말 대단한 알고리즘이다. 하여간 이걸 연습해야 하는데.. 레이지 프로퍼게이션에는 오일러 경로 테크닉이 자주 따라오는 거 같다. 이건 모르는거니 필요없는 것중에 연습을 좀 하고 있는데 굉장히 멋있는 문제인것 같아서 풀어봤다. 보통 레이지프로퍼게이션 입문은 구간합..