🐹 2. Data Structures

01. 배열과 문자열

[ 해시테이블 ]

: 키(key)를 값(value)에 대응시켜 효율적인 탐색이 가능한 자료구조

구현 방식

연결리스트(linked list)와 해시 코드 함수(hash code function)을 사용

1. key의 해시코드를 계산한다.
2. hash(key) % array_length와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다. (서로 다른 두 개의 해시 코드가 같은 인덱스를 가리킬 수 있다.)

3. 배열의 각 인덱스에 키와 값으로 이루어진 연결리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다.

   충돌(서로 다른 두 개의 해시 코드가 같은 인덱스를 가리킴)에 대비하여 반드시 연결리스트를 이용한다.

수행 시간

• 최악의 경우 : 모든 해시값이 충돌을 일으키는 경우 탐색 시간 O(N)
• 최선의 경우 : 충돌이 하나도 일어나지 않아 탐색 시간 O(1)

다른 구현방법

이진 탐색 트리(balanced binarysearch tree)를 사용

• 탐색 시간 : O(logN)
• 장점
  • 크기가 큰 배열을 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간 사용
  • 키의 집합을 특정 순서로 차례대로 접근 가능

[ ArrayList와 가변 크기 배열 ]

ArrayList는 일반 배열과 다르게 동적 가변 크기 기능이 있다.

• 접근 시간 : O(1), 배열이 가득 차는 순간 크기를 두 배로 늘리는 시간은 O(n)이지만 드문 일이다.

상환 입력 시간은 왜 O(1)이 되는가?

크기가 N인 배열이 있을 때, 배열의 크기를 늘릴 때 필요한 원소의 개수를 역으로 계산해본다.

⇒ N개의 원소를 삽입하기 위해서 해야하는 원소의 총 개수는 N/2 + N/4 + N/8 + … + 2 + 1로 N보다 작다

배열의 상황에 따라 최악의 경우 O(N)이 소요되는 삽입 연산도 존재하지만, 평균적으로 각 삽입은 O(1)이다.

[ StringBuilder ]

for문을 사용한 문자열 붙이기

문자열의 리스트가 주어졌을 때 하나의 문자열로 이어붙이려 한다. 이때의 수행시간은?

모든 문자열의 길이를 x라고 했을 때, 이어붙일 때마다 두 개의 문자열을 읽고 하나하나 새로운 문자열에 복사해야한다. 처음에는 x개, 두 번째는 2x개, 세 번째는 3x개, n번째는 nx개의 문자를 복사해야 한다.

따라서 총 수행시간은 O(x + 2x + … + nx), 즉 O(xn^2)이 된다.

\[1+2+...+n = n(n+1) \rightarrow O(n^2)\]

StringBuilder를 이용한 문자열 붙이기

StringBuilder는 가변 크기 배열을 이용하여 필요한 경우에만 문자열을 복사하게 해준다.

02. 연결리스트

: 차례로 연결된 노드를 표현해주는 자료구조(단방향, 양방향)

• 탐색: O(N)
• 삽입, 삭제: O(1) (특정 애플리케이션에서 유용)

[ 연결리스트 만들기 ]

• 단방향 연결리스트

  

위 코드에서 LinkedList를 사용하지 않고 연결리스트에 접근할 때 head 노드의 주소를 참조하는 방법을 사용했다.

→ 여러 객체들이 동시에 연결리스트를 참조하는 도중에 head가 바뀌면 어떤 객체들은 이전 head를 계속 가리키고 있을 수도 있다.

위 문제를 해결하기 위해 Node 클래스를 포함하는 LinkedList 클래스를 만드는 것이 좋다. 그렇게 하면 head Node 변수를 단 하나만 정의해 놓음으로써 위의 문제점을 완전히 해결할 수 있다.

[ 단방향 연결리스트에서 노드 삭제 ]

노드 n을 삭제하고자 할 때 이전 노드 prev를 찾아 prev.next를 n.next와 같도록 설정한다.

