너비 우선 탐색(Breadth First Search, BFS) 맹목적 탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. 재귀적으로 동작하지 않는다. 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다. (즉, 선입선출(FIFO) 원칙으로 탐색) 시간복잡도 인접 리스트로 표현된 그래프 : O(N+E) 인접 행렬로 표현된 그래프 : O(N^2) 구현 방법 자료 구조 큐(Queue)를 이용 활용 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을..
깊이 우선 탐색(Depth First Search, DFS) 맹목적 탐색 방법의 하나로 탐색 트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표 노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식 자기 자신을 호출하는 순환 알고리즘의 형태 시간복잡도 (N : 노드, E : 간선) 인접 리스트로 표현된 그래프 : O(N+E) 인접 행렬로 표현된 그래프 : O(N^2) 깊이 제한과 백트래킹(backtracking) 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)을 사용한다. 깊이 제한에 도달할 때까지 목표 노드가 발견되지 않..
힙(Heap) 완전 이진 트리의 일종으로, 우선순위 큐를 위하여 만들어진 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 우선순위 큐 우선순위의 개념을 큐에 도입한 자료구조 데이터들이 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나감 이용 : 시뮬레이션 시스템, 네트워크 트래픽 제어, 운영 체제에서의 작업 스케쥴링, 수치 해석적 계산 우선순위 큐는 배열, 연결리스트, 힙으로 구현 가능 힙의 종류 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 key(부모 노드) >= key(자식 노드) 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 key(부모 노드)..
힙 정렬(Heap Sort) 힙 트리(트리구조에서 자식노드보다 부모노드가 큰 상태)를 이용해서 정렬하는 방법 힙(Heap) : 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전이진트리 완전이진트리(Complete binary tree) : 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨 시간복잡도 : O(n log n) 임시 저장을 위한 메모리 사용이 필요 없어서 병합 정렬의 단점을 보완한 정렬방법 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법 (내림차순 정렬 : 최대 힙 구성 / 오름차순 정렬 : 최소 힙 구성) 알고리즘 n개의 노드에 대한 완전 이진트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다. 최대 힙을 구성한다. 최대..
퀵 정렬(Quick Sort) 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 분할 정복(divide and conquer) 방법을 통해 리스트 정렬 시간 복잡도 : O(n log n) *최악의 경우 : O(n^2) 분할 정복(divide and conquer) 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 분할 정복 방법은 대개 순환 호출을 이용하여 구현 장점 속도가 빠르다. 추가 메모리 공간을 필요로 하지 않는다. 단점 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행 시간이 더 많이 걸린다. 알고리즘 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot)이라고 한다. 피벗 앞에는 피벗보다 값이 작은 모든..
선택 정렬(Selection Sort) 제자리 정렬(in-place sorting) 알고리즘의 하나 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬방법 해당 순서에 원소를 넣을 위치는 이미 정해져잇고, 어떤 원소를 넣을지 선택하는 알고리즘 과정 주어진 배열 중에서 최솟값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다.(pass) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 하나의 원소만 남을때까지 위의 과정을 반복한다. 장점 자료 이동 횟수가 미리 결정된다. 단점 안정성을 만족하지 않는다. 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다. References
