초코레

검색과 데이터의 추가와 삭제도 효율적으로 수행할 수 있는 방법 키 값을 해시 값으로 만드는 과정을 해시 함수(hash function)라고 한다. 해시 값(hash value)은 데이터에 접근하기 위한 인덱스 해시 값이 인덱스가 되도록 원래의 키 값을 저장한 배열이 해시 테이블(hash table) 해시 테이블의 각 요소를 버킷(bucket)이라고 한다. 키 값과 해시 값은 반드시 1 대 1로 대응되지 않는다. 저장할 버킷이 중복되는 현상을 충돌(collision)이라고 한다. 해시 함수는 가능하면 해시 값이 치우치지 않도록 고르게 분포된 값을 만들어야 한다. 충돌이 발생할 경우 체인법과 오픈 주소법으로 대처할 수 있다. 체인법(chaining) 같은 해시 값을 같는 데이터들을 사슬(chain) 모양으로..

트리란? 데이터 사이의 계층 관계를 나타내는 자료구조 모든 노드가 가지는 자식 노드 수가 n 이하인 트리를 n진 트리라고 한다. 모든 노드의 자식 수가 2개 이하인 경우는 특별히 이진 트리라고 한다. 형제 노드의 순서를 따지면 순서 트리(ordered tree), 따지지 않으면 무순서 트리(unordered tree)라고 한다. 순서 트리의 노드를 스캔하는 방법은 너비 우선 탐색과 깊이 우선 탐색이 있다. 너비 우선 탐색 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 검색하고 한 레벨에서의 검색이 끝나면 다음 레벨로 내려가는 탐색 방법 깊이 우선 탐색 리프까지 내려가면서 검색하는 것은 우선순위로 하는 탐색 방법 언제 노드를 방문할지에 따라 세 종류로 구분한다. 전위 순회(Preorder) : 노드 방문 ..

원형 리스트 : 연결 리스트의 꼬리 노드가 머리 노드를 가리키는 자료구조. 고리 모양으로 나열된 데이터를 저장할 때 알맞은 자료구조이다. 이중 연결 리스트 : 각 노드가 다음 노드에 대한 포인터와 앞쪽 노드에 대한 포인터를 가지고 있는 자료구조. 양방향 리스트라고도 한다. 원형 이중 연결 리스트는 이 두가지의 개념이 합해진 구조이다. 원형 이중 연결 리스트에서는 노드의 삽입과 삭제 처리를 원활하게 하도록 리스트의 머리에 계속 존재하는 더미 노드를 가진다. 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 42 43 44 45 46 47 48 49 50 ..

포인터로 만든 연결 리스트는 노드의 삽입과 삭제를 데이터 이동 없이 수행한다는 특징이 있지만 삽입과 삭제를 수행할 때마다 노드용 객체를 위한 메모리 영역을 만들고 해제하는 과정이 필요했다. 만약 데이터 수가 크게 바뀌지 않고 데이터 수의 최댓값을 미리 알 수 있다고 한다면 배열을 사용해 연결 리스트를 만들 수 있다. 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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 7..

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명의 점수에 대해 도수 정렬하기 도수분포표 ..