양방향인 경우에는 n.next가 가리키는 노드를 갱신하여 n.next.prev가 n.prev와 같도록 설정한다.

• 주의할 점
  • null 포인터 검사를 반드시 해야한다.
  • 필요한 경우 head와 tail 포인터도 갱신해야 한다.
  • (메모리 관리가 필요한 언어일 경우 ex. C, C++) 할당된 메모리가 제대로 반환되었는지 확인해야한다.

[ Runner 기법 ]

: 연결리스트를 순회할 때 두 개의 포인터를 동시에 사용하는 것 (Runner(부가 포인터라고도 함)은 연결리스트 문제에서 많이 활용되는 기법)

이때 한 포인터가 다른 포인터보다 앞서도록 한다.

예시

연결리스트 $a_1 \rightarrow a_2 \rightarrow \cdots \rightarrow a_n \rightarrow b_1 \rightarrow b_2 \rightarrow \cdots \rightarrow b_n$ 이 있을 때 이 리스트를 $a_1 \rightarrow b_1 \rightarrow a_2 \rightarrow b_2 \rightarrow \cdots \rightarrow a_n \rightarrow b_n$으로 재정렬하고 싶다. 정확한 길이는 모르지만, 길이가 짝수라는 정보는 알고 있다.

이때 포인터 p1(앞선 포인터)를 두고, 따라오는 포인터 p2가 한 번 움직일 때마다 포인터 p1이 두 번 움직이도록 설정해 본다.

그랬을 때 p1이 연결리스트 끝에 도달하면 p2는 가운데 지점에 있게 된다. 이 상태에서 p1을 다시 맨 앞으로 옮긴 다음 p2로 하여금 원소를 재배열하도록 만들 수 있다.

즉, 루프가 실행될 때마다 p2가 가리키는 원소를 p1 뒤로 옮기는 것이다.

[ 재귀 문제 ]

연결리스트 문제를 푸는데 상당수는 재귀 호출에 의존함

재귀 호출의 깊이가 n이 될 경우, 해당 재귀 알고리즘이 적어도 O(n) 만큼의 공간을 사용한다.

재귀 알고리즘을 반복(iterative) 형태로 구현도리 수 있긴 하지만 반복적 형태로 구현하면 한층 복잡해질 수 있다.

03. 스택과 큐

[ 스택 구현하기 ]

: LIFO(Last-In-First-Out)에 따라 자료 배열

• 스택의 연산
  • pop(): 스택에서 가장 위에 있는 항목 제거
  • push(item): item 하나를 스택의 가장 윗 부분에 추가
  • peek(): 스택의 가장 위에 있는 항목 반환
  • isEmpty(): 스택이 비어 있을 때 true 반환
• 특징
  • 배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 없다.
  • 하지만 데이터 추가, 삭제 연산은 상수 시간에 가능하다. (배열처럼 원소를 하나씩 밀어줄 필요가 없음)

• 스택의 사용

  • 재귀 알고리즘

    재귀적으로 함수를 호출해야 하는 경우 임시 데이터를 스택에 넣어주고, 재귀함수를 빠져나와 백트래킹을 할 때는 스택에 넣어 두었던 임시 데이터를 빼줘야 한다. 스택은 이런 행위를 직관적으로 가능하게 해준다.

[ 큐 구현하기 ]

: FIFO(First-In-First-Out)에 따라 자료 배열

• 큐의 연산
  • add(item): item을 리스트의 끝부분에 추가
  • remove(): 리스트의 첫 번째 항목을 제거
  • peek(): 큐에서 가장 위에 있는 항목 반환
  • isEmpty(): 큐가 비어 있을 때 true 반환

큐 또한 연결리스트로 구현 가능하다.

• 큐의 사용

  • 너비 우선 탐색(breadth-first search)

    처리해야 할 노드의 리스트를 저장하는 용도

    노드를 접근한 순서대로 처리할 수 있다.

  • 캐시 구현