AI 기초 및 활용 4회: 알고리즘과 탐색 — 기계가 길을 찾는 법

SVIL 「AI 기초 및 활용」 시리즈 4회차입니다. 모든 내용은 이미지 없이 본문 텍스트만으로 완전히 이해할 수 있도록 구성되어 있습니다.

1. 오늘의 질문: 내비는 어떻게 1초 만에 길을 찾을까?

출발지와 목적지를 찍으면 1초도 안 돼 경로가 뜹니다. 그런데 생각해 보세요. 서울에서 부산까지 갈 수 있는 길의 조합은 사실상 무한합니다. 교차로마다 갈림길이 있고, 갈림길마다 또 갈림길이 있죠. 컴퓨터가 그 무한에 가까운 조합을 '다 계산'하는 걸까요? 그럴 리가요. 그랬다면 답이 나오기 전에 우주가 끝납니다.

비밀은 탐색(search)이라는, AI의 가장 오래되고 가장 우아한 기술에 있습니다. 오늘은 역사 여행을 끝내고 처음으로 원리의 세계에 들어가는 날이에요. 이번 회차가 끝나면 여러분은 내비게이션, 게임 속 컴퓨터 상대, 물류 로봇이 길을 찾는 방법을 남에게 설명할 수 있게 됩니다. 약속대로 수식은 없습니다. 필요한 건 미로 하나와 약간의 상상력뿐입니다.

2. 지난 회차 연결: 역사에서 원리로

1~3회차에서 우리는 큰 그림을 그렸습니다. AI란 무엇인지(1회), 그 꿈이 어떻게 시작됐고(2회), 어떤 겨울을 지나 부활했는지(3회). 그 역사 속에서 탐색은 계속 등장했습니다. 로직 시어리스트가 증명을 찾은 것도, 딥블루가 체스 수를 읽은 것도, 라이트힐 보고서가 지적한 조합 폭발도 — 전부 탐색 이야기였죠.

탐색은 2회차에서 배운 기호주의 AI의 심장이자, 지금도 모든 소프트웨어에 스며 있는 현역 기술입니다. 1회차의 'AI 효과' 대표 사례이기도 하고요 — 너무 성공해서 아무도 AI라 부르지 않게 된 기술. 오늘 그 심장을 열어봅니다.

3. 발상의 전환: 문제를 지도로 바꾸기

탐색의 출발점은 기술이 아니라 발상입니다. 어떤 문제든 이렇게 바꿔 생각하는 거예요. "이 문제의 가능한 모든 상황을 지도 위의 지점들로 펼치고, 지금 위치에서 목표 지점까지 가는 길을 찾자."

이 지도를 상태 공간(state space)이라고 부릅니다. 미로라면 각 위치가 하나의 상태고, 루빅스 큐브라면 큐브의 각 배열 하나하나가 상태입니다. 체스라면 말들의 배치 하나하나가 상태고요. 상태와 상태 사이는 '행동'으로 연결됩니다. 한 칸 이동하기, 큐브 한 면 돌리기, 말 하나 옮기기.

이 발상이 왜 혁명이냐면, 전혀 달라 보이는 문제들이 전부 같은 문제가 되기 때문입니다. 미로 찾기, 퍼즐 맞추기, 경로 계산, 게임의 수읽기, 일정 짜기 — 겉모습은 제각각이지만 상태 공간으로 바꾸면 모두 "지도에서 길 찾기"입니다. 하나의 해법으로 수천 가지 문제를 푸는 만능 틀. 이게 탐색의 힘입니다.

4. 세 가지 부품: 상태, 행동, 목표

상태 공간 문제를 정의하려면 딱 세 가지만 있으면 됩니다. 첫째, 시작 상태 — 지금 어디에 있는가. 둘째, 행동 — 각 상태에서 무엇을 할 수 있고, 하면 어느 상태로 가는가. 셋째, 목표 판정 — 어떤 상태가 '도착'인가.

내비게이션으로 번역하면: 시작 상태는 현재 위치, 행동은 "다음 교차로에서 직진/좌회전/우회전", 목표는 목적지 도착입니다. 여기에 하나를 더 얹을 수 있어요. 행동마다 비용(거리, 시간, 통행료)을 붙이는 겁니다. 그러면 문제는 "아무 길이나 찾기"에서 "가장 싼 길 찾기"로 업그레이드되죠.

