반응형 분류 전체보기131 Hash (해시) Hash 임의의 크기를 가진 데이터(key)를 고정된 데이터의 크기(value)로 변환시키는 것 시간복잡도: O(1) // 해시 값 자체를 index로 사용, 검색과 저장이 빠른 자료구조 Direct Addressing key-value 쌍의 데이터를 배열에 저장할 때, key값을 직접적으로 배열의 인덱스로 사용하는 방법 key값의 최대 크기만큼의 공간을 사용. 크기는 매우 큰데 저장하고자 하는 데이터가 작다면 공간 낭비의 위험 ex) key값이 3인 데이터가 있다면, 이를 index가 3인 위치에 저장하고 데이터 연결 / 삭제는 NULL 값 넣기 Hash Table key값을 테이블에 저장할 때 "함수"를 이용해서 계산을 수행한 후, 그 결과값을 index로 사용하여 저장 해시 함수(Hash Funct.. 2022. 3. 14. 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 ··· 30 31 32 33 다음 반응형