CS 기초·알고리즘
탐색 알고리즘 선택
연락처 1만 명 목록에서 이름으로 검색하는 기능을 만듭니다. 순차 검색과 '정렬 후 이진 탐색'은 성능이 어떻게 다르고, 실제 앱에서는 어떤 구조를 쓰겠습니까?
면접관은 이 답을 어떻게 들을까요? 넘어갈지, 더 물어볼지, 떨어뜨릴지 알려 주고, 걸리는 문장은 콕 집어 줘요. 점수는 그대로예요.
짧은 답 보기
순차 O(n), 이진 탐색 O(log n)이지만 정렬 비용 O(n log n)이 먼저 든다. 정확 일치는 Dictionary, 접두어는 정렬 배열의 lower bound, 부분 일치는 로컬 DB 인덱스나 사전 계산한 토큰 역색인이 낫다.
이어서 보기
CS 기초·알고리즘주관식딥다이브
오프라인에서도 동작하는 검색어 자동완성을 만들어야 합니다. 후보 단어 50만 개, 입력마다 상위 10개를 16ms 안에 돌려줘야 합니다. 자료구조를 어떻게…
#trie #search
CS 기초·알고리즘주관식기초
해시맵을 직접 구현한다면 어떻게 만들겠습니까?
#dictionary
CS 기초·알고리즘주관식심화
메모리 이미지 캐시를 LRU로 직접 구현해야 합니다. 어떤 자료구조로 get/put을 O(1)로 만들 수 있나요?
#dictionary
CS 기초·알고리즘객관식입문
다음 Swift 컬렉션 연산 중 평균 시간 복잡도가 O(1)인 것을 모두 고르세요.
#dictionary