Partially Committed

기업 코테에서 세그먼트 트리를 요구하는 경우는 흔치 않은 것 같지만 필요한 일이 생겨서 이참에 정리해보려고 한다.. 값이 변하지 않는 데이터가 주어졌을 때, 구간 합을 빠르게 구하는 방법은 prefix sum 을 이용하면 된다. https://www.crocus.co.kr/843 구간 합(Prefix Sum) 알고리즘 목차 1. 구간 합(Prefix Sum)이란? 2. 구간 합(Prefix Sum)이 어디에 쓰일까? 3. Prefix Sum Algorithm 4. Prefix Sum이 쓰이는 문제들 1. 구간 합(Prefix Sum)이란? 공부를 하다보면 부분 합, 구간 합의 개념이 헷갈릴 때 www.crocus.co.kr 만약, 데이터가 변한다면 Fenwick tree 를 구현해서 구간 쿼리를 효율적으..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net N 명의 선수가 선분을 번갈아가면서 그리는 게임을 M 차례까지 진행했을 때, 중간에 사이클이 생긴다면 사이클이 생겼던 회차를, M 번 진행하는 동안 사이클이 발생하지 않았다면 0 을 출력하면 된다. 예제를 통해 생각해보자. 0 과 1 을 선택하여 0-1 선분을 긋는다는 것은 0 과 1 은 같은 집합으로 Clustering 된다는 것이다. m 번의 회차마다 주어지는 두 포인트를 같은 집합으로 ..

본 포스팅은 자바의 정석 교재를 공부하며, 간단히 정리/기록 용도로 작성하였습니다. 혹여, 잘못된 내용이 있다면 지적해주시면 감사하겠습니다. 0. Collections Framework Collections Framework 란 data group 을 다루고 표현하기 위한 단일화된 architecture 을 말한다. Collections Framework 의 핵심 인터페이스는 List, Set, Map 이다. List 는 (순서가 있는) 데이터의 중복을 허용하며 ArrayList, LinkedList, Stack, Vector 등으로 구현된다. Set 은 (순서가 없는) 데이터의 중복을 허용하지 않는 것으로 HashSet, TreeSet 등으로 구현된다. Map 은 key - value pair 로 이뤄..