🐣 2. Data Structures

📚 1. 배열과 문자열

1. Hash Tables

• 해시테이블 : 효율적인 탐색을 위한 자료구조

• 키(key)를 값(value)에 대응한다.

• 간단한 해시테이블 구현 방법

  • 연결리스트(linked list), 해시 코드 함수(hash code function)
• 해시테이블 데이터 삽입 과정
  • 키의 해시 코드를 계산한다.
    • 키의 자료형은 보통 int 혹은 long 이 된다.
    • ➡️ 이는 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있음을 나타냄!
  • hash(key) % array_length 와 같은 방식으로 해시 코드를 이용해, 배열의 인덱스를 구한다.
  • 배열의 각 인덱스에는 키-값 으로 이루어진 연결리스트가 존재한다.
    • 충돌에 대비하여 반드시 연결리스트를 이용한다!

🤔 해시 충돌?

• 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나
• 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우

🕐 수행 시간

• 최악의 경우 : $O(N)$
• But 일반적으로 해시에 대해 이야기할 때는 충돌을 최소화하도록 잘 구현된 경우를 가정한다. ➡️ 이 경우는 O(1)

---

2. ArrayList & Resizable Arraya

• ArrayList : 동적 가변 크기 기능 내재 자료형

  • ArrayList는 필요에 따라 크기를 변화시킬 수 있으면서 $O(1)$ 의 접근 시간을 유지한다.
  • 배열이 가득 차는 순간, 배열의 크기를 2배로 늘린다.

• 크기를 2배 늘리는 연산은 $O(N)$ 이지만 자주 발생하지 않으므로, $O(1)$이 된다.

  • _ ⭐️상환 입력 시간 개념 도입!_

---

3. StringBuilder

• 문자열을 하나로 이어붙이는 방법

• ex1

String joinWords(String[] words){
	String sentence = "";
	for (String w : words) {
		sentence = sentence + w;
	}
	return sentence;
}

• 문자열을 이어붙일 때마다 새로운 문자열에 복사하는 방법
  • 처음에는 x개, 두 번째는 2x개, 세 번째는 3x개, n번째는 nx개의 문자를 복사한다.

• 시간복잡도 : $O(xn^2)$

  • $1 + 2 + … + n = n(n + 1)/2$

• ex2

String joinWords(String[] words) {
	StringBuilder sentence = new StringBuilder();
	for (String w : words) {
		sentence.append(w);
	}
	return sentence.toString;
}

• StringBuilder 를 이용하여 가변 크기 배열을 사용하는 방법
  • 필요한 경우에만 문자열을 복사하게끔 한다.

---

📚 2. 연결리스트

• 연결리스트 : 차례로 연결된 노드를 표현해주는 자료구조
• 단방향 연결리스트 : 개별 노드 ➡️ 다음 노드
• 양방향 연결리스트 : 개별 노드 ➡️ 다음 노드 & 이전 노드
• ⭐️ 시작 지점에서의 아이템 추가 및 삭제 연산이 상수 시간 소요

1. Creating a Linked List

• 단방향 연결리스트 구현 코드

class Node {
  Node next = null;
  int data;
  public Node(int d) {
   data = d;
  }
  void appendToTail(int d){
   Node end = new Node(d);
   Node n = this;
   while(n.next != null){
    n = n.next;
   }
   n.next = end;
  }
}

• 단방향 연결리스트에서의 고려사항 : head 가 바뀌면 어떻게 되는가?
  • 👉 head 가 바뀌었음에도 어떤 객체는 head를 계속 가리키고 있을 수도 있다.
  • Node 클래스를 포함하는 LinkedList 클래스를 만든다.(head Node 변수에 head를 가리키는 값 저장)

2. Deleting a Node from a Singly Linked List

• 삭제 노드 : n
  1. prev.next 를 n.next 로 연결한다.
  2. (양방향 연결리스트일 경우) n.next.prev 를 n.prev 로 연결한다.
