깊이 우선 탐색(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
합병 정렬, 병합 정렬(Merge Sort) 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬하는 방식 실행 시간의 상한은 O(n log n) 실행 시간의 하한도 역시 Ω(n log n) 병합 정렬(합병 정렬)은 전화번호부의 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 것과 공통점이 있다. 그리고 이 과정은 재귀적으로 구현되기 때문에 재귀를 학습하면 더 이해하기 쉽다. 병합 정렬의 실행 시간의 상한은 O(n log n)이다. 숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문이다. 실행 시간의 하한도 역시 Ω(n log n)이다. 숫자들이 이미 정렬되었는지 여부에 관계없이 나누고 병..
