자료구조 & 알고리즘13 알고리즘 - 힙 정렬(Heap Sort) / 힙 정렬 구현 우선순위 큐란?우선순위 큐는 정렬된 배열과 비슷한 리스트로 추상 데이터 타입의 한 예이다. 우선순위 큐 앞에서만 데이터에 접근하고 삭제하는 데 데이터를 삽입할 때는 데이터를 특정 순서대로 정렬시킨다. 우선순위 큐를 간단하게 구현하기 위해서는 아래와 같은 제약을 가진 정렬된 배열을 이용하면 된다. 데이터를 삽입할 때 항상 순서를 유지한다.데이터는 배열의 끝에서만 삭제한다. 배열 기반 우선순위 큐는 삭제 효율성은 O(1)이고 삽입 효율성은 O(N)이다. 이러한 우선순위 큐에서 힙은 효율적으로 사용되는 자료구조이다. 힙(Heap)이란? 힙은 완전 이진 트리 (Complete Binary Tree)의 일종으로, 부모 노드와 자식 노드 간에 특정한 조건을 만족하는 자료구조를 말한다. 여기서 완전 이진 트리란 부모.. 2024. 8. 5. 알고리즘 - 퀵 정렬 (Quick Sort) / 퀵 정렬 구현 분할이란?퀵 정렬은 분할이라는 개념에 기반한다. 배열은 분할한다는 의미는 배열로부터 임의의 수를 가져와 피벗보다 작은 모든 수는 피벗의 왼쪽에 피벗보다 큰 모든 수는 피벗의 오른쪽에 두는 것이다. 여기서 피벗(pivot)은 배열로부터 가져온 임의의 수를 의미한다. 📌 분할 알고리즘 순서* 가장 오른쪽에 있는 수를 피벗으로 정했을 때.왼쪽 포인터를 한 셀씩 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다.오른쪽 포인터를 한 셀씩 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다.오른쪽 포인터가 멈춘 경우왼쪽 포인터가 오른쪽 포인터에 도달했으면 4단계로 넘어간다.그렇지 않으면 왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 값을 교환한 후 1-3단계를 반복한다.왼쪽 포인터가 현재 가리.. 2024. 8. 2. 알고리즘 - 머지 정렬(Merge sort) / 머지 정렬 구현 머지 정렬?머지는 두 개의 정렬된 배열을 하나의 큰 정렬된 배열로 합치는 작업을 의미한다. 배열을 정렬할 때 배열을 반으로 나누어 각각의 절반에 대해서 재귀적으로 정렬을 수행하고 정렬된 결과를 다시 재귀적으로 병합하는 것을 머지 정렬이라고 한다. 📌 하향식 머지 정렬하향식 머지 정렬은 배열이 주어졌을 때, 배열을 더 이상 나눌 수 없을 때까지 나누고 배열이 더 이상 나누어질 수 없을 때 머지 정렬을 실행한다. 📌 실행 시간 개선 방법머지 정렬은 재귀적으로 동작하기 때문에 나누어진 배열의 크기가 작다면 삽입 정렬 알고리즘을 사용하는 게 좋다.배열이 이미 정렬되었는지 확인하고 이미 정렬된 상태로 입력되는 배열에 대한 중복된 정렬을 생략하면 이미 정렬된 부분 배열에 대한 실행 시간이 선형으로 줄어든다.원본.. 2024. 8. 2. 알고리즘 - 셀 정렬(shell sort) / 셀 정렬 구현 셀 정렬?🔑 keyword : gap, 마지막엔 삽입 정렬 셀 정렬은 ‘Donald L. Shell’이라는 사람이 제안한 방법으로 삽입정렬을 보완한 알고리즘이다. 삽입 정렬은 크기가 크고 정렬되지 않은 배열을 처리하는데 느리다. 그러나 셀 정렬은 서로 멀리 떨어진 항목 간에도 교환이 일어날 수 있다. 그리고 삽입 정렬이 빠르게 처리할 수 있도록 부분적으로 정렬된 배열을 만든다. 📌 셀 정렬 동작 순서매 h번째 한목들 간에 삽입 정렬을 수행한다.부분적으로 정렬된 배열을 h-정렬 되었다고 한다.큰 h값에 대해 h-정렬을 해서 서로 멀리 떨어진 배열 항목들을 이동시킨다.h값을 정해진 만큼 줄여나가서 1이 될 때까지 줄이면서 위의 과정을 반복한다. 📌 h-정렬h-정렬된 배열은 서로 교차하며 존재하는 h개의.. 2024. 8. 2. 알고리즘 - 삽입 정렬 (insertion sort) / 삽입 정렬 구현 삽입 정렬?항목을 삽입할 공간을 만들기 위해 삽입할 항목보다 큰 항목들을 전부 오른쪽으로 밀어서 이동시키고 확보된 빈 공간에 항목을 삽입하는 정렬 알고리즘이다. 📌 삽입 정렬의 동작 순서첫 패스스루에서 임시로 두 번째 셀(index = 1)의 값을 삭제하고 이 값을 저장해 둔다.인덱스 1에 값이 없이 때문에 공백이 생긴다.이후 각 패스스루마다 다음 인덱스의 값을 삭제한다.공백 왼쪽에 있는 각 값을 가져와 저장해둔 값과 비교한다.공백 왼쪽에 있는 값이 저장해둔 값보다 크면 그 값을 오른쪽으로 시프트한다.값을 오른쪽으로 시프트 해서 공백이 왼쪽으로 옮겨진다.임시로 삭제한 값보다 작은 값을 만나거나 배열의 왼쪽 끝에 도달하면 시프트 단계가 끝난다.임시로 제거한 값을 현재 공백에 삽입한다.1-3단계가 하나의.. 2024. 8. 2. 알고리즘 - 선택 정렬(selection sort) / 선택 정렬 구현 선택 정렬?선택 정렬은 반복적으로 남은 배열 안에서 가장 작은 항목을 선택하는 정렬 알고리즘이다. 📌 선택 정렬의 동작 순서배열 안에서 가장 작은 항목을 찾는다.그다음으로 가장 작은 항목을 찾아 두 번째 항목과 교환한다.모든 배열이 정렬될 때까지 1-2단계를 반복한다. 📌 선택 정렬의 효율성선택 정렬은 비교와 교환, 두 가지 단계를 포함하고 있다.비교 : 각 패스스루 내에서 각 값을 현재까지 찾은 최솟값과 비교한다.교환 : 최솟값을 올바른 위치에 있는 수와 교환한다. 배열의 크기가 N일 때, (N+1) + (N-2) + (N+3) + ... + 1번의 비교 연산이 필요하다. 교환은 한 번의 패스당 최대 한 번이 일어난다. 등차수열의 합 공식에 의하면 N(N-1)/2 이므로 O(N^2)이 된다. 📌 .. 2024. 8. 2. 이전 1 2 3 다음
