Computer Science/자료구조 & 알고리즘
-
[자료구조] 트리(Tree), 트리 순회(Tree Traversal)와 이진 탐색 트리(Binary Search Tree)Computer Science/자료구조 & 알고리즘 2020. 11. 23. 20:26
# 트리 (Tree) 가계도와 같은 계층적인 구조를 표현할 때 사용하는 자료구조이다. - 루트 노드 (root node): 부모가 없는 최상위 노드 ex) A - 단말 노드 (leaf node): 자식이 없는 노드 ex) G, E, F - 크기 (size): 트리에 포함된 모든 노드의 개수 ex) 7개 - 깊이 (depth): 루트 노드부터 해당 노드까지의 거리 ex) A: 0 / B, C: 1 / D, E, F: 2 / G: 3 - 높이 (height): 깊이 중 최댓값 ex) 3 - 차수 (degree): 각 노드의 (자식 방향) 간선 개수 ex) A, B: 2 / C, D: 1 - 트리의 크기가 N일 때, 전체 간선의 개수는 N - 1개 # 트리의 순회 (Tree Traversal) 트리 자료구조에..
-
[자료구조] 우선순위 큐(Priority Queue)와 힙(Heap)Computer Science/자료구조 & 알고리즘 2020. 11. 23. 15:58
# 우선순위 큐 (Priority Queue) 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 우선순위 큐는 리스트(List), 힙(Heap) 두가지 방식으로 구현 가능하다. 리스트의 경우 데이터를 단순히 리스트의 뒤에 삽입하고 우선순위를 기준으로 선형탐색한다. 따라서 삽입시간은 시간복잡도가 O(1)이지만, 삭제시간은 선형탐색으로 인해 O(N)이 소요된다. 반면, 힙은 삽입시간, 삭제시간 모두 O(logN)의 시간복잡도를 보장한다. 힙의 또다른 특징은 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업만으로도 정렬이 수행된다는 점이다. 이를 힙 정렬(Heap Sort)이라 하는데, 힙 정렬은 O(NlogN)의 시간 복..
-
[알고리즘] 이진 탐색Computer Science/자료구조 & 알고리즘 2020. 11. 18. 16:05
# 순차 탐색 일반적으로 자주 사용되는 탐색으로, 앞에서부터 데이터를 하나씩 차례대로 확인하며 리스트 안에 있는 특정 데이터를 찾는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾을 때 사용한다. 충분한 시간이 있다면 데이터가 아무리 많아도 항상 원하는 데이터를 찾을 수 있는 것이 장점이다. 시간 복잡도는 최악의 경우 O(N)을 보장한다. # 순차 탐색 함수 구현 def sequential_search(target, array): for i in range(len(array)): if array[i] == target: return i + 1 # 현재 위치 반환 (인덱스이므로 1을 더함) array = [4, 5, 1, 3, 2] target = 3 print(sequential_search(tar..
-
[알고리즘] 정렬 알고리즘Computer Science/자료구조 & 알고리즘 2020. 11. 17. 18:19
# 정렬(Sorting)이란? 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다. # 선택 정렬 (Selection Sort) 데이터가 무작위로 여러 개 있을 때, 가장 작은 데이터를 선택해 앞으로 보내는 과정을 반복하는 정렬이다. 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 다음으로 작은 데이터를 골라 앞에서 두 번째 데이터와 바꾸는 과정을 끝까지 반복해 데이터를 정렬한다. 선택 정렬을 파이썬으로 구현하면 다음과 같다. # 배열의 원소를 오름차순으로 정렬 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i+1, len(arra..
-
[알고리즘] DFS(Depth-First Search) & BFS(Breadth-First Search)Computer Science/자료구조 & 알고리즘 2020. 10. 20. 20:19
# 그래프 탐색 하나의 자료구조로서 그래프(Graph)는 데이터와 데이터 사이의 관계를 잘 표현해주는 자료구조이다. 그래프는 기본적으로 데이터가 담기는 노드(Node)와 데이터 사이를 연결하는 간선(Edge)으로 이루어져있다. 노드는 정점(Vertex)이라고도 불린다. 그래프 탐색은 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말하며, 간선으로 연결되어 있는 두 노드는 서로 '인접'해 있다고 한다. # DFS (Depth-First Search, 깊이 우선 탐색) DFS는 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 특정한 경로로 먼저 최대한 깊숙이 탐색한 후, 다시 돌아와 다른 경로를 탐색한다. DFS는 스택이나 재귀함수를 활용해 구현하며, 기본 순서는 다음과 같다. 1. 탐색 시작 ..
-
[알고리즘] 재귀 함수(Recursive Function)Computer Science/자료구조 & 알고리즘 2020. 10. 20. 16:39
# 재귀 함수 자기 자신을 다시 호출하는 함수를 의미한다. 이는 어린 시절 수학 과목을 공부할 때 마주하는 프랙털(Fractal) 구조와 비슷하다. 프랙털 구조에서는 같은 모양의 도형이 무한히 반복되는 형태를 볼 수 있다. 재귀 함수가 자기 자신을 호출하는 것도 무한히 반복되는 양상을 보인다. 따라서, 재귀 함수를 사용할 때는 항상 종료 조건을 명시해 함수의 끝을 만들어야 한다. 또한, 재귀 함수는 컴퓨터 내부 메인 메모리의 스택 공간에 적재된다. 이 말은 재귀 함수가 스택 자료구조와 내부적으로 동일함을 의미한다. 따라서, DFS와 같이 스택 자료구조를 사용해야 하는 알고리즘은 재귀 함수를 통해 간편히 구현할 수 있다. 다음은 파이썬으로 구현한 간단한 재귀 함수이다. def recursive_functi..
-
[자료구조] 스택(Stack)과 큐(Queue)Computer Science/자료구조 & 알고리즘 2020. 10. 20. 16:18
# 스택(Stack) 스택 자료구조는 상자 쌓기와 비슷하다. 차곡 차곡 아래서부터 위로 상자를 쌓아 나가면, 상자를 뺄 때는 상자들이 무너지지않게 맨 위의 가장 나중에 쌓은 상자부터 빼야 한다. 스택도 마찬가지다. 가장 나중에 들어온 데이터를 가장 먼저 빼는 후입선출(LIFO: Last In First Out) 구조를 가진다. 파이썬에서는 별도의 라이브러리 없이 기본 리스트 자료형으로 스택을 쉽게 구현할 수 있다. # Stack으로 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() 구현 stack = [] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stac..