search

[백준] 2343 - 기타 레슨 (자바 Java)

[Silver I] 기타 레슨 - 2343 문제 링크 성능 요약 메모리: 89916 KB, 시간: 732 ms 분류 이분 탐색(binary_search), 매개 변수 탐색(parametric_search) 문제 설명 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 ..

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

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