본문 바로가기

Java82

[백준] 1915: 가장 큰 정사각형 - 세 방향을 확인하는 2차원 DP (Java) 문제 바로가기모든 정사각형을 직접 확장하지 않는다0과 1로 이루어진 배열에서 값이 모두 1인 가장 큰 정사각형의 넓이를 구해야 한다.각 칸을 정사각형의 시작점으로 정하고 크기를 하나씩 늘리며 내부가 모두 1인지 확인할 수 있다. 하지만 같은 영역을 여러 번 검사하게 되고, 정사각형이 커질수록 확인할 칸도 많아진다.나는 현재 칸에서 끝나는 정사각형의 크기를 이전에 계산한 주변 값으로 구하는 DP를 사용했다.핵심은 현재 칸에 1이 있는지만 보는 것이 아니라, 현재 칸을 오른쪽 아래 꼭짓점으로 삼았을 때 왼쪽 위 방향으로 얼마나 큰 정사각형을 만들 수 있는지 저장하는 것이다.dp에 정사각형의 한 변 길이를 저장한다DP 상태를 다음과 같이 정의했다.dp[i][j]= (i, j)를 오른쪽 아래 꼭짓점으로 하는 .. 2024. 5. 14.
[백준] 2357: 최솟값과 최댓값 - 세그먼트 트리로 구간 질의 처리하기 (Java) 문제 바로가기같은 배열에서 구간 질의를 반복한다N개의 값이 주어지고, M개의 구간마다 최솟값과 최댓값을 출력해야 한다.질의를 받을 때마다 구간의 모든 원소를 확인하면 한 번에 최대 O(N)이 필요하다. 질의가 M개라면 전체 시간은 O(NM)까지 커질 수 있다.배열의 값은 질의 중에 바뀌지 않는다. 따라서 구간별 최솟값과 최댓값을 미리 묶어 두고, 요청한 구간을 몇 개의 묶음으로 나눠 계산할 수 있다.나는 각 노드가 담당하는 구간의 최솟값과 최댓값을 함께 저장하는 세그먼트 트리를 사용했다.원본 배열→ 구간별 최솟값과 최댓값으로 트리 생성→ 질의 구간과 겹치는 노드만 선택→ 선택한 결과들을 다시 최소와 최대로 결합트리 노드에는 두 값을 함께 저장한다하나의 구간에서 최솟값과 최댓값을 모두 구해야 하므로 Nod.. 2024. 5. 14.
[백준] 1725: 히스토그램 - 세그먼트 트리와 분할 정복으로 최대 직사각형 구하기 (Java) 문제 바로가기모든 구간을 직접 확인할 수는 없다히스토그램의 각 막대 높이가 주어질 때, 연속된 막대로 만들 수 있는 가장 큰 직사각형의 넓이를 구해야 한다.어떤 연속 구간을 선택하면 직사각형의 높이는 그 구간에서 가장 낮은 막대보다 높을 수 없다. 따라서 구간 left...right 전체를 사용하는 직사각형의 넓이는 다음과 같다.구간의 최소 높이 × 구간의 너비모든 시작점과 끝점을 선택하면 구간이 O(N²)개다. 각 구간의 최소 높이까지 직접 찾으면 시간이 더 커진다.나는 구간의 최소 높이 인덱스를 세그먼트 트리로 찾고, 그 인덱스를 기준으로 구간을 나누는 분할 정복을 사용했다.현재 구간의 최소 높이 인덱스 탐색→ 해당 인덱스를 포함하는 최대 직사각형 계산→ 최소 높이의 왼쪽 구간 탐색→ 최소 높이의 오.. 2024. 5. 14.
[백준] 11000: 강의실 배정 - 정렬과 최소 힙으로 필요한 강의실 수 구하기 (Java) 문제 바로가기동시에 열리는 수업 수만큼 강의실이 필요하다각 수업의 시작 시간과 종료 시간이 주어질 때 모든 수업을 진행하는 데 필요한 강의실의 최소 개수를 구해야 한다.한 수업이 끝나는 시간과 다음 수업이 시작하는 시간이 같다면 같은 강의실을 이어서 사용할 수 있다.수업 A: 1 ~ 3수업 B: 3 ~ 5A가 끝난 강의실에서 바로 B 진행 가능결국 새 수업이 시작될 때 기존 강의실 중 하나가 비어 있으면 재사용하고, 모두 사용 중이라면 새 강의실을 추가해야 한다.처음에는 수업마다 앞선 모든 수업과 시간이 겹치는지 비교할 수 있다. 하지만 N개의 수업을 서로 비교하면 O(N²)이 걸린다.내가 실제로 필요한 정보는 기존 강의실 중 가장 빨리 비는 시간이다. 이를 빠르게 찾기 위해 종료 시간을 최소 힙에 저장.. 2024. 5. 14.
[백준] 1202: 보석 도둑 - 정렬과 최대 힙을 이용한 Greedy (Java) 문제 바로가기작은 가방부터 가장 비싼 보석을 고른다각 보석에는 무게와 가격이 있고, 가방마다 담을 수 있는 최대 무게가 정해져 있다. 가방 하나에는 보석을 하나만 넣을 수 있으며, 같은 보석을 여러 번 사용할 수 없다.처음에는 가격이 높은 보석부터 확인해 들어갈 수 있는 가방을 찾는 방법을 생각할 수 있다. 하지만 매번 적절한 가방을 찾으면 탐색 비용이 커지고, 큰 가방을 먼저 사용하면 무거운 보석을 넣을 자리가 사라질 수 있다.나는 가방을 용량 오름차순으로 처리하면서, 현재 가방에 들어가는 보석 중 가장 비싼 것을 선택했다.작은 가방부터 처리→ 현재 용량 이하인 보석을 후보에 추가→ 후보 중 가격이 가장 높은 보석 선택이 과정을 빠르게 처리하기 위해 보석은 무게순으로 정렬하고 후보 가격은 최대 힙에 저.. 2024. 5. 14.
[백준] 11066: 파일 합치기 - 누적합과 구간 DP로 최소 비용 구하기 (Java) 문제 바로가기파일을 합치는 순서에 따라 총비용이 달라진다여러 파일을 순서대로 하나의 파일로 합칠 때 필요한 최소 비용을 구해야 한다. 인접한 파일이나 이미 합쳐진 연속 구간끼리 합칠 수 있고, 두 파일을 합치는 비용은 두 파일 크기의 합이다.예를 들어 크기가 40, 30, 30인 파일이 있다고 하자.앞의 두 파일을 먼저 합치면 다음과 같다.40 + 30 = 7070 + 30 = 100총비용 = 70 + 100 = 170뒤의 두 파일을 먼저 합치면 비용이 달라진다.30 + 30 = 6040 + 60 = 100총비용 = 60 + 100 = 160최종 파일의 크기는 어느 순서로 합쳐도 100이다. 하지만 중간 파일을 만들 때 낸 비용까지 누적되므로 총비용은 달라진다.처음에는 크기가 작은 파일부터 합치면 될 것.. 2024. 5. 14.
[백준] 11049: 행렬 곱셈 순서 - 구간 DP로 최소 연산 횟수 구하기 (Java) 문제 바로가기곱셈 순서에 따라 연산 횟수가 달라진다여러 행렬을 입력된 순서대로 모두 곱할 때 필요한 곱셈 연산의 최솟값을 구해야 한다. 행렬의 순서를 바꿀 수는 없지만, 괄호를 묶는 위치는 바꿀 수 있다.크기가 A × B인 행렬과 B × C인 행렬을 곱하려면 다음 횟수의 연산이 필요하다.A × B × C예를 들어 세 행렬의 크기가 다음과 같다고 하자.M0: 5 × 3M1: 3 × 2M2: 2 × 6왼쪽부터 곱하는 경우는 다음과 같다.(M0 × M1) × M2M0 × M1: 5 × 3 × 2 = 30결과 행렬: 5 × 2(5 × 2) × M2: 5 × 2 × 6 = 60총 연산 횟수: 90뒤의 두 행렬을 먼저 곱하면 비용이 달라진다.M0 × (M1 × M2)M1 × M2: 3 × 2 × 6 = 36결과 행.. 2024. 5. 14.
[백준] 2410: 2의 멱수의 합 - 1의 개수로 경우를 나누는 DP (Java) 문제 바로가기같은 수를 순서만 바꾼 경우는 하나로 센다정수 N을 2의 멱수의 합으로 나타내는 방법의 수를 구해야 한다.사용할 수 있는 수는 다음과 같다.1, 2, 4, 8, 16, ...같은 수를 여러 번 사용할 수 있지만 순서는 구분하지 않는다. 예를 들어 1 + 2와 2 + 1은 같은 방법이다.처음에는 각 멱수를 동전처럼 보고 일반적인 동전 조합 DP를 사용할 수 있다고 생각했다. 하지만 이 문제에서는 2의 멱수라는 규칙을 이용하면 1차원 점화식을 더 간단하게 만들 수 있다.dp[n] = n을 2의 멱수의 합으로 나타내는 방법의 수핵심은 각 표현에 포함된 1의 개수를 기준으로 경우를 나누는 것이다.1이 두 개 이상인 경우어떤 표현에 1이 두 개 이상 들어 있다면 그중 1 두 개를 제거할 수 있다.n의.. 2024. 5. 13.
[백준] 1655: 가운데를 말해요 - 두 힙으로 중앙값 유지하기 (Java) 문제 바로가기입력될 때마다 정렬하면 반복 작업이 많다숫자가 하나씩 들어올 때마다 지금까지 입력된 숫자의 중앙값을 출력해야 한다. 숫자의 개수가 짝수라면 가운데 두 값 중 작은 값을 출력한다.처음 떠올릴 수 있는 방법은 숫자를 배열에 추가하고 매번 정렬하는 것이다. 하지만 숫자가 들어올 때마다 전체를 다시 정렬하면 이미 정리했던 값까지 반복해서 처리한다.이 문제에서는 전체 정렬 결과보다 가운데 값만 계속 알면 된다. 나는 숫자를 중앙값 기준으로 두 그룹에 나누고, 각 그룹에서 중앙에 가장 가까운 값만 바로 꺼낼 수 있도록 우선순위 큐 두 개를 사용했다.자료구조저장하는 값맨 위의 값left작은 값 절반작은 쪽에서 가장 큰 값right큰 값 절반큰 쪽에서 가장 작은 값left는 최대 힙, right는 최소 힙.. 2024. 5. 13.
[백준] 15681: 트리와 쿼리 - DFS와 트리 DP로 서브트리 크기 미리 구하기 (Java) 문제 바로가기질문마다 같은 하위 정점을 다시 세지 않는다트리의 간선과 루트 R이 주어진다. 각 질문에서는 정점 U를 루트로 하는 서브트리에 정점이 몇 개 있는지 구해야 한다. U 자신도 개수에 포함한다.나는 질문마다 DFS를 다시 실행하면 같은 정점을 반복해서 세게 된다고 생각했다. 트리와 루트가 질문 사이에 바뀌지 않으므로, R에서 DFS를 한 번 실행해 모든 정점의 서브트리 크기를 저장했다.전처리: 루트 R에서 DFS → 모든 정점의 서브트리 크기 저장질문: dp[U] 조회 → 바로 출력여기서 U를 기준으로 트리 전체의 루트를 다시 정하는 것은 아니다. R을 기준으로 정해진 부모와 자식 관계에서 U와 그 자손만 세는 것이다.서브트리 크기는 자신 1개와 자식들의 크기의 합이다상태를 다음과 같이 정의.. 2024. 5. 13.

티스토리툴바