• ⚠️ 메모리 관리가 필요한 언어를 사용해 구현하는 경우에는 삭제한 노드에 할당되었던 메모리가 제대로 반환되었는지 확인 필요!
• 노드 삭제 코드

Node deleteNode(Node head, int d) {
   Node n = head;
   if (n.data == d) {
    return head.next;
   }

   while (n.next != null) {
    if (n.next.data == d) {
       n.next = n.next.next;
       return head;
    }
     n = n.next;
   }
  return head;
}

3. The “Runner” Technique

• Runner : 연결리스트를 순회할 때 두 개의 포인터를 동시에 사용한다.
• 한 포인터가 다른 포인터보다 앞서도록 하고 포인터를 움직일 때 지정된 개수 혹은 여러 노드를 한번에 움직일 수 있도록 설정한다.

4. Recursive Problems

• 연결리스트 문제 ≒ 재귀 호출
• ⚠️ 재귀(recursive) 알고리즘은 적어도 $O(n)$의 공간 복잡도를 갖는다!

---

🎓 1. CS50 2020 - Lecture 2 - Arrays

int scores[3];

• a chunk of memory
• 연속된 값으로 입력된다.

int scores[3];
scores[0] = 72;
scores[1] = 73;
scores[2] = 33;

💡 일종의 프로그래밍 관례로 0부터 인덱스를 시작한다.

• 배열을 선언할 때 “[3]”과 같은 표현을 쓰는 데, 이는 총 값의 수를 나타낸다.
• 배열에 색인을 생성할 때, 해당 메모리 청크의 특정 위치로 이동하면 유사한 숫자를 사용한다.
  • ➡️ 상대적인 위치를 참조(첫 번째, 두 번째, 세 번째)

---

🎓 2. Arrays | Coursera

1. Arrays

• Array : 메모리의 연속적인 영역

  • 하나의 메모리 청크

• Key Point : random access

  • 배열의 어느 특정한 요소에 접근할 수 있다.
  • “Constant time access to read, Constant time access to wright”
• 각 원소의 영역은 모두 같은 사이즈로 할당이 된다.
• 원소의 주소를 도출하는 수식

\[arrayAddr + elemSize * (i - firstIndex)\]

---

2. Multi-Dimensional Arrays

• row - column 쌍으로 표현이 가능하다.

• 접근 방법

  • 접근하려는 요소 이전의 행들을 건너뛴다.
  • 한 행의 모든 요소들의 개수를 곱한다.

\[elemSize _ ((3-1) _ 6 + (4-1))\]

2-1. row-major ordering & column-major ordering

_(좌 : row-major ordering

우 : column-major ordering)_

• 메모리에는 다음과 같이 배치된다.

• row-major ordering : 원소가 행에 따라 연속적으로 배치되는 방식
• column-major ordering : 원소가 열에 따라 연속적으로 배치되는 방식
  • 언어와 컴파일러마다 다르다.

---

3. Times for Common Operations

• beginning : n개 요소 재정렬
• end : 전체 원소의 개수만 업데이트하면 됨

• middle : n/2개 요소 재정렬

• ⭐ 핵심 : 원소에 접근/읽기/쓰기에 일정한 시간이 소요된다.

---

✨ Summary

• Array : contiguous area of memory consisting of equal-size elements indexed by contiguous integers.
• Constant-time access to any element.
• Constant time to add/remove at the end.
• Linear time to add/remove at an arbitrary location.

---

🎓 3. Dynamic Arrays | Coursera

1. Problem

• 문제 사항 : 배열은 정적이다.

  • 해결 : 런타임시에 크기가 결정되는 동적 가변 배열을 사용한다.

• Solution : dynamic arrays

  • 동적으로 할당되는 배열의 포인터를 저장하고 새로 할당이 필요할 때에는 해당 포인터를 바꾼다.
  • 이전 배열의 원소들을 복사하고 이전 배열의 위치를 가리키던 포인터 값을 새로운 배열을 가리키는 포인터 값으로 바꾼다.

