CS12 [알고리즘] 이분탐색 (Binary Search) 이분 탐색이란 ? 정렬된 배열에서 원하는 값의 존재 여부 및 위치를 찾는 알고리즘으로 탐색할 때마다 검사 범위가 절반으로 줄어듭니다. 시간 복잡도 : O(log N) 이분 탐색 과정 1. 검사 범위에서 중간 값(mid)를 선택해 찾고자 하는 값(target)이 같은지 확인 2. 찾고자 하는 값이라면 해당 값 반환 3. 찾고자 하는 값보다 작다면 (mid target), high = mid - 1 5. 1 ~ 4번을 (low = M) {// 집에 가져가려하는 길이 M보다 큰 경우 ans = mid; low = mid + 1;// 덜 가져가야하므로 더 크게 } else {// 반대의 경우 high = mid - 1;// .. 2022. 9. 7. [자료구조][C++] Map Map이란 ? Key와 Value로 이루어진 자료구조로 Key와 Value가 하나의 쌍으로 연결되어 Key를 통해 Value에 접근할 수 있도록 만들어졌습니다. Map의 특징 Key의 중복을 허용하지 않아야 한다. 순서가 유지되지 않는다. Value의 중복은 허용된다. Map의 종류 HashMap 중복을 허용하지 않는다. 순서를 보장하지 않는다. TreeMap 이진검색트리의 형태로 Key와 Value의 쌍으로 이루어진 데이터를 저장한다. 순서를 보장하며 저장하므로 빠른 검색이 가능하다. 저장할 때 정렬을 하기 때문에 시간이 오래 걸린다. LinkedHashMap 데이터 입력한 순서대로 쌓아 저장한다. 배열, 리스트처럼 인덱스 접근에 용이하다. Map 기본 형태 map m; Map 사용방법 1. Map 선.. 2022. 9. 6. 이전 1 2 3 다음