배열 개념에 대해 이해하고 활용하는 방법을 알아봅시다. 코딩 테스트 난이도별로 배열 관련 문제를 풀며, 여러 함정을 확인하고 이를 해결하는 방법에 익숙해지도록 정리했습니다.
1. 배열 개념
배열은 인덱스와 값을 일대일 대응해 관리하는 자료구조입니다. 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있습니다.
1.1 배열 선언
배열을 선언하는 방법은 다음과 같습니다. 이름이 arr이고 길이가 6인 정수형 배열을 선언하는 방법을 알아보겠습니다.
1.1.1 일반적인 방법
int[] arr = {0, 0, 0, 0, 0, 0}; // ➊
int[] arr = new int[6]; // ➋ 결괏값 동일
이렇게 선언한 배열은 컴퓨터에 이런 모습으로 저장됩니다.
배열은 인덱스가 0부터 시작합니다. 즉, 3번째 데이터에 접근하려면 arr[2]와 같이 접근하면 됩니다. ➊과 ➋는 결괏값이 동일합니다. 자세히 말하자면 자바에서는 배열을 생성하면, int형 배열은 기본값을 0으로 초기화하므로 ➊과 ➋는 실행 결과가 동일합니다. 배열은 코딩 테스트에서 가장 많이 사용하는 자료구조이므로 확실히 알아두고 넘어가야 합니다.
자바에는 배열과 유사한 기능을 가진 ArrayList 자료구조가 있습니다. 배열과 ArrayList의 차이점은 배열은 처음 선언할 때 배열의 크기가 결정되고, ArrayList는 크기가 동적이라는 것입니다. 따라서 정확한 데이터의 개수를 알 수 있다면 코드가 더 간결하고 속도가 더 빠른 배열을 사용하면 되고, 저장해야 할 데이터의 개수를 정확히 알 수 없다면 ArrayList를 사용하시면 됩니다.
※ 엄밀히 말하자면 ArrayList도 초기에 크기가 결정되지만 동적으로 변하는 것처럼 구현되어 있습니다.
1.2 배열과 차원
배열은 2차원 배열, 3차원 배열과 같이 다차원 배열을 사용할 때도 많습니다. 하지만 컴퓨터 메모리의 구조는 1차원이므로 2차원, 3차원 배열도 실제로는 1차원 공간에 저장합니다. 다시 말해 배열은 차원과는 무관하게 메모리에 연속 할당됩니다.
1.2.1 1차원 배열
1차원 배열은 가장 간단한 배열 형태를 가집니다. “간단하다”라고 말한 이유는 1차원 배열의 모습이 메모리에 할당된 실제 배열의 모습과 같다는 겁니다. 다음 그림을 보면 쉽게 이해할 수 있습니다.
왼쪽 그림이 1차원 배열의 모습이고, 오른쪽 모습이 실제 메모리에 배열이 할당된 모습입니다. 배열의 각 데이터는 메모리의 낮은 주소에서 높은 주소 방향으로 연이어 할당됩니다.
1.2 2차원 배열
2차원 배열은 1차원 배열을 확장한 겁니다. 2차원 배열은 자바에서 다음과 같이 선언할 수 있습니다.
// 2차원 배열 생성
int[][] arr = {{1, 2, 3}, {4, 5 ,6}};
// arr[1][2]에 저장된 값을 출력
System.out.println(arr[1][2]); // 6
// arr[1][2]에 저장된 값을 7로 변경
arr[1][2] = 7;
// 변경된 값을 출력
System.out.println(arr[1][2]); // 7
2차원 배열 데이터에 접근하는 방법은 1차원 배열과 비슷합니다. 행과 열을 명시해 [ ] 연산자를 2개 연이어 사용한다는 점만 다릅니다.
int[][] arr = {{1, 2, 3}, {4, 5 ,6}}; // 2행 3열 2차원 배열 선언
이를 그림으로 나타내면 다음과 같습니다.
왼쪽은 2차원 배열을 사람이 이해하기 쉽도록 2차원으로 표현한 것이고, 오른쪽은 실제 메모리에 2차원 배열이 저장된 상태를 표현한 겁니다. 사람이 이해하기에는 왼쪽의 형태로 이해하는 것이 편리하므로 2차원 배열을 왼쪽의 행과 열 공간처럼 표현하는 경우가 많지만 실제로는 오른쪽처럼 0행, 1행 순서로 데이터를 할당해 1차원 공간에 저장합니다. 이런 배열의 특성을 잘 기억해두기 바랍니다.
※ 엄밀히 말하자면 자바에서는 1차원 배열 역시 하나의 객체이므로, 2차원 배열을 1차원 배열 객체의 배열로 표현합니다. 즉, 2차원 배열은 1차원 배열 객체가 여러 개 있는 것입니다. 따라서 2차원 배열은 메모리에 데이터가 반드시 연속으로 저장되지는 않을 수 있습니다.
2. ArrayList 사용법
자바에서 크기가 동적으로 변경되는 배열이 필요할 때는 ArrayList를 활용합니다. 여기서는 코딩 자바에서 크기가 동적으로 변경되는 배열이 필요할 때는 ArrayList를 활용합니다. 여기서는 코딩테스트에 자주 활용하는 ArrayList 사용 방법에 대해서 알아보겠습니다.
2.1 ArrayList에 데이터 추가
여기서는 ArrayList에 데이터를 삽입하는 방법을 알아보겠습니다.
2.1.1 add( ) 메서드로 데이터 추가
맨 끝에 데이터를 추가하려면 add( ) 메서드를 사용하면 됩니다.
ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가
list.add(1); // [1]
list.add(2); // [1, 2]
list.add(3); // [1, 2, 3]
2.1.2 다른 컬렉션의 데이터로부터 초기화
ArrayList의 생성자의 매개변수로 컬렉션을 넘기면 매개변수로 넘긴 컬렉션에 담긴 데이터로 초기화할 수 있습니다.
ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가
list.add(1); // [1]
list.add(2); // [1, 2]
list.add(3); // [1, 2, 3]
ArrayList<Integer> list2 = new ArrayList<>(list);
System.out.println(list2); // [1, 2, 3]
2.1.3 get( ) 메서드로 인덱스를 통해 데이터에 접근
특정 인덱스에 있는 데이터에 접근하기 위해서는 get( ) 메서드를 사용하면 됩니다.
ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가
list.add(1); // [1]
list.add(2); // [1, 2]
list.add(3); // [1, 2, 3]
System.out.println(list.get(1)); // 2
2.1.4 remove( ) 메서드로 데이터 삭제
remove( ) 메서드를 사용하면 특정 위치의 데이터를 삭제할 수 있습니다.
ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가
list.add(1); // [1]
list.add(2); // [1, 2]
list.add(3); // [1, 2, 3]
list.remove(list.size() - 1); // 끝에 있는 데이터 삭제
System.out.println(list); // [1, 2]
다만 remove( ) 메서드는 데이터를 삭제하는 위치에 따라 데이터를 복사하는 연산이 필요하므로 시간 복잡도가 O(N)까지 증가할 수 있기 때문에 주의해야 합니다.
💡[합격 조언] 깨알 같은 배열, ArrayList 연관 메서드
이외에도 코딩 테스트에서 활용하면 유용한 깨알 같은 몇 가지 기능을 코드와 함께 소개하겠습니다.
- 배열의 전체 데이터 개수를 가진 length 변수
- 배열의 모든 데이터를 정렬하는 Arrays 클래스의 sort( ) 메서드
- 배열의 모든 데이터를 String으로 반환하는 Arrays 클래스의 toString( ) 메서드
- ArrayList의 전체 데이터 개수를 반환하는 size( ) 메서드
- ArrayList에 저장된 데이터가 없는지 여부를 반환하는 isEmpty( ) 메서드
- ArrayList의 모든 데이터를 정렬하는 Collections 클래스의 sort( ) 메서드
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]
sort( ) 메서드에 정렬하려는 대상 외에 다른 인수를 전달하지 않으면 전체 데이터를 오름차순으로 정렬합니다. 특정 범위의 데이터만 정렬하고자 할 때에는 From 인덱스와 To 인덱스를 지정해서 정렬할 수도 있습니다.
3. ArrayList의 효율성
이제 배열 연산의 시간 복잡도를 공부하면서 배열의 효율성을 알아보겠습니다.
3.1 배열 연산의 시간 복잡도
배열 데이터에 접근할 때의 시간 복잡도를 알아봅시다. 배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단번에 접근할 수 있습니다. 따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)입니다. 배열에 데이터를 추가하는 경우는 어떨까요? 배열은 데이터를 어디에 저장하느냐에 따라 추가 연산에 대한 시간 복잡도가 달라집니다.
※ 삭제 연산의 경우도 추가와 마찬가지의 시간 복잡도를 가집니다.
3.1.1 맨 뒤에 삽입할 경우
다음과 같은 배열이 있을 때 2를 추가한다고 생각해봅시다. 맨 뒤에 삽입할 때는 arr[3]에 임의 접근을 바로 할 수 있으며 데이터를 삽입해도 다른 데이터 위치에 영향을 주지 않습니다. 따라서 시간 복잡도는 O(1)입니다.
3.1.2 맨 앞에 삽입할 경우
데이터를 맨 앞에 삽입한다면 어떨까요? 이 경우 기존 데이터들을 뒤로 한 칸씩 밀어야 합니다. 즉, 미는 연산이 필요합니다. 데이터 개수를 N개로 일반화하면 시간 복잡도는 O(N)이 되겠네요.
3.1.3 중간에 삽입할 경우
중간에 삽입할 경우도 보겠습니다. 5 앞에 데이터를 삽입한다면 5 이후의 데이터를 뒤로 한 칸씩 밀어야 할 겁니다. 다시 말해 현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산을 해야 합니다. 밀어야 하는 데이터 개수가 N개라면 시간 복잡도는 O(N)이겠네요.
4. 배열을 선택할 때 고려할 점
데이터에 자주 접근하거나 읽어야 하는 경우 배열을 사용하면 좋은 성능을 낼 수 있습니다. 예를 들어 그래프를 표현할 때 배열을 활용하면 임의 접근을 할 수 있으므로 간선 여부도 시간 복잡도 O(1)로 판단할 수 있습니다. 하지만 배열은 메모리 공간을 충분히 확보해야 하는 단점도 있습니다. 다시 말해 배열은 임의 접근이라는 특징이 있어 데이터에 인덱스로 바로 접근할 수 있어 데이터에 빈번하게 접근하는 경우 효율적이지만 메모리 낭비가 발생할 수 있습니다. 따라서 코딩 테스트에서는 다음 사항을 고려해 배열을 선택해야 합니다.
- 할당할 수 있는 메모리 크기를 확인해야 합니다. 배열로 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당에 실패할 수 있습니다. 운영체제마다 배열을 할당할 수 있는 메모리의 한계치는 다르지만 보통은 정수형 1차원 배열은 1000만 개, 2차원 배열은 3000 * 3000 크기를 최대로 생각합니다.
- 중간에 데이터 삽입이 많은지 확인해야 합니다. 배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아져 실제 시험에서 시간 초과가 발생할 수 있습니다.
다음편에서 계속 됩니다.
자료구조, 알고리즘, 빈출 97 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(자바 편)
저자 김희성
현 42dot 백엔드 개발자. 이전에는 삼성SDS에서 소프트웨어 개발자, 쿠팡에서 풀스택 개발자로 근무했다. 특히 삼성SDS 시절에는 사내 SW역량테스트 강사로 활약했다. 귀찮은 거 싫어하고 집에서 자는 게 가장 좋은 백엔드 개발자다. 어려운 문제와 맞닥뜨렸을 때 더욱 불타오르는 타입. 새벽 시간에 코드짜는 걸 좋아하며 주말에 밤새 코딩하는 일을 즐기는 ESTJ.
