Algorithm

처음으로 소개드릴 알고리즘은 정렬 중에서도 버블 정렬입니다. 버블이라는 어원은 컵에 액체를 따르면 액체 보다 가벼운 공기 방울(버블)이 컵위로 떠오른다는 점에서 착안하여 버블 정렬이라는 이름이 붙게 되었습니다.버블 정렬은 인접한 두 요소의 대소 관계를 비교해서 정렬합니

단순 선택 정렬은 컬렉션의 가장 작은 요소부터 정렬을 시작해 알맞은 위치로 옮기며 정렬하는 알고리즘입니다. 단순 선택 정렬의 시간복잡도는 O(n^2)입니다.다음과 같은 배열을 단순 선택 정렬로 정렬해보겠습니다.우선 배열에서 가장 작은 요소를 선택합니다. 그리고 배열의

단순 삽입 정렬은 선택한 요소를 선택한 요소 앞쪽의 알맞은 위치에 삽입하는 정렬입니다. 단순 삽입 정렬의 시간 복잡도도 O(n^2)로 단순 선택 정렬, 버블 정렬과 같습니다.선택 정렬과 마찬가지로 정렬된 부분과 정렬되지 않은 부분으로 나누어서 이용합니다. 자세한 삽입

셸 정렬은 정렬할 배열의 요소를 몇 개의 그룹으로 나누어 각 그룹으로 단순 삽입 정렬을 하고 그룹을 합쳐나가며 정렬을 하는 방식입니다. 그룹으로 나눌 때 h칸 만큼 떨어진 요소끼리 모아 h개의 그룹으로 나누어 정렬방식을 h-정렬 이라고 합니다. 셸 정렬의 시간 복잡도는

퀵 정렬은 가장 많이 사용되고 있는 가장 빠른 정렬 방식입니다. 정렬 대상을 특정 기준으로 두 개의 그룹을 나누고 다시 나눈 그룹에 대해 또 그룹을 나누고를 반복하여 정렬하는 방식입니다. 이때 특정 기준으로 설정하는 기준점을 피벗(Pivot)이라고 합니다. 퀵 정렬의

병합 정렬은 배열을 두개로 나누고 나눈 배열끼리 비교해서 작은 값을 먼저 넣으며 정렬하는 방식입니다. 이 과정에 한 번으로만 쪼개면 제대로된 정렬이 될리 없으므로 재귀를 이용해서 나눈 배열을 또 나누고 나누어 각 요소가 1개일 경우까지 쪼갠다음 비교해서 작은것 부터 순

이번에 소개할 정렬방식은 힙(Heap) 정렬입니다. 힙이란 보통 부모 노드가 자식 노드보다 큰 조건을 가진 완전 이진 트리를 의미합니다. 힙에 대한 설명은 이 포스트를 참조해주세요.힙 정렬은 전체 트리, 서브 트리에서 가장 큰 값이 부모 노드로 위치하는 트리 구조를 이

카운팅 정렬은 도수 정렬, 계수 정렬 등의 다양한 이름으로 불리웁니다. 여기에서는 카운팅 정렬이라는 용어를 사용하도록 하겠습니다.카운팅 정렬은 정렬 시 대소 관계를 판단하지 않고 정렬하는 정렬 방법입니다. 카운팅 정렬은 시간복잡도가 O(n)으로 빠른 알고리즘이지만, 정

기수 정렬은 요소의 대소 관계를 파악하지 않고 정렬하는 방식입니다. 기수 정렬의 시간 복잡도는 O(kn)으로 여기서 k는 요소의 최대 자릿수를 의미합니다. 즉, 정렬하려는 요소가 1의 자리라면 O(n)수준의 아주 빠른 시간 복잡도를 가질 것 이고, 1000, 10000

유클리드 호제법(Euclidean Algorithm)은 두 정수의 최대공약수를 구하는 수학 알고리즘입니다. 두 정수의 최대공약수는 두 정수에서 큰 값을 작은 값으로 나누었을 때, 나머지가 0으로 나누어 떨어지는 값이 최대공약수입니다. 하지만, 보통 한 번의 계산으로는

하노이 탑은 아래 사진과 같이 세개의 기둥에 원반을 꽂는 장난감입니다. 하지만 모든 기둥에는 반드시 큰 원반이 작은 원반보다 아래 와야한다는 규칙이 있습니다.초기 상태는 첫 번째 기둥에 모든 원반이 차례대로 쌓여있으며 이 원반들을 세 번째 기둥에 차례대로 쌓아 놓는 것

검색 알고리즘은 컬렉션에서 원하는 요소를 찾아내는 알고리즘입니다. 검색은 보통 조건을 n개 주고 그 조건에 해당하는 요소를 반환하게됩니다. 그 조건에 부합하는 요소를 키(key)라고 하며, 키와 일치하는 값이 컬렉션 내부에 있으면 검색이 성공한 것이고, 일치하는 값이

선형 검색은 자료를 처음부터 끝까지 순회하며 검색하기 때문에 자료가 클수록 나쁜 효율을 보여줍니다. 그래서 이 단점을 보완하고자 등장한 방식이 이진 검색입니다. 이진 검색 이진 검색(Binary Search)은 일반적으로 선형 검색보다 더 빠른 검색 속도를 보여주는 알

선형 검색과 이진 검색 두가지 방식은 대게 숫자와 같은 요소들을 검색하는데 편리한 방식이었습니다. 하지만 문자열에 이 방식들을 대입하기엔 쉽지 않습니다. 그래서 문자열들을 검색할 수 있는 몇 가지 방법들을 소개하려고 합니다.브루트-포스 법(Brute-Force Meth

단순하게 처음부터 끝까지 일일히 검사하는 브루트-포스 법은 간단하지만 비효율적이라는 단점을 가지고있습니다. 이런 단점을 보완하고자 고안된 방식이 Boyer Moore 법이며, 이 방식이 많이 사용되고 있습니다.Boyer Moore 법은 브루트-포스와는 다르게 키의 마지