↓Skip to main content

[Algorithm] 자료구조 - 배열, 문자열, 연결리스트, 스택, 큐

Table of Contents



배열 #

해시 테이블 #

  • 키(key) 를 값(value) 에 대응시킨 자료구조로써 매우 빠르게 데이터를 저장, 삭제, 검색할 수 있다.
  • 각각의 key에 해시 함수(hash function) 를 적용해서 고유한 Index 값을 얻고, 그 Index 값을 이용해서 value를 해시 테이블에 저장한다.

  • 대표적인 해시 함수들
    • $k$ : 키
    • $n$ : 테이블 크기
    • $A$ : $0$ ~ $1$ 사이의 실수
해시 함수명 고유한 Index 값을 얻는 법
Division Method $h(k) = k \mod n$
Multiplication Method $h(k) = (kA \mod 1) × m$
Digit Folding key 문자열을 ASCII 코드로 바꾸고 값을 합한 것
Univeral Hashing 해시 함수를 무작위로 선택하는 것

  • 충돌이란?
    • 각기 다른 key의 해시값이 똑같을 때를 말한다.
  • 충돌을 해결할 수 있는 방법들…
  • [ 분리 연결법(Separate Chaining) ]
    • 동일한 버킷(해시 테이블에서 하나의 블록)의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장한다.
    • (1) 연결 리스트(linked list)를 이용한 체이닝(chaining)
      • 최악의 경우 원소를 찾는데, $O(n)$ 시간이 걸린다.
    • (2) 균형 이진 탐색 트리(balanced binary search tree)를 이용한 체이닝
      • 최악의 경우 원소를 찾는데, $O(\log n)$ 시간이 걸린다.
  • [ 개방 주소법(Open Addressing) ]
    • 비어있는 해시 테이블의 공간을 활용하는 방법이다.
    • (1) 선형 탐색(Linear Probing)
      • 고정폭 만큼씩 이동한다.
    • (2) 2차 탐색(Quadratic Probing)
      • 폭을 제곱으로 늘리며 이동한다. $1^2$ > $2^2$ > $3^2$
    • (3) 2중 해시(Double Hashing Probing)
      • 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다.
    • 단점
      • 해시 테이블에 담을 수 있는 전체 데이터가 배열의 크기에 제한된다.
      • 클러스터링(clustering) 문제
        • 예를 들어 배열의 크기가 100일 때 20~29가 채워져있다면, 다음 수가 인덱스 30으로 갈 확률이 10%나 된다.

  • 각 언어별 해시 자료구조
자료구조 구현 정렬 연속할당 랜덤접근 검색/삽입/삭제
C++ map 레드블랙트리 O X Via Key $O(\log n)$
C++ unordered_map 해시 테이블 X O Via Key $O(1)$
C# SortedDictionary 이진탐색트리 O X Via Key $O(\log n)$
C# Dictionary 해시 테이블 X O Via Key $O(1)$



가변 크기 배열 #

  • 할당된 capacity를 넘어서면 자동으로 2배의 크기를 재할당한다.

  • C++ vector

    • 멤버 중에 size()는 담긴 데이터의 개수이고, capacity()는 할당된 공간의 개수이다.
    • resize()는 인자값만큼의 size()로 만든다. 늘릴때는 0으로 채운다. 줄일 때는 원소를 없앤다.
    • reserve()는 size()는 변하지 않고, capacity()만 인자값만큼 늘린다. 늘리기만 된다.

  • C# List

    • 기존에 배치된 메모리 위치와 크기를 유지한 상태에서 추가적으로 부족한 메모리를 할당받아서 연결하겠지?
    • 아니다. 해당 크기의 2배의 메모리 공간을 새로 찾아서 할당하는 방식이다.
    • 따라서 이전 공간은 가비지를 발생시킨다.



문자열 #

C#의 StringBuilder #

  • C#의 string은 불변(Immutable) 객체이다.

    • 따라서 새로운 문자열으로 변경, 추가하면 기존 값이 대체되는 것이 아니라, 해당 크기의 다른 공간을 새로 할당한다.
    • 이것은 이전 공간의 가비지를 발생시킨다.

  • 이에 반해 가변(Mutable) 객체인 StringBuilder는

    • 새로운 문자열으로 변경, 추가하면 기존 메모리 공간에 값을 변경, 추가한다.
    • 따라서 변경이 일어나는 문자열은 StringBuilder를 사용해야 좋겠다.



연결리스트 #

  • 연결리스트의 특징
    • 랜덤접근이 불가능하다.
      • 따라서 특정 인덱스를 상수 시간에 접근할 수 없다. $K$번째 원소를 찾고 있다면, 처음부터 $K$번 루프를 돌아야 한다.
    • 순차접근이 일반 배열보다 느리다.
      • 메모리에 순차적으로 원소가 저장되는 배열과 다르게, 연결리스트는 불연속적으로 저장된다.
      • 따라서 (참조 지역성의 원리에 따라서) 캐시에 원소들이 함께 올라가지 않기 때문에 접근이 느릴 수밖에 없다.
    • 원소를 추가, 삭제하는 것이 상수 시간에 가능하다.
      • 가변 배열처럼 달리 추가, 삭제 후 나머지 원소를 뒤로 밀거나, 앞으로 옮기는 작업이 필요없다.

  • 각 언어별 연결리스트 자료구조
자료구조 구현 정렬 연속할당 랜덤접근 검색 삽입/삭제
C++ list 이중 연결리스트 User X X $O(n)$ $O(1)$
C# LinkedList 이중 연결리스트 User X X $O(n)$ $O(1)$

  • Runner 기법
    • 연결리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법이다.
    • 빠른 Runner : 2칸씩 건너뛴다.
    • 느린 Runner : 1칸씩 건너뛴다.
    • 빠른 런너가 연결 리스트의 끝에 도달하면, 느린 런너는 연결 리스트의 중간 지점을 가리키게 된다.
    • 여기서부터 값을 비교하거나 뒤집기를 시도하는 등 여러모로 활용할 수 있겠다.



스택과 큐 #

  • 스택과 큐 비교
자료구조 특징 정렬 연속할당 랜덤접근 검색 삽입/삭제 언어 지원
스택 LIFO X O Only Top Top: $O(1)$ $O(1)$ C++ stack
C# Stack
큐 FIFO X O Only Front Front: $O(1)$ $O(1)$ C++ queue
C# Queue

  • 스택
    • DFS(Depth-first search) 에서 사용한다.
    • 재귀적(Recursive) 함수를 호출할 때 사용한다.
    • 연결리스트로 구현할 수도 있다.
  • 큐
    • BFS(Breadth-first search) 에서 사용한다.
    • 컴퓨터 버퍼에서 주로 사용한다. 여러개가 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킨다.
    • 연결리스트로 구현할 수도 있다.



References #



↑