[이론] 배열 (feat. 코드트리 조별과제 : 3주차)

 

정적 배열

• 배열의 선언과 동시에 크기를 지정하며, 선언 이후에는 크기를 바꿀 수 없다.

동적 배열

• 길이가 자유자재로 변경될 수 있는 배열. 사용하고 싶은 만큼만 공간을 차지하고 사용할 수 있다.

 

정적 배열의 기본 연산

삽입

• 배열의 앞이나 가운데에 값이 삽입된다면, 새로운 값이 들어갈 자리를 확보하기 위해 다른 값들의 자리 이동이 필요하다. 따라서 일반적인(최악의 상황에서의) 시간복잡도는 O(N)이다.
• 즉, 다른 값들의 자리 이동이 필요하지 않은 상황( 맨 뒤에 값이 삽입되는 경우)는 시간복잡도가 O(1)이다.

삭제

• 삽입과 마찬가지로 배열의 맨 뒤에 값이 삭제된다면 삭제 후 다른 값들의 자리 이동이 필요하지 않다.
• 배열의 앞이나 가운데에서 값을 삭제한다면 삭제된 값의 빈 자리를 채워야 하므로 나머지 N-1 개의 값이 이동해야 한다. 따라서 시간복잡도는 O(N)이다.

탐색

• 원하는 값을 찾기 위해서는 모든 값을 탐색하는 것이다. 따라서 시간복잡도는 O(N)이다.
• 찾는 값이 맨 앞이나 뒤인 경우는 O(1)이겠지만, 시간복잡도는 최악의 상황을 고려하므로...

 

정적 배열과 동적 배열의 시간 복잡도 ⏱️

• 동적 배열은 삽입, 삭제, 탐색 과정은 모두 정적 배열과 동일하지만, 필요한 메모리만 차지한다.

	정적 배열 (Array)	동적 배열 (Dynamic Array)
삽입	O(N)	O(N)
삭제	O(N)	O(N)
탐색	O(N)	O(N)
K번째 원소 구하기	O(1)	O(1)

• K번째 원소를 구하는 경우엔 인덱스를 활용하여  탐색하므로 O(1) 이다.

 

Java 에서의 동적 배열 (ArrayList)

import java.util.ArrayList;

public class Main {
	public static void main(String[] args) {
    	ArrayList<Integer> al = new ArrayList<>(); // 정수를 관리할 ArrayList 선언
        
        // 1. add(E)
        al.add(2); 						// al : [2]
        al.add(3); 						// al : [2, 3]
        
        // 2. remove(index)
        al.remove(1); 					// 인덱스 1을 삭제
            
        // 3. size()
        al.size(); 						// 현재 ArrayList에 들어있는 데이터의 수를 반환
               
        // 4. get(index)
        al.get(0); 						// 인덱스 0에 있는 원소를 조회
        
    }
}

동적 배열(ArrayList) 기본 문제

 

 

자바에서 정적 배열과 동적 배열에 메모리 할당하는 방법은 어떻게 다를까??

차근차근.. 공부하고 알아보고 정리해봐야겠다..

추후에...