서티대비 집중학습 후기
Source
Google Keep/서티대비 집중학습 후기.md
Summary
5일간의 알고리즘/시스템 구현 대비 학습 기록으로, 각 일차별 문제(스트리밍 서버, IoT DB, 검색엔진, 호텔 예약, 텍스트 에디터)에서의 구현 삽질 포인트와 해결 과정을 정리함. 주요 교훈으로는 힙의 시간 복잡도 한계(O(n log n))로 인한 BST/링크드 리스트 선택, IoT DB의 공간 복잡도 최적화(무손실 압축/역해시 테이블), 해시 테이블 충돌 처리(오픈 어드레싱/체이닝), 그리고 문제 이해의 중요성(텍스트 에디터의 줄 삽입 구조) 등이 포함됨.
Key Points
- 스트리밍 서버: 힙 기반 구현은 heapify 과정으로 인해 O(n log n) 시간 복잡도 발생하여 시간 초과 위험이 있어, Binary Search Tree 또는 링크드 리스트 기반 구현이 필요함.
- IoT DB: 시간 및 공간 복잡도 모두 고려해야 함. 값으로 키를 검색할 때 선형 검색 대신 역해시 테이블을 사용하되, 메모리 부족을 해결하기 위해 ASCII 코드의 7비트 특성을 이용한 무손실 압축 기법 적용 필요.
- 검색엔진: 해시 테이블 사용 시 중복 처리를 위해 오픈 어드레싱과 체이닝 방식을 숙지해야 함.
- 호텔 예약 시스템: 전역 힙 사용 대신 위치별 리스트와 선형 검색을 조합하고 결과값만 힙으로 처리하는 방식이 더 적합함. 범위 값 처리 시 경계 조건 주의.
- 텍스트 에디터: 줄 삽입 기능이 요구될 경우 라인 단위 링크드 리스트 구조가 필요하며, 문제 요구사항을 정확히 이해하는 것이 중요함.
- 일반적 교훈: 연산 1억 회는 약 1 초로 간주하는 것이 좋음. 메모리 인덱싱 시 컨벤션 확립 및 매크로 활용 검토.