반응형 알고리즘42 Binary Search (이진 탐색) Binary Search 데이터가 정렬되어 있는 경우에서, 탐색 범위를 두 부분으로 나누어 가면서 원하는 원소를 찾는 방법 시간복잡도: O(log N) // 모두 탐색을 하는 경우에는 O(N) 이진 탐색의 과정 1. 탐색 범위를 설정 (start, end지점) 2. 탐색 지점(mid) 설정 후 찾는 값(key)와 비교한다. mid = (start+end) /2 3. mid == key 일 때의 해당 값을 찾는다. mid > key 이면, [start, mid-1] 로 탐색 범위 수정 mid end가 될 때까지, 2~3 과정을 반복 이진 탐색 코드 1. 반복문을 사용한 방법 int BinarySearch(int arr[], i.. 2022. 3. 13. [해시] 완주하지 못한 선수 1. 문제요약 - 마라톤 선수들의 이름이 담긴 participant, 완주한 completion - 완주하지 못한 선수의 이름 return 2. 풀이 - participant에는 있지만 completion에는 없는 이름이 완주하지 못한 선수 - 두 vector를 이름순으로 정렬하고, 0번째 index부터 이름을 검사한다. participant과 completion에 이름이 다른 순간이 participant에만 이름이 있는 것이므로, 그 이름을 return 한다. 3. 코드 #include #include #include using namespace std; string solution(vector participant, vector completion) { string answer = ""; sort(p.. 2022. 3. 13. 이전 1 ··· 8 9 10 11 다음 반응형