• Operations

  • get(i) : i번째에 위치한 원소
  • set(i, val) : i번째 위치에 val 삽입
  • pushback(val) : val을 마지막 위치에 삽입
  • remove(i) : i번째에 위치한 원소 제거
  • size(i) : 전체 원소 개수

• size :vs: capacity

• 배열이 다 찼을 경우
  1. 원래 크기의 두 배만큼 새로운 배열을 만든다.
  2. 기존 원소들을 복사하여 넣는다.
  3. 원래의 포인터 위치를 새 배열의 포인터 위치로 바꾼다.

---

2. Common Implementations

• C++ : vector
• Java : ArrayList
• Python : list
  • python에서는 정적 배열을 표현할 수 없다.

---

3. Runtimes

• get(i) : $O(1)$
• set(i, val) : $O(1)$
• pushback(val) : $O(n)$
• remove(i) : $O(n)$
• size() : $O(1)$

---

✨ Summary

• Unlike static arrays, dynamic arrays can be resized.
• Appending a new element to a dynamic array is often constant time, but can take $O(n)$.
• Some space is wasted.

---

🎓 4. Implementation Arrays

Implement a vector (mutable array with automatic resizing)

• Practice coding using arrays and pointers, and pointer math to jump to an index instead of using indexing.
• New raw data array with allocated memory
  • can allocate int array under the hood, just not use its features
  • start with 16, or if starting number is greater, use power of 2 - 16, 32, 64, 128
• size() - number of items
• capacity() - number of items it can hold
• is_empty()
• at(index) - returns item at given index, blows up if index out of bounds
• push(item)
• insert(index, item) - inserts item at index, shifts that index’s value and trailing elements to the right
• prepend(item) - can use insert above at index 0
• pop() - remove from end, return value
• delete(index) - delete item at index, shifting all trailing elements left
• remove(item) - looks for value and removes index holding it (even if in multiple places)
• find(item) - looks for value and returns first index with that value, -1 if not found
• resize(new_capacity) // private function
  • when you reach capacity, resize to double the size
  • when popping an item, if size is 1/4 of capacity, resize to half
• Time
  • O(1) to add/remove at end (amortized for allocations for more space), index, or update
  • O(n) to insert/remove elsewhere
• Space
  • contiguous in memory, so proximity helps performance
  • space needed = (array capacity, which is >= n) * size of item, but even if 2n, still O(n)

---

🤔 설계 고려사항

• 자료형은 int로 한정한다.
• 맨 처음 생성자를 통해 초기화 벡터가 생성된다.

New raw data array with allocated memory

• can allocate int array under the hood, just not use its features
• start with 16, or if starting number is greater, use power of 2 - 16, 32, 64, 128

• java의 ArrayList 를 사용하지 않고 정적 배열 형태로 동적 가변 배열을 구현한다.
• 기본 원소의 개수는 16부터 시작한다.
• 그 밖의 디테일한 구현 사항들은 문서화 주석으로 함수 정의문 위에 기록한다.

• ⚠️ 주의사항
  • 삽입 시, 배열 확장 고려
  • 삭제 시, 배열 축소 고려

public class Arrays {
    private int[] vector;
    private int elemCnt = 0;

    public Arrays(){
        vector = new int[16];
    }

    public int size(){
        return elemCnt;
    }

    public int capacity(){
        return vector.length - size();
    }

    /**
     * @return 비어있으면 True(1), 요소가 있으면 False(0)
     */
    public boolean is_empty(){
        return elemCnt == 0;
    }

    /**
     * 입력 인덱스가 범위 밖이면 'IndexOutOfBoundsException' 에러 발생
     */
    public int at(int index){
        if (index >= 0 || index < size()){
            return vector[index];
        } else {
            throw new IndexOutOfBoundsException();
        }
    }

    public void push(int item){
        if (capacity() == 0){
            resize(size() * 2);
        }
        vector[elemCnt++] = item;
    }

