휴리스틱(Heuristic)

핵심 요약

휴리스틱(heuristic)은 복잡한 문제를 완전하게 계산하지 않고, 경험적 규칙·추정값·간단한 평가 기준을 사용해 빠르게 해결하려는 방법이다.
휴리스틱은 최적해(optimal solution)나 정답을 항상 보장하지 않는다. 대신 계산량을 줄이고, 현실적인 시간 안에 충분히 좋은 해를 찾는 데 목적이 있다.
휴리스틱은 알고리즘 자체일 수도 있지만, 더 정확히는 알고리즘 안에서 사용되는 판단 기준, 평가 함수, 탐색 방향 설정 원리로 이해하는 편이 좋다.
인공지능에서는 경로 탐색, 게임 AI, 일정 계획, 조합 최적화처럼 경우의 수가 폭발하는 문제에서 중요하다.
인간 사고에서도 휴리스틱은 빠른 판단을 가능하게 하지만, 동시에 인지 편향(cognitive bias)을 만들 수 있다.

1. 휴리스틱의 기본 정의

휴리스틱은 문제를 풀 때 모든 가능성을 계산하지 않고, 그럴듯한 방향을 먼저 선택하게 해 주는 경험적 규칙이다.

간단히 말하면 다음과 같다.

휴리스틱은 “완벽한 계산” 대신 “빠른 추정”을 사용하는 문제 해결 방식이다.

예를 들어 길을 찾는 문제에서 가능한 모든 경로를 하나씩 비교하면 시간이 오래 걸린다. 이때 “목적지와 직선거리상 가까워지는 방향을 먼저 살펴보자”라는 규칙을 쓰면 탐색 범위를 크게 줄일 수 있다. 이 규칙이 바로 휴리스틱이다.

중요한 점은 휴리스틱이 항상 정답을 보장하지는 않는다는 것이다. 목적지에 가까워 보이는 길이 실제로는 막다른 길일 수도 있다. 하지만 대부분의 실제 문제에서는 완전 탐색이 너무 비싸기 때문에, 휴리스틱은 매우 실용적인 도구가 된다.

2. 정확한 알고리즘과 휴리스틱의 차이

문제 해결 방법은 크게 두 방향으로 나눌 수 있다.

구분	정확한 알고리즘	휴리스틱 기반 방법
목표	정답 또는 최적해 보장	충분히 좋은 해를 빠르게 찾기
방식	모든 조건을 엄밀히 계산	경험적 규칙·추정값 사용
장점	결과의 정확성	속도와 실용성
단점	계산량이 매우 클 수 있음	최적해를 놓칠 수 있음
예	완전 탐색, 동적 계획법	A*, 탐욕적 선택, 유전 알고리즘

정확한 알고리즘은 가능한 경우를 모두 고려하거나, 수학적으로 보장된 방식으로 해를 찾는다. 반면 휴리스틱은 현실적인 제약을 고려해 계산을 줄인다.

이 차이는 “정확성 대 속도”의 단순한 대립처럼 보일 수 있지만, 실제로는 더 복잡하다. 어떤 휴리스틱은 특정 조건에서 최적해를 보장하기도 하고, 어떤 정확한 알고리즘은 문제 규모가 커지면 현실적으로 사용할 수 없을 만큼 느려진다.

따라서 핵심은 다음과 같다.

휴리스틱은 부정확한 방법이 아니라, 계산 불가능하거나 계산 비용이 큰 문제를 다루기 위한 실용적 전략이다.

3. AI에서 휴리스틱이 중요한 이유

AI가 다루는 많은 문제는 경우의 수가 매우 크다.

대표적인 예는 다음과 같다.

체스
바둑
경로 탐색
로봇 이동 계획
일정 계획
물류 최적화
게임 캐릭터 행동 결정

