5장 자료구조

No.8·2023년 3월 24일

복잡도 비선형자료구조 선형자료구조 자료구조

면접을 위한 CS전공지식

목록 보기

1/4

자료구조

자료구조란
: 자료구조란 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 말한다

5.1 복잡도

복잡도는 시간 복잡도와 공간 복잡도로 나뉨

5.1.1 시간 복잡도

문제를 해결하는데 걸리는 시간과 입력의 함수 관계

빅오 표기법

'가장 영향을 많이 끼치는' 항의 상수 인자를 빼고 나머지 항을 없앤 것 O(n^2)

시간 복잡도의 존재 이유

효율적인 코드로 개선하는데 쓰이는 척도

5.1.2 공간 복잡도

프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양

5.1.3 자료 구조에서의 시간 복잡도

5.2 선형 자료 구조

일렬로 나열되어 있는 자료구조

5.2.1 연결 리스트

데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조
삽입과 삭제가 O(1)이 걸리고 탐색 O(n) 걸린다

연결 리스트 : prev 포인터와 next 포인터로 앞 뒤의 노드를 연결시킨 것
1. 싱글 연결 리스트
2. 이중 연결 리스트
3. 원형 이중 연결 리스트

맨 앞의 노드를 헤드라고 한다

장점:
배열과 달리 새로운 자료, 즉 노드를 뒤에 연결하거나 중간에 노드 몇개를 껴넣는 것이 쉽다.
단점:
자료 번호가 없이 연결 관계만 있기 때문에 특정한 노드를 불러내기가 어렵다

from collections import deque

a = deque()
for i in range(10):
    a.append(i)
for i in range(10):
    a.appendleft(i)
it = iter(a)
next(it)
a.insert(1, 1000)
print(*a)
a.popleft()
a.pop()
print(*a)

iter, next
iter는 객체의 iter 메서드를 호출해주고, next는 객체의 next 메서드를 호출해줍니다

iter

iter는 반복을 끝낼 값을 지정하면 특정 값이 나올 때 반복을 끝냅니다. 이 경우에는 반복 가능한 객체 대신 호출 가능한 객체(callable)를 넣어줍니다. 참고로 반복을 끝낼 값은 sentinel이라고 부르는데 감시병이라는 뜻입니다. 즉, 반복을 감시하다가 특정 값이 나오면 반복을 끝낸다고 해서 sentinel입니다.

iter (호출가능한객체, 반복을끝낼값)

예를 들어 random.randint(0, 5)와 같이 0부터 5까지 무작위로 숫자를 생성할 때 2가 나오면 반복을 끝내도록 만들 수 있습니다. 이때 호출 가능한 객체를 넣어야 하므로 매개변수가 없는 함수 또는 람다 표현식으로 만들어줍니다.

>>> import random
>>> it = iter(lambda : random.randint(0, 5), 2)
>>> next(it)
0
>>> next(it)
3
>>> next(it)
1
>>> next(it)
Traceback (most recent call last):
  File "<pyshell#37>", line 1, in <module>
    next(it)
StopIteration

next(it)로 숫자를 계속 만들다가 2가 나오면 StopIteration이 발생합니다. 물론 숫자가 무작위로 생성되므로 next(it)를 호출하는 횟수도 매번 달라집니다. 물론 다음과 같이 for 반복문에 넣어서 사용할 수도 있습니다.

>>> import random
>>> for i in iter(lambda : random.randint(0, 5), 2):
...     print(i, end=' ')
...
3 1 4 0 5 3 3 5 0 4 1

이렇게 iter 함수를 활용하면 if 조건문으로 매번 숫자가 2인지 검사하지 않아도 되므로 코드가 좀 더 간단해집니다. 즉, 다음 코드와 동작이 같습니다.

import random
 
while True:
    i = random.randint(0, 5)
    if i == 2:
        break
    print(i, end=' ')

next는 기본값을 지정할 수 있습니다. 기본값을 지정하면 반복이 끝나더라도 StopIteration이 발생하지 않고 기본값을 출력합니다. 즉, 반복할 수 있을 때는 해당 값을 출력하고, 반복이 끝났을 때는 기본값을 출력합니다. 다음은 range(3)으로 0, 1, 2 세 번 반복하는데 next에 기본값으로 10을 지정했습니다.

