백준189 백준 12899 c++ "데이터 구조" -PlusUltraCode- https://www.acmicpc.net/problem/12899 [필자 사고]이 문제는 세그먼트 트리를 이용하여 몇번째 숫자를 찾는 응용 문제이다.필자는 사전에 구슬문제를 통해 몇번째 숫자를 찾는게 익숙하여 해당 문제는 쉽게 해결할 수 있었다.조심해야 될점은 입력되는 숫자의 범위가 2000000이라는 점이다.트리의 크기를 이것보다 크게 잡아야 된다.![코드 해설] 세그먼트 트리 초기화 및 업데이트tree 벡터를 사용하여 세그먼트 트리를 관리합니다. 이 트리는 특정 구간의 값을 효율적으로 갱신하고 조회할 수 있도록 설계되었습니다.Update 함수:idx 위치의 값을 변경하는 함수입니다.start와 end는 현재 구간을 나타내며, node는 세그먼트 트리의 현재 노드입니다.만약 start == end이면.. 2025. 1. 11. 백준 2517 c++ "달리기" -PlusUltraCode- https://www.acmicpc.net/problem/3653[필자 사고]평범한 inversing index인줄 알았지만... 입력될 수 있는 범위가 겁나 크다.즉 새롭게 알게된 알고리즘 좌표 압축을 통해 내가 가지고 있는 배열에는 값이 아닌 index를 저장해놓는 방식이다. 필자는 myMap을 통해 위와 같은 문제를 해결했고 다른 분들의 코드를 살펴보니기존 배열을 다른 배열로 temp 를 담고 정렬뒤 해당 값을 찾으면 index를 arr원본 배열에 저장하는 식으로 좌표 압축을 하였다. 새로운 알고리즘 학습하기에는 좋은 문제다.[코드 해설] 입력 처리 및 초기화 (Input 함수)Input 함수는 데이터를 입력받아 초기화하는 역할을 한다.배열 arr에 입력된 데이터를 저장한다.입력 데이터를 정렬한 후.. 2025. 1. 11. 백준 10999 c++ "구간 합 구하기 2" -PlusUltraCode- https://www.acmicpc.net/problem/10999 [필자 사고] 새로운 알고리즘의 만남이다. 세그먼트 트리에 lazy 전파를 적용하는 것이다.아직 익숙지 않다. 많은 문제를 통해 lazy전파 알고리즘에 익숙해져 보자.약간 정리하자면 Query 나 update에서 항상 propagate를 1행에 실행시킨다.그리고 update에서 갱신되는 부분이 생기면 lazy[node] +=diff 를 갱신해주고다시 propagate 를 선언한다. 이정도??[코드 해설] 세그먼트 트리 초기화 (Init_Tree 함수)이 함수는 세그먼트 트리를 생성하는 역할을 한다.리프 노드에 도달하면 arr 배열의 값을 트리에 저장한다.내부 노드에서는 왼쪽과 오른쪽 자식의 값을 더하여 부모 노드에 저장한다.지연 전파 (.. 2025. 1. 11. 백준 1989 c++ "부분배열 고르기 2" -PlusUltraCode- https://www.acmicpc.net/problem/1989[필자 사고]이전 문제인 부분배열 고르기에 leftPtr 과 rightPtr을 넓이가 갱신될때마다 기록해주면 쉽게 해결할 수 있다. 분할정복:문제를 작은 구간으로 나누고, 각각의 구간에서 최대 값을 계산한 뒤 이를 합쳐 전체 구간의 최대 값을 구한다.효율성:각 구간에 대해 최소 높이를 유지하면서 넓이를 계산하기 때문에 최악의 경우에도 O(nlogn)O(n \log n)O(nlogn) 복잡도로 동작한다. [코드 해설]입력 데이터와 초기화먼저 배열에 값들을 저장하고, 누적합 배열을 생성하여 구간 합을 빠르게 계산할 수 있도록 준비한다.values[] 배열에 입력 값을 저장한다.prefixSum[] 배열을 사용해 누적합을 계산한다. 이를 통해.. 2025. 1. 11. 이전 1 ··· 4 5 6 7 8 9 10 ··· 48 다음
