백준/자료구조39 백준 17353 c++ "하늘에서 떨어지는 1, 2, ..., R-L+1개의 별" -PlusUltraCode- https://www.acmicpc.net/problem/17353 [필자 사고]이 문제는 세그먼트 자료구조를 이용하는 거다.다만 이 문제만의 특별한 점은 느린 세그먼트 자료구조를 이용하고해당 lazy배열을 열이 2개 행이 4*N 형태로 설정하여 첫번째 열에는 시작점 두번째 열애는 공차를 저장하는 형태로문제를 해결해야 된다. [코드 해설]1. SegmentTree 구조체SegmentTree는 세그먼트 트리와 lazy propagation을 구현한 구조체로, 세그먼트 트리 초기화, 구간 업데이트, 점 단위 쿼리 등을 제공합니다.주요 멤버 변수:segment_tree: 세그먼트 트리의 노드 값을 저장하는 벡터.lazy_updates: lazy propagation 처리를 위한 배열로, 구간 업데이트 정보를 .. 2025. 1. 20. 백준 18135 c++ "겨울나기" -PlusUltraCode- https://www.acmicpc.net/problem/18135[필자 사고]이 문제는 세그먼트 자료구조를 이용하여 푸는 문제이다.이 문제만의 특이점은 경로가 원형으로 되어 있다는 점이다.또한 특정 범위에 들어가면 갯수를 얻는 시스템이다 보니 좌표 압축을 해야 된다. 이 두가지 점만 신경쓰면 해결할 수 있다. [코드 해설]1. 세그먼트 트리 초기화 (Init_Tree 함수)Init_Tree 함수는 세그먼트 트리를 초기화합니다. 배열 arr의 값을 기반으로 세그먼트 트리를 구성하며, 다음과 같은 방식으로 작동합니다:기저 사례: start와 end가 같으면 리프 노드에 arr[start] 값을 설정합니다.재귀 호출: 현재 구간을 절반으로 나누어 왼쪽과 오른쪽 자식 노드를 초기화한 후, 두 자식 노드의 합.. 2025. 1. 20. 백준 15899 c++ "트리와 색깔" -PlusUltraCode- https://www.acmicpc.net/problem/15899 [필자 사고]이 문제는 세그먼트 자료구조를 이용하여 푸는 문제이다. 먼저 위계질서가 정해져 있으므로 DFS를 이용하여 index를 세그먼트화 해야 된다.또한 자신의 값들도 있으므로 세그먼트화 된 index에 맞게 해당 값들도 저장해야 된다. C보다 적은값의 갯수를 묻고 있으므로 c+1로 lowerBound하면 갯수를 구할 수 있다. 또한 정점 V의 서브트리라고 했으니 정점 V를 포함하여 index[a].first 부터 시작하면 된다. 정밀하지 않으면 실수가 많은 문제이다. 또한 많은 알고리즘이 들어가 있어서 배울수 있는 문제이다.[코드 해설]2. 입력 처리 (Input 함수)Input() 함수는 사용자 입력을 받아 데이터를 초기화합니다... 2025. 1. 19. 백준 2820 c++ "자동차 공장" -PlusUltraCode- https://www.acmicpc.net/problem/2820 [필자 사고]이 문제는 세그먼트 트리 자료구조를 이용해서 풀어야 되는 문제이다.다만 이 문제만의 재미난 점은 세그먼트 index를 설정해야 되는데 그게 dfs탐색을 이용한 오일러 알고리즘을 통해index들을 새로 정의 해야 된다. 또한 새로 정의된 index를 바탕으로 월급또한 같이 재정의 해야된다는 점이다. DFS알고리즘을 잘 수행했따면 Propagation 으로 느린전파 알고리즘을 이용하여 Update의 범위 쿼리를 갱신해주면 문제를 풀 수 있게 된다.여기서 필자는 1-based로 시작했기 때문에 index[a].first 가 의미하는 거는 a의 실제 index자신을 의미하므로 a보다 부하를 원하면 index[a].first +1 을 .. 2025. 1. 18. 이전 1 2 3 4 ··· 10 다음
