백준/트리11 백준 2268번 c++ "수들의 합 7" -PlusUltraCode- https://www.acmicpc.net/problem/2268 [필자 사고]이 문제는 세그먼트 트리 알고리즘을 이용하면 쉽게 풀 수 있다. 특이한 점은 처음 값들이 주어지지 않고 입력값을 통해 순차적으로 트리를 갱신해줘야 된다는 점이다.아래는 코드 해설이다.[코드 해설] 세그먼트 트리 초기화Init_Segment_Tree 함수는 입력 데이터 크기 N에 기반하여 세그먼트 트리의 높이와 크기를 계산하고 트리를 초기화한다.트리의 높이는 ⌈log2(N)⌉\lceil \log_2(N) \rceil⌈log2(N)⌉로 계산된다.트리의 전체 크기는 2(트리 높이+1)2^{(\text{트리 높이} + 1)}2(트리 높이+1)로 설정된다.트리는 vector 자료구조로 구현되며, 초기 값으로 0으로 채워진다.쿼리를 .. 2025. 1. 5. 백준 1275 c++ "커피숍2" -PlusUltraCode- https://www.acmicpc.net/problem/1275 [필자 사고]이 문제는 세그먼트 트리를 이용하면 쉽게 풀 수 있따.ㄷㅏ만 조심해야 될 부분은 갱신 부분인데 갱신할 부분을 숫자로 대체하고 다시 합을 구하는게 아닌기존값과 갱신값의 차이를 구한뒤 idx/=2 방식으로 값만 갱신해주면 시간복잡도 내에 문제를 해결할 수 있다.아래는 코드해설이다. [코드 해설]1. Input 함수배열의 크기 N과 명령 수 M을 입력받습니다.입력된 값은 배열 arr에 저장됩니다.2. Init_Segment_Tree 함수세그먼트 트리를 초기화합니다:트리 크기 계산:treeHeight: 배열 크기 N에 대한 로그 값을 계산하여 트리의 높이를 결정합니다.treeSize: 트리 전체의 노드 개수를 계산합니다.leftSta.. 2025. 1. 5. 백준 2357 c++ "최솟값과 최댓값" -PlusUltraCode- https://www.acmicpc.net/problem/2357 [필자 사고]이 문제를 처음 봤을 때 부르스트 알고리즘을 적용하려 했지만 범위를 보고 그만두었다.다음으로 누적합을 이용하면 뭐 달라질까?? 생각했지만 에초에 최솟값과 최댓값이라 상관이 없었따.처음으로 배운 세그먼트트리를 이용해야 된다. 세그먼트 트리는 초기값을 잘 설정하면 그 이후부터는 쉽게 풀 수 있따.시간복잡도가 logN 이라 시간내에 풀 수 있다.아래는 코드 해설이다.[코드 해설] Input 함수배열 크기(N)와 질의 수(M)를 입력받습니다.배열 arr를 초기화하고, 데이터를 입력받아 저장합니다.Init_Segment_Tree 함수세그먼트 트리를 초기화합니다:treeHeight: 배열의 크기(N)에 대한 로그 값으로 세그먼트 트리의 .. 2025. 1. 5. 백준 1922 c++ "네트워크 연결" -PlusUltraCode- https://www.acmicpc.net/problem/1922 [필자 사고]최소 스패닝 트리를 이용하며 쉽게 해결할 수 있다. 필자는 입력 받은 가중치들을 벡터에 오름차순으로 정렬 하였다.**** 실수 조심 >> 그 뒤 start와 end 값이 같으면 무시하고 start 와 end 가 현재 같은 Union인지 아닌지를 판다하여 문제를 해결해 나갔다. 아래는 코드 해설이다.설명크루스칼 알고리즘 개요:크루스칼 알고리즘은 가중치가 있는 그래프에서 **최소 스패닝 트리(MST)**를 구하는 알고리즘 중 하나입니다.먼저 모든 간선을 가중치 순서대로 정렬한 후, 사이클을 만들지 않으면서 최소 가중치 간선을 하나씩 선택하여 트리를 만들어 나갑니다.이를 위해 유니온-파인드(Union-Find) 자료구조를 사용해 사.. 2024. 9. 24. 이전 1 2 3 다음
