[ 코테 준비 PGS ] 코딩 테스트 합격자 되기(자바 편) - Ch 5

Ch 05. 배열

배열 개념

• 배열은 인덱스와 값을 일대일 대응해 관리하는 자료구조
• 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있다.
• 어디에 있는지만 알면 빠르게 탐색할 수 있으며 해당 접근 방식을 임의 접근(random access)라고 한다.

 

• 배열과 ArrayList의 차이점은 배열은 처음 선언할 때 배열의 크기가 결정되고, ArrayList는 크기가 동적이라는 것이다.
• 따라서 정확한 데이터의 개수를 알 수 있다면 코드가 더 간결하고 속도가 더 빠른 배열을 사용하면 되고, 저장해야 할 데이터의 개수를 정확히 알 수 없다면 ArrayList를 사용하면 된다.
• 엄밀히 말하자면 ArrayList도 초기에 크기가 결정되지만 동적으로 변하는 것처럼 구현되어 있다.

 

• 배열과 차원
  • 배열은 2차원 배열, 3차원 배열과 같이 다차원 배열을 사용할 때도 많다.
  • 하지만 컴퓨터 메모리의 구조는 1차원이므로 2차원, 3차원 배열도 실제로는 1차원 공간에 저장한다.
  • 다시 말해 차원과 무관하게 메모리에 연속 할당된다.
• 1차원 배열
  • 가장 간단한 배열 형태
  • "간단하다"라고 말한 이유는 1차원 배열의 모습이 메모리에 할당된 실제 배열 모습과 같다는 것
  • 왼쪽이 1차원 배열의 모습이고 오른쪽이 실제 메모리에 배열이 할당된 모습이다.
  • 배열의 각 데이터는 메모리의 낮은 주소에서 높은 주소 방향으로 연이어 할당된다.

• 2차원 배열
  • 1차원 배열을 확장한 것
  • 2차원 배열 데이터에 접근하는 방법은 1차원 배열과 비슷하다.
  • 왼쪽은 2차원 배열을 사람이 이해하기 쉽도록 2차원으로 표현한 것이고, 오른쪽은 실제 메모리에 2차원 배열이 저장된 상태를 표현한 것이다.
  • 사람이 이해하기에는 왼쪽의 형태로 이해하는 것이 편리하므로 2차원 배열을 왼쪽의 행과 열 공간처럼 표현하는 경우가 많지만 실제로는 오른쪽처럼 0행, 1행 순서로 데이터를 할당해 1차원 공간에 저장한다.
  • 엄밀히 말하자면 자바에서는 1차원 배열 역시 하나의 객체이므로, 2차원 배열을 1차원 배열 객체의 배열로 표현한다. 즉, 2차원 배열은 1차원 배열 객체가 여러 개 있는  것이다. 따라서 2차원 배열은 메모리에 데이터가 반드시 연속으로 저장되지는 않을 수 있다.

 

ArrayList 사용법

• ArrayList에 데이터 추가

// add() 메서드로 데이터 추가
ArrayList<Integer> list = new ArrayList<>();

// 리스트의 맨 끝에 데이터 추가
list.add(1); // [1]
list.add(2); // [1, 2]
list.add(3); // [1, 2, 3]

 

• 다른 컬렉션의 데이터로부터 초기화
  • ArrayList의 생성자의 매개변수로 컬렉션을 넘기면 매개변수로 넘긴 컬렉션에 담긴 데이터로 초기화할 수 있다.

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

list.add(1);
list.add(2);
list.add(3);

ArrayList<Integer> list2 = new ArrayList<>(list);
System.out.println(list2); // [1, 2, 3]

 

• get() 메서드로 인덱스를 통해 데이터에 접근
  • 특정 인덱스에 있는 데이터를 접근하기 위해서는 get() 메서드를 사용하면 된다.

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

list.add(1);
list.add(2);
list.add(3);

System.out.println(list.get(1)); // 2

 

• remove() 메서드로 데이터 삭제
  • remove() 메서드를 사용하면 특정 위치의 데이터를 삭제할 수 있다.
  • 다만 remove() 메서드는 데이터를 삭제하는 위치에 따라 데이터를 복사하는 연산이 필요하므로 시간 복잡도가 O(N)까지 증가할 수 있기 때문에 주의해야 한다.

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

list.add(1);
list.add(2);
list.add(3);

list.remove(list.size() - 1); // 끝에 있는 데이터 삭제
System.out.println(list); // [1, 2]

 

• 깨알같은 배열, ArrayList 연관 메서드
  • 배열의 전체 데이터 개수를 가진 length 변수
  • 배열의 모든 데이터를 정렬하는 Arrays 클래스의 sort() 메서드
  • 배열의 모든 데이터를 String으로 반환하는 Arrays 클래스의 toString() 메서드
  • ArrayList의 전체 데이터 개수를 반환하는 size() 메서드
  • ArrayList에 저장된 데이터가 없는지 여부를 반환하는 isEmpty() 메서드
  • ArrayList의 모든 데이터를 정렬하는 Collections 클래스의 sort() 메서드
  • sort() 메서드에 정렬하려는 대상 외에 다른 인수를 전달하지 않으면 전체 데이터를 오름차순으로 정렬한다. 특정 범위의 데이터만 정렬하고자 할 때에는 From 인덱스와 To 인덱스를 지정해서 정렬할 수도 있다.

