Hashing 도입을 통한 시간 복잡도 O(n²)에서 O(n)으로의 최적화 전략

Context

배열 기반 데이터 처리 시 단순 순회 및 중복 탐색으로 인한 성능 저하 발생. 특히 데이터 규모 증가에 따라 Brute force 방식의 시간 복잡도가 기하급수적으로 증가하는 한계 존재.

Technical Solution

• Hashing 구조를 활용한 Key-Value 매핑으로 요소 탐색 시간을 상수로 단축
• Two-pointer 및 Sliding Window 기법을 적용한 효율적인 배열 Traversal 설계
• Complement 계산 방식을 통한 단일 루프 내 Pair 탐색 로직 구현
• Prefix Sum 최적화로 부분 배열 합계 계산의 시간 복잡도 감소
• unordered_map 및 unordered_set을 통한 고속 Lookup 및 중복 제거 메커니즘 구축

Impact

• 시간 복잡도: O(n²) → O(n)으로 개선
• 공간 복잡도: O(n) 추가 할당을 통한 탐색 성능 극대화

Key Takeaway

데이터의 빈도수 측정이나 빠른 검색이 필요한 경우 공간 복잡도를 희생하여 시간 복잡도를 최적화하는 Trade-off 전략의 중요성 확인.