초코레

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816..

브루트-포스법을 개선한 KMP법보다 효율이 더 우수하기 때문에 실제로 문자열 검색에 널리 사용되는 알고리즘 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정한다. 패턴에 존재할 수 있는 모든 문자의 옮길 크기를 계산하고 저장해야 하기 때문에 건너뛰기 표의 요소 개수는 Character.MAX_VALUE + 1 이다. Character.MAX_VALUE는 Char형으로 나타낼 수 있는 문자 수 패턴의 문자열의 길이가 n일 때 옮길 크기는 다음과 같다. 패턴에 들어 있지 않은 문자를 만난 경우 패턴을 옮길 크기는 n 이다. (현재 검사하고 있는 텍스트의 문자 위치로부터 다음에 검사할 패턴의 마지막 문자 위치가 n만큼 떨어질 수 있도록..

브루트-포스법을 개선한 알고리즘으로 검사했던 위치 결과를 버리지 않고 이를 효율적으로 활용하는 알고리즘 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구함으로써 패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높인다. 몇 번째 문자부터 다시 검색할지에 대한 값을 미리 표로 만들어 둔다. 건너뛰기 표를 작성할 때는 패턴 안에서 중복되는 문자의 나열을 먼저 찾아나기 위해 패턴끼리 겹쳐놓고 생각하여 만든다. KMP법은 브루트-포스법보다는 복잡하고 Boyer-Moore법과는 성능이 같거나 좋지 않기 때문에 실제 프로그램에서는 거의 사용되지 않는다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31..

문자열 검색의 기초 알고리즘 브루트-포스법은 선형 검색을 확장한 알고리즘으로 단순법, 소박법이라고도 한다. 이미 검사를 진행한 위치를 기억하지 못하므로 효율은 좋지 않다. 다른 문자를 만나면 패턴에서 문자를 검사했던 위치 결과를 버리고 다음 텍스트의 위치로 1칸 이동한 다음 다시 패턴의 첫 번째 문자부터 검사한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 //브루트-포스법으로 문자열을 검색 //여러 개라면 가장 앞쪽에 있는 인덱스 반환 static int bfMatch(String txt, String pat) { int pt = 0; //텍스..

배열로 집합 만들기 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165..

요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘 if문 대신 for문만을 사용해 정렬할 수 있는 매우 아름다운 알고리즘 데이터의 비교, 교환 작업이 필요 없어 매우 빠르다. 단일 for문만을 사용하여 재귀 호출, 이중 for문이 없어 아주 효율적인 알고리즘 하지만 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 사용할 수 있다. 각 단계(for문)에서 배열 요소를 건너뛰지 않고 순서대로 스캔하기 때문에 같은 값에 대해서 순서가 바뀌는 일이 없어 안정적인 알고리즘이다. 도수 정렬 알고리즘은 도수분포표 작성, 누석도수분포표 작성, 목적 배열 만들기, 배열 복사의 4단계로 이루어진다. 10점 만점의 테스트에서 학생 9명의 점수에 대해 도수 정렬하기 도수분포표 ..

힙(heap)을 사용하여 정렬하는 알고리즘 힙은 '부모 값 >= 자식 값' 라는 조건을 만족하는 완전이진트리이다. 완전이진트리의 특징은 '완전이진' 상태이다. 완전 : 부모는 자식을 왼쪽부터 추가하는 모양을 유지한다는 뜻 이진 : 부모가 가질 수 있는 자식의 개수는 최대 2개라는 뜻 따라서 힙의 가장 위쪽에 있는 루트가 가장 큰 값이 된다. 힙은 형제의 대소 관계는 정해져 있기 않기 때문에 부분순서트리(partial ordered tree)라고도 한다. 힙의 요소를 배열에 저장하면 부모와 자식의 인덱스 관계는 다음과 같다. 부모는 a[(i - 1) / 2] 왼쪽 자식은 a[i * 2 + 1] 오른쪽 자식은 a[i * 2 + 2] 힙 정렬은 '가장 큰 값이 루트에 위치'한다는 특징을 이용하는 정렬 알고리즘..

배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘 정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘 먼저 배열을 앞부분과 뒷부분으로 나눈다. 이때 앞뒤의 각 배열을 정렬할 때는 다시 병합 정렬을 적용한다. 나눈 두 배열을 각각 정렬하고 병합하면 배열 모두를 정렬할 수 있다. 배열의 요소 개수가 2개 이상인 경우에 배열의 앞부분과 뒷부분을 각각 병합 정렬로 정렬하고 병합한다. java.util.Arrays 패키지에서 배열을 정렬하는 클래스 메서드인 sort를 제공한다. 기본 자료형의 배열을 정렬하는 sort 메서드는 퀵 정렬 알고리즘을 개선한 것으로 안정적이진 않다. 클래스 객체 배열을 정렬하는 sort 메서드는 병합 정렬을 개선한..

가장 빠른 정렬 알고리즘 중 하나 피벗을 기준으로 피벗보다 작은 요소로 이루어진 부분과 피벗보다 큰 요소 이루어진 부분으로 나눔을 반복함으로써 최종적으로 정렬 된다. 즉 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹의 개수가 1이 되면 정렬을 마친다. 서로 이웃하지 않고 멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지 않은 알고리즘이다. 시간 복잡도는 O(n log n) 정렬할 배열의 초깃값이나 피벗의 선택 방법에 따라 시간 복잡도가 증가하는 경우도 있다. 최악의 시간 복잡도는 O(n^2)이 된다. 배열을 두 그룹으로 나누기 피벗 이하의 요소를 배열 왼쪽으로 옮긴다. a[pl] >= x 가 성립할 때까지 pl을 오른쪽으로 스캔 피벗 이상의 요소를 배열 오른쪽으로 옮긴다. a[pr] pr..

단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법 퀵 정렬이 고안되기 전까지 가장 빠른 알고리즘으로 알려져 있었다. 4칸만큼 떨어진 요소를 모아 그룹을 4개로 나누어 정렬하는 방법을 '4-정렬'이라고 한다. 4-정렬 → 2-정렬 → 1-정렬을 적용하면 정렬을 마치게 된다. 4-정렬, 2-정렬로 조금이라고 정렬에 가까운 상태로 만든 다음 마지막으로 단순 삽입 정렬을 수행하여 정렬을 마친다. 여러 개의 그룹으로 나누어 정렬하는 이유는 단순 삽입 정렬의 장점은 살리고 단점은 보완하기 위해서이다. 셸 정렬 과정에서 수행하는 각각의 정..