개인사

[P3] 백준 12895번 화려한 마을 C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리, 비트마스킹

리뷰 https://www.acmicpc.net/problem/12895맞왜틀 하고 있는데 질문게시판에서 쿼리의 범위 중 L이 R보다 크게 나오는 케이스가 있다는 것을 봤다.그걸 해결해주니 AC를 받았는데 음 문제에 기재하거나 예제에 있었으면 좋겠다는 생각이 들었다.로직은 맞게 구현해도 이런 것 때문에 틀린다면 시간을 많이 날릴 것 같다.  전역 변수N : 인덱스의 최대 크기를 저장할 상수 변수n : 집의 개수를 저장할 변수t : 사용할 색의 개수를 저장할 변수q : 작업의 개수를 저장할 변수tree : 세그먼트 트리 정보를 저장할 배열lazy : 업데이트 정보를 저장할 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = ..

[P5] 백준 1777번 순열복원 C++ 세그먼트 트리

리뷰 https://www.acmicpc.net/problem/1777[P4] 백준 1849번 순열 C++ 세그먼트 트리 [P4] 백준 1849번 순열 C++ 세그먼트 트리리뷰 https://www.acmicpc.net/problem/1849구간 합 세그먼트 트리를 통해 답을 도출하는 문제  전역 변수N : 배열의 최대 크기를 저장할 상수 변수n : 수열 원소의 개수를 저장할 변수s : 매 원소를 입력zzzz955.tistory.com위 문제의 반대 버전  전역 변수N : 순열의 최대 크기를 저장할 상수 변수n : 순열의 크기를 저장할 변수s : 각 인버전 시퀀스 값을 저장할 변수lst : 순열의 인버전 시퀀스를 저장할 배열ans : 순열의 요소를 저장할 배열tree : 세그먼트 트리 정보를 저장할 배열..

[P4] 백준 1849번 순열 C++ 세그먼트 트리

리뷰 https://www.acmicpc.net/problem/1849구간 합 세그먼트 트리를 통해 답을 도출하는 문제  전역 변수N : 배열의 최대 크기를 저장할 상수 변수n : 수열 원소의 개수를 저장할 변수s : 매 원소를 입력 받을 변수lst : 초기엔 모두 1로, 이후엔 수열의 순서로 저장할 배열tree : 세그먼트 트리 정보를 저장할 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = lst[s]; else { int mid = (s + e) / 2; build(node * 2, s, mid); build(node * 2 + 1, mid + 1, e); tree[node] = tree[node * 2] +..

리뷰 https://www.acmicpc.net/problem/11962구간 업데이트 + 최소값 및 구간합 세그먼트 트리 문제  전역 변수N : 배열 크기의 최대값을 저장할 상수 변수n : 배열의 크기를 저장할 변수q : 쿼리의 개수를 저장할 변수lst : 배열의 초기값을 저장할 배열MS : 세그먼트 트리의 최소값 M, 구간 합 S를 정의할 구조체tree : 세그먼트 트리 정보를 저장할 MS타입 배열lazy : 세그먼트 트리의 느린 업데이트 처리를 위한 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = { lst[s], lst[s] }; else { int mid = (s + e) / 2; build(node * 2,..

리뷰 https://www.acmicpc.net/problem/2934문제를 봤을 때 이해가 잘 되지 않았는데 예시 그래프를 보고 이해 된 내용으로 시도했다.  전역 변수N : 좌표의 최대 범위를 저장할 상수 변수n : 식물을 심은 날의 수를 저장할 변수tree : 세그먼트 트리 정보를 저장할 배열lazy : 업데이트 정보를 저장할 배열 함수1. propagatevoid propagate(int node, int s, int e) { if (lazy[node]) { tree[node] += (e - s + 1) * lazy[node]; if (s != e) { lazy[node * 2] += lazy[node]; lazy[node * 2 + 1] += lazy[node]; } lazy[no..

