https://www.acmicpc.net/problem/2042알고리즘 분류 : 자료 구조, 세그먼트 트리 ❓문제🔅해석세그먼트 트리를 이용하는 가장 기본적인 문제이다.인덱스 트리 생성 - init인덱스 트리의 리프 노드에 배열을 담아야 하므로 리프 노드가 시작하는 인덱스 번호를 알아야한다.리프 노드의 개수를 S로 표현하고 S는 N 이상의 2^n으로 표현 가능한 수여야 한다.따라서 S 는 아래와 같이 구한다. (N은 주어진 배열의 크기)S = 1;while (S 리프 노드에 배열에 적혀있는 수를 넣기위해 S번째부터 넣는다.그 외 내부 노드는 S - 1번째부터 자식 노드(왼쪽, 오른쪽) 합을 대입한다.private static void init() { // leaf노드 채우기 for (in..
https://www.acmicpc.net/problem/1927알고리즘 분류 : 자료 구조, 우선순위 큐직접 힙을 구현하여 풀이하였습니다. ❓문제🔅해석직접 힙을 구현하여 풀어본 문제이다. 최소 힙은 ' 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다.'는 힙 조건을 가진다.힙 조건에 맞춰 삽입과 삭제 연산을 진행한다. 삽입 연산트리의 가장 마지막 위치에 노드를 삽입한다.추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인한다.만족하지 않는다면 부모와 자식의 키 값을 바꾼다.조건에 만족하거나 추가된 노드가 루트에 도달할 때까지 2 ~ 3을 반복한다. 입력을 받다가 '0'을 만나게 되면 삭제 연산을 수행한다. 삭제 연산힙의 삭제 연산은 항상 루트 노드를 삭제한다.트리의 가장 마지막 노드를 루..
https://www.acmicpc.net/problem/2805알고리즘 분류 : 이분 탐색, 매개 변수 탐색 ❓문제🔅해석투포인터와 비슷하게 세개의 포인터로 문제를 푼다.1 ~ 트리의 최대값까지의 배열을 만들어 start = 1, end = 트리의 최대값, mid = (start / end) / 2 로 초기화한다.mid 값을 현재 절단기 높이라고 생각하고, 입력받은 트리의 순회하면서 mid 값을 각각 빼주고 sum에 더한다. sum이 목표값보다 크다면 나무를 더 많이 잘랐다는 뜻으로 절단기 높이를 높이기 위해 start 값을 mid + 1로 설정한다.반대의 경우, end = mid - 1로 설정한다. 다시 mid = (start + end) / 2로 설정해고 위와 같이 트리를 순회하면서 절단된 나무들..