이런 문제에서는 가능한 모든 경우를 검토하는 방식이 현실적으로 불가능한 경우가 많다. 예를 들어 게임 AI가 모든 수를 끝까지 계산하려 하면 경우의 수가 폭발한다. 그래서 AI는 가능성이 낮은 선택지를 줄이고, 유망한 방향을 먼저 탐색해야 한다.

이때 휴리스틱은 다음 질문에 답하는 역할을 한다.

지금 수많은 선택지 중에서 어느 방향을 먼저 살펴보는 것이 그럴듯한가?

즉 휴리스틱은 AI에게 “정답”을 직접 알려주는 것이 아니라, 탐색의 우선순위를 정해 준다.

4. 대표적인 휴리스틱 사용 사례

4.1 A* 탐색 알고리즘

A* 탐색 알고리즘은 경로 찾기 문제에서 널리 사용되는 알고리즘이다. 핵심 아이디어는 현재까지 실제로 든 비용과 목표까지 남은 예상 비용을 함께 고려하는 것이다.

A*는 보통 다음 평가식을 사용한다.

f(n) = g(n) + h(n)

각 항의 의미는 다음과 같다.

g(n): 시작점에서 현재 노드 n까지 실제로 이동한 비용
h(n): 현재 노드 n에서 목표까지 남은 예상 비용
f(n): 현재까지의 비용과 앞으로의 예상 비용을 합친 전체 추정 비용

예를 들어 지도에서 길을 찾을 때 g(n)은 지금까지 실제로 이동한 거리이고, h(n)은 현재 위치에서 목적지까지의 직선거리 같은 추정값이 될 수 있다.

다만 A*가 항상 최적 경로를 보장하는 것은 아니다. 최적성을 보장하려면 휴리스틱 h(n)이 실제 남은 비용을 과대평가하지 않는 허용적 휴리스틱(admissible heuristic)이어야 한다. 그래프 탐색에서는 여기에 더해 일관성(consistency) 조건이 중요하다.

쉽게 말하면 다음과 같다.

A*는 좋은 휴리스틱을 쓰면 빠르고 정확할 수 있지만, 잘못된 휴리스틱을 쓰면 최적 경로를 놓칠 수 있다.

4.2 탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘은 매 순간 가장 좋아 보이는 선택을 하는 방식이다.

예를 들어 거스름돈을 줄 때 가장 큰 동전부터 고르는 방법은 탐욕적 사고에 가깝다. 현재 단계에서 가장 유리해 보이는 선택을 반복하기 때문이다.

하지만 탐욕 알고리즘은 항상 최적해를 보장하지 않는다. 어떤 문제에서는 순간적으로 좋아 보이는 선택이 전체적으로는 나쁜 결과를 만들 수 있다.

탐욕 알고리즘의 핵심은 다음과 같다.

지금 가장 좋아 보이는 선택이 전체적으로도 좋을 것이라고 가정하는 방식이다.

이 가정이 성립하는 문제에서는 매우 빠르고 강력하다. 예를 들어 일부 최소 신장 트리 문제에서는 탐욕적 선택이 최적해로 이어진다. 하지만 모든 문제에서 그런 것은 아니다.

4.3 유전 알고리즘(Genetic Algorithm)

유전 알고리즘은 자연 진화의 원리에서 아이디어를 얻은 최적화 방법이다.

기본 과정은 다음과 같다.

여러 후보 해를 만든다.
그중 성능이 좋은 후보를 선택한다.
선택된 후보들을 조합한다.
일부 후보에 무작위 변이를 준다.
이 과정을 반복해 더 나은 해를 찾는다.

유전 알고리즘은 특정 문제 하나에만 적용되는 단순한 휴리스틱이라기보다, 여러 최적화 문제에 적용할 수 있는 메타휴리스틱(metaheuristic)에 가깝다.

메타휴리스틱이란 특정 문제의 세부 규칙보다 더 높은 수준에서 탐색 방향을 조절하는 일반적 전략이다. 유전 알고리즘, 시뮬레이티드 어닐링(simulated annealing), 타부 탐색(tabu search) 등이 여기에 속한다.

