📌 서론.

바킹독은 배열의 정의, C++에서의 배열의 구현 방법 및 메소드 구현, 해당 메소드의 시간복잡도 설명를 설명했다.

그러나 C++ 기준으로 구현했기에 Java에서 사용되는 정적배열과 동적배열의 차이를 기준으로 해당 글에서 다뤄보고자 한다.

정적 배열의 성질

import java.io.IOException;

public class Main {

  public static void main(String[] args) throws IOException {
    int len = 5;
    int[] arr = {3, 4, 2, 1, 2};

    insert(3, 100, arr, len); //기댓값: 3, 4, 2, 100, 1, 2
    printArr(arr); //결과: 3,4,2,100,1

    System.out.println("----------------------------------------------------");
    int len2 = 5;
    int[] arr2 = {3, 4, 2, 1, 2};

    erase(3, arr2, len2); //기댓값 3, 4, 2, 2
    printArr(arr2);// 결과 : 3,4,2,2,2,
  }

  private static void insert(int index, int value, int[] arr, int len) {
    // 임의의 위치에 원소를 추가
    for (int i = index; i < len - 1; i++) {
      int temp = arr[i];
      arr[i] = value;
      arr[i + 1] = temp;
    }

  }

  private static void erase(int index, int[] arr, int len) {
    // 임의 위치의 원소 제거
    for (int i = index; i < len - 1; i++) {
      arr[i] = arr[i + 1];
    }
  }

  public static void printArr(int[] arr) {
    for (int i : arr) {
      System.out.print(i + " ");
    }
    System.out.println();
  }
}

강의에서 언급된 insert() 와 erase() 를 정적배열로 구현했다.

해당 함수를 돌려보면 원하는 기댓값과 다른 것을 알 수 있다.

정적배열은 메모리 공간에 연속적으로 저장되지만 처음에 지정된 크기에서 변동되는 것이 불가하기 때문이다.

장점

• 메모리 관리가 간편하다. → 배열의 요소가 메모리에 차례대로 저장되기에 관리가 간편하며 추가적으로 소모되는 메모리의 양이 거의 없다.
• 특정 인덱스의 원소를 O(1)로 참조할 수 있음.
• Cache hit rate 가 높음

  Cache hit rate: 캐시에 저장된 데이터를 찾아 사용하는 비율

  CPU는 메모리를 효율적으로 사용하기위해 캐싱을 사용하는데 정적 배열의 경우 다음과 같은 메커니즘으로 효율을 높힐 수있다.
  • 공간적 국소성: 정적 배열은 연속된 메모리 공간에 저장되어 CPU 캐시에 여러 요소를 한 번에 로드 가능
  • 사전 페칭: CPU는 정적 배열의 인접한 요소들을 미리 캐시에 로드하여 데이터 접근 속도를 향상시킬 수 있음.

단점

• 데이터 추가/삭제가 어렵다.
  • 요소 추가시, 공간이 없다면 배열을 재선언하고 기존 데이터를 복사해야하기에 성능이 저하됨.
  • 또한 공간이 있더라도, 데이터를 추가&삭제하려면 삭제할 데이터의 위치에 있는 다른 데이터들을 뒤로 이동해야 하기에 성능이 저하됨.

동적 배열의 성질.

동적 배열은 배열의 크기를 동적으로 변경할 수 있는 자료구조이다. Java의 ArrayList나 Python의 List가 이에 해당한다.

import java.util.ArrayList;

public class Main {

  public static void main(String[] args) {
    ArrayList<Integer> arr = new ArrayList<>(5);
    arr.add(3);
    arr.add(4);
    arr.add(2);
    arr.add(1);
    arr.add(2);

    arr.add(3, 100); // 기댓값: 3, 4, 2, 100, 1, 2
    printArr(arr); // 결과: 3, 4, 2, 100, 1, 2

    System.out.println("----------------------------------------------------");

    arr.remove(3); // 기댓값: 3, 4, 2, 1, 2
    printArr(arr); // 결과: 3, 4, 2, 1, 2
  }

  public static void printArr(ArrayList<Integer> arr) {
    for (int i : arr) {
      System.out.print(i + " ");
    }
    System.out.println();
  }
}

위의 코드에서는 ArrayList를 사용하여 insert()와 erase()를 Java로 구현했다.

장점

• 데이터 추가/삭제가 용이하다.
  • 요소 추가/삭제시, 배열의 크기를 동적으로 조절하므로 용이하다.
  • 공간이 부족하면 배열의 크기를 늘리고, 너무 많은 공간이 남아있다면 줄일 수 있다.
• 데이터 추가/삭제에 따른 성능 저하를 최소화 할 수 있다.

단점

• 메모리 관리가 복잡하다.
  • 배열의 크기를 동적으로 변경하면서 메모리를 할당/해제해야 하므로 관리가 복잡하다.
• 인덱스 제일 앞과 뒤의 원소를 추가/삭제 시간이 O(1)이지만, 다른 곳의 시간복잡도는 O(n)이다.
• 메모리 블록이 연속적이지 않을 수 있으므로, Cache hit rate가 낮을 수 있다.
  -> 24.05.27 이건 틀린말이다. 관련글.

🎯 결론.

정리

구분	정적 배열	동적 배열
크기	고정	동적 변화
메모리 관리	간편	복잡
접근 성능	빠름 (O(1))	느림 (최악의 경우 O(N))
캐싱 효율	높음	낮음
데이터 추가/삭제	어려움	용이
미래 데이터 변동 대비	불가능	용이
사용 상황	데이터 크기 고정, 빠른 접근 성능 중요	데이터 크기 변동, 데이터 추가/삭제 빈번

코딩 테스트 시에는 원소의 삽입과 삭제시, 정적배열과 동적배열의 장단점을 잘 숙지하고 진행해야겠다.