Kwangmin Kim - 알고리즘: 정렬 문제 모음

1 문제 1: K번째수

배열 array와 [i, j, k]를 원소로 가진 2차원 배열 commands가 주어진다. 각 command에 대해 다음 과정을 수행한다:

제한사항: - array의 길이는 1 이상 100 이하이다. - commands의 길이는 1 이상 50 이하이다.

입출력 예시: - array: [1, 5, 2, 6, 3, 7, 4] - commands: [[2, 5, 3], [4, 4, 1], [1, 7, 3]] - 결과: [5, 6, 3]

def solution(array, commands):
    """
    DS 트랙 관점: 가독성 높은 리스트 컴프리헨션 활용
    """
    return [sorted(array[i-1:j])[k-1] for i, j, k in commands]

시간 복잡도: \(O(M \cdot N \log N)\) — \(M\) 은 commands의 길이, \(N\) 은 array의 길이이다. 각 쿼리마다 정렬을 수행한다.
공간 복잡도: \(O(M + N)\) — 결과 리스트(\(M\))와 정렬을 위한 임시 리스트(\(N\)) 공간이 필요하다.

Big-O 정밀 분석: Python의 sorted()는 Timsort 알고리즘을 사용한다. 이는 삽입 정렬과 병합 정렬의 하이브리드 방식으로, 최악의 경우 \(O(N \log N)\), 이미 정렬된 데이터에 대해서는 \(O(N)\)의 성능을 보인다. 본 문제의 입력 크기가 매우 작으므로 최적의 선택이다.
대안 풀이 비교: 만약 \(N\)이 매우 크고 \(k\)가 작다면, 전체를 정렬하는 대신 Quick Select 알고리즘이나 Min-Heap을 사용하여 \(O(N \log k)\)로 최적화할 수 있다. 하지만 \(N \le 100\)인 환경에서는 sorted()의 오버헤드가 훨씬 적다.
공학적 고려사항: 슬라이싱 array[i-1:j]는 배열의 사본을 생성한다. 메모리가 극도로 제한된 환경(Embedded 등)이라면 원본 배열 인덱스만 제어하는 방식을 고민해야 하겠지만, 일반적인 DS 환경에서는 불변성을 유지하는 이 방식이 더 안전하다.

이 문제에서 배운 것