본문 바로가기

전체보기

 (451)
[427] 힙 정렬(Heap Sort) 1. 힙 정렬 개념힙 정렬은 영국의 컴퓨터 과학자 J. W. J. Williams가 1964년 고안한 정렬 알고리즘입니다.힙이라는 자료구조를 만들어 원소를 차례대로 정렬해 나가는 과정을 거칩니다. 힙은 완전이진트리를 이용하여 최대값이나 최소값을 쉽게 찾아내는 자료구조입니다.최대값을 쉽게 찾는 힙을 최대 힙, 최소값을 쉽게 찾는 힙을 최소 힙이라고 부릅니다.이런 특성 때문에 일반적으로 힙을 사용하여 (크기를 우선순위로 가지는) 우선순위 큐를 구현합니다. 힙 정렬은 두 단계를 거칩니다.먼저 모든 원소를 최대 힙으로 만듭니다.(힙 생성 단계, \(O(n)\))그 다음 최대 값을 하나 꺼내고, 나머지 부분을 힙으로 재구성하는 과정을 반복합니다.(정렬 단계, \(O(n\log{n})\)) 힙 정렬은 완전이진트리 ..
[426] 병합 정렬(Merge Sort) 1. 병합 정렬 개념존 폰 노이만이 1945년에 개발한 정렬 알고리즘입니다.분할 정복(Divide and Conquer) 기법을 사용한 알고리즘으로 시간 복잡도가 \(O(n\log{n})\)입니다. 주어진 배열을 n개의 부분 배열로 분할하여 재귀적으로 정렬하는 방식으로, 일반적으로 2개의 부분 배열로 나눕니다.이후 나누어진 부분 배열을 다시 합하는 과정에서 정렬된 배열을 임시로 저장할 메모리 공간이 필요하여 공간 복잡도는 \(O(n)\)입니다. 주어진 배열을 나누는 횟수는 (\(\log_2{n}\)) 번 일어나고, 병합될 때 정렬하는 과정에서 \(O(n)\)의 시간이 걸리므로 시간 복잡도는 항상 \(O(n\log{n})\)이 됩니다. https://ko.wikipedia.org/wiki/합병_정렬 합병 ..
[425] 퀵 정렬(Quick Sort) 1. 퀵 정렬 개념영국의 컴퓨터 과학자 토니 호어(Charles Antony Richard Hoare)가 1959년 고안한 정렬 알고리즘입니다.효율적인 알고리즘으로 빠르게 널리 사용되기 시작하였으며, 다양한 프로그래밍 언어와 시스템에서 기본 정렬 알고리즘으로 채택되었습니다. 퀵 정렬은 분할 정복(Divide and Conquer) 기법을 사용하여 배열을 정렬합니다.배열에서 한 원소를 선택합니다. 선택된 원소는 피벗(Pivot)이라고 부릅니다.피벗을 기준으로 피벗보다 작은 원소들은 왼쪽으로, 큰 원소들은 오른쪽으로 이동시킵니다.이 과정은 투포인터를 사용하여 해결할 수 있습니다.먼저 피벗을 제일 오른쪽 원소와 바꿉니다.(피벗을 제일 오른쪽에 위치시킵니다.)투포인터(i, j)를 첫 번째 자리에 위치시킵니다.한..
[424] 삽입 정렬(Insertion Sort) 1. 삽입 정렬 개념이미 정렬되어 있는 배열에 새로운 수를 추가하는 것은 아주 간단합니다.이런 방법을 바탕으로 범위를 늘려가며, 다음 원소를 이미 정렬된 범위 안에 삽입하는 방식으로 정렬합니다.마치 손 안의 카드를 정렬하는 방법과 유사합니다.2. 삽입 정렬 예제삽입 위치를 찾기 위해 정렬되어 있는 부분을 탐색하는 과정을 위 그림을 통해 볼 수 있습니다.이 과정을 이분 탐색으로 \(O(\log{n})\)의 시간에 빠르게 찾을 수 있을 것 같습니다.하지만 선택한 원소를 해당 위치에 삽입하기 위해서는 뒤쪽의 모든 원소를 한 자리씩 옮겨야하므로 결국 \(O(n)\)만큼의 시간이 소요되어 의미가 없어집니다.3. 삽입 정렬 코드nums = [5, 3, 4, 1, 2]def insertion_sort(nums): ..
[423] 선택 정렬(Selection Sort) 1. 선택 정렬 개념기준이 되는 원소를 맨 처음 원소로 정합니다.기준 원소로부터 맨 마지막 원소까지 탐색하여 최소값을 가지는 원소를 찾습니다.기준 원소가 최소값이 아닐 경우 해당 원소와 자리를 바꿉니다.(제자리 정렬)이 과정을 거치면 배열에서 가장 작은 값이 첫 번째 자리에 위치하게 됩니다.따라서 기준이 되는 원소를 순차적으로 바꿔가며 위 과정을 반복합니다.2. 선택 정렬 예제3. 선택 정렬 코드nums = [5, 3, 4, 1, 2]def selection_sort(nums): for i in range(len(nums)-1): index_min = i for j in range(i+1, len(nums)): if nums[index_min] > num..
[422] 버블 정렬(Bubble Sort) 1. 버블 정렬 개념맨 앞에서부터 맨 뒤까지 인접한 두 원소를 차례대로 비교합니다.비교한 결과 더 큰 원소가 앞에 있을 경우, 비교한 두 원소의 자리를 바꿔줍니다.(제자리 정렬)이 과정을 한 번 마치면 배열의 맨 뒤에는 가장 큰 원소가 위치합니다.따라서 이 과정을 범위를 한 칸씩 줄여가며 계속해서 반복합니다.2. 버블 정렬 예제3. 버블 정렬 코드nums = [5, 3, 4, 1, 2]def bubble_sort(nums): for i in range(1, len(nums)): for j in range(len(nums)-i): if nums[j] > nums[j+1]: nums[j], nums[j+1] = nums[j+1], nums[j]..
[421] 이분 탐색(Binary Search) 조건 분기 쉽게 이해하기(Lower Bound, Upper Bound) 1. 이분 탐색이란?정렬되어 있는 범위에서 원하는 값을 찾기 위해 반씩 줄여가며 탐색하는 알고리즘입니다.정렬만 되어 있다면, 선형적으로 다 탐색할 필요 없이 범위가 반씩 줄어들기 때문에 시간복잡도가 \(O(\log{n})\)으로 상당히 효율적인 알고리즘입니다.영어로 Binary Search입니다.Binary라는 단어가 한국어로 번역되면서 이진 탐색, 이진 검색 등으로 사용됩니다.하지만 탐색 과정을 살펴보면 범위를 반으로 쪼개며 진행되기 때문에 이분 탐색이라는 용어가 더 직관적인 것 같습니다. https://ko.wikipedia.org/wiki/이진_검색_알고리즘 이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 이진 검색 알고리즘(binary search algor..
[420] 파이썬 큐(Queue) 구현하기 1. 큐(Queue)큐는 자료구조 중 하나로 선입선출(First In First Out, FIFO) 하는 추상적인 개념을 말합니다.보통 큐를 연결리스트를 이용하여 구현합니다.https://ko.wikipedia.org/wiki/큐_(자료_구조) 큐 (자료 구조) - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬ko.wikipedia.org 2. 큐 구현하기가. 노드 class 만들기연결리스트를 사용하기 때문에 먼저 노드 class를 만듭니다.노드 객체는 값을 저장하는 data와 다음 연결되는 노드를 저..

티스토리툴바