DS Lec.4 - Arrays

Array in JAVA

• in java, it is public class Arrays, extending Object.
• This class also contains a static factory that allows arrays to be viewed as lists.
• The methods in this class all throw a NullPointerException, if the specified array reference is null, except where noted.

2차원 배열

int[][] Y = new int[8][10];		// row size : 8, col size : 10

• row length : Y.length
• col length : Y[i].length
  • col size can be different in each row!

Abstract Data Type (ADT)

• Definition

  • A mathematical model of the data objects that make up a data type as well as the functions that operate on these objects.
    = ADT란 데이터 타입을 이루는 데이터 객체들과, 이 객체들에 대해 수행되는 함수들로 구성된 수학적 모델이다.

  • Defined indirectly, by the operations that may be performed on it and by mathematical constraints on the effects of those operations.
    = ADT는 직접적으로 구현을 보여주지 않고, 그 위에서 어떤 연산들을 수행할 수 있는지와, 그 연산들이 어떤 수학적 제약(결과 조건, 불변식 등)을 만족해야 하는지를 통해 간접적으로 정의된다.

    ---

  • 즉, “추상 자료형(ADT)이란, 특정 데이터 객체들과 그 객체들에 대해 수행할 수 있는 연산 및 그 연산이 만족해야 하는 제약 조건으로 정의되는 수학적 모델이다.”

ArrayList ADT

• ArrayList는 Array가 아니라, Array의 확장 버전이다.
• 불특정 객체들의 연속이 저장되어 있다.
• 각 원소들은 인덱스를 통해 접근, 삽입, 삭제가 가능하다.
• 잘못된 인덱스가 주어지면 exception을 throw한다.

모든 자바 exception 클래스는 Throwable 클래스에서 파생된다.

• Main methods
  • get(integer i)
  • set(integer i, object o) : i번째 원소를 o로 바꾸고, 기존값 리턴
  • add(integer i, object o) : i에 삽입
  • remove(integer i) : i번째 요소 pop
• Additional methods
  • size() : element 개수 리턴
  • isEmpty()

Element insertion

• add(o)는 배열 맨 끝에 추가하기 때문에 O(1).
  • A[n]에 o 추가.
  • 배열 사이즈 1 증가.
• add(i, o)는 O(n) when i = 0
  - Makes a room for the new element by shifting forward n-i elements
  - Adds o at A[i]

  스택, 큐, 어레이 등의 자료구조에서 이 배열의 방향성을 나타내는 용어가 너무 헷갈리니 한 번 정리해보자.

  • 쓰이는 용어는 front back top forward 등.

  ArrayList

  • ArrayList에서 add할 때 n-i개의 원소들을 shift 'forward'할 때 이 'forward'는 인덱스가 증가하는 방향을 의미한다. 따라서 인덱스 i부터 끝까지 있는 원소들을 한 칸씩 오른쪽으로 옮긴다는 의미이다.
  • 반대로 인덱스가 줄어드는 방향은 backward이다.
  • ArrayList에서 단순히 add(o)를 하는 경우에는 A[n]에 추가가 된다. 따라서 인덱스가 큰 쪽이 back임을 알 수 있다.

  Stack (LIFO)

  보통 스택 자료구조에서는 front, back이라는 용어를 잘 쓰지 않는다. 그저 top이라는 용어만 존재. 하지만 실제 디버깅을 하는 과정에서는 리스트처럼 노출되므로 방향이 혼동될 수 있다.
  Stack A = [1, 3, 5, 8, 9] 이 때 top은 9.
  이게 헷갈렸던 부분. 보통 Array나 Queue는 좌/우 기준으로 어디가 앞이고 뒤인지 알 수 있는데, 스택은 그게 애매해서 헷갈렸다.
  -> 정리하자면, 통상적으로 배열의 좌측은 Front, 우측은 End이며, 스택에서는 우측이 Top이라고 보는 것이다. 왜냐, 어느 자료 구조든 원소를 '끝에 추가'할 때는 항상 오른쪽에 들어오기 때문.

  왜 '추가'는 항상 오른쪽?
  배열 왼쪽(앞쪽)에서 삽입/삭제하면 원소들을 전부 한 칸씩 shift해야 해서 O(n) 시간이 걸린다. 반면, 배열 오른쪽 끝에서는 삽입/삭제가 단순히 크기만 조정하면 되니까 O(1)로 빠르다. 그래서 관례적으로 스택은 배열의 오른쪽 끝을 top으로 잡는다.

  Queue(FIFO)

  그러므로, 위의 논리를 따라가면 Queue역시 굳이 다른 걸 추가로 구현할 필요 없이, pop만 좌측에서 되도록 하나 만들어주면 구조적으로 완성된다.
  그래서 파이썬에서도 deque.popleft()가 BFS 구현에 필요한 '큐'의 핵심 기능으로 사용됐던 것.

