Programming/알고리즘16 Boyer Moore 법 단순하게 처음부터 끝까지 일일히 검사하는 브루트 포스법은 간단하지만 비효율적이라는 단점을 가지고있습니다. 이런 단점을 보완하고자 고안된 방식이 Boyer Moore법이며, 이 방식이 많이 사용되고 있습니다. 1. Boyer Moore 법 Boyer Moore 법은 브루트 포스와는 다르게 키의 마지막 글자부터 처음 글자 순서로 검사를 진행합니다. 검사를 진행하다가 불일치하는 부분이있으면 그 부분만을 집중적으로 검사하고 그 칸수만큼 훌쩍 뛰어넘어 검사를 진행해서 검색 속도를 향상시키는 방법입니다. 다음 배열에서 'ABC'를 검색하려고 합니다. 우선 문자열에 키를 맞춘후 제일 마지막 요소 부터 검사를 시작합니다. 검사를 시작하는데 불일치하는 지점이 발견되었습니다. 그러면 불일치 지점에 대해 키를 이동시켜 비교.. 2021. 11. 12. 브루트-포스 법 선형 검색과 이진 검색 두가지 방식은 대게 숫자와 같은 요소들을 검색하는데 편리한 방식이었습니다. 하지만 문자열에 이 방식들을 대입하기엔 쉽지 않습니다. 그래서 문자열들을 검색할 수 있는 몇 가지 방법들을 소개하려고 합니다. 1. 브루트 포스 법 브루트 포스 법(Brute Force Method)는 마치 선형 검색처럼 모든 요소에 대해 일일히 비교하는 방식입니다. 한 문자열에서 'aba'라는 문자열을 찾으려고 한다면 다음과 같이 나타낼 수 있습니다. 우선 문자열의 인덱스 0과 키의 인덱스 0을 비교합니다. 이때 그 요소가 일치했다면 그 다음 인덱스와 키의 두번째 인덱스를 비교합니다. 비교한 결과가 일치했다면 3번째 인덱스를 다시 검사하겠지만 여기서는 불일치했기 때문에 키를 이동시켜 원 문자열 배열의 1번.. 2021. 11. 10. 이진 검색 선형 검색은 자료를 처음부터 끝까지 순회하며 검색하기 때문에 자료가 클수록 나쁜 효율을 보여줍니다. 그래서 이 단점을 보완하고자 등장한 방식이 이진 검색입니다. 1. 이진 검색 이진 검색(Binary Search)은 일반적으로 선형 검색보다 더 빠른 검색 속도를 보여주는 알고리즘입니다. 단 한가지 전제 조건이 있다면, 이진 검색은 정렬된 컬렉션에 대해서만 검색이 가능하다는 점 입니다. 그래서 정렬 방식에 따라 선형 검색보다 오래걸릴 수도 있습니다. 다음과 같은 배열에서 이진검색을 통해서 26을 검색해보겠습니다. 우선 배열 인덱스의 중앙에 있는 값을 검사합니다. 이 값이 우리가 찾는 키 값 26과 일치하는지 확인합니다. 만약 키 값보다 작다면 배열의 앞 부분을, 키 값보다 크다면 배열의 뒷 부분을 생각하지.. 2021. 11. 10. 선형 검색 이번에 소개할 알고리즘은 검색입니다. 주어진 컬렉션 내부를 정렬하는 것 만큼 유용하고 많이 쓰이는게 컬렉션 내부에서 요소를 찾아내는 것 입니다. 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. 이전 1 2 3 다음 300x250