next(반복가능한객체, 기본값)

>>> it = iter(range(3))
>>> next(it, 10)
0
>>> next(it, 10)
1
>>> next(it, 10)
2
>>> next(it, 10)
10
>>> next(it, 10)
10

0, 1, 2까지 나온 뒤에도 next(it, 10)을 호출하면 예외가 발생하지 않고 계속 10이 나옵니다.

지금까지 반복 가능한 객체의 개념과 이터레이터를 만드는 방법을 배웠습니다. 여기서는 이터레이터를 만들 때 iter, next 메서드 또는 getitem 메서드를 구현해야 한다는 점만 기억하면 됩니다.

5.2.2 배열

같은 타입의 변수들로 이루어져있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
중복을 허용, 순서가 있다

정적배열 기반

탐색 시 시간복잡도 O(1), 랜덤 접근이 가능
삽입, 삭제 시 시간 복잡도 O(n), 따라서 데이터 추가와 삭제를 많이 하는 것은 연결 리스트 탐색을 많이 하는 것은 배열로 하는 것이 좋음

랜덤 접근과 순차적 접근

랜덤 접근(직접 접근): 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능
순차적 접근: 저장된 순서대로 검색해야 함

배열과 연결 리스트 비교
배열: 상자를 순서대로 나열한 데이터 구조, 인덱스만 알면 해당 값을 알 수 있다

연결 리스트: 상자를 선으로 연결한 형태의 데이터 구조, 내부 요소 알기 위해선 내부 확인을 해봐야함

탐색 시 배열이 빠르고 연결 리스트는 느림
하지만 추가, 삭제는 연결 리스트가 더 빠르고 배열은 느림

5.2.3 벡터

동적으로 요소를 할당할 수 있는 동적 배열
컴파일 시점에 개수를 모른다면 벡터를 써야 함
중복 허용, 순서 존재, 랜덤 접근 가능
탐색, 맨 뒤의 요소 삭제, 삽입에 O(1)
맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는데 O(n)
그림을 보면 매번 크기 증가하지 않고 '2의 제곱승 + 1'마다 크기를 2배 늘린다
i번째 요소 추가 할 떄 드는 비용을 ci라고 한다면 ci는 1 또는 1 + 2^k다
그러므로 n번쨰 요소 추가 시 드는 비용 T(n)은 다음 식과 같다

이를 n으로 나누면 3, 1이라는 상수 시간보단 크지만 상수시간에 가까운 amortized복잡도를 가진다. 그렇기 떄문에 push_back()은 O(1)의 시간 복잡도를 가진다

v = []
for i in range(1, 11):
    v.append(i)
print(*v)
v.pop()

print(*v)
v = v[1:]

print(*v)
if 100 not in v:
    print("not found")

v = [10] * len(v)
print(*v)
v.clear()
print(*v)
# 1 2 3 4 5 6 7 8 9 10
# 1 2 3 4 5 6 7 8 9
# 2 3 4 5 6 7 8 9
# not found
# 10 10 10 10 10 10 10 10

5.2.4 스택

가장 마지막으로 들어간 데이터가 가장 첫번쨰오 나오는 성질(LIFO)을 가진 자료구조
웹 브라우저 방문 기록 등에 쓰임
삽입,삭제 시 O(1), 탐색 시 O(n)

stack = []
for i in range(10):
    stack.append(i)
while stack:
    print(stack.pop(), end=" ")
# 9 8 7 6 5 4 3 2 1 0

5.2.5 큐

먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO)을 지닌 자료 구조
스택과 반대
삽입, 삭제 시 O(1), 탐색 시 O(n)
CPU 작업 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용

from collections import deque

q = deque()
for i in range(10):
    q.append(i)
while q:
    print(q.popleft(), end=" ")
# 0 1 2 3 4 5 6 7 8 9

5.3 비선형 자료구조

일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다. 일반적으로 트리나 그래프를 말한다

5.3.1 그래프

그래프는 정점과 간선으로 이루어진 자료구조

정점과 간선

정점: 어떠한 곳(vertex)
간선: 어떠한 곳으로 가는 길(edge)

단방향 간선과 양방향 간선

