oVeron

1.금광을 개발했을 때의 가치는 2차원 배열로 나타낼 수 있다. 우리는 직사각형 형태의 구간을 정해 그 구간 내의 금광을 전부 개발했을 때의 가치의 최댓값을 구하고 싶다. 따라서 이 문제는 2차원 배열에서 부분합의 최댓값을 구하는 문제로 바꿔 풀 수 있다. 2.우선, 금광이 위치한 index의 범위가 매우 크므로 이를 값/좌표 압축으로 줄이자. \(N\)의 범위가 3000이므로 3000 이내의 2차원 배열로 모든 금광을 표현할 수 있다. 1차원 배열에서 부분합의 최댓값을 구하는 것은, 세그먼트 트리를 이용해 해결할 수 있음이 널리 알려져 있다.그렇다면 2차원 배열에서는 어떻게 하는가? x축을 기준으로 각 열의 누적 합을 구한 후 x축의 구간을 설정한다. 구간을 설정하기 위해서는 x축 내에서 2개의 값을 ..

알고리즘/baekjoon 2024. 7. 19. 12:27

1.두 개의 수평선을 그었을 때 수평선이 관통하는 직사각형의 수를 구하는 문제이다. 이 문제의 최대 난관은 두 개의 수평선이 같은 직사각형을 지나면 어떻게 할 것인가이다. lazy propagation으로 직사각형의 y좌표의 구간을 1씩 더하는 방법을 써도, 직사각형을 서로 구분할 수 없으므로 문제를 해결할 수 없다. 일단 수평선 하나를 임의로 그어놓고, 또 하나의 수평선을 추가로 긋는 작업을 상상해보자. 이미 그어놓은 수평선과 교차하는 직사각형들은, 수평선을 더 그을 때 중복 처리를 해야만 한다. 그렇다면 수평선과 교차하는 직사각형들을 아예 제거하는 것은 어떨까? 수평선과 교차하는 직사각형들을 제거하여, 위에서 설명한 lazy propagation으로 직사각형의 y좌표의 구간을 1씩 더하는 방법을 사용..

알고리즘/baekjoon 2024. 7. 8. 15:25

1.우선 각 직사각형을 x좌표 기준으로 오름차순 정렬하자. 가장 먼저 할 수 있는 생각은 이 직사각형들을 x좌표 기준으로 차례대로 스위핑하여, y좌표 구간의 길이을 합하거나 빼가며 면적의 합을 구하는 것이다. y좌표의 구간에 속하는 직사각형의 변들이 변할 때마다 y좌표 구간의 길이에 x좌표 구간의 길이를 곱하면 답을 빠르게 구할 수 있을 것이다.문제는 y좌표 구간의 길이를 합하거나 빼는 게 쉬운 과정이 아니라는 것이다. 이 과정을 어떻게 빠르게 할 수 있을까? 2.우선 각 직사각형의 y좌표만 오름차순 정렬한 후, 이 좌표들의 차이를 배열에 저장하자(좌표 압축). 이 방식으로 y좌표 구간의 길이를 배열의 index 2개의 구간으로 표현할 수 있을 것이다. y좌표 : \(1, 5, 10, 14, 20, 25..

알고리즘/baekjoon 2024. 6. 28. 12:46

1.가장 먼저 생각해 볼 수 있는 것은 x좌표, y좌표 세그먼트 트리를 따로 만들어서 각 영역에서 일치하는 원소가 몇 개인지 세는 것이다. 하지만 이 방식은 세그먼트 트리에 점 좌표를 직접 넣어야 하기에 vector로 구현해야 하며, 실제로 x좌표, y좌표의 각 구간에서 일치하는 원소를 일일이 세어 봤다간 시간 초과를 피하기 힘들 것이다. 2.x좌표 구간은 특정한 방법으로 처리한 후, y좌표는 세그먼트 트리를 활용한 구간 합으로 구하는 방법을 생각해 보자.x좌표 구간을 어떻게 특정한 방법으로 처리할 수 있을까? 각 좌표와 x좌표에 대한 구간을 오름차순으로 정렬한 후, 스위핑을 통해 좌표와 구간을 일치시키며 오름차순으로 쿼리를 처리하는 방법을 생각할 수 있다. 쿼리를 처리할 때마다, 각 영역의 y좌표 구간..

알고리즘/baekjoon 2024. 6. 24. 17:11

1.세 개의 별을 전부 비교할 수는 없다. 문제 조건에서 s.x 이고 s.y > t.y  ex) 예제 입력 2 -> (-2, 0) (-2, 1) (-1, 0) (-1, 1) (0, 0) (0, 1) (1, 0) (1, 1) (2, 0) (2, 1) 이 점들 중 3개를 정렬된 순서대로 고르면 s.x 스위핑을 통해 점 u를 먼저 정하고, 그 다음 점 s, t를 정하면 좋을 것 같다. 그렇다면 조건 s.y > t.y  2.일단 점 t를 임의로 정했다 가정한 후, 점 s를 구하는 방법을 알아보자. 우리가 (0, 0)을 점 t로 정했다면, 조건 s.y > t.y에 따라 가능한 점은 (-2, 1) (-1, 1) 둘이다. 이 과정은 점 t보다 index가 작은 점들 중 y좌표가 큰 것을 고르는 것과 같다.점 u를 임..

알고리즘/baekjoon 2024. 6. 17. 16:12

1.모든 점에 대해서 완전 탐색을 돌릴 수는 없으므로, 다른 방법을 생각해 보자. 우선 y좌표가 작은 순으로, y좌표가 같다면 x좌표가 큰 순으로 점들을 정렬한다.  ex) (5, 3), (5, 2), (3, 1), (3, 2), (1, 7), (1, 5) -> (1, 7), (1, 5), (3, 2), (3, 1), (5, 3), (5, 2) 여기서 문제 조건을 생각해 보자. 한 점에서 다른 점으로 북서풍을 타고 이동할 수 있으려면, 그 다른 점이 한 점보다 y좌표는 큰 대신 x좌표는 작아야 한다. 위의 예시에서 (5, 3)이 이동할 수 있는 점은 (1, 7), (1, 5) 둘 뿐이다. 그런데 현재 y좌표가 작은 순대로, y좌표가 같다면 x좌표가 큰 순으로 정렬되어 있으므로, 우리는 (3, 1)의 왼편..

알고리즘/baekjoon 2024. 6. 17. 12:08