이 단순한 틀에 문제를 끼워 넣는 순간, 컴퓨터가 일할 준비가 끝납니다. 그럼 이제 컴퓨터는 이 지도를 어떻게 뒤질까요? 가장 정직한 두 가지 방법부터 봅시다.

5. 연습 문제: 8퍼즐로 감 잡기

구체적인 예 하나로 감을 잡고 가죠. 3×3 판에 1부터 8까지 숫자 타일이 있고 한 칸이 비어 있는 '8퍼즐'을 아시나요? 빈칸으로 이웃 타일을 밀어 넣으며 숫자를 순서대로 정렬하는 퍼즐입니다.

이걸 상태 공간으로 바꿔봅시다. 상태는 '타일들의 현재 배열'입니다. 행동은 '빈칸 방향으로 타일 밀기'(최대 4가지). 목표는 '1~8이 순서대로 정렬된 배열'. 끝입니다. 이제 이 퍼즐은 배열들이 점으로 찍혀 있고 '한 번 밀기'로 연결된 거대한 지도가 됐고, 퍼즐 풀기는 그 지도에서 길 찾기가 됐습니다.

참고로 이 작은 퍼즐의 상태 수는 18만 개가 넘습니다. 3×3짜리 장난감이 이 정도예요. 이 숫자를 기억해 두세요 — 잠시 후 조합 폭발을 실감할 때 다시 등장합니다.

6. 물결 탐색: 너비 우선(BFS)

첫 번째 방법. 연못에 돌을 던지면 물결이 동심원으로 고르게 퍼져나가죠. 너비 우선 탐색(BFS, Breadth-First Search)이 정확히 그렇게 움직입니다. 시작점에서 한 걸음 거리의 상태를 전부 확인하고, 그다음 두 걸음 거리를 전부, 그다음 세 걸음 거리를 전부 — 가까운 곳부터 층층이 훑어나가는 방식입니다.

이 방식의 보장이 하나 있습니다. 목표를 찾는 순간, 그 길이 가장 적은 걸음 수의 길이라는 것. 가까운 데를 다 보고 나서야 먼 데로 가니까, 처음 만난 답이 곧 최단 답입니다.

대신 대가가 있어요. 물결이 지나간 모든 지점을 기억해야 합니다. 지도가 크면 기억할 게 폭발적으로 늘어나서, 메모리가 먼저 바닥나죠. 꼼꼼하지만 몸이 무거운 방식입니다.

7. 한 우물 탐색: 깊이 우선(DFS)

두 번째 방법은 정반대 성격입니다. 깊이 우선 탐색(DFS, Depth-First Search)은 한 갈래를 골라 끝까지 파고듭니다. 막다른 곳에 닿으면 마지막 갈림길로 돌아와 다음 갈래를 파고요. 미로에서 "오른쪽 벽에 손을 대고 계속 걷기" 전략과 비슷합니다.

장점은 가벼움입니다. 지금 걷고 있는 한 갈래만 기억하면 되니 메모리를 거의 안 먹어요. 단점은 두 가지입니다. 처음 찾은 답이 최단이라는 보장이 전혀 없고, 재수 없으면 목표 반대 방향의 끝없는 갈래로 빠져 한참을 허비할 수 있습니다.

정리하면 이렇습니다. BFS는 최단 보장, 무거움. DFS는 가벼움, 무보장. 어느 쪽이 낫냐는 문제에 따라 다르고, 실무에선 둘을 절충한 변형들도 씁니다. 그런데 사실, 둘 다 공유하는 더 근본적인 약점이 있습니다.

8. 두 방식의 공통 약점: 눈이 없다

BFS와 DFS를 묶어 맹목 탐색(blind search)이라고 부릅니다. 이름이 힌트예요 — 둘 다 목표가 어느 쪽에 있는지 전혀 모른 채 뒤지기 때문입니다.

서울역에서 부산역 가는 길을 BFS로 찾는다고 해보죠. 물결은 방향을 가리지 않으니, 부산 쪽으로 퍼지는 만큼 의정부 쪽, 인천 쪽으로도 똑같이 퍼집니다. 정답과 정반대 방향을 정답 방향과 똑같은 정성으로 뒤지는 거예요. 사람이라면 절대 안 할 짓이죠. 우리는 "부산은 남쪽"이라는 감이 있으니까요.

