Edit Distance 편집 거리(Edit Distance) 알고리즘에 대해 알아보고 Python으로 Edit Distance 알고리즘을 구현해본다. ‘KITTEN’과 ‘SITTING’ 문자열 비교 편집 거리(Edit Distance)는 어떤 문자열을 다른 문자열로 바꾸기 위해 필요한 연산의 최소 횟수를 뜻한다. 한 문자열에 대해 삽입, 삭제, 변경의 연산을 몇 번에 걸쳐 바꿀 수 있는지를 기준으로 두 비교 대상의 유사도를 판단한다. ‘KITTEN’과 ‘SITTING’을 비교한다고 했을 때, […]
[Python] Memoization을 이용한 Fibonacci
Fibonacci using Memoization Legacy Fibonacci def fibo(n): return n if n < 2 else fibo(n-2) + fibo(n-1) def Main(): number = int(input(“Enter integer: “)) print(fibo(number)) if __name__==’__main__’: Main() Fibonacci using Memoization __fibo_cache = {} def fibo(n): if n in __fibo_cache: return __fibo_cache[n] else: __fibo_cache[n] = n if n < 2 else fibo(n-2) + fibo(n-1) return […]
[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’, […]
[Python] list, append vs. extend
Append vs. Extend Append append는 입력된 object를 list의 맨 뒤에 추가 x = [1,2,3] y = [4,5] x.append(y) print(x) [1, 2, 3, [4, 5]] Extend extend는 iterable object(list, tuple, dict)의 원소를 list의 맨 뒤에 순서대로 추가 x = [1,2,3] y = [4,5] x.extend(y) print(x) [1, 2, 3, 4, 5]
[Python] python3 설치 (소스 빌드하기)
Python 빌드하기 대부분의 Linux 배포판에서는 python 2.x 버전이 기본 설치 된다. 버전 2,3 간의 문법 차이가 제법 크고 현재 최신 버전인 3.7.0 에서 호환이 제대로 안되는 패키지들이 간혹 있어 직접 빌드하는 걸 개인적으로 선호하고, 멀티 노드 환경인 경우 이렇게 하는게 버전 관리하기도 좋은 것 같다. 준비사항 의존 시스템 라이브러리 설치 yum -y install gcc openssl-devel […]