5. 인간 사고에서의 휴리스틱

휴리스틱은 컴퓨터 알고리즘에만 있는 개념이 아니다. 인간도 일상적인 판단에서 휴리스틱을 사용한다.

인간은 모든 정보를 다 계산한 뒤 판단하지 않는다. 시간과 주의력은 제한되어 있고, 정보는 불완전하다. 그래서 인간은 빠른 판단 규칙을 사용한다.

대표적인 예는 다음과 같다.

5.1 대표성 휴리스틱(Representativeness Heuristic)

어떤 대상이 특정 집단의 전형적 이미지와 얼마나 비슷한지를 기준으로 판단하는 방식이다.

예를 들어 어떤 사람이 조용하고 책을 좋아한다는 설명만 듣고 “그 사람은 사서일 가능성이 높다”고 판단하는 경우가 있다. 하지만 실제 확률을 따지려면 사서의 전체 인구 비율 같은 기초율(base rate)도 고려해야 한다.

대표성 휴리스틱은 빠른 판단을 가능하게 하지만, 통계적 정보를 무시하게 만들 수 있다.

5.2 가용성 휴리스틱(Availability Heuristic)

머릿속에 쉽게 떠오르는 사례를 기준으로 가능성이나 빈도를 판단하는 방식이다.

예를 들어 비행기 사고 뉴스를 자주 보면 실제 확률보다 비행기 사고가 더 흔하다고 느낄 수 있다. 쉽게 떠오르는 사건이 반드시 자주 일어나는 사건은 아니다.

5.3 앵커링 효과(Anchoring Effect)

처음 제시된 숫자나 정보가 이후 판단에 과도한 영향을 주는 현상이다.

예를 들어 어떤 물건의 원래 가격이 100만 원이라고 먼저 제시되면, 할인 가격 70만 원이 싸게 느껴질 수 있다. 하지만 실제 가치는 그 기준 가격과 별개로 평가해야 한다.

6. 휴리스틱과 인지 편향

휴리스틱은 유용하지만 위험도 있다. 빠른 판단을 가능하게 하는 바로 그 구조가 오류를 만들 수 있기 때문이다.

즉 휴리스틱은 다음 두 얼굴을 가진다.

측면	설명
장점	빠른 판단, 낮은 계산 비용, 실용적 의사결정
단점	편향, 오판, 최적해 누락 가능성

카너먼(Daniel Kahneman)과 트버스키(Amos Tversky)의 연구는 인간이 불확실성 아래에서 판단할 때 대표성, 가용성, 앵커링 같은 휴리스틱을 사용하며, 이 과정에서 체계적인 편향이 발생할 수 있음을 보여 주었다.

따라서 휴리스틱은 단순히 “좋은 직관”이 아니다. 더 정확히 말하면 다음과 같다.

휴리스틱은 제한된 시간과 정보 속에서 판단을 가능하게 하는 압축된 사고 방식이며, 동시에 오류를 만들 수 있는 구조이다.

7. 휴리스틱에 대한 흔한 오해

오해 1. 휴리스틱은 대충 찍는 것이다

그렇지 않다. 휴리스틱은 무작위 추측이 아니라, 문제 구조에 대한 경험적 지식을 활용하는 방식이다. 다만 그 지식이 항상 완전하지 않을 뿐이다.

오해 2. 휴리스틱은 항상 부정확하다

그렇지 않다. 어떤 휴리스틱은 특정 조건에서 최적해를 보장할 수 있다. A*의 허용적 휴리스틱이 대표적인 예다.

오해 3. 정확한 알고리즘이 항상 더 좋다

이론적으로는 정확한 알고리즘이 좋아 보이지만, 실제 문제에서는 계산 시간이 너무 길어 사용할 수 없는 경우가 많다. 현실에서는 “완벽한 답을 너무 늦게 얻는 것”보다 “충분히 좋은 답을 빠르게 얻는 것”이 더 유용할 수 있다.