작은 지도에선 이 낭비를 감당할 수 있습니다. 하지만 지도가 커지면 어떻게 될까요? 여기서 우리의 오랜 친구가 다시 등장합니다.

9. 조합 폭발, 숫자로 실감하기

2회차부터 이름만 듣던 조합 폭발을 오늘은 숫자로 만나봅시다. 아까 3×3 8퍼즐의 상태가 18만이 넘는다고 했죠. 판을 4×4로 한 칸 키운 15퍼즐은? 상태 수가 약 10조 개입니다. 판 하나 키웠는데 18만에서 10조로 뛰는 것 — 이게 폭발입니다.

게임은 더합니다. 체스는 한 수마다 평균 수십 개의 선택지가 있고, 그 선택마다 상대의 수십 개 응수가 갈라집니다. 몇 수만 내다봐도 경우의 수가 수십억을 넘고, 게임 전체의 가능한 진행은 우주의 원자 수를 아득히 넘어선다고 추정됩니다. 바둑은 그보다 더하고요(3회차 알파고 이야기의 배경이 이거였죠).

결론은 명확합니다. "다 뒤진다"는 전략은 장난감 문제에서만 통한다. 라이트힐 보고서가 첫 겨울을 부르며 지적한 게 바로 이 벽이었습니다. 그럼 AI는 이 벽 앞에서 멈췄을까요? 아니요. 벽을 넘는 대신, 벽을 피해 가는 법을 찾아냈습니다. 사람처럼 '감'을 갖는 법을요.

10. 휴리스틱: 감을 숫자로 바꾸다

사람의 '감'을 컴퓨터에 주려면 숫자로 바꿔야 합니다. 방법은 이겁니다. 각 상태에 대해 "여기서 목표까지 대략 얼마나 남았을까?"를 빠르게 어림하는 계산식을 하나 만드는 거예요. 이 어림값을 휴리스틱(heuristic)이라고 부릅니다.

내비게이션의 고전적 휴리스틱은 직선거리입니다. 실제 도로가 어떻든, 지도상 직선거리는 좌표만 있으면 즉시 계산되죠. 정확하진 않지만 방향 감각으론 충분합니다 — 부산 가는데 의정부 쪽 교차로는 직선거리가 늘어나니 "저긴 아니다"를 바로 아는 겁니다. 8퍼즐이라면 "제자리를 벗어난 타일 개수" 같은 게 휴리스틱이 되고요.

핵심을 정리하면: 휴리스틱은 정답이 아니라 어림이고, 정확함보다 빠름이 생명이며, 탐색에게 방향 감각을 줍니다. 이제 이 감각을 어떻게 쓰느냐가 문제인데 — 처음 떠오르는 방법엔 함정이 있습니다.

11. 탐욕의 함정

가장 단순한 활용법: "매 순간 휴리스틱이 가장 좋은(목표에 가장 가까워 보이는) 상태로만 간다." 이걸 탐욕(greedy) 탐색이라고 합니다. 빠릅니다. 대체로 그럴듯한 방향으로 직진하니까요.

하지만 함정이 있습니다. 등산으로 비유하면, "정상과 가장 가까워 보이는 방향"만 좇다가 절벽 앞 막다른 능선에 갇히는 겁니다. 지도에선 이런 일이 흔해요. 목적지와 직선거리는 가깝지만 강을 건널 다리가 없는 동네로 들어가버리는 식이죠. 게다가 탐욕 탐색은 지금까지 얼마나 왔는지를 안 봅니다. 눈앞의 가까워 보임에 홀려서, 정작 총거리가 먼 길을 태연히 고를 수 있어요.

그러니까 좋은 길 찾기엔 두 가지 정보가 다 필요합니다. 지금까지 온 실제 거리, 그리고 앞으로 남은 어림 거리. 이 둘을 더하면 어떻게 될까 — 그 단순한 덧셈이, 탐색 역사상 가장 유명한 알고리즘을 낳았습니다.

12. A*: 최고의 균형

1968년에 발표된 A*(에이스타) 알고리즘의 아이디어는 한 문장입니다. 갈림길에서 후보 상태마다 "지금까지 온 실제 비용 + 남은 어림 비용"을 계산해, 그 합이 가장 작은 후보부터 탐색한다.

