개인사

[G4] 백준 18223번 민준이와 마산 그리고 건우 C++ 다익스트라

리뷰 https://www.acmicpc.net/problem/182231에서 v까지의 최단 경로와 p를 거쳐가는 경로의 길이가 같은지 여부를 찾는 문제  전역 변수V : 배열의 최대 크기를 저장할 상수 변수v : 정점의 개수를 저장할 변수e : 간선의 개수를 저장할 변수p : 건우가 위치한 정점을 저장할 변수Edge : 간선 정보 다음 노드 nn, 간선의 크기 nv를 정의할 구조체edges : 간선 정보를 저장할 Edge타입 벡터Pos : 시뮬레이션 정보 현재 노드 cn, 누적 간선 크기 cv를 정의할 구조체, cv를 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra(int sn, int dn) { priority_queue pq; pq.push({ sn, 0 }); vecto..

[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] = ..

리뷰 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 : 세그먼트 트리 정보를 저장할 배열..

리뷰 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,..