int[] arr = {1, 2, 4, 5, 3};
System.out.println(arr.length); // 5
Arrays.sort(arr); // 정렬 [1, 2, 3, 4, 5]
System.out.println(Arrays.toString(arr)); // 출력 [1, 2, 3, 4, 5]

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 4, 5, 3));
System.out.println(list.size()); // 5
System.out.println(list.isEmpty()); // false
Collections.sort(list); // 정렬 [1, 2, 3, 4, 5]
System.out.println(list); // 출력 [1, 2, 3, 4, 5]

 

ArrayList의 효율성

• 배열 연산의 시간 복잡도
  • 배열 데이터에 접근할 때의 시간 복잡도를 알아보자
  • 배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단번에 접근할 수 있다. 따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)이다.
  • 배열에 데이터를 추가하는 경우에는 배열은 데이터를 어디에 저장하느냐에 따라 추가 연산에 대한 시간 복잡도가 달라진다.
  • 삭제 연산의 경우도 추가와 마찬가지의 시간 복잡도를 가진다.
• 맨 뒤에 삽입할 경우
  • 맨 뒤에 데이터를 추가할 경우에는 임의 접근을 바로 할 수 있으며 데이터를 삽입해도 다른 데이터 위치에 영향을 주지 않는다. 따라서 시간 복잡도는 O(1)이다.
• 맨 앞에 삽입할 경우
  • 이 경우에는 기존 데이터들을 뒤로 한 칸씩 밀어야 한다. 즉, 미는 연산이 필요하다.
  • 데이터 개수를 N개로 일반화하면 시간 복잡도는 O(N)이 된다.
• 중간에 삽입할 경우
  • 현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산을 해야 한다. 밀어야 하는 데이터 개수가 N개라면 시간 복잡도는 O(N)이다.
• 배열을 선택할 때 고려할 점
  • 데이터에 자주 접근하거나 읽어야 하는 경우 배열을 사용하면 좋은 성능을 낼 수 있다.
  • 예를 들어 그래프를 표현할 때 배열을 활용하면 임의 접근을 할 수 있으므로 간선 여부도 시간 복잡도 O(1)로 판단할 수 있다.
  • 하지만 배열은 메모리 공간을 충분히 확보해야 하는 단점도 있다.
  • 다시 말해 배열은 임의 접근이라는 특징이 있어 데이터에 인덱스로 바로 접근할 수 있어 데이터에 빈번하게 접근하는 경우 효율적이지만 메모리 낭비가 발생할 수 있다.
  • 따라서 다음 사항을 고려해 배열을 선택해야 한다.
    • 할당할 수 있는 메모리 크기를 확인해야 한다. 배열로 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당에 실패할 수 있다. 운영체제마다 배열을 할당할 수 있는 메모리의 한계치는 다르지만 보통은 정수형 1차원 배열은 1000만개, 2차원 배열은 3000*3000 크기를 최대로 생각한다.
    • 중간에 데이터 삽입이 많은지 확인해야 한다. 배열은 선형 구조이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아져 실제 시험에서 시간 초과가 발생할 수 있다.

 

몸풀기 문제

• Arrays.sort() 메서드는 배열을 오름차순으로 정렬한다.
• 주목할 점은 sort() 메서드가 원본 배열 자체를 정렬시킨다는 것이다.
• 만약 원본 배열을 그대로 두고 싶다면 다음과 같이 구현하면 된다.

private static int[] solution(int[] arr){
    int[] clone = arr.clone();
    Arrays.sort(clone);
    return clone;
}

.

• 아래의 코드에서 원본 배열을 그대로 수정한 코드는 org의 출력값이 초깃값 [4, 2, 3, 1, 5]가 아니라 [1, 2, 3, 4, 5]로 바뀌어 있다.
• 참조값이 solution() 메서드로 넘어가 원본을 수정한 것이다.
• 원본 배열의 상태를 유지하면서 원본 배열로부터 새로운 배열을 복사해서 사용해야 되는 상황에서는 clone()메서드를 사용해야 한다.

// clone() 메서드를 사용하지 않고 원본 배열을 수정한 경우
public static void main(String[] args){
    int[] org = {4, 2, 3, 1, 5};
    int[] sorted = solution(org);
    System.out.println(Arrays.toString(org)); // [1, 2, 3, 4, 5]
    System.out.println(Arrays.toString(sorted)); // [1, 2, 3, 4, 5]
}

private static int[] solution(int[] arr) {
    int[] clone = arr;
    Arrays.sort(clone);
    return clone;
}

 

• sort()  메서드를 사용하지 않고 O(N²) 알고리즘을 사용하면?
  • O(N²) 정렬 알고리즘인 버블 정렬을 활용한 첫 번째 방법과, O(NlogN) 시간 복잡도를 가진 sort() API를 활용한 두번째 방법이 있다.
  • 결과를 보면 시간 차이가 상당히 난다.
  • 데이터 100,000개를 오름차순으로 정렬하는 데 버블 정렬은 1초가 걸렸지만 두 번째 방법은 0.1초도 걸리지 않았다.
  • 실행 환경마다 시간의 차이는 조금 생길 수 있겠지만 압도적으로 sort() API가 성능이 좋다는 것을 알 수 있다.
  • 참고로 sort() API의 정렬 알고리즘은 Dual-Pivot QuickSort혹은 Tim-Sort이다.