이 덧셈의 의미를 음미해 보세요. 앞부분(온 비용)은 BFS의 꼼꼼함입니다 — 이미 낭비한 길을 무시하지 않죠. 뒷부분(남은 어림)은 탐욕의 방향 감각입니다 — 목표 반대쪽을 헛되이 뒤지지 않죠. A*는 이 둘의 균형이에요. 과거의 사실과 미래의 짐작을 합쳐서, '전체 여정이 가장 짧아 보이는' 후보에 집중하는 겁니다.

결과는 놀랍습니다. 조건 하나만 지키면(다음 섹션), A*는 최적 경로를 보장하면서도 맹목 탐색과 비교할 수 없이 적은 상태만 확인합니다. 서울-부산 예시로 말하면, 의정부 방향 물결은 애초에 일지 않는 거예요. 반세기가 지난 지금도 경로 탐색의 기본기가 A*인 이유입니다.

13. 좋은 휴리스틱의 조건: 낙관하되 과장하지 말 것

A*가 최적을 보장받는 조건은 딱 하나입니다. 휴리스틱이 남은 비용을 절대 과대평가하지 않을 것. 실제 남은 거리가 100km라면, 어림값은 100 이하여야 한다는 뜻입니다. "실제보다 부풀리지만 않으면 된다"는 거죠.

직선거리가 훌륭한 휴리스틱인 이유가 여기 있습니다. 실제 도로는 직선보다 짧을 수 없으니, 직선거리는 남은 거리를 절대 과장하지 않거든요. 왜 과장이 금지냐면 — 어떤 길의 남은 거리를 부풀려버리면, 사실은 최적인 그 길을 "너무 멀어 보인다"며 건너뛸 수 있기 때문입니다. 낙관적인 어림은 손해를 안 끼치지만, 과장된 어림은 정답을 놓치게 만듭니다.

재미있는 트레이드오프도 있어요. 어림이 실제에 가까울수록 탐색은 더 적은 상태만 보고 끝납니다(감이 정확할수록 헛걸음이 줄죠). 그래서 탐색 연구의 상당 부분은 사실 "더 정확하되 과장하지 않는 휴리스틱 만들기"였습니다. 감을 수학으로 다듬는 학문이라니, 꽤 멋지지 않나요.

14. 상대가 있는 탐색: 게임의 세계

지금까지의 탐색엔 암묵적 전제가 있었습니다. 지도가 가만히 있다는 것. 그런데 체스는 다릅니다. 내가 한 수를 두면, 나를 이기려는 상대가 다음 상태를 결정합니다. 지도가 살아서 저항하는 거예요.

이런 문제는 게임 트리로 그립니다. 현재 판이 뿌리, 내 가능한 수들이 첫 가지, 각 수에 대한 상대의 응수들이 그다음 가지, 다시 내 수, 다시 상대 수... 아래로 자라는 나무죠. 그리고 질문이 바뀝니다. "목표까지의 길"이 아니라, "상대가 최선을 다해 방해해도 내게 가장 유리한 수"를 찾아야 합니다.

이 질문에 답하는 고전 알고리즘이 2회차에서 이름만 스쳤던 미니맥스입니다. 이름부터 풀어보죠.

15. 미니맥스: 최악을 가정하는 지혜

미니맥스(minimax)의 사고방식은 체스 고수의 수읽기 그대로입니다. "내가 이 수를 두면 → 상대는 자기에게 최선(내겐 최악)인 응수를 할 테고 → 그럼 나는 그 상황에서 최선을 두고 → 상대는 또..." 이렇게 몇 수 앞까지 가지를 뻗은 뒤, 끝 지점의 유불리를 점수로 매기고, 그 점수를 거슬러 올라오며 계산합니다. 내 차례 층에선 최대(max) 점수를, 상대 차례 층에선 최소(min) 점수를 고르면서요. 이름이 min과 max의 합성인 이유입니다.

핵심 철학은 이겁니다. 상대가 실수하길 바라지 말고, 상대가 완벽하다고 가정한 뒤에도 가장 나은 수를 골라라. 희망 대신 보장을 택하는 전략이죠.

