처음부터 차근차근

자료구조 Heap 완전 이진 트리의 일종으로, 우선순위 큐를 위하여 만들어진 자료구조입니다. 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조입니다. 자세한 내용은 해당 Post를 참조해주세요. [자료구조] Heap Heap Heap tree or Heap이라고 불린다. 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 완전 이진트리를 말한다. 우선순위 Queue를 위하여 만들어진 자료구조이다. 힙은 일종의 반 정 hangju95.tistory.com Heapsort 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 과정 설명 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)..

MergeSort 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나 이다. 분할 정복(divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 과정 설명 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬..

QuickSort 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속합니다. 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법입니다. 합병 정렬(merge sort)과 달리 퀵 정렬은 list를 비균등하게 분할합니다. 분할 정복(divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략입니다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현합니다. 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 퀵 정렬..

이번 시간에는 정렬방법 중 가장 구현하기 쉬운 방법인 버블 정렬, 선택 정렬, 삽입 정렬을 알아보겠습니다. BubbleSort 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환합니다. 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네번째를, ... 이런 식으로 (마지막 - 1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬합니다. 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두번째 자료까지는 정렬에서 제외됩니다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하..

Backtracking이란?? 해(답)을 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가서 다시 해를 찾아가는 기법을 의미한다. 즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 주로 DFS 등 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤, 그 이전으로 돌아가서 다시 다른 경우를 탐색하게 구현할 수 있다. 백트래킹 기법의 유망성 판단 어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking..

너비 우선 탐색(BFS)이란?? 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법을 의미한다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다., 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. DFS의 경우 BFS보다 좀 더 복잡하다. BFS의 특징 시작 노드에서 시작해서 거리에 따라 단계별로 탐색하기 때문에 직관적이지 않은 면이 있다. 재귀적으로 동작하지 않는다. 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 그렇지 않으면 무한 루프에 빠질 위험이 있다. BFS는 방문한 노드를 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다. 즉, ..

깊이 우선 탐색(DFS)이란?? 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 의미한다. 탐색하는 방법은 아래 그림과 같다. 미로와 같이 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것을 의미한다. DFS의 경우 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. 깊이 우선 탐색의 특징 자기 자신을 호출하는 순환 알고리즘 형태를 가지고 있다. 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다. 이 알고리즘..