    /**
     * 입력 인덱스가 범위 밖이면 'IndexOutOfBoundsException' 에러 발생
     */
    public void insert(int index, int item){
        if (index < size()){
            int[] newVector = new int[vector.length];

            if (capacity() == 0) {
                resize(size() * 2);
            }

            for (int i = 0; i < index; i++) {
                newVector[i] = vector[i];
            }
            newVector[index] = item;
            for (int i = index + 1; i < size() + 1; i++) {
                newVector[i] = vector[i - 1];
            }

            elemCnt++;
            vector = newVector;
        } else {
            throw new IndexOutOfBoundsException();
        }
    }

    public void prepend(int item){
        if (capacity() == 0){
            resize(size() * 2);
        }

        int[] newVector = new int[vector.length];

        for (int i = 0; i < size(); i++){
            newVector[i + 1] = vector[i];
        }
        newVector[0] = item;

        elemCnt++;
        vector = newVector;
    }

    /**
     * 벡터가 비었을 경우 'NullPointerException' 에러 발생
     */
    public int pop(){
        int rst;

        if (is_empty()){
            throw new NullPointerException();
        }

        rst = vector[elemCnt - 1];
        vector[elemCnt--] = 0;

        if (size() / 4 == vector.length){
            resize(size() / 4);
        }

        return rst;
    }

    /**
     * 입력 인덱스가 범위 밖이면 'IndexOutOfBoundsException' 에러 발생
     */
    public void delete(int index){
        if (index < size()){
            for (int i = index; i < size(); i++){
                vector[i] = vector[i + 1];
            }

            elemCnt--;

            if (size() / 4 == vector.length){
                resize(size() / 4);
            }
        } else {
            throw new IndexOutOfBoundsException();
        }
    }

    /**
     * item이 존재하는 모든 인덱스 위치의 원소 삭제
     */
    public void remove(int item){
        for (int i = 0; i < size(); i++) {
            if (vector[i] == item){
                delete(i);
            }
        }
    }

    /**
     * item이 벡터 내에 없으면 -1 리턴
     */
    public int find(int item){
        for (int i = 0; i < size(); i++) {
            return i;
        }
        return -1;
    }

    private void resize(int new_capacity){
        int[] newVector = new int[new_capacity];

        for (int i = 0; i < size(); i++) {
            newVector[i] = vector[i];
        }
        vector = newVector;
    }

    // test
    public static void main(String[] args) {
        Arrays tmpVector = new Arrays();
        System.out.println("test 1:" + tmpVector.size());
        System.out.println("test 2:" + tmpVector.capacity());
        System.out.println("test 3:" + tmpVector.is_empty());
        tmpVector.push(3);
        tmpVector.push(4);
        System.out.println("test 4:" + tmpVector.at(0)); // 3
        System.out.println("test 5:" + tmpVector.at(1)); // 4
        tmpVector.insert(0, 2);
        tmpVector.prepend(1);
        System.out.println("test 6:" + java.util.Arrays.toString(tmpVector.vector)); // [1, 2, 3, 4, ...]
        System.out.println("test 7:" + tmpVector.pop());
        tmpVector.delete(0);
        tmpVector.remove(2);
        System.out.println("test 8:" + tmpVector.find(3)); // 0
    }
}

---

🎓 4. Implementation LinkedList

• Implement (I did with tail pointer & without):
  • size() - returns number of data elements in list
  • empty() - bool returns true if empty
  • value_at(index) - returns the value of the nth item (starting at 0 for first)
  • push_front(value) - adds an item to the front of the list
  • pop_front() - remove front item and return its value
  • push_back(value) - adds an item at the end
  • pop_back() - removes end item and returns its value
  • front() - get value of front item
  • back() - get value of end item
  • insert(index, value) - insert value at index, so current item at that index is pointed to by new item at index
  • erase(index) - removes node at given index
  • value_n_from_end(n) - returns the value of the node at nth position from the end of the list
  • reverse() - reverses the list
  • remove_value(value) - removes the first item in the list with this value
  • Doubly-linked List
    • Description (video)
    • No need to implement