여기에 실전 필수 기술이 하나 붙습니다. 알파-베타 가지치기 — 계산 도중 "이 가지는 이미 다른 가지보다 나쁜 게 확정됐다" 싶으면 그 아래는 아예 보지 않고 잘라버리는 기법입니다. 결과는 동일하게 보장되면서 계산량은 극적으로 줄어요. 같은 시간에 몇 수를 더 깊이 읽을 수 있게 되는 거죠.

16. 딥블루의 비밀, 그리고 알파고의 진화

이제 2회차의 그 장면을 원리로 다시 볼 수 있습니다. 1997년 카스파로프를 꺾은 딥블루의 정체는 — 초당 수억 개의 판을 평가하는 전용 하드웨어 위에서 돌아간, 미니맥스 + 알파-베타 + 정교한 판 평가 함수였습니다. 마법이 아니라 탐색이었던 거예요. 1회차 오해 5("AI는 마법이다")의 살아있는 반례죠.

그런데 바둑에선 이 공식이 안 통했습니다. 가지가 너무 많아 가지치기로도 감당이 안 됐고, 무엇보다 바둑판의 유불리를 평가하는 함수를 사람이 만들 수 없었거든요. 2016년 알파고의 답은 탐색과 학습의 결합이었습니다. "어느 가지가 유망한가"와 "이 판이 유리한가"를 규칙이 아니라 딥러닝으로 배우게 하고, 그 직관으로 탐색을 안내한 겁니다. 고전 AI(탐색)와 현대 AI(학습)의 역사적 악수 — 3회차에서 예고한 그 장면의 정체입니다.

17. 오늘의 탐색: 당신 곁의 A*들

이제 실전 점검입니다. 오늘 배운 탐색이 2026년의 일상 어디에서 일하고 있을까요?

내비게이션과 지도 앱 — A* 계열 알고리즘이 도로망 위에서 시간·거리 비용을 계산합니다. 실시간 교통 정보로 비용이 계속 갱신되고, 머신러닝이 도착 시간을 예측해 얹죠(고전 탐색 + 학습의 하이브리드, 1회차에서 언급한 그대로예요). 게임 속 적 캐릭터 — 여러분을 쫓아오는 NPC의 이동 경로 대부분이 A*입니다. 게임 개발의 표준 기본기예요. 물류와 로봇 — 창고 로봇이 선반 사이를 누비는 경로, 배송 동선 최적화, 로봇청소기의 커버리지 계획에 탐색이 깔려 있습니다. 그 외에도 — 반도체 회로의 배선 경로, 네트워크 데이터의 전송 경로, 퍼즐 게임의 힌트 기능까지, 탐색은 이름 없이 어디에나 있습니다.

1회차의 판별 렌즈를 겹쳐보면 재미있죠. 이들 대부분은 '학습 없는 AI'입니다. 그런데도 훌륭하게 지능적인 일을 하고 있어요. 1회차에서 "머신러닝이 아닌 AI도 있다"고 했던 말이, 오늘 완전히 구체화된 겁니다.

18. 보너스: 탐색적 사고라는 도구

탐색은 컴퓨터만의 도구가 아닙니다. 사람의 문제 해결에도 그대로 쓸 수 있는 사고 틀이에요.

막막한 문제를 만나면 세 가지를 물어보세요. 지금 상태는 무엇인가? 목표 상태는 무엇인가? 내가 할 수 있는 행동은 무엇인가? 이것만으로 막연한 고민이 '지도 위의 길 찾기'로 바뀝니다. 이직 고민이라면 — 현재 상태(지금 직장·역량), 목표 상태(원하는 조건), 행동(이력서, 자격증, 네트워킹)으로 펼치는 순간 다음 한 걸음이 보이기 시작하죠.

휴리스틱도 챙기세요. 모든 선택지를 다 검토하는 건 인생에서도 조합 폭발입니다. "이 방향이 목표에 가까워지는가?"라는 어림 기준 하나로 대부분의 가지를 쳐내되, 탐욕의 함정(눈앞의 가까움만 좇다 막다른 길)만 조심하면 됩니다. AI를 배우는 게 곧 생각의 도구를 배우는 것이라는 걸 보여주는 첫 사례로 기억해 주세요.

19. 핵심 정리

오늘 배운 것을 세 줄로 요약합니다.