정점으로 나가는 간선을 해당 정점의 outdegree라고 한다
들어오는 간선을 해당 정점의 indegree라고 한다

가중치

간선과 정점 사이에 드는 비용

5.3.2 트리

그래프 중 하나로 그래프 특징과 같이 정점과 간선으로 이루어져 있다
트리 구조로 배열된 일종의 계층적 데이터 집합
루트 노드, 내부 노드, 리프 노드 등으로 구성
트리로 이루어진 집합을 숲이라고 한다

트리의 특징

트리의 구성

루트 노드: 가장 위에 있는 노드
내부노드: 루트 노드와 내부 노드 사이에 있는 노드
리프 노드: 자식 노드가 없는 노드

트리의 높이와 레벨

깊이: 트리에서 깉이는 각 노드마다 다르며, 루트에서부터 특정 노드까지의 최단 거리
높이: 루트에서 리프 노트까지 거리 중 가장 긴 거리
레벨: 문제마다 조금씩 다르지만 보통 깊이와 같은 의미
서브트리: 트리 내 하위 집합

이진 트리

자식의 노드 수가 두 개 이하인 트리
정이진 트리: 자식 노드가 0 또는 두 개인 이진트리
완전 이진 트리: 왼쪽에서부터 채워져 있는 이진 트리. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있고 마지막 레벨의 경우 왼쪽부터 채워져 있다
변질 이진 트리: 자식 노드가 하나밖에 없는 이진 트리
포화 이진 트리: 모든 노드가 꽉 차 있는 이진 트리
균형 이진 트리: 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리. map, set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나

이진 탐색 트리

이진탐색트리(BST)는 노드의 오른쪽 하위 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함되고, 왼쪽하위 트리에는 '노드 값보다 작은 값'이 들어 있는 트리
검색에 용이
탐색 시 평균 시간 복잡도: O(logn), 최악 시: O(n)
왜냐하면 삽인 순서에 따라 선형적일 수 있기 때문

AVL 트리

AVL 트리(Adelson-Velsky and Landis tree)는 위에서 설명한 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리. 두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있음

AVL트리 개념 설명 영상 Youtube
이진탐색 트리의 최악 경우를 방지하고자 만들어진 것이 AVL 트리
삽입, 삭제 시 왼쪽, 오른쪽 회전을 통해 균형을 맞춘다
균형도가 절대값 2 이상일 경우 불균형 1이내를 유지함
2 이상일시 좌측 비대, -2 이하일 시 우측 비대
탐색, 삽입, 삭제 모두 시간 복잡도 O(logn)

레드 블랙 트리

균형 이진 탐색 트리의 일종
탐색, 삽입, 삭제 모두 시간 복잡도 O(logn)
각 노드에 빨간색 혹은 검은색 나타내는 추가 비트 저장
삽입 삭제 중 트리가 균형을 유지하도록 사용됨

균형을 잡는데 쓰이는 규칙

모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다(블랙의 자식은 블랙일 수 있다)
특정 노드에서 후손 노드로 가는 경로는 동일한 수의 검정색 노드가 존재한다

레드블랙트리 개요 Youtube
레드블랙트리 설명

레드블랙트리와 AVL트리의 차이
1. 노드 재배치 가능성: 레드블랙트리 < AVL트리
2. 균형성: 레드블랙트리 < AVL트리
3. 노드 탐색횟수: 레드블랙트리 > AVL트리
4. 삽입, 삭제 성능: 레드블랙트리 > AVL트리(삽입 삭제 시 레드블랙트리의 노드 재배치 가능성이 낮기 때문)
그러므로 삽입, 삭제가 많을 시 레드블랙트리를, 연산이 적고 탐색 많을 시 AVL트리를 사용하는 것이 좋다

5.3.3 힙

완전 이진 트리 기반의 자료 구조
최소힙과 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지닌 트리

최대힙: 부모 노드에 있는 키는 모든 자식에 있는 키보다 커야한다
최소힙: 부모 노드에 있는 키는 모든 자식에 있는 키보다 작아야한다

최대힙의 삽입

힙에 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 삽입
이 새 노드를 부모들과 크기를 비교하며 교환해서 힙의 성질을 만족시킴

최대힙의 삭제

