Python으로 구현한 Merge Sort 분할정복 (Divide & Conquer) 기법을 이용하여 정렬한다. 주어진 리스트를 원소의 갯수가 1인 리스트가 될 때까지 분할한 뒤 그 리스트들을 다시 합치는 과정에서 원소를 비교하여 정렬을 수행한다. 소스코드 vi sort.py # Merge Sort def sort_merge(arr): if len(arr)<=1: return arr ## Exception ## Divide left = sort_merge(arr[:len(arr)//2]) right = sort_merge(arr[len(arr)//2:]) ## Conquer i,j,k […]
[Algorithm] Edit Distance
Edit Distance 편집 거리(Edit Distance) 알고리즘에 대해 알아보고 Python으로 Edit Distance 알고리즘을 구현해본다. ‘KITTEN’과 ‘SITTING’ 문자열 비교 편집 거리(Edit Distance)는 어떤 문자열을 다른 문자열로 바꾸기 위해 필요한 연산의 최소 횟수를 뜻한다. 한 문자열에 대해 삽입, 삭제, 변경의 연산을 몇 번에 걸쳐 바꿀 수 있는지를 기준으로 두 비교 대상의 유사도를 판단한다. ‘KITTEN’과 ‘SITTING’을 비교한다고 했을 때, […]
[Algorithm] Python으로 구현한 sort
[Algorithm] Python으로 구현한 sort Python은 list 자료형에 대해 sort 메소드를 기본적으로 제공하지만 필요에 따라 직접 구현할 필요도 있고, 또 Python 언어와 알고리즘 이해를 위해 작성한다. 오름차순 정렬 list_data.sort() 내림차순 정렬 list_data.sort(reverse=True) Sort Basic 선택 정렬 (Selection Sort) 삽입 정렬 (Insertion Sort) 거품 정렬 (Bubble Sort) 퀵 정렬 (Quick Sort) 선택 정렬 (Selection Sort) selection sort는 […]
[Algorithm] BFS
Python으로 구현한 BFS BFS 알고리즘은 Queue 자료구조를 사용한다. 그래프 노드를 순회하는데 최초 노드의 모든 자식 노드들을 먼저 탐색한다. 이후 그 자식 노드들의 자식 노드를 모두 탐색하는 과정을 반복한다. 소스코드 #!/bin/python graph = {‘A’: [‘B’, ‘C’, ‘D’], ‘B’: [‘A’, ‘E’, ‘F’], ‘C’: [‘A’, ‘G’], ‘D’: [‘A’, ‘H’, ‘I’], ‘E’: [‘B’], ‘F’: [‘B’, ‘J’], ‘G’: [‘C’], ‘H’: […]
[Algorithm] DFS
Python으로 구현한 DFS DFS 알고리즘은 Stack 자료구조를 사용한다. 그래프 노드를 순회하는데 leaf 노드인 순간까지 앞만 보고 방문한다. 만약 leaf 노드를 만나게 되면, 직전의 분기점으로 돌아가 다시 leaf 노드를 만날 때 까지 방문한다. 소스코드 #!/bin/python graph = {‘A’: [‘B’, ‘C’, ‘D’], ‘B’: [‘A’, ‘E’, ‘F’], ‘C’: [‘A’, ‘G’], ‘D’: [‘A’, ‘H’, ‘I’], ‘E’: [‘B’], ‘F’: [‘B’, […]