본문 바로가기

Algorithms/개념 익히기3

유클리드 호제법 개념과 구현 알고리즘 문제를 풀다가 최대공약수를 어떻게 구해야 하지? 하다가 유클리드 호제법을 간단히 정리해보았습니다. 유클리드 호제법 유클리드 호제법은 두 수가 있을 때 최대공약수를 구할 수 있는 알고리즘입니다. 알고리즘은 간단합니다. a, b의 최대공약수를 구해야 할 때, a > b인 경우 n = a%b으로 지정합니다. 만약 n = 0 이라면 b가 최대공약수가 됩니다. 만약 n이 0이 아닐 경우, b와 n에 대해 동일한 연산을 반복하면 최대공약수를 찾을 수 있습니다. 유클리드 호제법 구현하기(Python) 유클리드 호제법은 재귀나 반복문을 통해서 간단히 구현할 수 있습니다. 재귀로 구현 def findGCD(a, b): if a < b: a, b = b, a rem = a % b if rem == 0: retur.. 2021. 11. 17.
삽입정렬(Insertion sort) 개념 이해하고 구현하기 정렬 시리즈를 다시 공부하면서 공부했던 내용을 간단히 블로그에 업로드해보려 합니다. 이번 글에서는 삽입정렬을 다루어 보도록 하겠습니다. 삽입정렬(Insertion sort)은 무엇인가? 삽입정렬은 간단히 말하자면 i 번째 요소를 정렬하기 위해 i-1번째부터 1번째까지 순차적으로 탐색하면서 자신에게 맞는 위치를 찾는 방식으로 정렬하는 알고리즘입니다. 두 번째 수부터 시작해 같은 작업을 반복하기 때문에 i번째 수를 삽입하고자 할 때는 첫 번째부터 i-1번째는 수가 정렬된 상태이므로 정렬된 상태에 i번째 수를 넣는 위치를 찾을 수 있는 것이죠. 삽입정렬을 구현하는 간단한 수도코드를 작성해보았습니다. for i in (2번째 요소부터 끝까지) j = i -1로 시작해 현재 삽입하고자 하는 값보다 작거나 같은 값.. 2021. 11. 2.
Binary Search, Parametric Search 이해하기 알고리즘 문제를 풀다 보면 효율성 기준을 통과하지 못하는 경우가 종종 있습니다 🥲 이번 글에서는 이럴 때 떠올릴 수 있는 알고리즘 중 하나인 이분탐색(Binary Search)과 이와 유사한 Parametric search의 개념을 살펴보고, Parametric Search를 어떻게 풀 수 있을지 알아보도록 하겠습니다. Binary Search (이분탐색) 이분탐색은 쉽게 말하면 배열을 반씩 잘라가며 원하는 값을 탐색해나가는 알고리즘입니다. 중간에 위치한 값과 비교하고 바로 절반을 버리려면 배열이 정렬된 상태여야겠죠? 즉, 이진탐색은 정렬된 배열에서 값을 찾아내는 검색 알고리즘이라고 할 수 있겠습니다. 예를 들어 [1,2,3,4,5,6,7,8,9]라는 배열이 있을 때 9가 어디에 위치했는지 알고 싶다면 .. 2021. 7. 3.

티스토리툴바