Data Structure
파이썬 자료구조: 트라이
트라이(Trie)는 문자열을 효율적으로 탐색하기 위한 자료구조로, 문자열을 선형 시간 안에 찾아낼 수 있다. 트라이에 word를 삽입하는 insert 메소드와 prefix로 시작하는 문자열들의 리스트를 반환하는 starts_with 메소드를 구현했다.
파이썬 자료구조: 그래프
정점(vertex)들과 두 개의 정점을 잇는 간선(edge)들의 집합인 그래프(graph)는 광범위한 분야에 활용되는 자료구조이다. 그래프에 관한 용어들을 정리한 다음, 그래프에 속한 정점들을 빠짐없이 방문하는 두 가지 기본 연산인 깊이 우선 탐색(depth first search)과 너비 우선 탐색(breadth first search)을 구현했다. 그리고 최소 신장 트리(minimum spanning tree)를 찾는 Kruskal 알고리즘과 Prim 알고리즘, 최단 경로(shortest path)를 찾는 Dijkstra 알고리즘과 Floyd-Warshall 알고리즘에 대해 정리했다.
파이썬 자료구조: 탐색트리
이진탐색트리(binary search tree)는 정렬된 값들이 리스트에 존재할 때 주어진 값을 로그 시간 안에 찾는 방법인 이진탐색(binary tree)을 트리에 접목한 자료구조이다. 단순연결리스트에 비해, 저장된 값을 탐색하거나 임의의 값을 삽입하고 삭제하는 연산을 수행하는 데에 시간이 적게 걸린다는 장점이 있다. 이진탐색트리를 직접 구현해본 다음, 이진탐색트리에 기반한 자료구조인 AVL 트리, 2-3 트리, 좌편향 레드블랙트리(left-leaning red-black tree), B-트리에 대해서도 간단히 정리했다.
파이썬 자료구조: 이진트리와 힙
트리(tree)는 연결리스트와 달리 노드들이 위아래로 연결된 계층적인 자료구조이다. 특히 각각의 노드 아래에 두 개 이하의 노드가 연결된 이진트리(binary tree)의 활용성이 높다. 예를 들어, 이진트리를 활용하면 로그 시간 안에 가장 높은 우선순위를 가진 항목을 삭제하는 연산과 임의의 우선순위를 가진 항목을 삽입하는 연산을 제공하는 힙(heap)을 구현할 수 있다. 이진트리와 힙을 구현했다.
파이썬 자료구조: 스택과 큐
단순연결리스트를 이용하여 맨 앞에서만 항목을 삭제하거나 삽입하는 자료구조인 스택(stack)과 맨 앞에서는 항목을 삭제하기만 하고 맨 뒤에서는 항목을 삽입하기만 하는 자료구조인 큐(queue)를 구현했다. 스택에서는 마지막에 들어온 항목이 가장 먼저 나가므로 후입선출(Last In First Out, LIFO), 큐에서는 먼저 들어온 항목일수록 먼저 나가므로 선입선출(First In First Out, FIFO) 규칙이 적용된다. 데크(deque)은 맨 뒤와 맨 앞에서 삭제와 삽입이 둘 다 가능한 자료구조이다. 파이썬에는 스택과 큐 객체를 생성할 수 있는 queue 모듈과 데크 객체를 생성할 수 있는 deque 모듈이 존재한다.
파이썬 자료구조: 연결리스트
가장 기본적인 자료구조인 단순연결리스트와 함께, 이를 살짝 변형한 이중연결리스트, 원형연결리스트를 구현하면서 개념을 정리했다.
Algorithm
그래프에서 사이클의 존재 여부
무향 그래프와 유향 그래프에서 사이클의 존재 여부를 파악하는 방법을 정리했다.
오일러 경로·회로 찾기
오일러 경로(Eulerian path)란 그래프에서 모든 간선을 한 번씩만 방문하는 경로이다. 특별히 시작점과 끝점이 같은 오일러 경로를 오일러 회로(Eulerian circuit)라고 한다. 오일러 회로가 존재하려면 모든 정점에서 indegree와 outdegree가 동일해야 한다. 오일러 경로가 존재하려면 indegree가 1 작은 정점, outdegree가 1 작은 정점을 제외하고 모든 정점에서 indegree과 outdegree가 동일해야 하고, 이때 시작점은 indegree가 1 작은 정점, 끝점은 outdegree가 1 작은 정점으로 결정된다. DFS를 스택(stack)으로 구현하는 방식으로 주어진 그래프에서 오일러 경로를 찾을 수 있다.
중위 표기를 후위 표기로 변환하기
스택(stack) 자료구조를 활용하면 일반적인 중위 표기(infix notation)를 후위 표기(postfix)로 변환하여 컴퓨터가 계산하기 편리하게 만들어줄 수 있다.
이진탐색으로 상한과 하한 찾기
이진탐색(binary search)은 오름차순으로 정렬된 리스트에서 로그 시간 안에 특정 값의 위치를 찾을 수 있는 알고리즘이다.
Project
Airline on-time performance
Have you ever been stuck in an airport because your flight was delayed or cancelled and wondered if you could have predicted it if you’d had more data? This is your chance to find out.