---

🤔 설계 고려사항

• 자료형은 int로 한정한다.
• 맨 처음 생성자를 통해 초기화 링크드 리스트가 생성된다.

import java.util.*;

public class ImplLinkedList {
 private LinkedList<Integer> LinkedList;

 public ImplLinkedList() {
  LinkedList = new LinkedList<>();
 }

 public int size() {
  return LinkedList.size();
 }

 public boolean empty() {
  return LinkedList.size() == 0;
 }

 /**
  * 입력 인덱스가 범위 밖이면 'IndexOutOfBoundsException' 에러 발생
  */
 public int value_at(int index) {
  if (index >= 0 || index < size()){
   return LinkedList.get(index);
  } else {
   throw new IndexOutOfBoundsException();
  }
 }

 public void push_front(int value) {
  LinkedList<Integer> newLinkedList = new LinkedList<>();
  newLinkedList.push(value);

  for (int e : LinkedList)
   newLinkedList.push(e);

  LinkedList = newLinkedList;
 }

 /**
  * 링크드 리스트가 비었을 경우 'NullPointerException' 에러 발생
  */
 public int pop_front() {
  if (empty()){
   throw new NullPointerException();
  }
  return LinkedList.pollFirst();
 }

 public void push_back(int value){
  LinkedList.push(value);
 }

 /**
  * 링크드 리스트가 비었을 경우 'NullPointerException' 에러 발생
  */
 public int pop_back() {
  if (empty()){
   throw new NullPointerException();
  }
  return LinkedList.poll();
 }

 /**
  * 링크드 리스트가 비었을 경우 'NullPointerException' 에러 발생
  */
 public int front() {
  if (empty()){
   throw new NullPointerException();
  }
  return LinkedList.peekFirst();
 }

 /**
  * 링크드 리스트가 비었을 경우 'NullPointerException' 에러 발생
  */
 public int back() {
  if (empty()){
   throw new NullPointerException();
  }
  return LinkedList.peek();
 }

 /**
  * 입력 인덱스가 범위 밖이면 'IndexOutOfBoundsException' 에러 발생
  */
 public void insert(int index, int value) {
  if (index >= 0 || index < size()){
   LinkedList<> newLinkedList = new LinkedList<Integer>();

   for (int i = 0; i < index; i++) {
    newLinkedList.push(LinkedList.get(i));
   }

   newLinkedList.add(index, value);

   for (int i = index; i <= size(); i++) {
    newLinkedList.push(LinkedList.get(i));
   }
   LinkedList = newLinkedList;

  } else {
   throw new IndexOutOfBoundsException();
  }
 }

 /**
  * 입력 인덱스가 범위 밖이면 'IndexOutOfBoundsException' 에러 발생
  */
 public void erase(int index) {
  if (index >= 0 || index < size()){
   LinkedList.remove(index);
  } else {
   throw new IndexOutOfBoundsException();
  }
 }

 /**
  * 0번째 요소부터 가능 -> 0번째 요소 : 마지막 요소
  * 입력 인덱스가 범위 밖이면 'IndexOutOfBoundsException' 에러 발생
  */
 public int value_v_from_end(int n) {
  if (n >= 0 || n < size()){
   return LinkedList.get(size() - 1 - n);
  } else {
   throw new IndexOutOfBoundsException();
  }
 }

 public LinkedList<Integer> reverse() {
  LinkedList<Integer> newLinkedList = new LinkedList<>();

  for (int e : LinkedList)
   newLinkedList.add(0, e);

  return newLinkedList;
 }

 /**
  * 값이 없으면 아무것도 수행하지 않음
  * 다중 값 존재 시, 맨 앞 요소 제거
  */
 public void remove_value(int value) {
  for (int e : LinkedList){
   if (e == value)
    LinkedList.remove(e);
  }
 }
}