오해 4. 인간의 직관은 전부 휴리스틱이다

인간의 직관은 휴리스틱과 관련이 깊지만, 전부를 휴리스틱 하나로 설명할 수는 없다. 직관에는 경험, 기억, 정서, 신체 반응, 사회적 학습 등이 함께 작용한다.

8. 관련 개념 비교

8.1 휴리스틱 vs 알고리즘

알고리즘은 문제를 해결하기 위한 명시적 절차이다. 휴리스틱은 그 절차 안에서 탐색 방향을 줄이거나 판단을 빠르게 하는 규칙일 수 있다.

즉 모든 휴리스틱이 알고리즘은 아니며, 모든 알고리즘이 휴리스틱을 사용하는 것도 아니다.

8.2 휴리스틱 vs 완전 탐색

완전 탐색은 가능한 모든 경우를 검토한다. 휴리스틱은 가능성이 낮은 경우를 줄이고, 유망한 방향을 먼저 본다.

완전 탐색은 정답 보장에 유리하고, 휴리스틱은 속도와 규모 확장성에 유리하다.

8.3 휴리스틱 vs 확률 알고리즘

확률 알고리즘은 무작위성을 사용해 문제를 해결한다. 반면 휴리스틱은 반드시 무작위성을 포함하지 않는다.

물론 일부 휴리스틱 또는 메타휴리스틱은 무작위성을 사용한다. 유전 알고리즘의 돌연변이 과정이나 시뮬레이티드 어닐링의 확률적 이동이 그 예다.

9. 더 학습할 만한 주제

휴리스틱을 더 깊게 이해하려면 다음 주제를 이어서 공부하면 좋다.

A* 알고리즘의 최적성 조건
허용적 휴리스틱(admissible heuristic)
일관적 휴리스틱(consistent heuristic)
탐색 알고리즘의 종류
너비 우선 탐색(BFS)
깊이 우선 탐색(DFS)
균일 비용 탐색(uniform-cost search)
A* 탐색
최적화 문제와 메타휴리스틱
유전 알고리즘
시뮬레이티드 어닐링
타부 탐색
입자 군집 최적화
인지과학의 휴리스틱과 편향
대표성 휴리스틱
가용성 휴리스틱
앵커링 효과
기초율 무시(base-rate neglect)
AI와 인간 사고의 비교
인간의 제한 합리성(bounded rationality)
탐색 공간(search space)
평가 함수(evaluation function)
근사 추론(approximate reasoning)

10. 최종 정리

휴리스틱은 복잡한 문제를 현실적인 시간 안에 풀기 위한 핵심 전략이다. 완전한 계산을 포기한다는 점에서 불완전하지만, 바로 그 불완전성 덕분에 실제 문제를 다룰 수 있다.

AI에서 휴리스틱은 탐색 공간을 줄이고, 가능성 높은 방향을 먼저 살피게 한다. 인간 사고에서 휴리스틱은 빠른 판단을 가능하게 하지만, 동시에 인지 편향을 만들 수 있다.

따라서 휴리스틱을 이해할 때 가장 중요한 관점은 다음이다.

휴리스틱은 정답을 보장하는 마법 공식이 아니라, 제한된 시간·정보·계산 자원 속에서 더 나은 판단을 가능하게 하는 실용적 사고 도구이다.

참고 자료

Peter E. Hart, Nils J. Nilsson, Bertram Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics, 1968.
https://ai.stanford.edu/~nilsson/OnlinePubs-Nils/PublishedPapers/astar.pdf
Stanford CS221, “Search: A*”.
https://stanford-cs221.github.io/autumn2022-extra/modules/search/a-star.pdf
Amos Tversky, Daniel Kahneman, “Judgment under Uncertainty: Heuristics and Biases”, Science, 1974.
https://www.science.org/doi/10.1126/science.185.4157.1124
Stuart Russell, Peter Norvig, Artificial Intelligence: A Modern Approach.
https://dl.acm.org/doi/10.5555/1671238