출처 : Interview_Question_for_Beginner
Array (배열)
배열은 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조입니다.
배열의 장점으로는 원소의 인덱스 값을 알고 있으면 Big-O(1)의 시간 복잡도로 원소 검색이 가능합니다. 하지만 삭제 또는 삽입의 경우 배열의 빈 공간으로 원소들을 shift 해줘야 하며 Big-O(n)의 시간 복잡도가 요구됩니다.
Linked List
Linked List는 값과 주소로된 노드들이 순차적으로 연결되어 있는 자료구조입니다.
Linked List는 배열의 단점을 해결합니다. Linked List의 원소들은 본인 다음 원소의 주소를 기억하고 있기 때문에 해당 부분만 다른 값으로 바꿔주면 Big-O(1)의 시간 복잡도로 삭제 및 삽입이 가능합니다. 하지만 원소 삭제 및 삽입 전체 동작을 봤을 때, 동작에 해당하는 원소를 검색하는 과정에서 첫번째 원소부터 순차적으로 검색하기 때문에 Big-O(n)의 시간이 추가적으로 발생합니다.
결국 linked list는 검색, 삽입, 삭제에 대해서도 Big-O(n)의 시간 복잡도가 요구됩니다. 그럼에도 사용하는 이유는 Tree에서 사용되었을 때 그 유용성이 드러나기 때문입니다.
Stack
Stack은 먼저 들어간 원소가 나중에 나오는 First In Last Out 구조의 자료구조입니다.
Queue
Queue는 먼저 들어간 데이터가 먼저 나오는 First In First Out 구조의 자료구조입니다. 한쪽에서 데이터 삽입이 가능하면 다른 한 쪽에서는 삭제가 가능합니다.
Deque, Double-ended Queue (덱)
덱은 큐 2개를 겹쳐놓은것과 같기 때문에 Double ended Queue라고 부르며 양쪽에서 데이터의 입출력이 가능한 자료구조입니다.
Hash Table
Hash Table은 키를 해시값으로 매핑하고, 해시값을 index 삼아 데이터의 key와 value를 함께 저장하는 자료구조입니다.
보통 key보다 해시값이 더 적기 때문에 메모리 효율성이 좋습니다.
단점으로는 서로 다른 key가 동일한 해시값을 가지는 해시 충돌 문제가 일어날 수 있습니다.
충돌 문제 해결법으로는
첫 번째 방법은 Separate Chaning입니다. 체인법은 해당 버킷에 데이터가 이미 있다면 연결 리스트와 같이 다음 노드를 가리키는 노드를 추가하는 방법입니다. 이로인해 해시 테이블의 탐색, 삽입, 삭제의 시간복잡도는 평균적으로 Big-O(1)을 요구하지만, 충돌이 자주 일어나면 최악의 경우 Big-O(n)이 요구됩니다.
두 번째 방법은 Open Addressing입니다. Open Addressing은 버킷에 데이터가 이미 있다면 다른 주소에 데이터를 저장할 수 있도록하는 방법입니다. 이때 다른 주소에 저장된 데이터를 액세스(삽입, 삭제, 탐색)하는 방식에는 크게 세 가지가 있습니다. 선형 탐사는 버킷에 다른 데이터가 저장되어 있으면 고정 폭 만큼 옮겨 다음 버킷을 액세스합니다. 제곱 탐사는 버킷에 다른 데이터가 저장되어 있으면 제곱수 폭 만큼 옮겨 다음 버킷을 액세스합니다. 이중 해시는 버킷에 다른 데이터가 저장되어 있으면 또 다른 해시함수에서 나온 값의 폭 만큼 옮겨 다음 버킷을 액세스합니다.
Direct-Address Table
Direct-Address Table은 key의 개수와 해시값의 개수가 동일한 해시 테이블입니다.
Hash Table과 같이 충돌은 나지 않지만 실제 사용되는 key가 적을 경우 메모리 효율성이 떨어집니다.
Dictionary
Dictionary는 key와 value를 한 쌍으로 하는 값을 저장하는 자료구조입니다.
cf 1. Hash 알고리즘 고득점 Kit
cf 2. Hash 대표 알고리즘 문제 (베스트 엘범 Level 3)
# python
from collections import defaultdict
def solution(genres, plays):
answer = []
# 총 play 수와 장르 별 노래 및 고유 번호 dictionary로 저장
d_total_plays = defaultdict(int)
d_genres = defaultdict(list)
i = 0
for key, value in zip(genres, plays):
d_total_plays[key] += value
d_genres[key].append([value, i])
i += 1
# 노래가 많이 재생된 장르순 배열 생성
l_total_plays = []
for key, value in d_total_plays.items():
l_total_plays.append([value, key])
# 노래가 많이 재생된 장르부터 고유 번호 탐색
for i in sorted(l_total_plays)[::-1]:
key = i[1]
l_genres = sorted(d_genres[key])[::-1]
# 노래가 하나인 경우 하나만 수록
if (len(l_genres) == 1):
answer.append(l_genres[0][1])
else:
# 재생 횟수가 같은 노래는 고유 번호가 낮은 노래 수록
if (l_genres[1][0] == l_genres[0][0]) and (l_genres[1][1] < l_genres[0][1]):
answer.append(l_genres[1][1])
answer.append(l_genres[0][1])
else:
answer.append(l_genres[0][1])
answer.append(l_genres[1][1])
return answer
재귀함수와 DFS 그리고 Stack (깊이 우선 탐색)
재귀함수
def recursive(n):
if n == 0:
return
else:
print(n, end = ' ')
recursive(n-1)
recursive(5) # 5, 4, 3, 2, 1
def recursive(n):
if n == 0:
return
else:
recursive(n-1)
print(n, end = ' ')
recursive(5) # 1, 2, 3, 4, 5
재귀함수는 Stack 자료구조와 같이 동작한다.
cf 1. n! 구하기
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
factorial(5)
# Stack 처럼 생각
# factorial(1) = 1
# factorial(2) = 2 * factorial(1)
# factorial(3) = 3 * factorial(2)
# factorial(4) = 4 * factorial(3)
# factorial(5) = 5 * factorial(4)
cf 2. 피보나치 수열 구하기
# 피보나치 수열 : [1, 1, 2, 3, 5, 8 ...]
def Fibonacci(n):
if n == 1 or n == 2:
return 1
else:
return Fibonacci(n-2) + Fibonacci(n-1)
Fibonacci(5)
DFS 그리고 Queue (깊이 우선 탐색)
- 이진트리의 깊이 우선 탐색
cf. 부모 노드 2 = 왼쪽 노드 부모 노드 2 + 1 = 오른쪽 노드
# 이진트리의 깊이 우선 탐색
def DFS(v):
if v > 7:
return
else:
print(v, end = ' ')
DFS(v * 2)
DFS(v * 2 + 1)
DFS(1) # 1, 2, 4, 5, 3, 6, 7
BFS (너비 우선 탐색 (레벨 탐색))
출발 지점에서 도착 지점까지 가는 최단 경로, 최소 비용 등을 구할 때.
- 이진트리의 너비 우선 탐색
from collections import deque
def BFS():
Q = deque()
Q.append(1)
L = 0
while Q:
n = len(Q)
print(L, ' : ')
for i in range(n):
v = Q.leftpop()
print(v, end = ' ')
for nv in [v*2, v*2 + 1]:
# 7 까지만 탐색 (Level 2 까지)
if nv > 7:
continue
Q.append(nv)
print()
L += 1
BFS()
응용 예시
# 아래 규칙에 따라 0지점에서 출발하여 특정 위치로 갈 수 있는 최소 이동 횟수 구하기
# 한번 이동할 때 +1, 1-, +5 만큼 이동할 수 있다. (음수 좌표는 갈 수 없다.)
from collections import deque
def DFS(destination):
Q = deque()
Q.append(0)
L = 0
memo = []
while Q:
n = len(Q)
for i in range(n):
v = Q.popleft()
for nv in [v - 1, v + 1, v + 5]:
if nv == destination: return L + 1
if nv >= 0 and not (nv in memo):
Q.append(nv)
memo.append(nv)
L += 1
print(DFS(10)) # 2
print(DFS(14)) # 4
print(DFS(25)) # 5
print(DFS(24)) # 6
print(DFS(345)) # 69
cf. 같은 문제 DFS vs. BFS
# n*n 영역에서 1인 영역 개수 구하기
# DFS
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def DFS(x, y, board):
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= 0 and ny >= 0 and nx < len(board) and ny < len(board) and board[nx][ny] == 1:
board[nx][ny] = 0
DFS(nx, ny, board)
def solution(board):
answer = 0
n = len(board)
for i in range(n):
for j in range(n):
if board[i][j] == 1:
answer += 1
DFS(i, j, board)
return answer
solution([[0, 1, 1, 0, 0], [0, 1, 1, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 1, 1, 0]]) # 2
# BFS
from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def BFS(Q, x, y, board):
Q.append([x, y])
while Q:
n = len(Q)
for _ in range(n):
v = Q.popleft()
for i in range(4):
nx = v[0] + dx[i]
ny = v[1] + dy[i]
if nx >= 0 and ny >= 0 and nx < len(board) and ny < len(board) and board[nx][ny] == 1:
board[nx][ny] = 0
Q.append([nx, ny])
def solution(board):
answer = 0
Q = deque()
n = len(board)
for i in range(n):
for j in range(n):
if board[i][j] == 1:
answer += 1
BFS(Q, i, j, board)
return answer
solution([[0, 1, 1, 0, 0], [0, 1, 1, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 1, 1, 0]]) # 2
그래프 (Gragh)
- G(V, E) : Vertex (정점), Edge (간선)
인접 행렬로 그래프 표현
# 무방향 그래프
edge = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 4]] # 입력 정보
gragh = [[0] * (n+1) for _ in range(n+1)]
for [a, b] in edge:
gragh[a][b] = 1
gragh[b][a] = 1
print(gragh[3][4]) # 1
print(gragh[4][3]) # 1
# 방향 그래프
# 행에서 열로 이동
edge = [[1, 2], [1, 3], [2, 5], [3, 4], [4, 2]] # 입력 정보
gragh = [[0] * (n+1) for _ in range(n+1)]
for [a, b] in edge:
gragh[a][b] = 1
print(gragh[3][4]) # 1
# 가중치 방향 그래프
# 행에서 열로 이동
edge = [[1, 2, 2], [1, 3, 4], [2, 5, 5], [3, 4, 5], [4, 2, 2]] # 입력 정보
gragh = [[0] * (n+1) for _ in range(n+1)]
for [a, b, c] in edge:
gragh[a][b] = c
print(gragh[3][4]) # 5
인접 리스트로 그래프 표현
# 무방향 그래프
edge = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 4]] # 입력 정보
gragh = [[] for _ in range(n+1)]
for [a, b] in edge:
gragh[a].append(b)
gragh[b].append(a)
print(gragh[2]) # [1, 4, 5]
# 방향 그래프
edge = [[1, 2], [1, 3], [2, 5], [3, 4], [4, 2]] # 입력 정보
gragh = [[] for _ in range(n+1)]
for [a, b] in edge:
gragh[a].append(b)
print(gragh[2]) # [5]
# 가중치 방향 그래프
edge = [[1, 2, 2], [1, 3, 4], [2, 5, 5], [3, 4, 5], [4, 2, 2]] # 입력 정보
gragh = [[] for _ in range(n+1)]
for [a, b, c] in edge:
gragh[a].append([b, c])
print(gragh[2]) # [[5, 5]]