인공지능의 본질은 "문제를 입력받아 해(Solution)를 찾아내는 탐색"입니다. 그래프와 미로를 풀던 전통 심볼릭 AI의 상태 공간 탐색부터, 현대 거대 언어 모델(LLM)의 잠재 지식 검색(RAG), 그리고 사고 트리(Tree of Thoughts)와 추론 시간 컴퓨팅(o1/R1)으로 완성된 인지적 탐색 혁명까지 총망라합니다.
💡 "컴퓨터 과학자가 연구하는 대부분의 지능적 알고리즘은 탐색 공간(Search Space)에서 최적의 경로를 찾아내는 탐색 알고리즘이다"
쉽게 얘기하면 컴퓨터 과학에서의 탐색 (Search) 알고리즘은 문제를 입력해서 그 문제에 대한 해(Solution)를 얻는 알고리즘입니다. 문제를 풀기 위해 컴퓨터 과학자가 연구하는 대부분의 알고리즘들은 일종의 탐색 알고리즘들입니다 (문제해결 (Problem Solving)).
문제를 푸는 가능한 모든 해를 모아둔 전체 집합을 탐색 공간 (Search Space) 또는 상태 공간 (State Space) 이라고 부릅니다. 무정보 탐색 (Uninformed Search) 알고리즘은 탐색 공간을 탐색하는 가장 단순하고 직관적인(intuitive) 무차별 방법을 사용합니다. 반면에 정보 탐색(Informed Search, 휴리스틱 탐색 (Heuristic Search)) 알고리즘은 탐색 시간을 줄이기 위해 탐색 공간의 구조에 대한 지식을 응용하는 휴리스틱을 사용합니다.
📑 서브 리소스: 용어 (term) | 논문 (paper) | 사이트 (site) | 연구실 (lab) | 도서 (book) | 기업 (company) | 데모 (demo)
무정보 탐색은 문제의 독특한 성질을 고려하지 않는 알고리즘입니다. 따라서 쉽게 구현 가능하고, 똑같은 구현 방식을 추상화(abstraction)해서 넓은 범위의 문제들에 적용할 수 있습니다. 그러나 대부분의 상태 공간이 매우 크기 때문에, 무정보 탐색(특히 트리의 경우)은 아주 작은 크기의 문제에만 합리적인 시간이 소요되며 크기가 커지면 조합 폭발로 계산 불가능해집니다.
리스트 탐색 알고리즘은 탐색 알고리즘 중에서 가장 기본적인 것입니다. 목적은 어떤 키(Key)에 의해 집합의 한 요소를 찾는 것입니다. 가장 쉬운 알고리즘은 각 요소를 순서대로 검사하는 선형 탐색(Linear Search)입니다. 대부분의 리스트 탐색 알고리즘(Linear Search, Binary Search, Self-balancing Binary Search Trees 등)은 주어진 키보다 더 크거나 작은 모든 값을 찾기 위해 부가적인 비용이 거의 들지 않도록 확장될 수 있는데, 이를 범위 탐색(Range Search)이라고 합니다. 그러나 해시 테이블(Hash Tables)은 구조적 특성상 범위 탐색을 효율적으로 수행할 수 없습니다.
트리 탐색 알고리즘은 탐색 기술의 핵심입니다. 트리 (Tree) 가 명시적이든 암시적이든 (예를 들면 바둑 (Baduk) 에서처럼) 트리의 노드를 탐색합니다. 기본 원리는 하나의 노드가 자료구조에서 얻어지고 그 자식 노드들이 검사되어 자료구조에 더해진다는 것입니다.
정보 탐색에서는 그 문제에 고유한 휴리스틱이 가이드로서 사용됩니다. 뛰어난 휴리스틱은 정보 탐색을 극적으로 만들며 어떠한 무정보 탐색보다도 월등한 성능을 발휘합니다. 대부분의 정보 탐색 알고리즘은 트리와 그래프에서 사용되며, 최상우선 탐색 (Best-first Search), A* 알고리즘 등이 대표적입니다.
게임 (Game) 프로그램과 기계 계획(Machine Planning) 등 인공지능의 다른 영역들은 상대방의 대응을 고려하는 최소최대 (Mini-max) 알고리즘, 탐색 트리 가지치기(Search Tree Pruning), 알파베타 가지치기 (Alpha-Beta Pruning) 와 같은 탐색 알고리즘을 사용합니다.
제약 만족 (Constraint Satisfaction) 은 제약조건 만족 문제 (Constraint Satisfaction Problem, CSP) 를 푸는 탐색의 유형입니다. 이는 출발지부터 목표지점까지의 '경로'를 찾기보다는 단순히 제약 조건을 만족하는 변수에 할당된 값의 조합을 찾는 것입니다. 변수들은 어떤 순서로도 처리될 수 있기 때문에 보통의 트리 탐색 알고리즘은 비효율적이며, 조합 탐색(Combinatorial Search)과 백트래킹(Backtracking)을 통해 제약 문제의 자유도를 활용합니다.
문자열 탐색(String Search)은 텍스트 내의 패턴을 탐색하며 접미사 트리(Suffix Tree)가 대표적입니다. 또한 유전알고리즘 (Genetic Algorithm) 은 상태 공간을 줄이기 위해 생물학적 진화 (Evolution) 의 교차·돌연변이 원리를 차용하며, 모의 담금질 (Simulated Annealing) 은 금속의 냉각 과정에서 아이디어를 얻은 확률적(Probabilistic) 전역 최적화 탐색 알고리즘입니다.
"공짜점심 같은 것은 없다 (There ain't no such thing as a free lunch)"에서 유래한 No-Free-Lunch 정리 는, 모든 수학적으로 가능한 문제 공간 전체를 평균 내어 평가할 때, 어떤 탐색 알고리즘도 다른 알고리즘보다 본질적으로 우월할 수 없음을 수학적으로 증명합니다. 특정 탐색 알고리즘이 뛰어난 성능을 내는 것은 그 알고리즘의 편차(Bias)가 풀고자 하는 도메인의 특성과 우연히 잘 맞아떨어졌기 때문이며, 만병통치약(Silver Bullet) 탐색 알고리즘은 존재하지 않습니다.
BFS, DFS, IDDFS
사전 지식 없이 기계적 전수 조사. 작은 미로, 퍼즐 해결.
A*, Best-First, IDA*
평가 함수 h(n) 가이드. GPS 내비게이션 최단 경로, 게임 길찾기.
Minimax, Alpha-Beta
상대방의 최적 수 고려. 체스(Deep Blue), 바둑, 체커.
Backtracking, MRV
변수 제약 충족. 스도쿠, 항공기 승무원 스케줄링, 지도 채색.
Genetic Alg, MCTS
생물학적 진화와 시뮬레이션. AlphaGo, 복잡한 파라미터 최적화.
"정형 그래프의 경로 찾기"에서 "외적 지식 검색(RAG)"과 "사고 공간의 추론 시간 탐색(Inference-Time Compute)"으로의 거대한 진화
과거의 언어 모델은 훈련 데이터에 존재하는 지식을 수천억 개의 파라미터에 '암기'하여 답변했습니다. 그러나 이는 학습 시점 이후의 최신 정보를 반영하지 못하고, 존재하지 않는 사실을 지어내는 환각(Hallucination)을 필연적으로 야기합니다.
현대 LLM은 RAG (Retrieval-Augmented Generation) 를 통해 탐색의 패러다임을 바꿨습니다. 답변을 생성하기 전, 수백억 개의 웹 문서와 사내 데이터베이스를 고차원 벡터 공간(Dense Semantic Search)과 키워드(BM25)의 하이브리드 탐색으로 실시간 검색한 뒤, 가장 정확한 증거만을 프롬프트 컨텍스트로 제공받아 답합니다. 검색이 언어 모델의 신뢰성을 지탱하는 절대적 안전망이 된 것입니다.
전통 AI에서 탐색이 미로를 푸는 일이었다면, 최신 LLM(OpenAI o1, DeepSeek-R1)에서 탐색은 "생각의 공간(Thought Space)을 체스처럼 시뮬레이션하는 일"입니다. 이것이 바로 2024년 이후 인공지능 학계를 뒤흔든 추론 시간 컴퓨팅(Inference-Time Compute Scaling) 혁명입니다:
Perplexity, SearchGPT, 구글 제미나이 등 최신 생성형 탐색 엔진은 단순한 키워드 매칭을 넘어선 자율 에이전틱 루프를 구동합니다:
사용자의 복잡한 질문 분해 ➔ 1차 웹 탐색 ➔ 검색 결과 비판적 평가(Critique) ➔ 누락된 정보 식별 및 2차 검색어 자동 재작성(Query Reformulation) ➔ 종합 분석 및 최종 답변 생성. 과거 인간이 1시간 동안 브라우저 창을 수십 개 띄워놓고 수행하던 수동 탐색을 AI 에이전트가 단 수 초 만에 자율 탐색합니다.
| 비교 차원 | 전통 인공지능 탐색 (Classical Search) | 최신 LLM 탐색 (Modern LLM Search) |
|---|---|---|
| 탐색 공간 (Space) | 명시적/암시적으로 수학 정의된 이산 그래프 (미로, 체스보드) | 자연어 잠재 공간(Latent Space) + 웹 전역 비정형 텍스트 |
| 탐색의 주체 | 단일 탐색 알고리즘 코드 (BFS, A*, Minimax) | 신경망(LLM) + 추론 검증기(PRM) + 자율 에이전트 |
| 노드 및 연산자 | 사전 정의된 규칙(예: '말을 e4로 이동', '우회전') | 생성된 문장(사고 단계) 및 외부 툴/API 호출 |
| 평가 함수 (Heuristic) | 수동 엔지니어링된 수학 함수 h(n) (예: 맨해튼 거리) | 강화학습 보상 모델(Process Reward Model) 및 벡터 유사도 |
| 최종 산출물 | 초기 상태에서 목표 상태로 이르는 최단 경로 좌표열 | 검증된 논리적 추론 사슬과 정확한 자연어 종합 답변 |
| 대표적 구현 | Dijkstra 내비게이션, Deep Blue 체스 | OpenAI o1, DeepSeek-R1, Perplexity, GraphRAG |
세계 최고의 인공지능 교과서 저자이자 전 구글 연구소장인 피터 노빅(Peter Norvig) 박사의 CITRIS 특별 강연을 통해 인공지능과 검색 엔진 기술의 유기적 결합을 영상으로 확인하세요.
강연자: Peter Norvig (Google Research Director) | 대규모 웹 데이터와 확률적 인공지능 탐색 기술의 만남.