Programming 기초
-
[Python 자료구조 #탐색트리2] 이진탐색트리를 이용한 맵Programming 기초/Python 2023. 5. 26. 18:05
* 이진탐색트리를 이용한 맵 ↓BSTNode(), inorder(), count_node(),search_bst()함수 코드참고.(이전 블로그 글 참고) 더보기 class BSTNode: def __init__(self, key, value): self.key = key self.value = value self.left = None self.right = None def inorder(n): # 중위 순회 함수 if n is not None: inorder(n.left) # 왼쪽 서브트리 처리 print(n.key, end=" ") # 루트노드 처리(화면 출력) inorder(n.right) def count_node(n): if n is None: return 0 else: return 1 + cou..
-
[Python 자료구조 #탐색트리1] 이진탐색트리(BST)Programming 기초/Python 2023. 5. 26. 15:53
* 이진탐색트리(BST, Binary Search Tree) 효율적인 탐색을 위한 이진트리 기반의 자료구조이다.(이진탐색트리는 이진트리의 한 종류이다.) 트리의 연산들을 보다 단순하게 설계하기 위해 이진탐색트리에서는 보통 중복을 허용하지 않는다. 그렇지만, 필요하다면 중복된 키를 허용할 수도 있다. 이진탐색트리의 모든 노드들을 중위 순회로 방문하면 오름차순으로 노드를 방문하게 된다. 따라서 어느 정도 정렬된 상태를 유지하고 있다고 볼 수 있다. 이진탐색트리는 탐색을 위한 자료구조이므로 노드의 데이터는 하나의 엔트리, (탐색키, 키에 대한 값)의 형태가 되어야 한다. ● 모든 노드는 유일한 키를 갖는다. ● 왼쪽 서브트리의 키들은 루트의 키보다 작다. ● 오른쪽 서브트리의 키들은 ..
-
[Python 자료구조 #트리3] 힙(Heap), 허프만 코드Programming 기초/Python 2023. 5. 25. 21:45
* 힙(Heap) 사전상 의미는 "더미". 컴퓨터 분야에서 힙은 "더미"와 모습이 비슷한 완전이진트리 기반의 자료 구조를 의미한다. 힙은 여러 개의 값들 중에서 가장 큰(또는 작은) 값을 빠르게 찾아내도록 만들어진 자료 구조이다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 정도의 느슨한 정렬 상태만을 유지. 최대 힙(max heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전이진트리 (key(부모노드)≥key(자식노드)) 최소 힙(min heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전이진트리 (key(부모노드)≤key(자식노드)) * 힙 트리 삽입 연산 힙에 새로운 항목을 삽입할 때 힙의 순서 특성(최대 힙, 최소 힙)과 트리의 형태..
-
[Python 자료구조 #트리2] 모르스 코드 결정트리Programming 기초/Python 2023. 5. 25. 14:25
* 이진트리의 응용 : 모르스 코드 결정트리 모르스 부호는 도트(점)와 대시(선)의 조합으로 구성된 메시지 전달용 부호로 1830년대에 미국의 사뮤엘 모르스(Samuel Morse)에 의해 고안되었다. 결정트리는 여러 단계의 복잡한 조건을 갖는 문제에 대해 조건과 그에 따른 해결방법을 트리 형태로 나타낸 것을 말한다. 결정트리를 이용하면 알파벳을 찾는데 걸리는 시간은 O(log_2 n)이다. table =[('A', '.-'), ('B', '-...'), ('C', '-.-.'), ('D', '-..'), ('E', '.'), ('F', '..-.'), ('G', '--.'), ('H', '....'), ('I', '..'), ('J', '.---'), ('K', '-.-'), ('L', '.-..'),..
-
[Python 자료구조 #트리1] 이진 트리, 전위/중위/후위/레벨 순회Programming 기초/Python 2023. 5. 25. 00:21
* 트리(Tree) 계층적인 관계를 가진 자료의 표현에 유용한 자료구조가 트리(tree)이다. 리스트나 스택, 큐, 덱 등은 모두 자료들이 일렬로 나열된 형태인 선형 자료 구조이다. 트리는 계층적인 구조(hierarchical structure)이다. 트리는 순환적으로 정의된다. 활용 : 폴더 구조, 효율적인 탐색을 위한 탐색트리, 우선순위 큐를 위한 힙 트리, 인공지능 문제에서 의사결정 구조를 표현하기 위한 결정 트리(decision tree) 등 * 트리의 용어 루트(root) 노드: 계층적인 구조에서 가장 높은 곳에 있는 노드, 트리에서 모든 노드는 자신의 서브트리의 루트 노드이다. 간선 또는 에지(edge): 노드와 노드를 연결하는 선 부모(parent) 노드와 자식(child) 노드 : 간선으로..
-
[Python 자료구조 #정렬과 탐색2] 순차탐색, 이진탐색, 보간탐색, 해싱Programming 기초/Python 2023. 5. 24. 18:41
* 탐색(searching) 탐색은 레코드(record)의 집합에서 원하는 레코드를 찾는 작업이다. 테이블(table) : 보통 이러한 레코드들의 집합 탐색키(search key) : 레코드들이 서로를 구별하여 인식하기 위해 가지고 있는 키(key) 탐색은 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업이다. 탐색에서는 테이블을 구성하는 방법에 따라 효율이 달라진다. 맵 또는 딕셔너리는 자료를 저장하고 탐색키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 탐색을 위한 자료구조를 말한다. * 맵(map) 맵(map)은 엔트리(entry)라고 불리는 키를 가진 레코드(keyed recod)의 집합이다. 엔트리는 두 개의 필드를 가진다. 키(key) : 영어 단어나 사람의 이름과 같은 레코드를 구분할..
-
[Python 자료구조 #정렬과 탐색1] 선택정렬, 삽입정렬, 버블정렬, 정렬 응용한 집합Programming 기초/Python 2023. 5. 23. 21:32
* 정렬(sorting) 오름차순( ascending order) 내림차순(descending order) 레코드(record) : 정렬시켜야 될 대상 필드(field) 레코드는 여러 개의 필드로 이루어지고, 필드는 속성들이다. 키(key) 또는 정렬 키(sort key) : 정렬의 기준이 되는 필드 정렬 : 레코드들을 키(key)의 순서로 재배열하는 것 * 정렬 장소에 따른 분류 내부(internal)정렬 : 모든 데이터가 메인 메모리에 올라와 있는 정렬 외부(external)정렬 : 외부 기억 장치에 대부분의 데이터가 있고 일부만 메모리에 올려 정렬하는 방법으로 대용량 자료를 정렬하기 위해 사용한다. * 구현 복잡도와 알고리즘 효율성에 따른 분류 단순하지만 비효율적인 방법 : 삽입정렬, 선택정렬, 버..
-
[Python 자료구조 #연결리스트3] 이중연결리스트 : 연결된 덱Programming 기초/Python 2023. 5. 23. 02:21
* 이중연결리스트의 응용 : 연결된 덱(linked deque) 먼저 덱을 단순연결리스트로도 구현할 수 있다. 그러나 deleteRear연산에서 문제가 생긴다. 다른 연산들은 모두 O(1)에 처리가 가능한데 비해 이 연산은 O(n)이 걸린다. 후단을 삭제하고 나면 rear가 한 칸 앞으로 움직여야 하는데, 선행 노드의 정보가 없어서 front부터 탐색해야 하기 때문이다. 이 문제를 해결하는 방법은 이중연결리스트를 사용하는 것이다. ※ 이중연결리스트를 이용하면 전후단 삭제의 시간 복잡도는 모두 O(1)이 된다. class DNode: # 이중연결리스트는 2개의 링크를 갖는다. def __init__(self, elem, prev=None, next=None): self.data = elem # 노드 내의 ..