자료구조/알고리즘 신입 성능 최적화 면접

이 코드의 시간복잡도는 O(N×M)입니다. 사용자 수(N)와 상품 수(M)를 각각 곱한 만큼 연산이 발생하므로, 1000×1000 = 100만 번의 연산이 실행됩니다. 중첩 반복문은 데이터가 증가할수록 연산 횟수가 기하급수적으로 늘어나기 때문에 성능 병목이 발생합니다. 이를 개선하려면 해시맵이나 인덱싱을 활용해 내부 반복문을 제거하고 O(N+M)으로 최적화할 수 있습니다.

해시맵(또는 딕셔너리, 객체)을 사용하면 조회 성능을 개선할 수 있습니다. 배열은 특정 ID를 찾기 위해 처음부터 순차 탐색해야 하므로 O(N)의 시간복잡도를 가집니다. 반면 해시맵은 키를 해시 함수로 변환해 직접 접근하므로 평균 O(1)의 조회 성능을 제공합니다. 사용자 ID를 키로, 사용자 정보를 값으로 저장하면 빠른 조회가 가능합니다.

캐싱 대상은 조회 빈도가 높고 변경 빈도가 낮은 데이터를 선택해야 합니다. 상품 정보처럼 자주 읽히지만 업데이트가 드문 데이터가 적합합니다. 주의할 점은 캐시 만료 시간(TTL)을 적절히 설정해 오래된 데이터가 제공되지 않도록 해야 하며, 원본 데이터가 변경될 때 캐시를 무효화(invalidation)하는 전략이 필요합니다. 또한 메모리 사용량을 고려해 캐시 크기를 제한하고 LRU 같은 교체 정책을 적용해야 합니다.

중복 제거 시 Set 자료구조를 사용하면 O(N)의 추가 공간이 필요합니다. 공간복잡도를 줄이려면 원본 배열을 정렬한 후 인접한 중복 요소를 제거하는 방식을 사용할 수 있습니다. 정렬은 O(1) 추가 공간으로 가능하며(in-place 정렬), 중복 제거도 투 포인터 기법으로 O(1) 공간에서 처리할 수 있습니다. 다만 시간복잡도는 O(N log N)으로 증가하므로 시간과 공간의 트레이드오프를 고려해야 합니다.

병합 정렬의 병합 과정을 활용하면 O(N+M)의 선형 시간에 합칠 수 있습니다. 두 배열의 시작 지점에 포인터를 두고, 각 원소를 비교하며 작은 값을 결과 배열에 추가하는 방식입니다. 현재 방식은 합친 후 정렬하므로 O((N+M) log(N+M))의 시간이 걸리지만, 투 포인터 방식은 각 원소를 한 번씩만 확인하므로 훨씬 효율적입니다. 이미 정렬된 상태라는 특성을 활용하는 것이 핵심입니다.

OFFSET과 LIMIT을 사용한 페이지네이션으로 필요한 데이터만 조회해야 합니다. 전체 데이터를 조회하는 것은 불필요한 메모리와 네트워크 비용을 발생시킵니다. 예를 들어 20개씩 보여준다면 LIMIT 20, OFFSET 페이지번호×20으로 해당 페이지 데이터만 가져옵니다. 더 나아가 커서 기반 페이지네이션을 사용하면 OFFSET의 성능 문제도 해결할 수 있습니다. 인덱스가 제대로 설정되어 있어야 빠른 조회가 가능합니다.

먼저 프로파일링 도구나 로깅으로 각 구간의 실행 시간을 측정해 병목 지점을 파악합니다. 데이터베이스 쿼리, 반복문, 외부 API 호출 등 시간이 오래 걸리는 부분을 찾습니다. 병목을 발견하면 해당 부분의 시간복잡도와 공간복잡도를 분석하고, 알고리즘 변경, 자료구조 교체, 캐싱 도입 등의 개선 방안을 적용합니다. 개선 후에는 다시 측정해 실제로 성능이 향상되었는지 검증하고, 새로운 병목이 없는지 확인합니다. 추측이 아닌 측정 기반으로 접근하는 것이 핵심입니다.