루트 노드를 삭제
마지막 노드를 루트 노드와 스왑
자식 노드 중 더 큰 값과 재귀적으로 스왑

5.3.4 우선순위 큐

우선순위 큐는 우선순위 대기열이라고도 한다
대기열에서 우선순위가 놓은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조

우선순위 큐는 결국 최소힙이나 최대힙에서 루트를 삭제하거나 새 요소를 삽입하는 것과 같다
시간복잡도는 최악의 경우에도 O(logn)

우선순위 큐와 힙 요약 Youtube

# 최소힙
import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 4)
heapq.heappush(heap, 3)
heapq.heappush(heap, 2)
heapq.heappush(heap, 1)

print(heap[0])
# 1 출력

# 최대힙
import heapq

heap = []
heapq.heappush(heap, -5)
heapq.heappush(heap, -4)
heapq.heappush(heap, -3)
heapq.heappush(heap, -2)
heapq.heappush(heap, -1)

print(-heap[0])  
# 5 출력

5.3.5 맵

특정 순서에 따라 키와 매핑된 값의 조합
레드블랙 트리 자료구조를 기반으로 형성되고 삽입 시 자동 정렬됨
map은 해시 테이블을 구현할 때 쓰며 정렬을 보장하지 않는 unordered_map과 정렬을 보장하는 map 두가지가 있다(c++)

C++의 map은 중복을 허용하지 않는 (key, value) 쌍으로 이루어진 트리입니다.
map의 내부 구현은 검색, 삽입, 삭제가 O(log n)으로 동작하는 RB Tree로 구성되어있습니다.

v = [0] * 10
umap = {
    "test1": 4,
    "test2": 10
}

for key, value in umap.items():
    print(key, "::", value)

print(umap["test1"])

5.3.6 셋

셋은 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며 중복되는 요소는 없고 오로지 희소한 값만 저장하는 자료구조

_set = set()
_set.add(("test", 1))
_set.add(("test", 1))
_set.add(("test", 1))
_set.add(("test", 1))
print(len(_set))
# 1

5.3.7 해시 테이블

해시 테이블은 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블. 삽입, 삭제, 탐색 시 평균적으로 O(1) 시간 복잡도 가진다

해싱이란?

해싱인란 임의의 길이의 값을 해시함수를 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다

해시테이블이란?

해시 테이블이란 해시함수를 사용하여 변환한 값을 index로 삼아 키와 데이터를 저장하는 자료구조를 말한다.
해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다.

이러한 해싱 구조로 데이터를 저장하면 key값으로 데이터를 찾을 시 함수를 1번만 수행하면 되므로 빠르게 삽입/삭제/조회 할 수 있다
해시테이블의 평균 시간복잡도는 O(1)이다

해시테이블의 문제점

해시테이블은 키값을 해시함수를 통해 해시값을 얻는 방식이기 때문에 다른 키값이 같은 해시값을 가지는 충돌의 문제가 생긴다
충돌을 이해하기 위해선 먼저 적재율에 대해 알아야한다

적재율이란 해시 테이블의 크기대비 키의 개수를 만한다. 키의 개수 K, 테이블의 크기 N이라 한다면 적재율은 K/N이다. 해시 테이블은 적재율이 1이상이기 때문에 충돌이 발생한다.
같은 인덱스에 모든 키값과 데이터가 저장된 경우 최악의 시간 복잡도 O(N)이 발생한다
결론적으로 이 충돌을 완하하는 것이 주요 쟁점이다
해결법에는 2가지가 있다

충돌해결 1: 해시 테이블의 구조 개선

a. 분리연결법(seperate chaining)

seperate chaining이란 쉽게 말해 연결리스트를 이용하는 방법이다
충돌 발생 시 이를 동일한 버킷에 저장하는데 추가적인 데이터를 사용, 이를 연결리스트 형태로 저장한다

장점

해시 테이블의 크기를 유지할 수 있고 간단히 구현가능하다
손쉽게 삭제할 수 있다

단점

데이터의 수가 많아지면 동일 버킷에 chaing되는 데이터가 많아지며 캐시의 효율성이 감소한다
탐색과 삭제 경우 최악 시 O(N)의 시간 복잡도 가진다

b. 개방 주소법(Open Addressing)

