알고리즘/정렬13 [알고리즘-17] 이진트리의 구현과 순회(Traversal) 방식 안녕하세요 기린입니다 :) 오늘은 완전 이진트리가 아닌 이진트리를 구현하는 방법과 해당 이진트리를 탐색하는 방법인 순회 방식에 대해 알아보겠습니다. 기본적으로 가장 많이 사용되는 비선형 자료구조는 이진 트리(Binary Tree)입니다. 이진 트리는 트리 자료구조를 활용한 대표적인 예시로 데이터의 탐색 속도 증진을 위해 사용하는 구조입니다. 이전에 힙 정렬(Heap Sort)을 구현할 때 간단하게 이진 트리에 대해 다루어 본 적이 있습니다. 힙 정렬에서 완전 이진 트리 구조를 사용했다면 이번 시간에는 실제로 트리를 제대로 구현해 보겠습니다. 일단 실제 트리를 구현하기 위해 포인터(Pointer)를 이용해 특정한 루트(Root)에서 자식 노드로 접근하도록 하겠습니다. 이진 트리의 구조는 위와 같이 생겼습니.. 2022. 5. 26. [알고리즘-16] 크루스칼 알고리즘(Kruskal Algorithm) 안녕하세요 기린입니다 :) 이번 시간에 배워볼 내용은 바로 크루스칼 알고리즘입니다. 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 다시 말해 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이라고 할 수 있습니다. 예를들어 여러 개의 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하고자 할 때 실제로 적용되는 알고리즘이죠 일단 용부터 정리해보겠습니다 노드 = 정점 = 도시 -> 그래프에서 동그라미에 해당하는 부분 간선 = 거리 = 비용 -> 그래프에서 선에 해당하는 부분 즉 아래의 그래프를 살펴보았을 때 노드의 갯수는 7개, 간선의 갯수는 11개 입니다. 크루스칼의 핵심 개념은 간선의 거리가 짧은 순서대로 그래프에 포함시키자 입니다. 일단 모든 .. 2022. 4. 28. [알고리즘-15] Union-Find (합집합 찾기) 안녕하세요 기린입니다 :) 오늘은 합집합 찾기(Union-Find)에 대해 알아보도록 하겠습니다. Union-FInd는 대표적인 그래프 알고리즘입니다. 바로 '합집합 찾기'라는 의미를 가진 알고리즘인데요. 서로소 집합(Disjoint-Set) 알고리즘이라고도 부릅니다. 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다. 위와 같이 여러 개의 노드가 서로 자유분방하게 존재한다고 생각해봅시다. 이와 같이 모두 연결되지 않고 각자 자기 자신만을 원소로 가지고 있을 때 아래 표와 같이 표현할 수 있습니다. 노드번호 1 2 3 4 5 6 7 8 부모노드번호 1 2 3 4 5 6 7 8 첫 번째 행은 '노드 번호'를 의미하고 두.. 2022. 4. 26. [알고리즘-14] 깊이 우선 탐색(DFS) 안녕하세요 기린입니다 :) 오늘은 지난 시간에 이어 깊이 우선 탐색(Depth-Frist Search)에 대해 알아보도록 하겠습니다. 먼저 깊이 우선 탐색이란 말 그대로 보다 깊은 것을 우선적으로 탐색하는 알고리즘입니다. 맹목적으로 각 노드를 탐색할 때 주로 사용되죠. 너비 우선 탐색과는 다르게 큐(Queue)를 사용하지 않고 스택(Stack)이 사용됩니다. 그리고 굳이 스택을 사용하지 않아도 구현이 가능하다는 특징이 있습니다. 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문입니다. DFS는 맨 처음에 시작 노드(Start Node)를 스택에 삽입하면서 시작합니다. 또한 그와 동시에 시작 노드를 방문했다고 알리는 '방문 처리'를 해주도록 합니다. 방문 처리는 파란색으로 해주도록 하겠습니다. 이제는 .. 2022. 4. 25. [알고리즘-13] 너비 우선 탐색(BFS) 안녕하세요 기린입니다 :) 오늘은 배울 알고리즘은 바로 너비 우선 탐색(Breadth-Frist Search, BFS)은 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 입니다. 특히 '맹목적인 탐색'을 하고자 할 때 사용할 수 있는 탐색 기법입니다. 너비 우선 탐색은 '최단 경로'를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용합니다. 준비물은 큐(Queue)인데요 아래와 같이 큐와 그래프를 준비해보도록 합시다. BFS는 맨 처음에 시작 노드(Start Node)를 큐에 삽입하면서 시작합니다. 또한 시작 노드를 방문 했다고 '방문 처리' 해주도록 합니다. 방문 처리는 파란색으로 해주도록 하겠습니다. 이제 BFS는 다음과 같은 간단한 알고리즘에 따라서 작동합니다. 1. 큐에서 하.. 2022. 4. 22. [알고리즘-12] 스택(Stack), 큐(Queue) 안녕하세요 기린입니다 :) 이번 시간에는 스택과 큐를 배워보겠습니다. 스택(Stack)과 큐(Queue)는 컴퓨터 공학에서 가장 기본이 되는 자료구조입니다. 말 그대로 자료를 표현하고 처리하는 방법에 관한 것입니다. 예를 들자면 스택은 택배 상하차를 생각하시면 되고, 큐는 은행 창구를 생각하시면 됩니다. 먼저, 스택부터 확인해봅시다. 어렵지 않은 개념이니 천천히 생각해보시죠 :] 스택은 아래와 같이 출구가 하나밖에 없는 상태로 표현할 수 있습니다. 첫 번째 명령어 삽입(7)이 실행되면 7이 삽입됩니다. 다음 명령어 삽입(5)이 실행되면 위와 같습니다. 이후에 원소 4가 삽입됩니다. 이제 명령어 삭제()가 수행되는데, 삭제할 때는 항상 가장 최근에 들어간 원소가 나갑니다. 이후에 원소 6이 삽입됩니다. 결.. 2022. 4. 19. 이전 1 2 3 다음
