본문 바로가기

백준189

백준 7578 c++ "공장" -PlusUltraCode- https://www.acmicpc.net/problem/7578 [필자 사고]이 문제는 세그먼트 트리 자료구조를 이용하여 풀 수 있는 문제이다.다만 사고 과정이 어렵다.처음 모든 세그먼트 트리를 0으로 초기화 해놓고A를 보면 132는 B에서 idx 3번에 해당한다.그러면 세그먼트 트리를 3번부터 N까지 Query를 날려 그 구간에 갯수가 있으면 결과에 더하는 형식으로 코드를 작성하면 된다. Query를 날리고 나서 3번 idx에 세그먼트 트리를 Update해 하나를 더해주면 선분이 완성된다.위와 같은 과정을 반복 하면 된다.[코드 해설] Input 함수Input 함수는 프로그램에 필요한 입력 데이터를 처리합니다.먼저, 수열의 크기 N을 입력받습니다.크기가 N인 배열 A에 수열의 값을 입력받아 저장합니다.. 2025. 1. 7.
백준 2243 c++ "사탕상자" -PlusUltraCode- https://www.acmicpc.net/problem/2243 [필자 사고] 세그먼트 자료구조를 이용하여 푸는 문제이다.단순히 세그먼트 자료구조를 만드는 것에서 그치지 않고 응용이 들어갔따.현재 4순위의 캔디를 뽑으세요 라고 주어지면 세그먼트 트리의 탐색 방법은 왼쪽 자식 노드의 캔디 수가 현재 캔디수보다 작다면왼쪽 자식으로 이동하고그렇지 않으면 오른쪽으로 이동 및 4순위 캔디를 왼쪽자식캔디만큼 빼야된다.세그먼트 트리는 많은 유형이 있다. 계속 반복해서 코드를 작성하다보면 감을 찾을것이다. [코드 해설] 세그먼트 트리 초기화 및 입력 처리입력으로 게임에 사용될 데이터를 받습니다.세그먼트 트리를 tree라는 벡터로 초기화하며, 4 * MAX + 1 크기의 배열로 설정합니다.명령 처리 로직총 N개의 명령.. 2025. 1. 7.
백준 2268번 c++ "수들의 합 7" -PlusUltraCode- https://www.acmicpc.net/problem/2268 [필자 사고]이 문제는 세그먼트 트리 알고리즘을 이용하면 쉽게 풀 수 있다. 특이한 점은 처음 값들이 주어지지 않고 입력값을 통해 순차적으로 트리를 갱신해줘야 된다는 점이다.아래는 코드 해설이다.[코드 해설] 세그먼트 트리 초기화Init_Segment_Tree 함수는 입력 데이터 크기 N에 기반하여 세그먼트 트리의 높이와 크기를 계산하고 트리를 초기화한다.트리의 높이는 ⌈log⁡2(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.

티스토리툴바