개방주소법은 해시값 충돌 시 비어있는 해시 테이블의 공간을 탐사(probe)하여 할당하는 방식이다

삽입: 계산한 해시 값에 대한 인덱스가 이미 차있는 경우 다음 인덱스로 이동하면서 비어있는 곳에 저장한다. 이렇게 비어있는 자리를 탐색하는 것을 탐사(Probing)라고 한다.
탐색: 계산한 해시 값에 대한 인덱스부터 검사하며 탐사를 해나가는데 이 때 “삭제” 표시가 있는 부분은 지나간다.
삭제: 탐색을 통해 해당 값을 찾고 삭제한 뒤 “삭제” 표시를 한다.

개방 주소법은 다시 3가지 기법으로 나뉜다

1. 선형탐사법(linear probing)

선형탐사는 가장 기본적인 충돌해결기법으로 바로 인접한 인덱스에 데이터를 삽입해가는 방법이다
선형탐사는 바로 인접한 인덱스에서 데이터를 삽입해가기 때문에 데이터가 밀집되는 클러스터링 문제가 발생하고 이로 인해 탐색과 삭제가 느려진다

2. 제곱탐사(Quadratic Probing)

말그대로 제곱 수씩 뛰어넘어가며 탐사하는 방식으로 선형탐사에 비해 폭넓게 탐사하여 탐색 및 삭제에 효율적일 수 있다. 하지만 역시나 클러스터링 문제가 발생하게 된다

3. 이중해싱(Double Hashing)

이중해싱은 선형탐사와 제곱탐사에서 발생하는 클러스터링 문제를 모두 피하기 위해 도입된 것이다. 처음 해시함수는 해시값을 찾기위해 사용되고 두번째 해시함수는 충돌이 발생했을 떄 탐사폭을 계산하기 위해 사용되는 방식이다
(위 그림에서 알파는 적재율이다)

충돌해결 2: 다양한 해시 함수 사용법

대표적 해시함수 4가지

1. 나눗셈법(Division Method)

나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다. (K = 키값의 수, N= 테이블의 크기)

h(k)=k mod N

2. Digit Folding

각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법

3. 곱셈법(Multiplication Method)

0 < A < 1 인 A에 대해서 다음과 같이 구할 수 있다

h(k) = [N(kA mod 1)]

kA mod 1의 의미는 kA의 소수점 이하 부분을 말하며 이를 N에 곱하므로 0부터 N사이의 값이 된다. 이방법의 장점은 N이 어떤 값이더라도 잘 작동하는다는 것이며 A를 잘 잡는 것이 중요하다

4. Univeral Hashing

다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

해시맵(hachmap)

해시맵은 맵과 유사하지만 내부 구현 방식이 다르다

일반적인 맵은 키-값 쌍을 저장할 때 각각의 키를 비교하여 순서를 유지하며 저장한다
해시맵은 내부적으로 해시 함수를 사용하여 키를 해시값으로 변환하고 이를기반으로 배열에 저장한다 따라서 순서를 보장하지 않는다

해시맵은 덕분에 빠른 검색 속도를 제공한다. 또한 null값을 키로 사용가능하다

해시맵과 해시테이블의 차이점

해시맵
a. 동기화 처리 안되어 있어서 해시테이블에 비해 속도 빠르다(별도 동기화 가능)
b. null값을 키로 사용할 수 있다
해시테이블
a. 동기화 처리가 외어 있어 멀티 스레드 환경에서 안전하게 사용 가능
b. 동기화 처리로 인해 해시맵에 비해 속도 느림

해시맵 사용 예시

많은 데이터를 빠르게 검색할 시 사용된다

