학습 키워드
- 알고리즘
- 자료구조
알고리즘
완전탐색
가능한 모든 경우의 수를 확인하여 문제를 해결하는 방법입니다.
장점
- 구현이 단순하고 이해하기 쉽습니다.
- 모든 경우를 확인하므로 반드시 정답을 찾을 수 있습니다.
- 문제를 처음 접근할 때 좋은 시작점이 됩니다.
단점
- 모든 경우를 확인하므로 실행 시간이 오래 걸립니다.
- 경우의 수가 많아지면 현실적으로 해결이 어려울 수 있습니다.
그라디 알고리즘
현재 상황에서 가장 좋아 보이는 선택을 하는 방법입니다.
장점
- 구현이 비교적 단순하고 실행 속도가 빠릅니다.
- 직관적이어서 이해하기 쉽습니다.
단점
- 항상 최적의 해를 보장하지는 않습니다.
- 적용할 수 있는 문제의 유형이 한정적입니다.
자료구조
자료구조란
- 데이터를 일정한 규칙에 따라 체계적으로 저장하고 관리하는 방식입니다.
- 데이터를 효과적으로 다루기 위해 만들어진 다양한 규칙과 구조가 바로 자료구조입니다.
효율적인 데이터 관리
- 많은 양의 데이터를 효율적으로 저장하고 찾을 수 있습니다.
- 데이터의 추가, 삭제, 검색을 더 빠르게 할 수 있습니다.
메모리 효율성
- 데이터를 구조화함으로써 메모리를 효율적으로 사용할 수 있습니다.
- 프로그램의 성능을 향상시킬 수 있습니다.
기본자료 구조
- 배열: 데이터를 순서대로 저장하는 방식입니다.
- 고정된 크기의 데이터를 순서대로 저장하고 빠르게 접근해야 한다면 사용합니다.
- 예:
[10, 20, 30, 40]
- 연결 리스트: 데이터가 노드로 연결된 구조입니다.
- 데이터 추가와 삭제가 많다면 사용합니다.
- 예:
[10] → [20] → [30] → [40]
- 스택: 나중에 넣은 것이 먼저 나오는 후입선출 방식입니다.
- 최근 사용한 데이터를 우선적으로 처리해야 한다면 사용합니다.
- 예:
탄알집
- 큐: 먼저 넣은 것이 먼저 나오는 선입선출 방식입니다.
- 데이터를 시간 순서대로 처리해야 한다면 사용합니다.
- 예:
대기줄
응용 자료구조
- 트리: 계층적 관계로 저장하며, 부모-자식 관계를 표현합니다.
- 데이터가 계층적으로 정리되어 있다면 사용합니다.
- 예:
파일 탐색기, 가계도
- 그래프: 데이터 간의 연결 관계를 표현합니다.
- 복잡한 관계를 표현해야 할 때 사용합니다.
- 예:
지하철 노선도, 소셜 네트워크
- 해시 테이블: 키-값 쌍으로 데이터를 저장합니다.
- 키를 통한 빠른 데이터 검색과 삽입이 필요하고 데이터의 순서가 중요하지 않을 때 사용합니다.
- 예:
사전, 단어집
1차원 배열
순차 탐색
- 배열의 처음부터 끝까지 순서대로 하나씩 탐색하는 가장 기본적인 탐색 방법입니다.
- 정렬되지 않은 배열에서도 사용할 수 있는 범용적인 탐색 방법입니다.
- 시간복잡도: O(N)
public class SequentialSearch {
public static int sequentialSearch(int[] arr, int target) {
// 1. 배열의 첫 번째 요소부터 시작
// 1-1. 배열을 순차적으로 탐색하기 위한 반복문 시작
for (int i = 0; i < arr.length; i++) {
// 1-2. 현재 인덱스의 요소에 접근
// 2. 찾고자 하는 값(target)과 현재 요소 비교
// 2-1. target과 현재 요소가 일치하면, 현재 인덱스 반환
if (arr[i] == target) {
return i;
}
// 2-2. 일치하지 않으면, 다음 인덱스로 이동하여 1-2부터 반복
}
// 3. 배열 탐색 완료 후 결과 처리
// 3-1. 배열 끝까지 탐색했는데 찾지 못한 경우 실패(-1) 반환
return -1;
}
public static void main(String[] args) {
// 테스트를 위한 예제 배열과 찾을 값 설정
int[] arr = {4, 2, 7, 1, 9, 3};
int target = 7;
// 순차 탐색 수행 및 결과 출력
int result = sequentialSearch(arr, target);
if (result != -1) {
System.out.println("찾은 위치: " + result);
} else {
System.out.println("값을 찾지 못했습니다.");
}
}
}이진 탐색
- 정렬된 배열에서 효율적으로 원하는 값을 찾기 위한 알고리즘입니다.
- 매 단계마다 탐색 범위를 절반으로 줄여가며 검색을 수행하므로 더 빠른 결과를 얻을 수 있습니다.
- 시간복잡도: O(log N)
public class Solution {
private static int binarySearch(int[] arr, int target) {
// 1. 탐색 범위의 시작점과 끝점 설정
// 1-1. left는 배열의 첫 번째 인덱스로 설정
int left = 0;
// 1-2. right는 배열의 마지막 인덱스로 설정
int right = arr.length - 1;
// 2. 탐색 범위가 유효한 동안 반복
while (left <= right) {
// 2-1. 중간 위치 계산
int mid = (left + right) / 2;
// 3. 중간 값과 target 비교 후 처리
// 3-1. 중간 값이 target과 같으면 해당 인덱스 반환
if (arr[mid] == target) {
return mid;
}
// 3-2. 중간 값이 target보다 크면 오른쪽 범위를 줄임
else if (arr[mid] > target) {
right = mid - 1;
}
// 3-3. 중간 값이 target보다 작으면 왼쪽 범위를 줄임
else {
left = mid + 1;
}
}
// 4. 탐색 완료 후 결과 처리
// 4-1. 찾지 못한 경우 실패(-1) 반환
return -1;
}
public static void main(String[] args) {
// 테스트를 위한 정렬된 예제 배열과 찾을 값 설정
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}; //정렬된 배열이어야 함
int target = 7;
// 이진 탐색 수행 및 결과 출력
int result = binarySearch(arr, target);
if (result != -1) {
System.out.println("찾은 위치: " + result);
} else {
System.out.println("값을 찾지 못했습니다.");
}
}
}투 포인터
- 두 개의 포인터를 이용하여 배열을 탐색하는 방법입니다.
- 두 개의 점을 이동 시키면서 원하는 값을 찾습니다.
- 연속된 구간의 합이나 특정 조건을 만족하는 부분을 찾을 때 주로 사용됩니다.
- 배열의 연속된 원소들의 합이
value이상이 되는 최소 길이의 부분 배열을 구하거나, 두 수를 선택해 목표 합을 만들 수 있는지 판단하는 문제에 적용할 수 있습니다.
- 배열의 연속된 원소들의 합이
- 시간복잡도: O(N)
public class Solution {
public static boolean findTwoSum(int[] arr, int target) {
// 1. 포인터 초기화
// 1-1. left 포인터는 배열의 첫 번째 인덱스로 설정
int left = 0;
// 1-2. right 포인터는 배열의 마지막 인덱스로 설정
int right = arr.length - 1;
// 2. 두 포인터가 교차하기 전까지 반복
while (left < right) {
// 2-1. 현재 두 포인터가 가리키는 값의 합 계산
int sum = arr[left] + arr[right];
// 2-2. 합과 목표값 비교
// 3. 합과 목표값 비교 후 포인터 이동
// 3-1. 합이 목표값과 같으면 true 반환 (쌍을 찾음)
if (sum == target) {
System.out.println("찾은 두 수: " + arr[left] + ", " + arr[right]);
return true;
}
// 3-2. 합이 목표값보다 작으면 left 포인터를 오른쪽으로 이동 (더 큰 값 필요)
else if (sum < target) {
left++;
}
// 3-3. 합이 목표값보다 크면 right 포인터를 왼쪽으로 이동 (더 작은 값 필요)
else {
right--;
}
}
// 4. 탐색 완료 후 결과 처리
// 4-1. 목표값을 만드는 쌍을 찾지 못한 경우 false 반환
return false;
}
public static void main(String[] args) {
// 테스트를 위한 예제 배열과 목표 합 설정
int[] arr = {4, 1, 8, 7, 3, 2}; // 정렬되지 않은 배열
int target = 10; // 찾고자 하는 합
// 투 포인터 탐색 수행 및 결과 출력
System.out.println("원본 배열: " + Arrays.toString(arr));
System.out.println("목표 합: " + target);
boolean result = findTwoSum(arr, target);
System.out.println("합이 " + target + "이 되는 두 수가 " +
(result ? "존재합니다." : "존재하지 않습니다."));
}
}import java.util.Arrays;
public class Solution {
public static int findExactSum(int[] arr, int target) {
// 1. 포인터와 현재 합계, 결과값 초기화
// 1-1. start 포인터는 배열의 첫 번째 인덱스로 설정
int start = 0;
// 1-2. end 포인터는 배열의 두 번째 인덱스로 설정
int end = 1;
// 1-3. 현재까지의 합을 첫 번째 원소로 초기화
// - 초기 구간은 첫 번째 원소만을 포함
// - start 포인터가 가리키는 원소부터 end-1까지의 합
int currentSum = arr[0];
// 1-4. 찾은 구간의 개수를 0으로 초기화
// - target과 정확히 일치하는 구간을 찾을 때마다 증가
int count = 0;
// 2. 구간 탐색
// 배열의 모든 구간을 확인할 때까지 반복
while (start < arr.length) {
// 2-1. 현재 구간의 합이 정확히 target과 같은 경우
if (currentSum == target) {
// target과 일치하는 구간을 찾았으므로 count 증가
count++;
// end가 배열 끝에 도달하지 않은 경우
if (end < arr.length) {
// 구간을 확장하기 위해 end 위치의 원소를 더하고 end 증가
currentSum += arr[end++];
}
// end가 배열 끝에 도달한 경우
else {
// 더 이상 구간을 확장할 수 없으므로 start를 이동
currentSum -= arr[start++];
}
}
// 2-2. end가 배열 끝에 도달하지 않았고, 현재 합이 target보다 작은 경우
else if (end < arr.length && currentSum < target) {
// 구간의 합을 늘리기 위해 end 위치의 원소를 더하고 end 증가
currentSum += arr[end++];
}
// 2-3. end가 배열 끝에 도달했거나, 현재 합이 target보다 큰 경우
else {
// 구간의 합을 줄이기 위해 start 위치의 원소를 빼고 start 증가
currentSum -= arr[start++];
}
}
// 3. 탐색 완료 후 결과 처리
// 3-1. 찾은 모든 구간의 개수 반환
return count;
}
public static void main(String[] args) {
// 테스트를 위한 예제 배열과 목표 합 설정
int[] arr = {1, 2, 3, 1, 2}; // 예시 배열
int target = 3; // 목표값
// 입력 데이터 출력
System.out.println("원본 배열: " + Arrays.toString(arr));
System.out.println("목표 합: " + target);
// 결과 계산 및 출력
int result = findExactSum(arr, target);
System.out.println("합이 정확히 " + target + "인 연속된 구간의 개수: " + result);
// 모든 가능한 구간 출력 (설명을 위한 추가 코드)
System.out.println("\n만족하는 구간들:");
for (int i = 0; i < arr.length; i++) {
int sum = 0;
for (int j = i; j < arr.length; j++) {
sum += arr[j];
if (sum == target) {
System.out.println(Arrays.toString(Arrays.copyOfRange(arr, i, j + 1))
+ " (합: " + sum + ")");
}
}
}
}
}버블 정렬
- 배열을 반복적으로 순회하면서 인접한 두 요소를 비교하여 정렬하는 단순한 정렬 알고리즘입니다.
- 배열의 앞에서부터 차례대로 두 개씩 비교하고, 순서가 잘못된 경우 위치를 바꿔주는 과정을 반복하여 정렬합니다.
- 시간복잡도: O()
- 장점
- 이해하기 쉽고 구현하기 간단합니다.
- 작은 데이터를 정렬할 때 사용하기 좋습니다.
- 단점
- 다른 정렬 알고리즘에 비해 시간복잡도가 큽니다.
- 데이터가 많을 때는 시간이 오래 걸리 수도 있습니다.
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
// 1. 외부 반복문: 정렬 과정(패스)을 몇 번 반복할지를 결정
// - 배열의 크기만큼 반복하며, 한 번 반복할 때마다 하나의 숫자가 최종 위치를 찾음
for (int i = 0; i < n - 1; i++) {
// 2. 내부 반복문: 실제 비교와 교환이 일어나는 과정
// - 이웃한 두 숫자를 비교
// - 범위가 점점 줄어듦 (n-i-1): 이미 정렬된 요소는 제외
for (int j = 0; j < n - i - 1; j++) {
// 3. 인접한 두 요소 비교 및 교환
// - 왼쪽 숫자가 오른쪽 숫자보다 크면 두 숫자의 위치를 바꿈
if (arr[j] > arr[j + 1]) {
// 이웃한 두 수 자리 교환
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 배열 출력을 위한 유틸리티 메서드
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
public static void main(String[] args) {
// 예시 배열 [5, 3, 8, 2]로 테스트
int[] arr = {5, 3, 8, 2};
System.out.println("정렬 전 배열:");
printArray(arr);
// 버블 정렬 수행
bubbleSort(arr);
System.out.println("정렬 후 배열:");
printArray(arr);
}
}계수 정렬
- 데이터의 값을 직접 비교하지 않고, 각 데이터가 몇 번 등장하는지 세어서 정렬하는 알고리즘입니다.
- 정수로 이루어진 배열에서 각 숫자의 출현 횟수를 세고, 이를 이용해 정렬된 배열을 만듭니다.
- 시간복잡도: O(N + K)
- 장점
- 양의 정수 데이터의 정렬 속도가 매우 빠릅니다.
- 비교 연산이 필요 없어서 구현이 간단합니다.
- 단점
- 0 이상의 정수로 표현 가능한 데이터만 정렬할 수 있습니다.
- 데이터의 범위만큼 추가 메모리가 필요합니다.
- 데이터의 최댓값이 매우 크면 비효율적입니다.
public class CountingSort {
public static void countingSort(int[] arr) {
// 1. 최댓값 찾기 - O(N)
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 2. 카운팅 배열 생성 및 초기화
int[] counts = new int[max + 1];
// 3. 숫자 세기 - O(N)
for (int num : arr) {
counts[num]++;
}
// 4. 결과 배열 생성
int index = 0;
for (int i = 0; i <= max; i++) {
while (counts[i] > 0) {
arr[index] = i;
index++;
counts[i]--;
}
}
}
// 배열 출력을 위한 유틸리티 메서드
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
public static void main(String[] args) {
// 예시 배열 [4, 1, 3, 1, 2]로 테스트
int[] arr = {4, 1, 3, 1, 2};
System.out.println("정렬 전 배열:");
printArray(arr);
// 계수 정렬 수행
countingSort(arr);
System.out.println("정렬 후 배열:");
printArray(arr);
}
}안정 계수 정렬
- 동일한 값을 가진 요소들의 원래 순서를 유지하는 정렬 방식입니다.
- 계수 정렬을 안정 정렬로서 구현 하기 위해 누적 합 배열을 사용합니다.
- 시간 복잡도: O(N + K)
public class StableCountingSort {
public static int[] stableCountingSort(int[] arr) {
// 1. 카운팅 배열 생성
// 원본 배열의 최댓값 찾기
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 원본 배열의 최댓값 크기만큼의 카운팅 배열을 생성
int[] counts = new int[max + 1];
// 원본 배열을 순회하면서 각 숫자가 몇 번 등장했는지 카운팅 배열에 기록
for (int num : arr) {
counts[num]++;
}
// 2. 누적 합 배열 생성
// 카운팅 배열과 같은 크기의 누적 합 배열을 생성
int[] cumulative = new int[max + 1];
// 카운팅 배열을 순회하면서 각 위치까지의 누적 합을 계산
cumulative[0] = counts[0];
for (int i = 1; i <= max; i++) {
cumulative[i] = cumulative[i - 1] + counts[i];
}
// 3. 결과 배열 생성
// 결과 배열을 원본 배열과 같은 크기로 생성
int[] result = new int[arr.length];
// 원본 배열을 뒤에서부터 순회
for (int i = arr.length - 1; i >= 0; i--) {
int num = arr[i];
// 현재 숫자를 num이라 할 때, (cumulative[num] - 1)을 인덱스로 하여 결과 배열에 num을 저장
result[cumulative[num] - 1] = num;
// cumulative[num]의 값을 1 감소
cumulative[num]--;
}
return result;
}
// 배열 출력을 위한 유틸리티 메서드
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
public static void main(String[] args) {
// 예시 배열 [4, 1, 3, 1, 2]로 테스트
int[] arr = {4, 1, 3, 1, 2};
System.out.println("정렬 전 배열:");
printArray(arr);
// 안정 계수 정렬 수행하고 결과 받기
int[] sortedArr = stableCountingSort(arr);
System.out.println("정렬 후 배열:");
printArray(sortedArr);
}
}2차원 배열
행과 열 두 차원을 가진 배열입니다.
요소 접근
- 2차원 배열의 각 요소는 [행][열] 2개의 인덱스를 통해 접근합니다.
- 행과 열 모두 0부터 시작하는 인덱스를 가집니다.
- 두 개의 인덱스를 통해 원하는 위치의 데이터에 즉시 접근할 수 있습니다.
크기
- 생성 시점에 행과 열의 크기를 모두 지정해야 합니다.
- 배열의 크기는 변경할 수 없습니다.
- 크기를 변경하려면 새로운 2차원 배열을 만들어야 합니다.
연속된 메모리 공간
- 1차원 배열과 같이 메모리에 연속적으로 저장됩니다.
- 행 우선 또는 열 우선 방식으로 저장될 수 있습니다.
- Java의 경우 행 우선 방식을 사용합니다.
// 2차원 배열 선언과 초기화
int[][] matrix = new int[3][4]; // 3행 4열의 2차원 배열 생성
// 초기 값을 바로 넣어 3행 3열 배열 생성
int[][] scores = {
{90, 85, 95},
{75, 80, 85},
{88, 92, 96}
};
// 2차원 배열 요소 접근하기
matrix[0][1] = 10; // 1행 2열 위치에 10을 저장
int score = scores[1][2]; // scores[1][2]는 2행 3열 값, 즉 85
// 중첩 for문을 이용한 2차원 배열 순회
for (int i = 0; i < scores.length; i++) {
for (int j = 0; j < scores[i].length; j++) {
System.out.print(scores[i][j] + " ");
}
System.out.println(); // 각 행 출력 후 줄바꿈
}
// for-each문을 이용한 2차원 배열 순회
for (int[] row : scores) { // scores 배열에서 한 행씩 꺼내기
for (int value : row) { // 해당 행에서 각 값 꺼내기
System.out.print(value + " ");
}
System.out.println();
}행렬 순회 방법
- 기본 순회: 행 우선, 열 우선, 지그재그
- 시간 복잡도: O(N×M)
- 시간 복잡도: O(N×M)
public class MatrixTraversal {
public static void rowMajorOrder(int[][] arr) {
int rows = arr.length;
int cols = arr[0].length;
// 1. 행 반복문(바깥쪽)과 열 반복문(안쪽) 설정
// 1-1. 행 인덱스 i는 0부터 행의 크기-1까지 반복
for (int i = 0; i < rows; i++) {
// 1-2. 열 인덱스 j는 0부터 열의 크기-1까지 반복
for (int j = 0; j < cols; j++) {
// 2. 현재 위치(i,j)의 원소에 접근
// 2-1. arr[i][j] 형태로 각 원소에 접근
System.out.print(arr[i][j] + " ");
}
// 3. 다음 행으로 이동하여 반복
// 3-1. 현재 행의 순회가 끝나면 다음 행으로 이동
System.out.println();
}
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
System.out.println("행 우선 순회 결과:");
rowMajorOrder(matrix);
}
}public class MatrixTraversal {
public static void columnMajorOrder(int[][] arr) {
int rows = arr.length;
int cols = arr[0].length;
// 1. 열 반복문(바깥쪽)과 행 반복문(안쪽) 설정
// 1-1. 열 인덱스 j는 0부터 열의 크기-1까지 반복
for (int j = 0; j < cols; j++) {
// 1-2. 행 인덱스 i는 0부터 행의 크기-1까지 반복
for (int i = 0; i < rows; i++) {
// 2. 현재 위치(i,j)의 원소에 접근
// 2-1. arr[i][j] 형태로 각 원소에 접근
// 2-2. 각 열을 위에서 아래로 순회
System.out.print(arr[i][j] + " ");
}
// 3. 다음 열로 이동하여 반복
// 3-1. 현재 열의 순회가 끝나면 다음 열로 이동
System.out.println();
}
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
System.out.println("열 우선 순회 결과:");
columnMajorOrder(matrix);
}
}public class MatrixTraversal {
public static void zigzagOrder(int[][] arr) {
int rows = arr.length;
int cols = arr[0].length;
// 1. 행 인덱스에 따른 순회 방향 결정
for (int i = 0; i < rows; i++) {
// 1-1. 행 인덱스(i)가 짝수인 경우: 왼쪽에서 오른쪽으로 순회
if (i % 2 == 0) {
// 2-1. 짝수 행: j를 0부터 열의 크기-1까지 증가
for (int j = 0; j < cols; j++) {
System.out.print(arr[i][j] + " ");
}
}
// 1-2. 행 인덱스(i)가 홀수인 경우: 오른쪽에서 왼쪽으로 순회
else {
// 2-2. 홀수 행: j를 열의 크기-1부터 0까지 감소
for (int j = cols - 1; j >= 0; j--) {
System.out.print(arr[i][j] + " ");
}
}
// 3. 다음 행으로 이동하여 반복
// 3-1. 현재 행의 순회가 끝나면 다음 행으로 이동
System.out.println();
}
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
System.out.println("지그재그 순회 결과:");
zigzagOrder(matrix);
}
}- 델타 탐색
- 현재 위치를 기준으로 상하좌우나 대각선 등 특정 방향의 인접한 요소를 탐색하는 방법입니다.
아래와 같은 5x5 격자가 있다고 가정하겠습니다:
0 1 2 3 4
0[1] [2] [3] [4] [5]
1[6] [7] [8] [9] [10]
2[11][12][13][14][15]
3[16][17][18][19][20]
4[21][22][23][24][25]
현재 위치: (2,3) → 값 14가 있는 칸
상하좌우를 통해 확인할 칸:
- 상: (1,3) 값 9
- 하: (3,3) 값 19
- 좌: (2,2) 값 13
- 우: (2,4) 값 15
1. 델타 배열 정의하기
- 2차원 격자에서 상하좌우 인접 칸을 확인하고 싶다면, 이동 방향은 아래와 같습니다.
- 상(Up): 행 -1, 열 0
- 하(Down): 행 +1, 열 0
- 좌(Left): 행 0, 열 -1
- 우(Right): 행 0, 열 +1
- 이를 배열 형태로 표현해보면 다음과 같습니다.
dx = [0, 0, -1, 1] // 열 변화량: 상(0), 하(0), 좌(-1), 우(1)
dy = [-1, 1, 0, 0] // 행 변화량: 상(-1), 하(1), 좌(0), 우(0)
dx, dy의 인덱스 i에 따라 방향이 결정됩니다.
i=0일 때 상
i=1일 때 하
i=2일 때 좌
i=3일 때 우
2. 현재 위치에서 시작하기
- 현재 탐색하고 싶은 위치를 (row, col)이라 하겠습니다.
3. 델타를 이용한 인접 위치 탐색
- 상하좌우 각각에 대해 새로운 좌표를 계산합니다.
- i=0 (상) 방향일 때:
```
newRow = row + dy[0] = 2 + (-1) = 1
newCol = col + dx[0] = 3 + (0) = 3
```
이때 (1, 3)이 행렬 범위 내인지 확인합니다.
범위 내의 값이라면 필요한 작업을 수행할 수 있습니다.
- i=1 (하) 방향일 때:
```
newRow = 2 + dy[1] = 2 + 1 = 3
newCol = 3 + dx[1] = 3 + 0 = 3
```
새 좌표는 (3,3). 범위 내인지 확인 후 처리합니다.
- i=2 (좌) 방향일 때:
```
newRow = 2 + dy[2] = 2 + 0 = 2
newCol = 3 + dx[2] = 3 + (-1) = 2
```
새 좌표는 (2,2). 범위 내인지 확인 후 처리합니다.
- i=3 (우) 방향일 때:
```
newRow = 2 + dy[3] = 2 + 0 = 2
newCol = 3 + dx[3] = 3 + 1 = 4
```
새 좌표는 (2,4). 범위 내인지 확인 후 처리합니다.행렬의 회전
- 시간 복잡도: O(N×M)
// 90도 회전 (직사각형 행렬)
public static int[][] rotate90(int[][] matrix) {
int N = matrix.length; // 행의 개수
int M = matrix[0].length; // 열의 개수
int[][] result = new int[M][N]; // 결과 배열의 크기가 바뀜
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
result[j][N-1-i] = matrix[i][j];
}
}
return result;
}
// 180도 회전 (직사각형 행렬)
public static int[][] rotate180(int[][] matrix) {
int N = matrix.length;
int M = matrix[0].length;
int[][] result = new int[N][M]; // 원래 크기 유지
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
result[N-1-i][M-1-j] = matrix[i][j];
}
}
return result;
}
// 270도 회전 (직사각형 행렬)
public static int[][] rotate270(int[][] matrix) {
int N = matrix.length;
int M = matrix[0].length;
int[][] result = new int[M][N]; // 결과 배열의 크기가 바뀜
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
result[M-1-j][i] = matrix[i][j];
}
}
return result;
}
반갑습니다!