Min'sLog

● 너비 우선 탐색(Breadth-First-Search:BFS)이란?     - 너비 우선 탐색은 그래프 탐색 방법 중 하나로 시작 정점(vertex)을 기준으로 인접한 모든 정점들을 우선 방문하는       탐색 방법이다. 더 이상 방문하지 않은 정점이 없을때까지 탐색을 진행한다.    - 그래프는 트리의 구조와는 다르게 Cycle 이 존재하기 때문에, 깊이 우선 탐색 방식(DFS과 마찬가지로 방문한 정점에       대해서 방문 표시를 한다.   ● BFS 동작 원리  1.해당 정점을 기준으로 연결된 인접 정점들을 차례대로 방문하며,방문이 완료된 정점에 대한    표시 및 Queue에 저장한다. 2. 다음 순회의 기준 정점은 Queue에 방문한 정점을 빼내어(Dequeue) 기준으로 삼고, 만약 c..

ㅁ● 그래프 탐색이란  - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다.● 깊이 우선 탐색(DFS, Depth-First Search)이란 ?   - 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에     해당 분기를 완벽하게 탐색하는 방법을 말한다.ex)   미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면    다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.   즉, 깊게(deep) 탐색할 길을 끝까지 탐색한 후, 더이상 길이 존재하지 않으면, 가장 가까운 분기점(Branch)으로 돌아와      다음 탐색 위치를 탐색하는 방식이다.  ..

● 그래프란?정점(V, vertext)과 그 정점을 연결하는 간선(E, edge)의 집합 / 정점과 간선을 하나로 모은 자료구조이다.그래프 (G)의 정점의 집합 -> V(G) 로 표시,그래프 (G)의 간선의 집합 -> E(G) 로 표시한다.  ● 그래프의 종류  ○ 무방향 그래프(Undirected Graph)     무방향 그래프는 두 정점(vertext)을 잇는 간선(edge)의 방향이 없는 그래프이다.(간선을 표현할때 () 소괄호로 표현)ex)     V(G1) = {동수,지민,지율,민석,수정,정희)     E(G1) = {(동수,지민),(동수,지율),(지율,민석),(지민,민석),(민석,수정),(민석,정희),(수정,정희)}      ○  방향 그래프(Directed Graph)        방향 그..

● 해시 테이블이란? 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나   검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. ● 테이블 자료구조   데이터가 key와 value 한쌍을 이루며, key가 데이터의 저장 및 탐색의 도구가 된다.   ○ 테이블 자료구조의 특징 -  즉 테이블 자료구조에서는 원하는 데이터를 단번에 찾을 수 있다. -  테이블 자료구조의 탐색 연산..

● AVL트리란? AVL 트리(발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름)는 자가 균형 이진 탐색 트리이다.스스로 균형을 잡는 데이터 구조 중 처음으로 발명되었다. AVL 트리에서, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다. 만약 어떤 시점에서 높이 차이가 1보다 커지면 이 속성을 유지하기 위해서 스스로 균형을 잡는다. 일반적인 이진 탐색 트리의 탐색 연산은 O(log2n) 의 시간 복잡도를 가져야 하지만,한쪽으로 치우쳐질수록(skewed) 시간 복잡도가 O(n) 에  가까워진다.  이에 따라,  한쪽으로 치우지지 않고 탐색 연산의 성능을 높이기 위해 트리의 구조를 변형하는트리의 한 종류가 AVL 트리이다.  ● Balance Factor(균형인수)란?AVL..

● 이진 탐색 트리란?   이진트리를 기반으로 탐색을 용이하게 하기 위해 규칙을 추가한 트리이다.해당 규칙은 다음과 같다.  1.  이진탐색트리의 각 노드에 저장된 Key 값은 유일하다.  2.  루트노드의 키보다 작은 값은 왼쪽 서브트리에 저장 / 루트노드 보다 큰 키값은 오른쪽 서브트리에 저장한다.   3.  왼쪽 / 오른쪽 서브트리 역시 이진 탐색 트리이다.   이진 탐색 트리의 탐색은 탐색을 할때 마다, 탐색할 대상 데이터가 절반 길이씩 줄기 때문에,   균형잡힌 이진 탐색트리라 가정한다면 수행속도는 O(log2n) 이 된다. ● 이진 탐색 트리를 구성하는 노드 구조체    이진 탐색 트리를 구성하는 노드의 구조체는 이진트리의 구조체와 동일하며, 다음과 같다.   구조체 자신을 참조를 하는 포인터..

● 퀵 정렬(quick sort) 이란‘  찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)’가 개발한 정렬 알고리즘   퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다.   분할 정복 알고리즘(Divide and Conquer)의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법● 퀵정렬 : 정렬 방법 정리  분할 정복(Divide Conquer)을 활용한 순환호출로 구현한다. ○  퀵정렬 과정    1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.    2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고      피벗보다 큰 요소들은 모두 피..

● 병합 정렬: Divide and Conquer (DAC)  - '존 폰 노이만(John von Neumann)’이 제안한 정렬 방법. - 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복(DAC) 알고리즘의 하나이다.※ 분할정복 (Divide And Conquer) 란?   - 1단계 분할(Divide) : 해결이 용이한 단계까지 문제를 분할해 나간다.   - 2단계 정복(Conquer) : 해결이 용이한 수준까지 분할된 문제를 해결한다.   - 3단계 결합(Combine) : 분할해서 해결한 결과를 결합하여 마무리한다. 병합정렬은 아래와 같이 구현한다.  ○ Divide    별도의 정렬을 진행하지 않아도 될 수준까지 분할을 진행한다.   1/2 씩 분할하며,  분할은 가장..