검색

[알고리즘] 완전 검색, Baby-Gin (자바/Java)

목차 완전 검색 가능한 모든 경우의 수를 확인하는 기법 Brute-force, Generate-and-Test 기법 경우의 수가 작을 때 유용함 정확성은 높지만, 경우의 수가 커진다면 비효율적일 수 있음 Baby-Gin 임의의 숫자 6개를 뽑아 run과 triplet으로만 구성된 카드 = baby-gin run: 3장의 카드가 연속적인 번호를 갖는 경우 triplet: 3장의 카드가 동일한 번호를 갖는 경우 모든 경우의 수 구하기 (순열) 6개의 숫자는 6!개의 순열이 가능 먼저 6개 숫자에서 가능한 세 자리 순열(6P3)을 구하여 run 또는 triplet에 해당하는지 검사 true를 반환한다면, 다시 남은 3가지 수 중에서 순열을 구하여 run 또는 triplet에 해당하는지 검사 for (int i..

[알고리즘] 검색 Search - 순차 검색, 이진 검색 (자바/Java)

목차 검색 자료에서 원하는 항목을 찾는 작업 종류 순차 검색 이진 검색 인덱싱 순차 검색 일렬로 되어 있는 자료를 순서대로 검색 장점: 배열, 연결 리스트 등에서 유용 단점: 자료의 크기가 큰 경우에 비효율적 정렬X 첫 번째 원소부터 마지막 원소까지 키 값이 같은 원소가 있는지 검색 동일한 원소를 찾으면 검색을 중지하고 그 인덱스를 반환 마지막 원소까지 키를 찾지 못하면 실패 시간 복잡도: O(n) 정렬O 첫 번째 원소부터 키 값보다 큰 원소가 나올 때까지 검색 동일한 원소를 찾으면 반환, 키 값보다 큰 원소가 나왔는데 찾지 못하면 검색 실패 시간 복잡도: O(n) 그러나 정렬되지 않았을 때보다 평균 비교 횟수가 절반으로 줄어든다. 이진 검색 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위..