재귀8 퀵 정렬(Quick Sort) in Python 목차 머리말 들어가기 전에 합병 정렬에 이어 분할 정복 알고리즘을 이용한 두 번째 정렬인 퀵 정렬에 대해 알아 보자. 퀵 정렬(Quick Sort) 정의 기준 데이터(피벗, pivot)를 설정하여, 그 기준보다 큰 데이터와 작은 데이터를 구분하는 '분할(partition) 알고리즘'을 재귀적으로(recursively) 반복하여 다시 조합해 나가는 정렬 알고리즘 배열 중에서 임의의 데이터를 '피벗(pivot)'이라 불리는 기준 데이터로 설정한다. 피벗을 기준으로 자기보다 크기가 작은 그룹과 큰 그룹을 최대한 분할한 이후 조합하면서 정렬을 해 나가는 알고리즘이다. 동작 과정 Sorting quicksort animation - Quicksort - Wikipedia 동작 과정 분할 정복 알고리즘에 맞게 세 .. 2023. 4. 4. [백준] (Swift) 1850번: 최대공약수 📌 문제 1850번: 최대공약수 📌 풀이 처음에는 입력값이 실제 정수가 아닌 1의 개수라서 이를 정수로 변환하는 함수를 만들었다. 하지만 그렇게 하면 입력값이 클 경우 시간이 너무 오래 걸리는 경우가 생겼다. 몇 번 실제로 값을 계속 넣어 보니 겉으로만 1의 개수이지, 1의 개수들끼리 최대공약수를 구하여 이를 정수로 변환만 하면 된다. 이를 눈치채지 못하면 계속 돌고 돌아 멘붕에 빠질 수 있다. 최대공약수를 구하는데 사용한 유클리드 호제법(Euclidean Algorithm)은 아래의 링크에서 자세히 설명해 두었다. [재귀] 유클리드 호제법과 최대공약수, 최소공배수 [재귀] 유클리드 호제법과 최대공약수, 최소공배수 유클리드 호제법을 배워 보고 재귀적으로(recursively) 구현한 것과 반복적으로(it.. 2023. 4. 3. 재귀) 유클리드 호제법과 최대공약수, 최소공배수 목차 머리말 들어가기 전에 유클리드 호제법을 배워 보고 재귀적으로(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. 프로그래머스) 분수의 덧셈 (Swift) 📌 문제 코딩테스트 연습 - 분수의 덧셈 | 프로그래머스 📌 접근 방식 두 분수를 더하여 기약분수로 만드는 알고리즘은 크게 세 단계로 나누어진다. 통분: 서로 다른 분모를 같게 만든다. 덧셈: 분모를 같게 하기 위하여 곱해진 분자를 서로 더한다. 약분: 분모, 분자를 더 이상 나눌 수 없을 때까지 나눈다. → 최대공약수 이용 여기서 통분과 덧셈은 단순한 사칙연산으로 해결이 가능하지만, 약분에서는 최대공약수를 구하여 한번에 나누는 게 핵심이다. 최대공약수을 구하는 방법은 유클리드 호제법을 이용했는데, 이에 대한 설명은 아래에 자세히 다루었으니 참고 하자. [재귀] 유클리드 호제법과 최대공약수, 최소공배수 유클리드 호제법을 배워 보고 재귀적으로(recursively) 구현한 것과 반복적으로(iterative.. 2023. 3. 27. [백준] (Swift) 10872번: 팩토리얼 (재귀 vs 반복) 📌 문제 10872번: 팩토리얼 📌 풀이 개요 N에서 1까지 차례로 곱하는 팩토리얼은 크게 2가지 경우로 풀어 볼 수 있다. 재귀적으로(recursively) 푸는 방식이거나, 반복적으로(iteratively) 푸는 방식이다. 📌 풀이 1: 재귀함수 재귀에 대한 개념은 아래의 링크 페이지에 정리해 두었다. [알고리즘] 재귀(Recursion)와 콜 스택(Call Stack) 알고리즘 이론에서 기본이며, 분할 정복이나 백트래킹 같은 여러 알고리즘의 기반을 맡고 있는 재귀(recursion)는 무엇일까? 이에 대해 자세히 알아 보자. 인형 안에, 조금 더 작지만 모양이 같은 andy-archive.tistory.com 재귀함수로 푸는 방식은 아래와 같다. 팩토리얼에 대한 함수를 정의해야 한다. → $\mat.. 2023. 3. 18. [알고리즘] 재귀(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. 이전 1 다음 반응형
