Java, 자료구조 Array 배열의 개념과 시간복잡도

 

자료구조 - 배열

 

순서(index)를 가진 데이터의 집합

 

- 가장 기본적인 자료구조

- 생성과 동시에 크기가 고정됨

- 전체 원소가 메모리상에 일렬로 저장됨

 

자료구조라고 하면 어렵게만 생각할 수 있는데, 배열, 문자열도 모두 자료구조의 일종입니다.

데이터를 담고 활용을 하고 있기 때문입니다.

 

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] arr = new int[N]; // 배열 생성
for(int i = 0; i < N; i++)
	arr[i] = sc.nextInt(); // 배열의 저장
    
 long sum = 0;
 for (int i = 0; i < N; i++)
 	sum += arr[i]; // 배열의 탐색, 원소의 접근

1. 배열 생성할때는 크게 2가지가 필요합니다. 
   1. 어떤 타입의 배열인지
   2. 원소를 몇개나 담을 것인지
2. 각 배열의 칸에 원소를 담을때는 대괄호 연산자를 통해 i번째 원소에 바로 접근할 수 있다.
3. 배열의 원소에 접근할 수 있으면 value도 알 수 있습니다.

 

보통 배열을 사용할때는 위의 코드처럼 반복문과 함께 사용될 때가 많습니다.

 

배열을 생성하는 다른 방식은 다음과 같습니다.

총 10개의 원소를 가진 int[]가 생성되고, arr.length를 통해 배열의 크기를 알 수 있습니다.

// 원하는 값으로 배열을 생성
int[] arr = {7, 9, 4, -1, 4, 10, 0, 2, 5, 6};

long sum = 0;
int len = arr.length; // 배열의 크기
for (int i = 0; i < len; i++;) 
	sum += arr[i]; // 배열의 탐색, 원소의 접근

 

 

 

원소를 최대 10개까지 담을 수 있고, 현재는 8개까지만 담겨져 있는 배열입니다.

 

배열에 대한 아래 기능들의 시간복잡도는?

• get(int idx) : idx번째 원소 반환
• change(int idx, int val) : idx번째 원소를 val로 변경
• append(int val) : 가장 뒤에 원소 삽입
• Insert(int idx, int val) :  현재 idx번째 원소의 앞에 원소 삽입
• erase(int idx) : idx번째 원소 삭제

앞으로 문제풀이에서 많게는 10만~1000만개까지 데이터를 받고 활용해야하는데, 가장 많이 사용되는게 배열입니다.

각 기능들에 대한 복잡도를 계산해야지 더 효율적인인 알고리즘을 계산할 수 있습니다.

 

배열의 연산

get(int idx) : idx번째 원소 반환

메모리가 연속적이기 때문에 arr의 시작 주소로 부터 idx만큼 덜어진 원소의 주소를 바로 계산하고, 접근할 수 있다.

4번 인덱스값인 4를 읽고 싶다면 어떻게 해야할까요? 

물론 대괄호연산을 사용해서 4번 인덱스 원소에 접근을 할 수 있습니다. arr[4]

그렇다면 대괄호 연산자는 어떻게 4번 인덱스를 찾아가는 걸까요?

 

우리가 배열을 생성할때 배열은 그 크기만큼 연속된 메모리로 저장이 됩니다. 그래서 배열의 시작 주소로 부터 인덱스만큼 떨어진 원소의 주소를 바로 계산을 할 수 있습니다. 예를 들어서, arr[]이 1000번에서 시작한다고 할때, integer는 4바이트라서 각 원소 한 칸당 4바이트를 차지할 것입니다. 그렇다면 4번 원소를 접근하고 싶다면 4x4를 해서 바로 1016번에 4번 원소가 있다는 것을 알 수 있습니다.

 

그래서 대괄호 연산을 할때 주소를 바로 계산할 수 있기 때문에 접근이 가능한 것입니다.

이러한 주소 계산이 연산 한번으로 이뤄질 수 있기 때문에 상수 시간복잡도를 가집니다.

// 시간복잡도 : O(1)
public static int getElement(int[] arr, int idx) {
	return arr[idx];
}

 

change(int idx, int val) : idx번째 원소를 val로 변경

[]연산자를 통해 idx번 원소에 바로 접근하고, 값을 변경할 수 있습니다.

// 시간복잡도 : O(1)
public static void changeElement(int[] arr, int idx, int val) {
	arr[idx] = val;
}

 

append(int val) : 가장 뒤에 원소 삽입

배열을 0번부터 차례대로 값을 기록한다고 할때, 마지막 원소의 뒷부분에 새로운 값을 삽입하는 것입니다.

현재 배열에 담긴 원소의 개수를 알면 해당 인덱스에 요청받은 원소를 넣는다.

 

만약에 배열이 꽉 차 있다면?

한 번 생성된 배열은 고정 길이이다. 배열의 칸을 덜 쓰거나 할 순 있어도 배열 자체의 크기를 늘리거나 줄일 수는 없다.

원소들이 연속되어있는 배열의 마지막에 원소를 추가할 때 이미 배열이 꽉 찼다면 그보다 큰 새 배열을 생성해 옮겨 담아야 한다.

// 시간복잡도 : O(1)
public static void appendElement(int[] arr, int arrCount, int val) {
	if(arrCount == arr.length) // arrCount 원소의 개수
    	return false;
    arr[arrCount] = val;
    return true;
}

 

 

Insert(int idx, int val) :  현재 idx번째 원소의 앞에 원소 삽입

배열의 중간에 원소를 삽입해보겠습니다.

원소들이 연속되어있는 배열의 중간에 원소를 추가하기 위해서는 추가되는 원소의 뒷 원소들이 모두 한 칸씩 뒤로 이동해 새 원소를 삽입할 수 잇는 자리를 만들어야 한다. 한 칸씩 뒤로 먼저 옮겨 4번 공간을 만든다.

// 시간복잡도 : O(N)
public static void insertElement(int[] arr, int arrCount, int idx, int val) {
	if(idx > arrCount || arrCount >= arr.length)
    	return false;
    for (int i = arrCount; i > idx; i--)
    	arr[i] = arr[i - 1];
    arr[idx] = val;
    return true;
}

 

erase(int idx) : idx번째 원소 삭제

중간에 있는 원소를 삭제해보겠습니다.

원소들이 연속되어있는 배열의 중간원소를 삭제할때에는 해당 원소의 뒷 원소들을 모두 한 칸씩 앞으로 이동해야 한다.

// 시간복잡도 : O(N)
public static void eraseElement(int[] arr, int arrCount, int idx) {
	if(idx >= arrCount) // 지우려는 인덱스가 배열의 원소 개수 이상이라면? 거기엔 원소가 X
    	return false;
    for (int i = idx; i < arrCount; i++) // 한 칸씩 땡겨온다
    	arr[i] = arr[i + 1];
    return true;
}

 

결론

 

원소에 접근하고 변경하는 것은 빠르나, 중간 원소를 추가/삭제하는 것은 데이터의 이동이 일어나면서 최대 배열 원소의 개수까지 시간이 걸린다. 이 단점을 보완하기 위해 list같은 자료구조가 있습니다.

 

---

📕본 포스팅은 패스트캠퍼스의 "핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 초격차 패키지 Online." 을 공부하면서 정리한 내용입니다.