---

Element removal

• remove(i) : i번째 원소 삭제 후 n - i - 1개의 원소를 backward(idx 감소 방향)로 shift해줘야 한다.
  • O(n) when i = 0

Performance

• Computational Complexity
  • 메모리 : O(n)
  • 수행 시간 of methods
    • size() : O(1)
      • get(i) : O(1)
      • set(i, o) : O(1)
      • add(o) : O(1)
      • add(i, o) : O(n) time in the worst case
      • remove(i) : O(n) time in the worst case

        굳이 O-notation에 'worst case'라는 말을 붙여야 하나? -> Average case, Best case와 구분하려고.
        어떤 알고리즘은 상황별로 복잡도가 다름.
        QuickSort → best: O(n log n), worst: O(n^2)
        HashTable → average: O(1), worst: O(n)
        이럴 땐 “O(n) in worst case”라고 말해줘야 정확히 전달됨.

Growable Array-based ArrayList

• When array is full in an add operation,
  • thorws an exception
  • replacing the array with a larger one
• Then, how large it should be?
  1. Incremental strategy : 상수값만큼 증가
  2. Doubling strategy : 두배로 증가

Algorithm add(o)
	input array A of n integers
    output array A of n+1 integers
    if n = A.length then
    	// 1. A보다 큰 사이즈의 배열 선언
    	S <- new array of size ...
        // 2. A 원소들을 S에 복사
        for i <- 0 to n-1 do
        	S[i] = A[i]
        // 3. A를 S로 대체
        A <- S
    n <- n + 1		// 4. 배열의 마지막 + 1번째 인덱스 갱신
    A[n-1] <- o		// 5. n-1 인덱스에 o 삽입

n번의 add(o) operations를 진행할 때 소요되는 총 T(n)을 비교해보자.
1. empty array에서 시작
2. Amortized time : T(n)/n을 생각해보자.

왜 n으로 나눈 시간을 고려해야 하는가?
Amortized time : 여러 번의 연산을 평균냈을 때 한 연산당 걸리는 시간.
add(o)는 O(n)이라 느려보이지만, 실제로 대부분 O(1)이고, 배열이 꽉 찼을 때만 resize해주기 때문에 실제 시간은 T(n)/n이 합리적.

Incremental strategy

• How many times is array replaced?
  k = n / c times (c : 증가 상수)
• ex) 총 6개를 넣고 싶다. n = 6, c = 2(2씩 증가한다고 치자.)
  • k = n/c = 3 ... 총 3번의 resize과정이 발생.
  • n + (c + 2c + ... + kc) = n + c*{k(k+1)/2}
  • 6 + (12 + 22 + 32) = 6 + 2{3*4/2} = 18
    • n : 반복 횟수. 총 add는 6번.
    • (c + 2c + 3c ... + kc) : 새 배열 constructions
      즉, 2개 배열 복사, 4개 배열 복사, 6개 배열 복사.
• T(n) = O(n^2), Amortized time = O(n)

Doubling strategy

• k = logn
• ex) 총 16개를 넣고 싶다. -> 총 4번 리사이즈.
  • k = 4 ... 1 > 2 > 4 > 8 > 16
  • n + (1 + 2 + 4 + 8 + ... + 2^k) = 3n - 1
• T(n) = O(n), Amortized time = O(1)