알고리즘10 알고리즘) 선형 탐색 (Linear Search) in Swift 머리말 정렬이 되지 않은 배열을 효율적으로 탐색하려면? 하버드 대학교 CS50 수업에서 알고리즘에 대한 수업을 할 때 나오는 내용 중 하나가 바로 선형 탐색이다. 이에 대한 블로그는 여기에 정리해 두었다. 본문 이를 한번 Swift 언어의 코드로 구현해 보자. 코드 타입을 명확히 하지 않고 제네릭으로 추상화하였고, 구현에서 이를 실체화하기 위해 메타 타입을 이용했다. import Foundation func linearSearch( array: [T], value: T, type: T.Type ) -> T? { for element in array { if element == value { // 등호를 쓰기 위해 Equatable 프로토콜 채택 return element } } return nil } f.. 2024. 3. 31. 퀵 정렬(Quick Sort) in Python 목차 머리말 들어가기 전에 합병 정렬에 이어 분할 정복 알고리즘을 이용한 두 번째 정렬인 퀵 정렬에 대해 알아 보자. 퀵 정렬(Quick Sort) 정의 기준 데이터(피벗, pivot)를 설정하여, 그 기준보다 큰 데이터와 작은 데이터를 구분하는 '분할(partition) 알고리즘'을 재귀적으로(recursively) 반복하여 다시 조합해 나가는 정렬 알고리즘 배열 중에서 임의의 데이터를 '피벗(pivot)'이라 불리는 기준 데이터로 설정한다. 피벗을 기준으로 자기보다 크기가 작은 그룹과 큰 그룹을 최대한 분할한 이후 조합하면서 정렬을 해 나가는 알고리즘이다. 동작 과정 Sorting quicksort animation - Quicksort - Wikipedia 동작 과정 분할 정복 알고리즘에 맞게 세 .. 2023. 4. 4. 재귀) 유클리드 호제법과 최대공약수, 최소공배수 목차 머리말 들어가기 전에 유클리드 호제법을 배워 보고 재귀적으로(recursively) 구현한 것과 반복적으로(iteratively) 구현한 것을 서로 비교해 보자. 재귀(Recursion)에 대한 개념이 궁금하다면? 본문 유클리드 호제법(Euclidean Algorithm) 이름도 어려운 호제법은 무엇일까? '호제(互除)'는 '서로 덜어낸다'는 뜻이다. '무엇을 덜어내냐' 하면 바로 '큰 수를 작은 수로 나눈 나머지'를 구하는 것이다. 또다시 기존의 작은 수는 큰 수가 되고, 구한 나머지는 작은 수가 되어 또 다른 나머지를 구한다. Mathematical Treasure: First Euclid's Elements in Greek and Latin | Mathematical Association of.. 2023. 4. 2. 합병 정렬(병합 정렬; Merge Sort) in Python 지난 글에 분할 정복 알고리즘의 개념에 대해 알아 보았다. 이제는 실제로 이를 적용한 합병 정렬에 대해 알아 보자. [알고리즘] 분할 정복(Divide and Conquer) 개요 정렬 알고리즘에서 버블 정렬과 선택 정렬, 삽입 정렬에 대해 알아 보았다 이 세 가지 정렬 알고리즘은 코드가 직관적이긴 하지만 $n$(데이터의 크기)에 대한 이중 for 문으로 되어 있기에 굉장히 andy-archive.tistory.com 📌 정의 합병 정렬(merge sort)은 주어진 배열을 더 이상 쪼갤 수 없을 때까지 재귀적으로 데이터 크기의 절반으로 계속 나누고, 다시 정렬을 통합하여 정렬하는 알고리즘이다. 📌 동작 과정 합병 정렬은 요소가 하나가 될 때까지 계속해서 절반으로 나눈 뒤, 조합해 가면서 정렬해 나간다... 2023. 3. 30. 분할 정복 알고리즘(Divide and Conquer Algorithm) 목차 머리말 들어가기 전에 정렬 알고리즘 저번에 포스팅한 정렬 알고리즘에서 버블 정렬과 선택 정렬, 삽입 정렬에 대해 알아 보았다. 효율성 이 세 가지 정렬 알고리즘은 코드가 직관적이긴 하지만 데이터 크기 n에 대한 이중 for 문으로 되어 있기에 굉장히 비효율적이다. 분할 정복 알고리즘 이들의 시간복잡도는 $O(n^2)$이다. 보다 효율적인 정렬 알고리즘을 배우기 위해 분할 정복(Divide and Conquer)에 대해 알아 보자. 배우기 전 알아야 할 개념 재귀 그렇다면 위의 3단계는 어떻게 구현할 수 있을까? 분할과 정복, 통합은 재귀적으로(recursively) 하는 것이다. 따라서 재귀 알고리즘에 대해 먼저 알아야 분할 정복 알고리즘을 제대로 알 수 있다. 분할 정복 알고리즘(Divide an.. 2023. 3. 29. [알고리즘] 재귀(Recursion)와 콜 스택(Call Stack) 알고리즘 이론에서 기본이며, 분할 정복이나 백트래킹 같은 여러 알고리즘의 기반을 맡고 있는 재귀(recursion)는 무엇일까? 이에 대해 자세히 알아 보자. 📌 정의 In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many.. 2023. 3. 14. [알고리즘] 삽입 정렬(Insertion Sort) in Python 카드 놀이를 할 때 나도 모르게 카드를 정렬한 적이 있는가? 그때 어떠한 방식으로 정렬을 했는지 생각해 보자. 정렬 알고리즘에서 세 번째로 배워 볼 것은 바로 삽입 정렬이다. 삽입 정렬이 어떻게 동작하는지 알아 보고 실제 코드로 구현해 보자. 📌 정의 Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in .. 2023. 3. 13. [알고리즘] 선택 정렬(Selection Sort) in Python 정렬 알고리즘에서 두 번째로 배워 볼 것은 선택 정렬이다. 선택 정렬은 어떻게 동작하는지 알아 보고 실제 코드로 구현해 보자. 📌 정의 Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list. 선택 정렬은 리스트(배열)의 정렬되지 않은 부분에서 가장 작은(혹은 가장 큰) 요소를 반복적으로 선택하여, 리스트의 정렬된 부분으로 옮기는 방식의 간단하고 효율적인 정렬 알고리즘이다. Sele.. 2023. 3. 12. [알고리즘] 버블 정렬(Bubble Sort) in Python 정렬 알고리즘 중에서 가장 직관적이고 간단한 버블 정렬에 대해 알아보자. 그리고 버블 정렬이 어떻게 동작하는지 배우고 이를 코드로 구현해 보자. 📌 정의 Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. 가라앉는 정렬이라고도 불리는 버블(거품) 정렬은, 입력된 리스트의 요소 별로, 현재 요소를 바로 다음의 요소와 비교를 하는데, 필요에 따라 서.. 2023. 3. 10. [알고리즘] 정렬 알고리즘(Sorting Algorithms) 개요 📌 서문 알고리즘 강의에서, 대개 정렬 알고리즘을 가장 먼저 배운다. 정렬 알고리즘은 무엇이고, 왜 공부하는 것이며 강의 초반에 배우는 것일까? 📌 정의 In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. 컴퓨터 과학에서, 정렬 알고리즘은 하나의 리스트(배열)의 요소들을 일정한 순서에 맞게 분류하는 것을 의미한다. Sorting algorithm - Wikipedia 📌 학습 목적 1. 정렬 알고리즘은 주어진 데이터를 처리하는 알고리즘의 기초가 되는 문제 중 하나이다. 일상에서 주어진 데이터의 집합을 어떠한 규칙으로 나열하는 것(알파벳순, 내림차순, 오름차순 등)을 쉽게 접할 .. 2023. 3. 9. 이전 1 다음 반응형
