Exact 알고리즘과 휴리스틱(근사) 알고리즘의 선택 기준

필자는 개발보다 알고리즘을 먼저 접했기 때문에, 휴리스틱한 기법보단 증명을 통한 완벽한 계산에 익숙했다.
하지만 최근 직접 서비스를 개발해보고, 다양한 AI-ML 알고리즘을 접하기도 하며 휴리스틱과 근사 방법에 어느정도 익숙해지면서, "엄밀한 증명"만 생각하던 상태에서 벗어나게 되었다.
이 과정에서 자연스럽게 "Exact 알고리즘"과 "휴리스틱 알고리즘"의 분류 기준을 생각하게 되었다.

 

• Exact 알고리즘
  • 정확한 답이 증명으로 보장된 알고리즘 
• 휴리스틱 알고리즘
  • 정확한 답이 아니더라도, 정확한 답 수준의 풀이를 반환하는 알고리즘

원래의 정의는 이렇지만, 이 정의는 실무에서 알고리즘을 선택하는데에는 약간의 미흡함이 있다고 생각했다.

따라서 정의를 다음과 같이 약간 수정했다.

 

• Exact 알고리즘
  • 정확한 답이 증명으로 보장된 알고리즘 
  • 빅-오로 "예측 가능"한 시간 안에 풀이를 반환하는 알고리즘
• 휴리스틱 알고리즘
  • 정확한 답이 아니더라도, 정확한 답 수준의 풀이를 반환하는 알고리즘
  • 빅-세타로 "계산 가능"한 시간 안에 풀이를 반환하는 알고리즘

 

명확한 증명은 없지만, 증명 기반 알고리즘만 학습해오던 상태에서 벗어나 다양한 휴리스틱과 개발을 경험해보며 느낀 경험적 선택 기준을 정리한다.

엄밀한 증명보다 휴리스틱이 들어가는 기법을 "근사 알고리즘"으로 정의할 것이기 때문에, 본 글에서는 백트래킹/A* 알고리즘과 같은 계열도 모두 휴리스틱으로 볼 것이다.

 

---

필자는 이를 판단할 기준을 P-NP에서 찾을 수 있었다.

P 문제

• 시간복잡도가 다항 시간 안에 풀리는 문제
• 일반적으로 코딩 테스트와 단순한 비즈니스 로직의 개발 단계에서 자주 접하게 되는 문제이다.

NP 문제

• 시간복잡도가 지수 시간 안에 풀리는 문제

다항 시간은 지수시간보다 작기 때문에, NP 문제는 P 문제를 모두 포함한다.

NP-Hard 문제

• 시간복잡도가 지수시간 안에 풀리면서, 다항시간 안에 풀리지 않는 문제
  • 일반적으로 실제 코어 비즈니스 로직 개발 환경이나 ML 알고리즘과 같은 환경에서 자주 접하게 되는 문제이다.
  • 실제로 완벽한 해를 찾기 어려우니, 이 경우 현재 할 수 있는 최선의 판단이나 근사해를 자주 적용하게 된다.

---

언제 Exact 알고리즘이 필요한가

• 비가역적이고, 실패 시 손실이 큰 경우
  • 최적성/수행시간/정확성 보장(정리, 상·하한, 수렴증명, 허용적 휴리스틱 등)이 필요.
• 최악의 경우 성능이 중요한가?
  • 실시간/최악 입력(적대적 트래픽, DDoS) 대응
  • O( ) 복잡도 보장
• 입력 분포가 불확실·적대적인가?
  • 사기 탐지, 게임이론적 환경
  • 확정적/확률적 보장 있는 방법 우선.
• 단순한 다항 시간에 풀 수 있는가?
  • 이 경우, 근사해보다 Exact 알고리즘이 안정적이다.

언제 “휴리스틱/경험적 접근”을 써야 하나

• NP-Hard/조합폭발
  • 차량경로
  • 작업스케줄링
  • 대규모 배치
  • etc.
• 시간·리소스 제약: “지금 1분 안에 충분히 좋은 해”가 필요
  • 지금까지 최선이었던 해를 찾아야 한다.
• 입력 분포가 안정적이고 A/B로 빠르게 검증 가능
  • 성능지표(KPI)로 경험적으로 이기는 것을 채택하자.
  • 테스트가 빠르기 때문에, 굳이 완벽한 해를 찾을 필요가 없다.
• 비용함수/제약이 자주 바뀔 경우: 실무 도메인은 살아 움직인다.
  • 온라인 튜닝/학습형 휴리스틱이 유리하다.
• 완전한 이론 모델이 부정확: 현실의 잡음·비정형 제약이 많음
  • 모델과 현업의 괴리를 휴리스틱으로 메운다.