동적계획법
동적 프로그래밍
동적 프로그래밍은 세부 계산으로 나뉘어지는 하나의 큰 문제를 세부 계산 결과를 미리 구해서 저장한 후 큰 계산의 결과를 빠르게 도출해내는 문제해결 기법이다.(이름과는 달리 프로그래밍 테크닉은 아니다.) 흔히 피보나치 수열을 계산할 때 memoization도 동적 프로그래밍의 범주로 볼 수 있다. 더 보기 »동적계획법
순열생성로직연구
사실 이 포스팅은 순열을 만드는 방법에 대한 매우 비효율적인 접근에 대한 글입니다. 효율적인 순열/조합 생성 코드는 이 글을 참고하세요.
순열을 만드는 가장 간단한 방법으로는 특정 원소를 하나씩 뺀 후 배열의 나머지를 순열한 각 결과에 빼냈던 원소를 앞에 붙여준 결과를 모으는 방법이 있다. 대략의 코드는 다음과 같다.
def rec_perm(iterable):
if len(iterable) == 1:
return [list(iterable)]
result = []
for i in range(len(iterable)):
head = iterable[i]
tail = iterable[:i] + iterable[i+1:]
result += [[head] + x for x in rec_perm(tail)]
return result
이 알고리듬의 가장 큰 문제는 한 번에 모든 순열을 다 생성해서 그 리스트를 만환한다는 말이다. 만약 원소가 100개라면?1 메모리 부족으로 컴퓨터가 뻗을 수 있다. 물론 10개 미만의 연속열에 대해서는 나름 나쁘지 않은 성능을 낼 수 있다.
더 보기 »순열생성로직연구버블 정렬 (Bubble Sort)
버블정렬은 정렬 중에서 가장 기본적이고 쉬운 알고리듬이다. 버블정렬은 배열의 앞에서부터 큰 원소를 뒤쪽으로 보내는 작업을 반복적으로 시행하여 배열 전체를 정렬한다. 이 때 큰 값들이 물속에서 거품이 떠오르는 것처럼 움직이기 때문에 ‘버블’이라는 이름이 붙었다.
간단한 예를 통해서 버블 정렬이 어떻게 작동하는지 살펴보자. 아래와 같은 배열이 있다고 가정하자.
더 보기 »버블 정렬 (Bubble Sort)이진탐색트리 (Binary Search Tree) 구현하기 – python
Binary Search Tree
이진 탐색 트리는 이진 트리 구조 속에 이진 탐색 알고리듬을 이용하여 키-값 쌍을 저장하는, 어찌보면 맵(혹은 사전이라고도 하는) 구조와 유사한 형태이다. 이진 탐색 자체가 데이터가 정렬된 상태를 전제하기 때문에, 구조 내에 자료를 삽입/삭제하는 과정이 단순하지는 않지만, 어떤 정렬된 상태의 키를 기준으로 데이터를 찾는데는 매우 유리한 구조이다.
이진 탐색 트리는 특정 노드가 어디에 위치하는데에는 크게 관심이 없다. 단지 이를 사용하여 효율적인 탐색을 할 수 있게 한다. 보면 알겠지만 해시테이블이 메모리 공간을 더 사용하고 반대급부로 성능을 얻는 것과는 달리, 이진 탐색 트리는 트리 구조 자체의 특성을 사용하므로 부가적인 메모리 공간의 낭비는 적다고 볼 수 있다.
더 보기 »이진탐색트리 (Binary Search Tree) 구현하기 – python
Parse Tree
이진트리 애플리케이션
파스 트리
트리 데이터 구조를 구현하는 방법을 알게 되면 이제 이 자료구조를 사용하여 실제 문제를 풀 수 있는 사용처에 대해서 살펴보자. 트리는 부분 요소로 나눠지는 데이터를 표현하기에 좋으므로 파싱과 관련된 작업에 많이 사용된다. 이럴 때 사용되는 트리를 파스 트리(Parse Tree)라 하는데, 파스 트리는 실제 문장이나 수학식을 표현하는데 사용될 수 있다.
http://interactivepython.org/runestone/static/pythonds/_images/nlParse.png
다음은 간단한 수학식을 트리로 표현한 것이다.
*
/ \
+ -
/ \ / \
7 3 5 2
> ( 7 + 3) * ( 5 - 2 )
우선순위 큐 혹은 최소/최대힙
우선순위 큐 (priority queue)는 큐와 비슷하게 뒤쪽으로 원소를 삽입하고 앞쪽으로 꺼낼 수 있는 자료 구조이다. 하지만 각 원소는 내부적으로 논리적인 우선순위 값을 가지고 있고, 따라서 선입선출(FIFO)의 규칙에 의해서 나오는 것이 아니라, 큐 내부에서는 높은 우선순위를 갖는 원소가 앞쪽으로 오게 된다. 즉, 큐와 마찬가지로 원소를 꺼낼 때는 앞에서부터 꺼내게 되는데, 이 순서가 큐 내부에서의 우선순위 순과 일치하게 되는 것이다. 일종의 자동으로 정렬되는 큐라고 생각하면 된다. 언어나 알고리듬 책에 따라서는 이를 최소/최대힙(min/max heap) 혹은 힙큐(heap queue)라고 부르기도 한다.더 보기 »우선순위 큐 혹은 최소/최대힙
Hash Map 이란 무엇인가
해싱
이진 트리 탐색에서는 리스트의 값이 순서대로 정렬되어 있다는 점을 활용하여 로가디즘시간(리스트의 크기가 커지면 탐색 시간이 리스트 크기의 로그값만큼 증가하는)에서 탐색이 이루어지도록 탐색 성능을 개선시킬 수 있음을 보았다. 이 장에서는 보다 나아가 고정시간이 걸리는 탐색을 살펴보고자 한다. 이 컨셉은 “해싱”이라는 기법으로 불린다.
이를 사용하기 위해서는 리스트에서 원소가 어디쯤에 위치할 것인지에 대해 좀 더 많은 것을 알아야 한다. 만약 모든 원소가 있어야 할 위치에 있다면 단 한 번의 비교 만으로도 아이템을 찾을 수 있다. 더 보기 »Hash Map 이란 무엇인가
후위식 변환
중위식과 후위식
B * C와 같은 수식에서 그 형태는 보는 사람에게 정보를 전달하여 이를 정확하게 해석할 수 있게 한다. 이 식에서 계산 방법은 두 수 B, C 사이에 있는 연산자에 의해서 결정되며 여기서는 두 수를 곱하는 계산을 표현하고 있다.