첫째, 탐색의 출발은 발상의 전환이다 — 어떤 문제든 상태·행동·목표로 정의하면 '상태 공간이라는 지도에서 길 찾기'가 되고, 미로·퍼즐·경로·게임이 전부 한 가지 문제로 통일된다.

둘째, 맹목 탐색(BFS는 최단 보장·무거움, DFS는 가벼움·무보장)은 조합 폭발의 벽에 막힌다. 돌파구는 '감'을 숫자로 바꾼 휴리스틱이며, A*는 '온 비용 + 남은 어림'의 덧셈으로 방향 감각과 최적 보장을 동시에 얻는다(단, 어림은 과장 금지).

셋째, 상대가 있는 게임은 미니맥스(상대가 완벽하다고 가정하고 최선 찾기)와 알파-베타 가지치기로 풀며, 딥블루가 그 정점이었다. 바둑에선 탐색에 학습을 결합한 알파고가 답을 냈고, 오늘날 내비·게임·물류 곳곳에서 탐색은 이름 없이 일하고 있다.

20. 용어 정리

상태 공간 — 문제의 가능한 모든 상황(상태)을 지점으로, 행동을 연결선으로 펼친 지도.

너비 우선 탐색(BFS) — 가까운 상태부터 물결처럼 층층이 훑는 방식. 최단 경로를 보장하지만 메모리를 많이 쓴다.

깊이 우선 탐색(DFS) — 한 갈래를 끝까지 파고든 뒤 되돌아오는 방식. 가볍지만 최단 보장이 없다.

맹목 탐색 — 목표의 방향 정보 없이 뒤지는 탐색(BFS·DFS). 조합 폭발에 취약하다.

휴리스틱 — 어떤 상태에서 목표까지 남은 비용을 빠르게 어림하는 계산. 탐색에 방향 감각을 준다.

A* — '지금까지 온 실제 비용 + 남은 어림 비용'이 가장 작은 후보부터 탐색하는 알고리즘. 휴리스틱이 과대평가만 안 하면 최적을 보장한다.

게임 트리 — 나와 상대의 수가 번갈아 가지를 치며 자라는, 대결 상황의 상태 공간.

미니맥스 — 상대가 완벽하게 둔다고 가정하고, 내 차례엔 최대·상대 차례엔 최소 점수를 골라 올라오며 최선 수를 찾는 알고리즘.

알파-베타 가지치기 — 결과가 이미 뒤처짐이 확정된 가지를 잘라 미니맥스 계산량을 줄이는 기법.

21. 생각해볼 질문

오늘의 과제는 실습형입니다. 여러분이 요즘 고민 중인 문제 하나를 골라 상태 공간으로 펼쳐보세요 — 현재 상태, 목표 상태, 가능한 행동 세 가지만 적으면 됩니다. 그리고 여러분만의 휴리스틱("어느 방향이 목표에 가까워지는 걸까"를 판단하는 기준)을 한 줄로 만들어 보세요. 문제를 지도로 바꾸는 순간 무엇이 달라졌는지, 그 경험을 댓글로 나눠주시면 다음 회차에서 흥미로운 사례를 함께 이야기하겠습니다.

22. 다음 회차 예고

다음 시간은 제1부의 마지막, 「지식 표현과 논리」입니다. 탐색이 '길 찾는 다리'였다면, 다음 주제는 '아는 것을 담는 머리'입니다. 컴퓨터에 지식을 어떻게 적어 넣을까요? "새는 난다, 펭귄은 새다, 그런데 펭귄은 못 난다" — 이 흔한 상식이 왜 컴퓨터에겐 악몽인지, 1970~80년대 전문가 시스템이 어떻게 영광과 몰락을 오갔는지(3회차의 그 이야기를 원리로 다시 봅니다), 그리고 규칙 기반 AI가 2026년에도 살아남은 곳은 어디인지. 기호주의의 심장부로 들어가는 마지막 역사+원리 여행, 5회차에서 만나요!

이 포스트는 SVIL 연구소 「AI 기초 및 활용」 30회 시리즈의 4회차입니다. 하버드 CS50 AI, MIT 6.S191 등 공개 교육과정의 구조를 참고해 2026년 7월 기준으로 작성했으며, 모든 내용은 이미지 없이 본문만으로 이해할 수 있도록 구성되어 있습니다. 모든 이미지에는 내용을 설명하는 대체텍스트가 포함되어 있습니다.