전체 글
-
[Python 자료구조 #그래프2] 그래프의 탐색(DFS, BFS), 연결 성분 검사Programming 기초/Python 2023. 5. 27. 14:15
* 그래프의 탐색 - 깊이 우선 탐색 깊이 우선 탐색(Depth First Search, DFS)은 스택을 이용한 미로 탐색과 유사하다.(이전 포스팅 참고) 탐색 과정에 이미 방문한 정점을 관리하는 집(또는 리스트)가 필요한데, 이를 visited라 하면 맨 처음에는 visited가 공집합이어야 한다. 가장 최근에 만났던 갈림길로 되돌아가야 하므로 스택을 사용하여 구현할 수 있지만, 순환의 형태로 구현하는 것이 더 직관적이다. 그래프가 인접리스트로 표현되어 있으면 O(n + e) 이고(n은 노드 수 e는 간선 수), 인접 행렬로 표시되어 있다면 O(n^2)이다. # 인접 리스트 방식으로 표현된 그래프를 활용한 dfs. 인접행렬을 이용하면 달라짐 # 매개 변수로 그래프, 시작 정점, 그리고 visited를..
-
[Python 자료구조 #그래프1] 그래프 용어, 인접 행렬/ 인접 리스트로 표현한 그래프카테고리 없음 2023. 5. 27. 01:06
* 그래프(graph) 그래프는 연결된 객체들 사이의 관계를 표현할 수 있는 자료구조이다. 선형 자료구조들이나 트리도 그래프로 표현할 수 있기 때문에 그래프의 한 종류로 볼 수 있다.(그래프는 가장 일반화된 자료구조이다.) * 그래프 이론(graph theory) 그래프와 관련된 다양한 문제를 연구하는 학문 분야 그래프는 수학자 오일러(Euler)에 의해 처음 창안되었다. * 그래프 용어 정점(vertex) 또는 노드(node): 객체(object) 간선(edge) 또는 링크(link) : 객체간의 관계. 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. G = (V, E) : 그래프의 수학적 표기법 V(G) : 그래프 G의 정점들의 집합 E(G) : 그래프 G의 간선들의..
-
[Python 자료구조 #탐색트리3] AVL트리, AVL트리를 이용한 맵Programming 기초/Python 2023. 5. 26. 19:36
* 심화 학습 : 균형이진탐색트리 - AVL 트리 AVL 트리는 Adelson-Velskii와 Landis에 의해 제안된 트리이다. AVL트리는 항상 균형 트리를 보장하기 때문에 탐색과 삽입, 삭제 연산에서 항상 O(log_2 n)의 처리시간을 보장한다. AVL 트리를 정의하기 위해서는 균형인수를 정의해야 한다. 어떤 노드의 균형 인수(balance factor)는 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차로 정의된다. AVL 트리는 비균형 상태가 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. AVL 트리 정의 AVL 트리는 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1을 넘지 않는 이진탐색 트리이다. 즉 모든 노드의 균형 인수는 0이나 ±1이 되어야 한다. * AVL 트리..
-
[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) 노드 : 간선으로..