# 결정적 알고리즘 (Deterministic Algorithms) 결정적 알고리즘은 입력이 주어졌을 때 항상 동일한 출력과 실행 경로를 산출하는 알고리즘을 말한다. 실행 중에 임의성이나 확률적 선택이 개입되지 않으며, 주어진 입력에 대하여 한 가지 결정된 결과만을 내놓는다. 이러한 특성으로 인해 재현성(reproducibility)과 예측 가능성(predictability)이 보장된다. ## 정의 - 정의: 임의성 없이 고정된 규칙에 따라 입력으로부터 출력을 결정하는 알고리즘. - 수학적 표현: 알고리즘은 입력 문자열 또는 데이터 구조 S에 대해 결정 함수 f를 적용하여 출력 O를 생성한다. 실행 과정의 모든 단계는 결정적이며, 동일한 입력에 대해 동일한 실행 트레이스를 따른다. ## 특징 - 결정성: 같은 입력에 대해 항상 같은 출력과 실행 경로를 보장한다. - 재현성: 연구, 검증, 최적화 과정에서 동일한 결과를 반복적으로 얻을 수 있다. - 예측 가능성: 시간 복잡도와 공간 복잡도가 이론적으로 분석 가능하고, 구현에 따라 일정한 성능 경향을 보인다. - 독립성: 외부 난수원이나 외부 상태에 의존하지 않는 경향이 강하다. ## 분류(기술적 관점) - 비교 기반 vs 비교 기반: 항목 간의 비교를 통해 결정하는 알고리즘과, 비교 없이도 결정하는 알고리즘으로 구분할 수 있다. - 그리디(Greedy), 분할정복(Divide-and-Conquer), 동적 계획법(Dynamic Programming), 탐색(Searching) 등 기법별로도 결정적 특성을 보인다. - 그래프 알고리즘, 정렬 알고리즘, 최단 경로 알고리즘 등 다양한 분야에서 결정적 구현이 일반적이다. ## 시간 복잡도와 공간 복잡도 - 시간 복잡도: 입력 크기 n에 대해 보장된 상한선을 제공한다(Proven worst-case bound). - 공간 복잡도: 필요한 메모리의 양도 입력에 따라 결정적이며, 순차적 구현에서 추가 공간이 더 적게 필요할 수 있다. - 예: 이진 탐색은 O(log n) 시간, 합병 정렬은 O(n log n) 시간, O(n) 공간의 비용을 갖는다. ## 대표 예시 알고리즘 - 이진 탐색(Binary Search): 정렬된 배열에서 목표 값을 로그 시간에 찾는 결정적 알고리즘. 시간 복잡도 O(log n). - 합병 정렬(Merge Sort): 분할정복 기법으로 배열을 정렬하는 결정적 알고리즘. 시간 복잡도 O(n log n), 보통 O(n) 이상의 추가 공간 필요. - 선택 정렬(Selection Sort): 간단한 비교 기반 정렬 알고리즘. 시간 복잡도 O(n^2), 추가 공간 O(1). - 다익스트라 알고리즘(Dijkstra’s Algorithm): 가중치가 있는 그래프에서 한 정점에서 모든 정점까지의 최단 경로를 구하는 결정적 알고리즘. 우선순위 큐를 사용하면 시간 복잡도는 O((V + E) log V) 등으로 표현된다. - 유클리드 알고리즘(Euclidean Algorithm)으로서의 최대공약수(GCD) 계산: 반복적이고 결정적인 방식으로 작동한다. - 깊이 우선 탐색(Depth-First Search, DFS) 및 너비 우선 탐색(BFS): 그래프의 탐색을 위한 결정적 방법으로, 인접 순서 등 고정된 규칙에 따라 실행된다. ## 비교: 결정적 알고리즘 vs 비결정적 알고리즘 - 결정적 알고리즘: 입력에 대해 항상 하나의 결정 경로와 출력이 존재한다. 난수나 외부 상태에 의존하지 않는다. - 비결정적 알고리즘: 여러 가능한 선택 경로가 존재할 수 있으며, 같은 입력이라도 다른 실행 경로를 택할 수 있다(예: 이론적 비결정형 머신, 일부 확률적 알고리즘의 독립적 구성). 실제 구현에서도 시드(seed)나 외부 난수에 의존한다면 결과가 다를 수 있다. - 실무상의 차이: 결정적 알고리즘은 재현성과 안정성이 필요한 시스템에 선호되며, 비결정적 또는 확률적 알고리즘은 문제의 복잡도나 해법의 탐색 공간이 지나치게 큰 경우에 유용하다. ## 구현상의 고려사항 - 결정성 보장을 위한 규칙 고정: 자료 구조의 초기화, 순회 순서, 우선순위 큐의 비교 함수 등 실행 중 결정 경로를 좌우하는 요소를 명확히 정의해야 한다. - 예외 처리: 입력 검증, 경계 조건 처리 등을 일관되게 구현해야 한다. - 최적화와 안정성의 균형: 특정 상황에서 더 빠른 평균 성능을 보이는 비결정적 기법을 선택해야 할지 여부를 판단한다. ## 응용 분야 - 형식 검증(formal verification) 및 모델 체크(model checking): 시스템의 동작이 특정 속성을 만족하는지 확정적으로 증명하는 데 유리하다. - 컴파일러 최적화, 정적 분석 도구: 결정적 알고리즘을 이용하여 예측 가능한 결과와 성능을 보장한다. - 데이터 정렬, 탐색, 최단 경로 문제 등 광범위한 컴퓨팅 문제에 적용 가능. - 암호학에서의 결정적 프로토콜 구성 및 보안 분석: 예측 가능한 동작과 재현 가능한 테스트를 필요로 하는 부분에 활용된다. ## 한계와 대안 - 모든 문제에 대해 효율적인 결정적 알고리즘이 존재하는 것은 아니다. 특히 큰 탐색 공간이나 불확실한 환경에서는 비결정적 방법이나 확률적 알고리즘이 더 적합한 경우가 있다. - 난수의 의존이나 외부 상태에 의해 성능이 달라지는 알고리즘은 엄밀한 의미의 결정적 알고리즘으로 분류되기 어렵다. - 대체 접근으로는 결정적 알고리즘의 강화, 입력 순서를 고정하는 방법, 하이브리드 알고리즘 등이 있다. ## 역사적 배경 - 결정성의 개념은 초기 계산 이론에서부터 중요하게 다루어져 왔으며, 결정적 튜링 머신과 결정 시간 복잡도의 연구를 통해 알고리즘의 이론적 한계와 가능성을 이해하는 데 기여했다. - 20세기 중반 이후 현대 컴 teor리의 발전과 함께 P, NP 등의 복잡도 이론이 확립되면서 결정적 알고리즘의 분류 체계가 발전했다. ## 용어 정리 - Deterministic: 결정적인, 입력에 대해 항상 같은 결과를 낳는 특성. - Non-deterministic: 비결정적, 여러 가능한 선택지가 존재하는 특성. - Time complexity: 시간 복잡도, 알고리즘이 문제 크기에 따라 소비하는 실행 시간의 성장률. - Space complexity: 공간 복잡도, 알고리즘이 필요로 하는 기억 공간의 양. --- 관련 문서: [[비결정적 알고리즘]], [[결정 문제와 복잡도]]