자바스크립트120 선형 검색 이번에 소개할 알고리즘은 검색입니다. 주어진 컬렉션 내부를 정렬하는 것 만큼 유용하고 많이 쓰이는게 컬렉션 내부에서 요소를 찾아내는 것 입니다. 1. 검색 알고리즘 검색 알고리즘은 컬렉션에서 원하는 요소를 찾아내는 알고리즘입니다. 검색은 보통 조건을 n개 주고 그 조건에 해당하는 요소를 반환하게됩니다. 그 조건에 부합하는 요소를 키(key)라고 하며, 키와 일치하는 값이 컬렉션 내부에 있으면 검색이 성공한 것이고, 일치하는 값이 없다면 검색에 실패했다고 볼 수 있습니다. 2. 선형 검색 선형 검색은 가장 기본적이고 간단한 알고리즘입니다. 심지어는 프로그래밍 입문해서 지금까지도 숨쉬듯이 사용했을 수도 있습니다. 다만 이름 선형 검색이라는 것은 이번에 처음 알게된 사실일 수도 있습니다. 선형 검색은 요소가 .. 2021. 11. 9. 하노이 탑 이번에 소개할 알고리즘은 하이노 탑입니다. 재귀를 이용한 알고리즘이며, 워낙 유명해서 재귀를 설명한다고 하면 이 하노이 탑을 예시로 드는 경우가 많습니다. 1. 하노이 탑 하노이 탑은 아래 사진과 같이 세개의 기둥에 원반을 꽂는 장난감입니다. 하지만 모든 기둥에는 반드시 큰 원반이 작은 원반보다 아래 와야한다는 규칙이 있습니다. 초기 상태는 첫 번째 기둥에 모든 원반이 차례대로 쌓여있으며 이 원반들을 세 번째 기둥에 차례대로 쌓아 놓는 것이 하노이 탑의 목표입니다. 2. 하노이 탑의 작동 다음과 같은 3개 원반을 1번 기둥에서 3번 기둥으로 옮기려고 합니다. 가장 작은 빨간 원반을 3번 기둥으로 보냅니다. 그리고 중간 크기인 주황 원반을 2번 기둥에 보냅니다. 이때, 빨간 원반을 2번에 보내고, 주황 원.. 2021. 11. 8. 재귀 알고리즘 - 유클리드 호제법 정렬에 이어 처음으로 소개할 알고리즘은 재귀의 유클리드 호제법입니다. 1. 유클리드 호제법 유클리드 호제법(Euclidean Algorithm)은 두 정수의 최대공약수를 구하는 수학 알고리즘입니다. 두 정수의 최대공약수는 두 정수에서 큰 값을 작은 값으로 나누었을 때, 나머지가 0으로 나누어 떨어지는 값이 최대공약수입니다. 하지만, 보통 한 번의 계산으로는 나누어 떨어지지 않죠. 그래서 큰 값을 다시, 이전에 나온 나머지값으로 나누어 계산합니다. 이 과정을 반복하면 두 정수의 최대공약수를 구할 수 있습니다. 예) 30, 12 30/12 = 2 ... 6 30/6 = 5 ...0 따라서, 두 수의 최대 공약수는 5 최대공약수 구하는 과정을 보니 어디를 재귀적으로 처리해야할지 감이 잡히시나요? 2. 유클리드.. 2021. 11. 8. 기수 정렬 이번에 소개할 기수 정렬(Radix sort)도 지난번에 다룬 카운팅 정렬 처럼 두 요소의 대소관계 파악없이 진행하는 정렬법 입니다. 그리고 제가 기본적으로 소개할 기본적인 정렬방식의 마지막이기도 합니다. 1. 기수 정렬 기수 정렬은 요소의 대소 관계를 파악하지 않고 정렬하는 방식입니다. 기수 정렬의 시간 복잡도는 O(kn)으로 여기서 k는 요소의 최대 자릿수를 의미합니다. 즉, 정렬하려는 요소가 1의 자리라면 O(n)수준의 아주 빠른 시간 복잡도를 가질 것 이고, 1000, 10000의 자리 이런식으로 늘어날수록 시간 소모가 늘어납니다. 2. 기수 정렬의 동작 원리 기수 정렬은 각 요소를 분해해서 한자리 씩 비교합니다. 숫자라면 일의 자리는 일의 자리끼리, 문자열이라면 마지막 글자 끼리 비교합니다. 그.. 2021. 11. 7. 카운팅 정렬 카운팅 정렬은 도수 정렬, 계수 정렬 등 다양한 이름으로 불리우는 방식입니다. 책마다, 사람마다 다른 이름을 사용하고 있지만 모두 같은 정렬을 말하고 있으며 이 블로그에서는 카운팅 정렬이라고 부를 예정입니다. 1. 카운팅 정렬 카운팅 정렬은 정렬 시 대소 관계를 판단하지 않고 정렬하는 정렬법입니다. 카운팅 정렬을 시간복잡도가 O(n)으로 빠른 알고리즘이지만, 정렬하려는 대상에 따라서 시간 복잡도가 매우 커질 수 있습니다. 정확히는 시간 복잡도가 O(n+k)이기 때문입니다. 여기서 k는 컬렉션 내부의 최대 숫자입니다. 그래서 k가 무지막지하게 커질 경우 시간도 오래걸리게 됩니다. 이렇게 되는 이유는 잠시 후 카운팅 정렬의 방식을 공부해보면 알 수 있습니다. 그리고 그동안 배운 몇 가지의 정렬법이 모두 두 .. 2021. 11. 6. 병합 정렬 이번에 소개할 정렬 방식은 병합 정렬입니다. 1. 병합 정렬 병합 정렬은 배열을 두개로 나누고 나눈 배열끼리 비교해서 작은 값을 먼저 넣으며 정렬하는 방식입니다. 이 과정에 한 번으로만 쪼개면 제대로된 정렬이 될리 없으므로 재귀를 이용해서 나눈 배열을 또 나누고 나누어 각 요소가 1개일 경우까지 쪼갠다음 비교해서 작은것 부터 순차적으로 넣으면됩니다. 병합 정렬의 시간 복잡도는 O(n log n)입니다. 다음과 같은 배열이 있으면, 두개의 배열로 나눕니다. 두 개의 배열로 나눈 다음에 나눈 배열의 첫 번째 요소끼리 비교해서 작은 요소를 먼저 넣고 인덱스를 1증가시켜 큰 요소를 넣으면 됩니다. 이대로 넣으면 [3, 9, 2, 4, 5, 7, 1, 8]로 정렬이 안되겠죠? 이를 위해 4개로 나눈것에서 다시 오.. 2021. 11. 3. 이전 1 ··· 4 5 6 7 8 9 10 ··· 20 다음 300x250
