본문 바로가기

세그먼트 트리6

[프로그래머스] 징검다리 건너기 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]위과 같은 배열으로 징검다리들의 숫자가 입력으로 들어온다. 디딤돌을 밟을때마다 숫자가 1씩 줄어들고, 0인 돌이 있다면 안뛰고 건너뛸 수 있다. 하지만, 입력으로 k가 주어지는데 한번에 k개의 돌만 건너뛸 수 있다. 예를 들어, `[5, 3, 2, 1, 4]` 이러한 배치를 하고있다면 3명이 돌을 건너간 후의 상태는 `[2, 0, 0, 0, 1.. 2024. 5. 19.
[백준] 7578: 공장 - JAVA https://www.acmicpc.net/problem/7578 풀이A열과 B열에 같은 숫자들을 연결할 때, 케이블들이 서로 교차하는 부분의 개수를 세는 문제이다. A열: 1 2 3 4 5 B열: 2 4 1 3 5 위와 같이 주어졌을 때, B열에서 A열로 줄을 쏴주었다. B열의 2에서 A열의 2로 줄을 쐈을 때, A열의 2보다 오른쪽에 이미 연결된 점이 있다면 그 점이 교차하는 점이다. B열은 앞에서부터 순서대로 보는데, A열의 연결된 점 오른쪽으로 연결된 점이 있다는 것은 B열의 앞쪽 점과 연결되어 있다는 것이므로 교차한다는 것이다. A열의 인덱스를 저장해주었고, B열의 점이 A열의 어떤 인덱스와 연결되는지 저장했다. 세그먼트 트리를 이용해 A열의 인덱스부터 N까지 구간합을 구해 교차점이 몇개인지 구.. 2024. 5. 18.
[백준] 10868: 최솟값 - JAVA https://www.acmicpc.net/problem/10868 풀이N개의 정수 배열의 a~b구간에서의 최솟값을 찾아야 한다. 세그먼트트리를 만들어 구간별로 최소값을 갖는 배열의 인덱스를 저장했다. a~b구간에서 최솟값의 인덱스를 찾아 배열의 값을 출력하면 된다. 인덱스를 저장하지 않고 최솟값 자체를 세그먼트트리에 저장하는 것도 좋다.  메모리: 48788KB시간: 600ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class SegmentTree { int[] tree; int treeSize; public SegmentTree(int arrSize) { .. 2024. 5. 18.
[백준] 2517: 달리기 - JAVA https://www.acmicpc.net/problem/2517 풀이N명의 선수의 실력을 입력받는다. 입력을 받는 순서대로 해당 위치에 있다고 할 때, 실력이 자기보다 안좋은 선수가 앞에 있으면 역전할 수 있다. 예를들어 실력이 2, 8, 10으로 주어졌다면 8실력을 가진 선수는 앞에 자기보다 낮은 실력의 선수 1명이 있으므로 이 선수가 할 수 있는 최선의 등수는 1등이다. 10인 선수는 앞에 2명을 앞지를 수 있으므로 최선의 등수는 1등이 된다. 세그먼트 트리를 이용하여 실력을 tree의 인덱스로 하여 1늘린다. 1부터 자신의 인덱스까지 구간합을 구하면 자신과 자신보다 실력이 낮은 선수들의 합이 된다. 구간합과 입력받은 순서를 이용하여 최선의 등수를 계산할 수 있다. 각 선수의 실력은 모두 다르므로 .. 2024. 5. 18.
[백준] 2357: 최솟값과 최댓값 - JAVA https://www.acmicpc.net/problem/2357 풀이구간이 주어지면 그 구간에서 최소, 최댓값을 찾아야 한다. 세그먼트 트리를 이용해 풀었다. 세그먼트 트리는 구간별로 값을 담아서 최댓값, 최솟값, 구간합 등 문제에 유용한 자료구조이다. 최소, 최대를 구해야 하기 때문에 Node라는 class를 만들어 최소, 최댓값을 담았다. Node배열을 만들어 세그먼트 트리로 이용했다. N개의 정수가 주어진다고 하면 트리 배열의 사이즈를 구하는 방법은 다음과 같다.// 트리의 높이int height = (int) Math.ceil(Math.log(arrSize) / Math.log(2));// 트리의 노드 수this.treeSize = (int) Math.pow(2, height + 1);하지만 N.. 2024. 5. 14.
[백준] 1725: 히스토그램 - JAVA https://www.acmicpc.net/problem/1725 풀이각 칸들의 높이가 주어지고, 내부에 가장 큰 직사각형을 구하는 문제이다. 아랫변을 구간으로 나눠 그 구간으로 이룰 수 있는 직사각형의 넓이를 비교해주었다. 세그먼트트리에는 구간별로 최소 높이를 갖는 인덱스를 저장해주었다. 구간으로 탐색할 때 인덱스를 기준으로 나누기 위함이다. (1, N)구간에서 넓이를 구하면 밑변은 (N - 1 + 1)이 되고, 높이는 해당 구간의 최소 높이를 세그먼트트리에서 찾아주면 된다. 이렇게 구한것이 해당 구간에서 만들수있는 직사각형의 최대이다. 위에서 찾은 최소 높이의 인덱스를 idx라고 하면 (1, idx - 1), (idx + 1, N)으로 나누어 계속 진행한다.  메모리: 39272KB시간: 356ms언.. 2024. 5. 14.

티스토리툴바