본문 바로가기

세그먼트 트리

 (3)
[백준] 2243번 : 사탕상자 2243번: 사탕상자 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 🤔 문제분석 세그먼트 트리와 팬윅트리를 활용하여 문제를 해결하였습니다. 팬윅 트리 팬윅 트리로 문제를 해결 할때에는 이분탐색과 팬윅트리를 사용하여 문제를 해결하였습니다. 사탕의 순위를 누적합으로 계산시키고, 이분탐색으로 사탕을 찾아 나아 갑니다. 쿼리함수의 인자는 사탕의 가치가 되고 사탕의 가치를 입력하면 현재 그 사탕의 가치의 순위가 리턴 됩니다. 업데이트 함수는 사탕의 정보를 업데이트 합니다. 쿼리함수로 리턴받..
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 [백준] 6549번 : 히스토그램에서 가장 큰 직사각형 6549번: 히스토그램에서 가장 큰 직사각형 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 🤔 문제분석 이틀공안 고민하다가, 결국 해결하지 못하여, 풀이법을 참조하였습니다. 😂 해당 문제를 해결하는 방법은 스택을 활용하여 푸는 방법과, 분할정복, 세그먼트 트리를 활용하여 푸는 방법이 있습니다. 분할정복, 세그먼트 트리 최소 높이를 찾아서, 그 지점을 기준으로 양쪽을 분할한다. 해당 구간에서 최대 ..
[백준] 7578번 : 공장 7578번: 공장 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 📄 문제개요 라인 A와 라인 B가 있을때 라인 A와 B에는 N개의 기계가 각각 있다고 하고, 직선으로 각각의 기계를 1:1 매칭 하였을때, 겹치는 선분의 개수를 구하는 문제이다. 1:1 매칭은 같은 유니크한 숫자를 매칭시킨다. 🤔 문제분석 라인 A의 기계들을 리터레이션 하는데, 하나씩 연결해보면서, 겹치는 선분이 있는지 확인한다. B의 위치를 알기위해서는 딕셔너리 자료구조를 활용하여 위치를 파악한다. 📝 의사코드 A의 배열의 값을 순회한다...

티스토리툴바