백준/자료구조39 백준 1395 c++ "스위치" -PlusUltraCode- https://www.acmicpc.net/problem/1395 [필자 사고]이 문제는 세그먼트 자료구조를 이용하여 풀어아 되는 문제이다.또한 Update함수를 호출할때 범위 내 left 와 right의 변경을 요함으로 매번 하나하나 변경하게 되면시간초과가 발생하게 된다. 이에 대한 해결법은 Propagation을 이용하여 느린 전파를 하게 되면 시간내에 풀수 있다.또한 이 문제만의 매력은 ^연산자 즉 xor연산자를 사용하여 0을 1로 1을 0으로 뒤집는 연산이다.모든 연산을 ^으로 하는게 아니라 갱신만 저렇게 하고 나머지는 합을 구하므로 합연사으로 진행해 주어야 된다.[코드 해설]1. Lazy Propagation을 활용한 업데이트 (Update 함수)목적: 특정 구간의 값을 XOR 연산을 통해 반전.. 2025. 1. 15. 백준 17408 c++ "수열과 쿼리 24" -PlusUltraCode- https://www.acmicpc.net/problem/17408 [필자 사고]이 문제는 세그먼트 트리 자료형을 구해서 풀어야 되는 문제이다.ㅇㅣ 문제만의 특징은 특정 구간 내에 A1+A2의 최댓값을 구하라는 문제이다. 필자는 구간내 최대로 큰 숫자를 가지고 있는 A1을 찾은뒤 idx를 이용하여해당 idx를 제외한 나머지 범위에 쿼리를 날려 그 중 큰 수를 가지고 있는 A2를 찾는 방식으로코드를 작성했다. 위와 같은 형태로 구하기 위해서는 트리를 초기화 할때 pair을 사용하여값과 인덱스 모두 저장해야 된다.두가지 인덱스를 사용해야 된다는 점에서 많은 공부가 된 문제다.[코드 해설]1. 입력 처리 및 초기화 (Input 함수)목적: 배열과 세그먼트 트리를 초기화합니다.배열 크기 NNN을 입력받습니다.배.. 2025. 1. 15. 백준 13681 c++ "Bolhas e Baldes" -PlusUltraCode- https://www.acmicpc.net/problem/13681 [필자 사고]이 문제는 세그먼트 트리 기본문제이다. 세그먼트 트리를 설계를 할줄 알면 손쉽게 해결할 수 있다.N의 범위도 10^5이라 문제될거 없다. [코드 해설] 세그먼트 트리 초기화vector tree를 사용하여 세그먼트 트리를 선언하고, 배열 크기의 4배로 초기화합니다. 세그먼트 트리는 구간 합을 관리하기 위해 사용됩니다.업데이트 함수 (Update)Update 함수는 세그먼트 트리에 특정 인덱스의 값을 업데이트하는 역할을 합니다.기저 조건: 현재 노드가 업데이트하려는 인덱스에 도달하면 값을 더합니다.재귀 호출: 해당 인덱스가 포함된 구간을 찾아 좌측 자식 노드 또는 우측 자식 노드로 이동합니다.노드 값 갱신: 자식 노드들의 합으.. 2025. 1. 14. 백준 14449 c++ "Balanced Photo" -PlusUltraCode- https://www.acmicpc.net/problem/14449 [필자 사고]이 문제는 inverstion Counting 을 응용한 문제이다.현재 idx보다 앞 뒤로 놓여진 숫자들을 구해야 된다.필자는 세그먼트 트리를 이용하였다. 이 문제에서 핵심은 좌표 압축이라고 생각한다.기존 배열을 idx와 val 를 함께 저장하고 val를 기준으로 오름차순을 진행한다.진행한 뒤 compressedArr[arr[i].second] = i 를 하게 되고 사용할때는 compressedArr[i]를 사용하면좌표 압축 성공이다.[코드 해설]1. 입력 처리 및 초기화사용자로부터 배열 크기 NNN과 NNN개의 숫자를 입력받는다. 입력받은 숫자들을 값과 인덱스로 묶어서 저장한 뒤, 값을 기준으로 정렬한다. 정렬된 배열을 .. 2025. 1. 14. 이전 1 2 3 4 5 6 7 ··· 10 다음
