본문 바로가기

알고리즘

Kruskal's Algorithm and Union-Find 크루스칼 알고리즘 파이썬 python 최소 비용 신장 트리를 만들기 위해 쓰이는 크루스칼 알고리즘. 일단 그래프에서 최소 비용인 엣지들을 오름차순으로 나열한다. 사이클을 만들지 않는 최소 비용인 엣지를 선택한다. 선택된 엣지가 노드의 총 개수 -1 이면 끝. 말은 쉽다. 그래도 말이 최소 비용 신장 트리지 복잡하게 트리를 만드는 과정은 없다. 배열로 끝낼 수 있다. 변의 개수 E, 꼭지점의 개수 N이라고 할 때 O(ElogV)의 시간 복잡도. Union-Find를 알아야 한다. 두 노드가 같은 집합에 속하는 지를 판단하기 위해 쓰인다. Find로 각 노드가 어느 집합에 있는 지 확인, Union으로 각 집합을 합치기. 개선하기Union:집합을 합칠 때, 두 집합 중 크기가 작은 것이 큰 집합에 붙는 것이 효율적이다.Find:한 노드가 어느 ..
Binary Search Tree BST 이진 탐색 검색 트리 파이썬 python 삽입, 탐색은 비교적 쉬워서 좀 어려운 삭제에 대한 그림을 그렸다. 1. 초기 이진 탐색 트리2. 삭제할 key를 찾았고 이를 node라고 한다. node의 오른쪽 자식 중에 가장 작은 값을 찾는다. child가 된다. 40은 parent.3. 그림에서 번호를 1~4까지 붙인대로 코드가 작성되어 있다. 지우려는 노드와 그 노드의 오른쪽 자식들 중 가장 작은 값을 바꾸는데, 말은 쉽지만 해야할 일들이 있다. (1) 노드의 왼쪽 자식은 child의 왼쪽 자식에 붙이기. (2) child의 오른쪽 자식은 parent의 왼쪽 자식으로 만들기 (3) 노드의 오른쪽 자식은 child의 오른쪽 자식 (4) 마지막으로 child를 node로 만들면 기존 node에 child가 덮어씌워진다.4. child.left에 n..
초간단 python DFS Depth First Search 깊이 우선 탐색 graph={ 1:[2,3], 2:[1,4,5,7], 3:[1,5,9], 4:[2,6], 5:[2,3,7,8], 6:[4], 7:[5,2], 8:[5], 9:[3], } def DFS(graph,root): stack=[root] visited=[] while stack: n=stack.pop() for i in graph[n]: if i not in visited: stack.append(i) if n not in visited: visited.append(n) print('v',visited) return visited print(DFS(graph,1))파이썬으로 짠 위 DFS 코드에서 쓰인 그래프 [1, 3, 9, 5, 8, 7, 2, 4, 6] 강의 영상
초간단 python BFS Breadth First Search 너비 우선 탐색 graph={ 1:[2,3], 2:[1,4,5,7], 3:[1,5,9], 4:[2,6], 5:[2,3,7,8], 6:[4], 7:[5,2], 8:[5], 9:[3], } def BFS(graph,root): visited=[] queue=[root] while queue:#while queue is not empty n = queue.pop(0) if n not in visited:#if n is not in visited list. visited.append(n)#put the n to the visited list. for i in graph[n]:#the numbers i connected with n if i not in visited:#i is not in visited list. queue.a..
이진 검색 트리 3 Delete자식 노드가 없는 경우 그냥 삭제한다.자식 노드가 1개인 경우부모와 자식이 각각 1개이므로 선형적인 형태이다. 삭제하려는 노드의 부모와 삭제하려는 노드의 자식을 이어주면 된다.자식 노드가 2개인 경우해당 노드를 삭제하고 다른 곳의 노드 값을 넣는다. predecessor, successor를 넣어야 한다.자식이 2개이므로 오른쪽 서브트리의 최소값이 successor가 된다.그 successor의 자식이 없다면 그냥 삭제하면 되고, 1개라면 자식을 successor의 위치에 넣는다. tree_delete(T,z): if left[z] == None or right[z] == None: #자식 노드가 없는 경우 삭제. y=z else: y = tree_successor(z) #자식이 있다면 suc..
이진 검색 트리 2 x를 루트로 하는 이진트리에서 최소값을 찾으려면 맨 왼쪽에 있는 리프 노드까지 도달하면 된다. 왼쪽으로 계속 내려가다가 더 이상 자식이 없다면 그 값이 최소값이다.tree-minimum(x): while left[x] != None: x=left[x] return x 반대로 최대값은 오른쪽 아래로 내려가야 한다.tree-maximum(x): while right[x] != None: x=right[x] return x Successor노드 x의 successor란 key[x]보다 크면서 가장 작은 키를 가진 노드.1. 노드 x의 오른쪽 부트리가 존재할 경우, 오른쪽 부트리의 최소값.2. 오른쪽 부트리가 없는 경우, 노드 x의 부모를 따라 올라가다가 처음으로 오른쪽 방향으로 올라간다면 그 노드가 x의 su..
이진 검색 트리 계층적인 자료를 표현하기 위해 트리를 사용한다.여러 개의 키를 저정한다.다음과 같은 연산들을 지원하는 자료구조insert - 새로운 키의 삽입search - 키 탐색delete - 키 삭제 search insert delete 배열 정렬 O(logn) O(n) O(n) 정렬x O(n) O(1) O(1) 연결리스트 정렬 O(n) O(n) O(1) 정렬x O(n) O(1) O(1) 정렬되거나 정렬되지 않은 배열 혹은 연결리스트를 선택하면 O(n)은 항상 존재함.탐색트리, 해쉬를 사용해서 보다 효율적인 방법을 구현할 수 있음.search, insert, delete의 연산은 트리의 높이에 비례하는 시간 복잡도를 가짐. search찾으려는 값 k와 노드 key[x]를 비교한다. 같다면 찾은거고 k가 작다면 왼쪽..
트리와 이진트리 계층적인 구조를 표현조직도, 디렉토리, 가계도 트리는 노드(node)와 링크(link)로 구성됨맨 위의 노드는 루트(root), 노드들을 연결하는 선을 link, edge, branch라고 부름 어떤 노드 A의 아래에 노드 B가 있으면 노드 A는 B의 부모 노드이고 B는 A의 자식 노드이다.부모가 동일한 노드는 형제(sibling) 관계이다.루트 노드를 제외한 트리의 모든 노드들은 유일한 부모 노드를 가진다.자식이 없는 노드는 리프(leaf) 노드 서브(sub)트리 : 트리의 어떤 부분을 잘라내도 트리다.레벨 : root 노드의 레벨을 0이라고 하면 아래로 내려갈 수록 1, 2, 3 ... n 레벨이 된다. root 노드의 레벨을 1이라고 하면 아래로 내려갈 수록 2, 3, 4, ... n이 된다. 트리..

티스토리툴바