[Coding Test] 자료구조 1

Do it! 알고리즘 코딩테스트 with JAVA
인프런 로드맵 보기

---

배열

배열이란?

메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조

int[] array = new int[100];

배열의 특징

1. 인덱스를 사용하여 값에 바로 접근할 수 있다.
   
2. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다.
   
3. 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.
   

---

리스트

리스트란?

값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조

ArrayList<Integer> list = new ArrayList<>();

리스트의 특징

1. 인덱스가 없고 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. (속도가 느리다.)
2. 포인터로 연결되어 있어 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다.
3. 선언할 때 크기를 별도로 지정하지 않아도 된다.

코딩테스트에서는 리스트를 직접 구현할 필요가 없다.
Java에서 제공하는 ArrayList, LinkedList를 사용하면된다.

---

구간 합

구간 합이란?

합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

합 배열이란??

// S[i] = A[0]부터 A[i]까지의 합
S[i] = A[0] + A[1] + A[2] + ... + A[i - 1] + A[i] 

// 합 배열 S 만드는 공식
S[i] = S[i - 1] + A[i] 

// 구간 합 구하는 공식 (i ~ j)
S[j] - S[i - 1]

합 배열을 이용하면 기존 배열의 일정 구간 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 줄어든다.

---

투 포인터

투 포인터란?

2개의 포인터로 알고리즘의 시간 복잡도를 최적화 하는 방법

int[] arr = {1, 2, 3, 4, 5};
int start = 0, end = 0, sum = 0, count = 0;
int target = 5;

while (end < arr.length) {
    if (sum < target) {
        sum += arr[end++];
    } else if (sum > target) {
        sum -= arr[start++];
    } else {
        count++;
        sum -= arr[start++];
    }
}
System.out.println("합이 " + target + "인 경우의 수: " + count);

투 포인터의 특징

1. 정렬된 배열에서 특정 조건을 만족하는 부분 배열을 찾을 때 자주 사용된다.
2. 시간 복잡도는 보통 O(N)이다. (모든 원소를 한 번씩만 탐색하기 때문)
3. 두 포인터를 이용해 범위를 줄이거나 넓히면서 연속적인 구간을 효율적으로 탐색할 수 있다.

---

슬라이딩 윈도우

슬라이딩 윈도우란?

고정된 크기의 윈도우(부분 배열)를 배열 위에서 한 칸씩 이동시키며 문제를 푸는 기법

int[] arr = {1, 2, 3, 4, 5};
int k = 3; // 윈도우 크기
int maxSum = 0, windowSum = 0;

// 첫 윈도우 합 구하기
for (int i = 0; i < k; i++) {
    windowSum += arr[i];
}
maxSum = windowSum;

// 슬라이딩 윈도우 시작
for (int i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k]; // 앞 요소 빼고, 새 요소 더하기
    maxSum = Math.max(maxSum, windowSum);
}

System.out.println("크기가 " + k + "인 연속 부분 배열 중 최대 합: " + maxSum);

슬라이딩 윈도우의 특징

1. 고정된 크기의 구간에서 최댓값, 최솟값, 합 등을 구할 때 사용한다.
2. 매번 윈도우를 전부 다시 계산하지 않고, 이전 결과를 재활용하여 효율적으로 계산할 수 있다.
3. 시간 복잡도는 O(N)이다. (모든 원소를 한 번씩만 처리하기 때문)