리뷰 https://www.acmicpc.net/problem/18227오일러 경로를 구할 때 노드의 깊이를 구해준 후 구간합 쿼리에 해당 깊이를 곱해준 뒤 출력하는 문제회사 문화 문제와 비슷하나 노드의 깊이를 구해주어야 하는 조건이 추가된 문제  전역 변수N : 배열의 최대 크기를 저장할 상수 변수n : 도시의 수를 저장할 변수c : 수도의 번호를 저장할 변수q : 쿼리의 개수를 저장할 변수tree : 세그먼트 트리 정보를 저장할 배열it : 오일러 경로의 진입 시점을 저장할 배열ot : 오일러 경로의 탈출 시점을 저장할 배열dep : 노드의 깊이를 저장할 배열t : 오일러 경로의 시간을 저장할 변수edges : 인접 리스트를 저장할 벡터 배열 함수1. dfsvoid dfs(int level, int ..

리뷰 https://www.acmicpc.net/problem/9345누적합, 최대, 최소 세그먼트 트리 모두 사용하여 AC를 받았다.  전역 변수N : DVD수의 최대값을 저장할 상수 변수t : 테스트 케이스의 개수를 저장할 변수n : DVD의 개수를 저장할 변수k : 쿼리의 개수를 저장할 변수lst : DVD의 초기 위치를 저장할 배열presum : DVD의 초기 위치를 기준으로 누적합을 저장할 배열T : 세그먼트 트리의 누적합 SUM, 최대값 MAX, 최소값 MIN을 정의할 구조체tree : T타입의 세그먼트 트리를 요소를 저장할 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = { lst[s], lst[s], ls..

리뷰 https://www.acmicpc.net/problem/1321세그먼트 트리를 활용해 군인을 적절한 부대에 배치시키는 문제  전역 변수N : 배열의 최대 크기를 저장할 상수 변수n : 부대의 개수를 저장할 변수lst : 각 부대의 병사 수를 저장할 배열tree : 세그먼트 트리 정보를 저장할 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = lst[s]; else { int mid = (s + e) / 2; build(node * 2, s, mid); build(node * 2 + 1, mid + 1, e); tree[node] = tree[node * 2] + tree[node * 2 + 1]; }} 누적..

리뷰 https://www.acmicpc.net/problem/10090세그먼트 트리를 활용하여 배열 내 자신의 뒷 숫자 중 자기보다 작은 숫자의 개수를 구하는 문제  전역 변수N : 배열의 최대 길이를 저장할 상수 변수n : 배열의 길이를 저장할 변수tree : 세그먼트 트리 정보를 저장할 배열 함수1. buildvoid build(int node, int s, int e) 세그먼트 트리의 초기화를 진행할 함수매개 변수로 노드 정보 node, 탐색 구간 s, e를 전달 받는다.기저 조건으로 리프노드에 도달한 경우 현재 노드의 값을 1로 저장해 준다.좌, 우 자식 노드로 재귀를 진행하고, 재귀를 빠져나오며 현재 노드를 두 노드의 합으로 저장해 준다. 2. updatevoid update(int node,..

리뷰 https://www.acmicpc.net/problem/19598회의실의 개수와 관련된 문제들은 일반적인 회의실 문제와 좀 다른 것 같다.  전역 변수n : 회의의 개수를 저장할 변수lst : 회의의 시작과 종료 시간을 저장할 배열 함수없음  문제풀이n값을 입력 받고, n개의 회의의 시작과 종료 시간을 lst배열에 입력 받는다. 이 때 종료시간을 앞에 저장해 준다.lst배열을 오름차순으로 정렬해 준다, 종료 시간 기준으로 오름차순 되어야 한다.멀티셋 dic을 초기화 해주고, 정답을 저장할 변수 ans를 0으로 초기화 해준다.n개의 회의 정보를 순회하며 현재 회의의 시작 시간을 기준으로 dic에서 upper_bound해준다.반환된 이터레이터가 dic의 begin()이라면 dic에 현재 회의의 종료시..