Data Vision

DFS(깊이 우선 탐색) Depth-First Search의 약자로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프는 노드(Node)/정점(Vertex)과 간선(Edge)로 구성되는데 그래프를 표현하는 방법으로는 인접 행렬, 인접 리스트가 있다. 인접 행렬은 NxN 행렬을 만들어서 i번째 노드에서 j번째 노드로 갈 수 있다면 1을 표시, 갈 수 없다면 0을 표시하는 것이 일반적이다. 인접 리스트의 i번째 원소는 i번째...

힙이란 우선순위큐(Priority Queue)를 이진 트리로 구현한 자료구조 입니다. 힙의 삽입, 삭제 연산은 $O(\log n)$의 시간복잡도를 가집니다. 힙은 파이썬 내장모듈인 heapq를 이용해서 손쉽게 구현할 수 있습니다. import heapq arr = [4, 5, 6, 7, 9, 8, 3, 1, 2] heapq.heapify(arr) print(heapq.nsmallest(3, arr)) # 1 2 3 print(heapq.nlargest(3, arr)) # 7 8...

이번 포스팅에서는 여러 정렬 기법에 대해 알아보고 파이썬으로 간단하게 구현해보겠습니다. 선택 정렬(Selection Sort) 선택 정렬은 한마디로 Priority Queue with Unsorted Array라고 할 수 있습니다. 우선순위 큐가 하나 있다고 가정해봅시다. 데이터를 삽입할 때는 항상 끝에 삽입하고, pop 연산을 오름차순/내림차순으로 수행합니다. 또한 시간복잡도는 $O(n^2)$ 입니다. array = [7, 5, 9, 0, 3,...

내장 라이브러리인 itertools를 이용해서 조합, 순열, 중복순열, Cartesian Product 등을 손쉽게 구현할 수 있다. from itertools import combinations, permutations, combinations_with_replacement, product data = '123' l = combinations(data, 2) for e in l: print(*e) # 12 13 23 l = permutations(data, 2) for e in l: print(*e) # 12 13 21...

이번 포스팅에서는 스택, 큐에 대한 개념을 알아보고 파이썬으로 간단하게 구현해보겠습니다. 스택 스택은 LIFO(후입선출)의 특성을 가진 자료구조입니다. 시간복잡도는 다음과 같습니다. 삽입: $O(1)$ 삭제: $O(1)$ 파이썬에서는 다른 라이브러리를 쓸 필요없이 기본 자료형인 list를 활용하여 삽입 및 삭제 연산을 수행할 수 있습니다. arr = [1, 2, 3, 4, 5] stack = [] #...