캐시(cache) 구현: 해시맵은 검색 속도가 빠르기 때문에, 캐시 구현에 많이 사용됩니다. 캐시는 데이터를 미리 저장해 놓고, 이후에 동일한 요청이 들어올 경우 저장된 데이터를 반환하여 속도를 향상시키는 역할을 합니다.
검색과 연관된 작업: 해시맵은 검색과 관련된 작업에서 매우 유용합니다. 예를 들어, 특정 키를 가지는 데이터를 빠르게 검색하거나, 키에 해당하는 값을 수정하거나 삭제하는 작업 등을 수행할 수 있습니다.
대용량 데이터 처리: 해시맵은 대용량 데이터를 처리할 때 매우 효율적입니다. 이는 내부 구현 방식 때문인데, 해시맵은 해시 함수를 사용하여 데이터를 저장하므로 검색 속도가 매우 빠릅니다.
자료구조 구현: 해시맵은 자료구조를 구현할 때 매우 유용합니다. 예를 들어, 집합(set)이나 다중 집합(multiset)을 구현할 때 해시맵을 사용할 수 있습니다. 또한, 그래프에서 노드를 관리하는 경우에도 해시맵을 사용할 수 있습니다.
성능이 중요한 작업: 해시맵은 내부적으로 배열을 사용하므로, 빠른 속도를 보장합니다. 따라서, 대용량 데이터를 빠르게 처리해야 하는 경우나, 성능이 중요한 작업을 수행해야 하는 경우에도 해시맵을 사용할 수 있습니다.

예를 들어, 온라인 쇼핑몰에서 상품을 검색하는 기능을 구현해야 한다고 가정해보겠습니다. 이때, 사용자가 입력한 검색어와 일치하는 상품을 빠르게 찾아야 하므로 해시맵을 사용할 수 있습니다.

해시맵을 사용하면 검색 속도가 빠르기 때문에, 수백만 개의 상품 정보를 빠르게 검색할 수 있습니다. 또한, 사용자가 입력한 검색어를 키(key)로 사용하여 해당하는 상품 정보를 값(value)으로 저장하면, 사용자가 다시 같은 검색어를 입력했을 때 더 빠르게 결과를 반환할 수 있습니다.

또 다른 예로는, 소셜 미디어에서 해시태그 검색 기능을 구현하는 경우가 있습니다. 해시태그는 대용량 데이터이기 때문에, 검색 속도가 빠른 해시맵을 사용하면 빠르게 결과를 반환할 수 있습니다. 해시태그를 키(key)로 사용하여 해당하는 게시물 정보를 값(value)으로 저장하면, 사용자가 특정 해시태그를 검색할 때 해당하는 게시물을 빠르게 찾아볼 수 있습니다.

자료출처

해시테이블이란?

AVL 트리

https://www.youtube.com/watch?v=9BiHgy40NNE

레드블랙 트리

우선순위 큐와 힙

https://www.youtube.com/watch?v=AjFlp951nz0&t=4s

해시맵

https://velog.io/@db_jam/Java-%ED%95%B4%EC%8B%9C%EB%A7%B5HashMap-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%A0%95%EB%A6%AC

해시맵과 해시테이블

자료구조 면접질문

No.8

88888888

다음 포스트

5장 자료구조

면접을 위한 CS전공지식

자료구조

5.1 복잡도

5.1.1 시간 복잡도

5.1.2 공간 복잡도

5.1.3 자료 구조에서의 시간 복잡도

5.2 선형 자료 구조

5.2.1 연결 리스트

iter

iter (호출가능한객체, 반복을끝낼값)

next

next(반복가능한객체, 기본값)

5.2.2 배열

5.2.3 벡터

5.2.4 스택

5.2.5 큐

5.3 비선형 자료구조

5.3.1 그래프

5.3.2 트리

트리의 구성

이진 탐색 트리

AVL 트리

레드 블랙 트리

5.3.3 힙

최대힙의 삽입

최대힙의 삭제

5.3.4 우선순위 큐

5.3.5 맵

5.3.6 셋

5.3.7 해시 테이블

해싱이란?

해시테이블이란?

해시테이블의 문제점

충돌해결 1: 해시 테이블의 구조 개선

a. 분리연결법(seperate chaining)

장점

단점

b. 개방 주소법(Open Addressing)

1. 선형탐사법(linear probing)

2. 제곱탐사(Quadratic Probing)

3. 이중해싱(Double Hashing)

충돌해결 2: 다양한 해시 함수 사용법

1. 나눗셈법(Division Method)

2. Digit Folding

3. 곱셈법(Multiplication Method)

4. Univeral Hashing

해시맵(hachmap)

해시맵과 해시테이블의 차이점

해시맵 사용 예시

자료출처

4장 데이터베이스

0개의 댓글