시작 시간 10:30
- 최소 길이의 하위 배열
문제 제안: 이 문제의 핵심은 슬라이딩 윈도우 개념을 이해하는 것입니다. 텍스트 설명은 다소 복잡할 수 있으므로 동영상 강의를 먼저 참고하는 것이 좋습니다. 확장 문제는 우선 생략해도 됩니다. 문제 링크: https://leetcode.cn/problems/minimum-size-subarray-sum/ 강의 자료: https://programmercarl.com/0209.길이-최소-하위-배열.html 동영상 강의: https://www.bilibili.com/video/BV1tZ4y1q7XE
문제 감상: 슬라이딩 윈도우는 두 포인터 기법이라는 점에서 매우 유용합니다. 윈도우의 끝 지점을 결정하는 반복문을 통해 right 포인터가 오른쪽으로 이동할 때마다 해당 값을 sum에 추가합니다. sum이 목표 값보다 크거나 같아지면 현재 두 포인터 사이의 거리를 계산하고, 이전 최소 거리와 비교하여 갱신합니다. 이후 left 포인터의 값을 빼고 left를 오른쪽으로 이동한 후 다시 비교 과정을 반복합니다. 이 과정을 right 포인터가 배열 끝에 도달할 때까지 반복합니다.
int start = 0;
int currentSum = 0;
int minLength = Integer.MAX_VALUE;
for (int end = 0; end < nums.length; end++) {
currentSum += nums[end];
while (currentSum >= target) {
minLength = Math.min(minLength, end - start + 1);
currentSum -= nums[start++];
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
- 나선 행렬 II
문제 제안: 이 문제의 핵심은 순환 로직입니다. 이진 탐색에서 사용한 구간 정의 방식이 여기서 다시 활용됩니다.
문제 링크: https://leetcode.cn/problems/spiral-matrix-ii/ 강의 자료: https://programmercarl.com/0059.나선-행렬-II.html 동영상 강의: https://www.bilibili.com/video/BV1SL4y1N7mV/
문제 감상:
- 반복 구조를 처리할 때 반복 불변량 원칙을 지키는 것이 중요합니다. 여러 반복이 존재할 경우 불변량을 무시하면 각 반복 사이에 데이터 처리 로직이 복잡해지고 재사용성이 떨어집니다. 이를 방지하기 위해 모든 변수 업데이트와 종료 조건을 일관된 기준으로 관리해야 합니다.
- 순환 로직을 설계할 때는 한 번씩 회전하는 방식으로 접근해야 합니다. 각 회전에는 상, 하, 좌, 우 네 가지 방향의 반복이 포함되며, 시작점, 오프셋, 반복 횟수 등의 변수를 정의해야 합니다. 홀수 차수의 행렬일 경우 중앙 위치를 별도로 처리해야 합니다.
int[][] matrix = new int[n][n];
int startX = 0, startY = 0; // 각 루프의 시작 위치
int offset = 1;
int value = 1; // 채워야 할 숫자
int loopCount = 1; // 현재 루프 횟수
int i, j; // j는 열, i는 행
while (loopCount <= n / 2) {
// 상단
for (j = startY; j < n - offset; j++) {
matrix[startX][j] = value++;
}
// 우측
for (i = startX; i < n - offset; i++) {
matrix[i][j] = value++;
}
// 하단
for (; j > startY; j--) {
matrix[i][j] = value++;
}
// 좌측
for (; i > startX; i--) {
matrix[i][j] = value++;
}
startX++;
startY++;
offset++;
loopCount++;
}
if (n % 2 == 1) {
matrix[startX][startY] = value;
}
return matrix;
구간 합계 접두사 합계는 유용하고 직관적인 알고리즘 개념입니다. 이를 통해 특정 인덱스 범위의 합계를 빠르게 계산할 수 있습니다.
강의 자료: https://www.programmercarl.com/kamacoder/0058.구간-합계.html
문제 감상:
- 구간 합계는 배열 입력 시 누적 합계를 계산하여 저장합니다. 이 누적 배열을 통해 임의의 인덱스 범위 합계를 즉시 계산할 수 있습니다.
- 인덱스가 0인 경우는 특별히 처리할 필요가 없지만, 두 인덱스 모두 0이 아닌 경우는 주의가 필요합니다. 예를 들어 3~7 인덱스의 합계를 계산할 때는 7의 누적 합계에서 2의 누적 합계를 빼야 합니다.
- ACM 문제에서는 직접 입력/출력을 처리해야 하므로, 입력 순서를 주의해야 합니다. 아래 코드는 왼쪽 인덱스부터 입력하는 경우를 기준으로 작성되었습니다.
- 구간 합계는 사전 계산을 통해 후속 연산을 최적화하는 방식입니다.
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] array = new int[n];
int[] prefix = new int[n];
int cumulative = 0;
for (int i = 0; i < n; i++) {
array[i] = scanner.nextInt();
cumulative += array[i];
prefix[i] = cumulative;
}
while (scanner.hasNextInt()) {
int a = scanner.nextInt();
int b = scanner.nextInt();
int total;
if (a == 0) {
total = prefix[b];
} else {
total = prefix[b] - prefix[a - 1];
}
System.out.println(total);
}
scanner.close();
개발자 토지 구매 https://www.programmercarl.com/kamacoder/0044.개발자-토지-구매.html 문제 감상:
- 처음에는 분할 방법을 이해하지 못했지만, 단일 방향(수직 또는 수평)으로만 분할해야 한다는 것을 알게 되었습니다. 이에 따라 수직과 수평 방향을 별도로 분석하여 최소 차이를 계산해야 합니다.
- 토지 차이 계산은 전체 합에서 왼쪽 부분을 두 배로 뺀 값으로 계산됩니다. 수직 분할의 경우, 각 행의 합을 계산하여 비교하고, 수평 분할의 경우 각 열의 합을 계산하여 비교합니다.
- 계산 과정에서는 각 행과 열의 합을 먼저 계산한 후, 차이를 비교하여 결과를 도출합니다.
Scanner scanner = new Scanner(System.in);
int rows = scanner.nextInt();
int cols = scanner.nextInt();
int total = 0;
int[][] grid = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
grid[i][j] = scanner.nextInt();
total += grid[i][j];
}
}
// 가로 합계 계산
int[] horizontalSums = new int[rows];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
horizontalSums[i] += grid[i][j];
}
}
// 세로 합계 계산
int[] verticalSums = new int[cols];
for (int j = 0; j < cols; j++) {
for (int i = 0; i < rows; i++) {
verticalSums[j] += grid[i][j];
}
}
int minDifference = Integer.MAX_VALUE;
int currentHorizontal = 0;
for (int i = 0; i < rows; i++) {
currentHorizontal += horizontalSums[i];
minDifference = Math.min(minDifference, Math.abs(total - 2 * currentHorizontal));
}
int currentVertical = 0;
for (int j = 0; j < cols; j++) {
currentVertical += verticalSums[j];
minDifference = Math.min(minDifference, Math.abs(total - 2 * currentVertical));
}
System.out.println(minDifference);
scanner.close();