728x90 공부/알고리즘28 이진 트리 구현과 순회(Traversal) ※이 글은 나동빈님 강의를 보고 복습용으로 작성하는 글입니다. https://blog.naver.com/ndb796/221233560789 19. 이진 트리의 구현과 순회(Traversal) 방식 기본적으로 가장 많이 사용되는 비선형 자료구조는 이진 트리(Binary Tree)입니다. 이진 트리는 트리 자... blog.naver.com 이진 트리(Binary Tree)는 굉장히 많이 사용되는 비선형 자료구조입니다. 비선형이란 선, 즉 일렬로 구현되지 않았다는 뜻입니다. 또 트리 자료구조를 활용한 대표적인 예시로 데이터의 탐색 속도 증진을 위해 사용되는 구조입니다. 이전 Heap Sort 에서도 다뤄 본 적이 있었습니다. https://com24everyday.tistory.com/101 힙정렬 저번주에.. 2020. 6. 5. 크루스칼 알고리즘(Kruskal algorithm) 크루스칼 알고리즘에 대해 배워보겠습니다. 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 그니깐 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이죠. 실제로 여러 개의 도시 연결을 위해 도로 건설 최소 비용을 위해 적용되는 알고리즘 입니다. 그래프 용어를 정리해 보겠습니다. 노드 = 정점 = node = 도시 : 그래프에서 동그라미 간선 = 거리 = edge = 비용 : 그래프에서 선 이 그림의 노드 개수는 7개이고 간선의 개수는 11개입니다. 즉 7개의 도시, 11개의 도로인거죠. 크루스칼 알고리즘의 핵심은 다음과 같습니다. 정렬 후 비용이 작은 ( 거리가 짧은) 순서대로 그래프에 포함시키자. 모든 노드를 최소 비용 연결시키는 게 목적이니 모든 노드를 오.. 2020. 6. 4. Union-Find(합집합찾기) Union-Find는 대표적인 그래프 알고리즘 입니다. 바로 '합집합 찾기'라는 이름의 알고리즘인데요. 서로소 집합(Disjoint-Set) 알고리즘이라고도 불리기도 합니다. 여러 개의 노드가 존재할때 두 노드가 같은 집합 안에 속했는지, 즉 연결이 되어있는지를 판별하는 알고리즘 입니다. 다음과 같은 노드셋이 있습니다. 모든 노드가 연결되어 있지 않고 자기 자신만을 집합의 원소로 가지고 있는 때입니다. 모든 값이 자기 자신을 가리키도록 만드는 겁니다. 아래 표에선 첫번째 행은 '노드 번호'를 의미하고 두번째는 '부모 노드 번호'를 의미합니다. 즉, 자기 자신이 어떤 부모에게 포함되어 있는지를 의미합니다. 어차피 한 노드에만 연결되어 있으면 다른 노드에도 연결되어져 있게 되는거니깐요. 여기서 부모노드는 값.. 2020. 6. 4. 깊이 우선 탐색(DFS) ※이 글은 나동빈님의 유튜브를 보고 복습용으로 포스팅됩니다※ https://blog.naver.com/ndb796/221230945092 16. 깊이 우선 탐색(DFS) 깊이 우선 탐색(Depth First Search)은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 ... blog.naver.com 깊이 우선 탐색(Depth First Search)은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘입니다. 가까운게 우선이었던 너비 우선 탐색과는 다른 느낌이죠. 이 깊이라는 게 좀 애매하다고 느끼실 분도 계실 거 같습니다. 그냥 가장 아래까지 내려갔다 돌아오는 알고리즘이라고 생각하시면 될거 같아요. BFS와 동일하게 DFS는 맹목적으로 각 노드를 탐색할 때 주로 이용.. 2020. 6. 3. 이전 1 2 3 4 5 6 7 다음 728x90
