Language/Python

이전 포스트에서 이진 탐색 트리(Binary Search Tree)를 구현해보았습니다. 트리는 배열이나 스택, 큐등의 자료구조와는 달리 데이터를 직관적으로 살펴보기 어렵습니다. 따라서, 트리를 위한 별도의 순회 알고리즘이 필요합니다. 트리 순회 알고리즘트리 순회 알고리즘은 트리에 저장된 모든 값을 중복이나 빠짐없이 살펴볼 때 사용합니다. 이진 트리의 순회 방법 중 깊이 우선 순회 방법(Depth First Traversal, DFS)으로는 전위 순회(Pre-order Traversal), 정위 순회(In-order Traversal), 후위 순회(Post-order Traversal)가 있으며, 너비 우선 순회 방법(Breadth First Traversal)으로는 레벨 순회(Level-order Tra..

이진 트리(Binary Tree)는 최대 두 개의 자식 노드를 가진느 트리 형태의 자료구조로, 단순히 값을 저장하는 용도보다는 효율적인 탐색 혹은 정렬을 위하여 사용됩니다. 이진 탐색 트리(Binary Search Tree)를 사용하여 주어진 값 혹은 이보다 작거나 큰 값들을 평균 O(logn)의 시간 복잡도로 찾을 수 있으며, 이진 트리의 한 종류인 힙(heap)을 사용한 힙 정렬(heap)은 O(nlogn)의 시간 복잡도를 가집니다. 이진 탐색 트리 구현 이진 탐색 트리(Binary Search Tree)는 이진 트리의 특수한 케이스 중 하나입니다. 이진 트리 중 모든 노드에 대해 왼쪽 자식 노드들의 값이 현재 노드 값보다 작거나 같으며, 오른쪽 자식 노드들의 값이 현재 노드의 값보다 크다는 조건을 ..

Python 내장 라이브러리인 itertools는 Python에서 제공하는 자신만의 반복자를 만드는 휼륭한 모듈입니다. 특정 배열에 대하여 순열이나 조합을 만들어 이를 이용하는 문제를 풀 때, 직접 구현해도 되지만, 이 itertools를 이용한다면 효율적으로 반복자를 구할 수 있습니다. product() import itertools itertools.product('ABCD', repeat=2) # 결과: AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD 인수: p, q, ... [ 반복 = 1 ] 결과: 중첩된 for loop에 해당하는 데카르트의 곱 permutations() import itertools itertools.permutations('ABCD', ..

1. Key 값을 정렬 Python의 Dictionary 자료형은 { key: value } 쌍으로 값이 들어가 있다. Dictionary는 Default(기본) 정렬이 Key값을 기준으로 오름차순으로 Key 값을 정렬하는 것이다. fruits \= { 'apple': 2, 'banana' : 1, 'melon' : 0, 'pear' : 2, 'plum' : 1} sorted(fruits) # \['apple', 'banana', 'melon', 'pear', 'plum'\] sorted(fruits.keys()) # \['apple', 'b..

정규 표현식(Regular Expression)정규 표현식은 특정한 규칙을 가진 문자열의 패턴을 표현하는 데 사용하는 표현식(Expression)으로 텍스트에서 특정 문자열을 검색하거나 치환할 때 흔히 사용된다. 예를 들어, 웹페이지에서 전화번호나 이메일 주소를 발췌한다거나 로그파일에서 특정 에러메시지가 들어간 라인들을 찾을 때 정규 표현식을 사용하면 쉽게 구현할 수 있다. 정규 표현식은 간단히 정규식, Regex 등으로 불리우곤 한다.파이썬에서의 정규 표현식 사용정규식에서 가장 단순한 것은 특정 문자열을 직접 리터럴로 사용하여 해당 문자열을 검색하는 것이다. 예를 들어, 로그 파일에 "에러 1033" 이라는 문자열을 검색하여 이 문자열이 있으면 이를 출력하고 없으면 None을 리턴하는 경우이다. 이러한..