자료구조 선택의 기준

접근 패턴부터 확인하기

자료구조를 고르기 전에 어떤 연산이 자주 실행되는지 정리합니다. 순회가 많은지, 특정 키를 찾는지, 앞뒤에서 원소를 넣고 빼는지에 따라 선택이 달라집니다.

필요	검토할 구조	함께 확인할 비용
연속 순회	배열, 벡터	재할당, 삽입 위치
키로 조회	해시 테이블	해시 계산, 메모리
순서대로 처리	큐	최대 크기, 저장 방식

측정할 때의 조건

입력 개수와 실제 접근 순서를 맞춘 상태에서 비교합니다. 작은 입력에서의 결과만으로 더 큰 데이터의 성능을 확정하지 않습니다.

정리

시간 복잡도와 함께 메모리 배치, 객체 크기, 구현의 단순함도 살펴봅니다.