부트캠프교육중/알고리즘12 BFS, DFS 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점을 한번씩 방문(탐색)하는 것이 목적이다. 정점 탐색방법의 대표적인 두가지는 BFS와 DFS가 있다. 이 둘은 데이터를 탐색하는 순서만 다를뿐, 모든 자료를 하나씩 확인해 본다는 점은 같다. DFS와 BFS는 모든 정점을 한 번만 방문한다는 공통점을 가지고 있지만, 사용할때의 장단점은 분명하기 때문에 해당하는 상황에 맞는 탐색 기법을 사용해야 한다. BFS(Breadth-First Search) -너비를 먼저 탐색하는 방법이다. 너비 우선 탐색이라고 한다. -최단경로(주로 두 정점 사이의 최단 경로를 찾을때 사용한다.) -한 경로를 끝까지 모두 다 탐색하는 처음 발견한 답이 최단 거리가 아닐 수 있지만, BFS는 현재 있는 노드에서 가까운 곳부터.. 2023. 3. 16. 그래프(Graph) 그래프(Graph) - 여러개의 점이 서로 복잡하게 연결된 관계를 표현한 자료구조. - 분자처럼 생긴 H20 모양이다. -컴퓨터 공학에서 말하는 자료구조의 그래프는 마치 거미줄처럼 여러개의 점이 선으로 이어져있는 복잡한 네트워크망과 같은 모습을 가지고 있다. #그래프의 구조 -직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다. -간접적인 관계라면 몇개의 점과 선에 걸쳐 이어진다. -하나의 점을 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)라고 한다. -정점(vertex) : 노드라고도 하며 데이터가 저장되는 그래프의 기본 원소이다. -간선(edge) : 정점 간의 관계를 나타낸다. (정점을 이어주는 선) -인접 정점(adjacent vertex) : 하나의 정점에서 간선에 의.. 2023. 3. 16. 트리 순회 -트리의 모든 노드를 한번씩 방문하는 것. -모든 노드를 순회하는 방법엔 크게 세가지가 있다.(트리구조가 계층적구조라는 특별한 특징때문에) -전위 순회, 중위 순회, 후위 순회 -모두 노드를 순회할때 왼쪽부터 오른쪽으로 조회한다는 공통점이 있다. 전위 순회 (preorder traverse) -ABDHIEJK CFLMGNO -가장 먼저 방문하는 노드는 루트이다. -루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다. -부모 노드가 제일 먼저 방문되는 순회방식이다. -주로 트리를 복사할때 사용. 중위 순회 (inorder traverse) -HDIBJEKA LFMCNGO -제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드.. 2023. 3. 15. 이진트리, 이진탐색트리 -자식 노드가 최대 두개인 노드로 구성된 트리. 이 두개의 자식노드는 왼쪽 자식노드와 오른쪽 자식노드로 나눌수있다. -이진 탐색 트리와 이진 힙 구현에 사용되며, 효율적인 검색과 정렬을 위해 사용된다. -자료의 삽입, 삭제 방법에 따라 정이진트리, 포화이진트리, 완전이진트리로 나뉜다. #특징 -정 이진 트리(Full binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다. -포화 이진 트리(Perfect binary tree): 정 이진 트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져있는 트리이다. -완전 이진 트리(Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨이 노드.. 2023. 3. 15. 이전 1 2 3 다음
