본문 바로가기

백준188

백준 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.
백준 1016 c++ "제곱 ㄴㄴ 수" -PlusUltraCode- https://www.acmicpc.net/problem/1016 [필자 사고]이 문제는 에스트라 채를 알고 있냐 없냐 묻는 문제이다.그리고 중요한 점은 시작 위치를 정하는 startIdx를 구하는 방법인데 필자는 다음과 같이 구했다.(minNum+square-1)%square*square 방식을 startIdx를 구하고startIdx의 실제 배열의 위치를 구하기 위해startIdx - minNum 을 하게 되면 배열 압축을 할 수 있게 된다.이 정도만 조심하면 문제를 해결할 수 있다.[코듷 해설] 입력 받기:minNum과 maxNum 값을 입력받아 분석할 범위를 설정합니다.에라토스테네스의 체 변형:isPrime 벡터를 [minNum,maxNum][minNum, maxNum][minNum,maxNum] .. 2025. 1. 14.
백준 12899 c++ "데이터 구조" -PlusUltraCode- https://www.acmicpc.net/problem/12899 [필자 사고]이 문제는 세그먼트 트리를 이용하여 몇번째 숫자를 찾는 응용 문제이다.필자는 사전에 구슬문제를 통해 몇번째 숫자를 찾는게 익숙하여 해당 문제는 쉽게 해결할 수 있었다.조심해야 될점은 입력되는 숫자의 범위가 2000000이라는 점이다.트리의 크기를 이것보다 크게 잡아야 된다.![코드 해설] 세그먼트 트리 초기화 및 업데이트tree 벡터를 사용하여 세그먼트 트리를 관리합니다. 이 트리는 특정 구간의 값을 효율적으로 갱신하고 조회할 수 있도록 설계되었습니다.Update 함수:idx 위치의 값을 변경하는 함수입니다.start와 end는 현재 구간을 나타내며, node는 세그먼트 트리의 현재 노드입니다.만약 start == end이면.. 2025. 1. 11.

티스토리툴바