Kiki Devlog

1. Binary Search - 진행방법 배열을 반 잘라서 가운데 원소와 내가 찾는 x를 비교. 만약 "x = 배열 가운데 원소" 라면, 원하는 값 찾았으므로 알고리즘 종료. "x > 배열 가운데 원소" 라면 오른쪽 배열에서 다시 찾기(다시 오른쪽 배열 반 잘라서 가운데 원소와 비교) "x

Map : binary tree 사용 (red-black tree) 내부 데이터 정렬됨 평균 탐색 시간복잡도는 O(log n) 삽입 / 삭제 O(log n) key 중복 허용 X Hash Map (unordered_map 사용을 권장) : hash table 사용 내부 데이터 비정렬 평균 탐색시간복잡도는 O(1) 삽입 / 삭제는 O (1) unordered_map : 평균 탐색 시간복잡도는 O(1) hash table 사용 내부 데이터 비정렬 key 중복 허용 X #include 을 선언해야 함 데이터가 많을 시 map보다 성능 좋음 (유사한 key가 많으면 성능 떨어짐 주의/ 해쉬충돌)