🇺🇸 USC 빅데이터 컨퍼런스 참가기🇺🇸 |[USC AI/DS] Lesson 3. Problem Solving via Search

학교에서 컴퓨팅 문제와 알고리즘이라는 과목을 들을 때 배웠던 내용들이 거의 대다수 등장한 단원이었다.

기초적인 그래프 탐색을 시작으로
그래프와 트리의 개념, 그리고 대표적인 탐색 알고리즘인 BFS와 DFS를 다룬다.

그런데 이번 강의에서는 단순히

DFS는 깊게 탐색한다.
BFS는 넓게 탐색한다.

정도에서 끝나지 않았다.

조금 더 근본적인 관점에서

컴퓨터가 어떤 문제를 '탐색 문제'로 바꾸고, 그 안에서 해답을 어떻게 찾아가는가?

를 설명했다.

그리고 BFS와 DFS뿐만 아니라

• Uniform Cost Search
• Depth-Limited Search
• Iterative Deepening Search

와 같은 탐색 전략도 함께 다뤘다.

개인적으로 알고리즘 수업에서 이미 공부했던 내용이라 익숙한 부분도 많았지만,
이번에는 이를 AI의 Problem-Solving Agent 관점에서 바라본다는 점이 재미있었다.

---

Problem Solving이란 무엇일까?

강의에서는 문제 해결을 굉장히 추상적으로 정의한다.

어떤 문제에는 현재 상태가 있고,

Initial State

우리가 도달하고 싶은 상태가 있다.

Goal State

그리고 현재 상태를 다른 상태로 변화시키는 행동이 존재한다.

Operator / Action

결국 문제 해결이라는 것은

Initial State
↓
Action
↓
State
↓
Action
↓
State
↓
...
↓
Goal State

처럼 초기 상태에서 목표 상태까지 도달할 수 있는 행동의 순서를 찾는 것이라고 볼 수 있다.

예를 들어 길 찾기를 생각해보자.

현재 위치 : 전북대학교
목표 위치 : 전주역

그리고 내가 할 수 있는 행동은

버스를 탄다.
택시를 탄다.
걷는다.

등이 될 수 있다.

컴퓨터 입장에서는 결국

"어떤 행동들을 어떤 순서로 수행해야 목표 상태까지 갈 수 있을까?"

를 찾아내는 것이 문제 해결이다.

강의에서는 특히 가능하면 최소의 연산 또는 최소 비용으로 목표 상태에 도달하는 것을 중요하게 다룬다.

---

Offline Problem Solving과 Online Problem Solving

여기서 문제 해결 방식도 두 가지로 나눌 수 있다.

Offline Problem Solving

Offline Problem Solving은
실제로 행동하기 전에 해결 방법을 먼저 찾아놓는 방식이다.

문제 분석
↓
해결 경로 탐색
↓
경로 결정
↓
실제 행동

말 그대로 계획을 모두 세운 뒤 움직인다.

예를 들어 내비게이션이 경로를 먼저 계산하고

전북대
→ 백제대로
→ 기린대로
→ 전주역

이라는 길을 알려주는 것과 비슷하다.

강의에서는 이를 약간 재미있게

solution executed "eyes closed"

라고 표현했다.

이미 해결 방법을 알고 있기 때문에
그 계획을 그대로 실행하면 된다는 의미다.

---

Online Problem Solving

반대로 Online Problem Solving은
환경에 대한 정보를 완전히 알지 못하는 상태에서 행동한다.

행동
↓
새로운 정보 획득
↓
다음 행동 결정
↓
새로운 정보 획득
↓
...

예를 들어 미로 전체 지도를 모르는 상태에서
직접 움직이며 길을 찾는 로봇을 생각하면 된다.

이 경우에는

탐색 → 행동 → 관찰 → 다시 탐색

이 반복된다.

---

Problem의 종류

강의에서는 문제를 환경에 대한 정보가 얼마나 주어지는지에 따라 여러 종류로 나누었다.

처음에는 용어가 조금 복잡해 보였는데
결국 핵심은

현재 상황을 얼마나 정확하게 알고 있는가?

라고 생각하면 이해하기 쉬웠다.

---

Single-State Problem

가장 단순한 경우다.

환경이 Deterministic하고 Fully Observable하다.

즉,

현재 내가 어디 있는지 정확히 알고 있고
+
어떤 행동을 했을 때 어떤 결과가 나오는지도 알고 있다.

예를 들어

A → B → C → Goal

이라는 길을 정확하게 알고 있다면

Right
Right
Right

와 같은 행동 Sequence를 만들면 된다.

우리가 코딩테스트에서 일반적으로 풀게 되는
그래프 탐색 문제 대부분은 이런 형태라고 볼 수 있다.

---

Conformant Problem

이번에는 현재 상태를 정확하게 알 수 없다.

즉 Non-observable 환경이다.

센서가 없어서 내가 정확히 어떤 상태인지 모르지만
그래도 모든 경우를 고려해서 목표에 도달해야 한다.

이때는 단순한 물리적인 State 하나가 아니라

현재 존재할 가능성이 있는 State들의 집합

을 고려하게 된다.

강의에서는 이를 Belief State라고 표현한다.

---

Contingency Problem

환경이

Nondeterministic
또는
Partially Observable

한 경우다.

행동의 결과가 항상 동일하지 않을 수도 있고
환경의 일부 정보만 관찰할 수도 있다.

따라서 해결 방법도 단순한 하나의 Action Sequence가 아니라

만약 A라면 → 행동 1
만약 B라면 → 행동 2

같은 조건부 계획(Contingent Plan) 또는 Policy가 된다.

즉,

Search
↓
Execution
↓
새로운 정보
↓
Search

가 반복될 수 있다.

---

Vacuum World

강의에서는 이러한 차이를 설명하기 위해
AI 분야에서 자주 등장하는 Vacuum World 예제를 사용했다.

청소기가 두 공간을 이동하면서
먼지를 제거하는 매우 단순한 환경이다.

청소기가 수행할 수 있는 행동은

Left
Right
Vacuum
NoOp

정도다.

목표는 단순하다.

모든 공간에 먼지가 없는 상태

이다.

Single-State Problem이라면 현재 청소기 위치와
먼지가 어디 있는지 모두 알고 있으므로

Right
Vacuum

같은 명확한 해결 방법을 만들 수 있다.

하지만 현재 위치나 먼지의 위치를 알 수 없다면
가능한 모든 상태를 고려해야 한다.

그리고 환경이 불확실하다면

Right
if dirt then Vacuum
Left
if dirt then Vacuum
...

처럼 조건에 따라 행동을 결정해야 한다.

결국 같은 청소 문제라도

환경에 대한 정보를 얼마나 알고 있느냐에 따라 문제의 형태가 완전히 달라진다.

---

그렇다면 문제를 어떻게 표현할까?

이제부터가 그래프 탐색과 직접적으로 연결되는 부분이다.

강의에서는 하나의 Single-State Problem을 네 가지 요소로 정의한다.

1. Initial State
2. Successor Function
3. Goal Test
4. Path Cost

하나씩 살펴보자.

---

1. Initial State

탐색이 시작되는 상태다.

예를 들어 루마니아의 도시 간 길 찾기 문제에서

현재 위치 = Arad

라면

Initial State = Arad

가 된다.

---

2. Successor Function

현재 상태에서
다음으로 이동할 수 있는 상태들을 정의한다.

예를 들어 Arad에서 직접 갈 수 있는 도시가

Zerind
Sibiu
Timisoara

라면

S(Arad)
=
{Zerind, Sibiu, Timisoara}

정도로 생각할 수 있다.

즉,

현재 상태에서 어떤 행동을 수행할 수 있으며 그 결과 어떤 상태가 되는가?

를 정의한다.

코딩테스트에서 그래프의 인접 노드를 찾는 것과 거의 같다.

---

3. Goal Test

현재 상태가 우리가 원하는 목표인지 검사한다.

예를 들어 목적지가 Bucharest라면

현재 도시 == Bucharest ?

를 검사하면 된다.

이처럼 목표가 정확한 하나의 상태로 주어질 수도 있고,

청소기 문제처럼

모든 먼지가 제거되었는가?

처럼 조건 형태로 정의될 수도 있다.

---

4. Path Cost

목표까지 이동하는 데 필요한 비용이다.

예를 들어 도시 간 이동에서는

거리

가 비용이 될 수 있다.

반면 퍼즐에서는

한 번 이동 = 비용 1

이라고 정의할 수도 있다.

그러면 전체 경로 비용은

각 이동 비용의 합

이 된다.

결국 우리가 원하는 것은 단순히 Goal에 도착하는 경로가 아니라
경우에 따라서는

Goal까지 가는 경로 중 가장 비용이 작은 경로

일 수 있다.

---

State Space, Problem Space

이제 문제를 그래프로 표현할 수 있다.

강의에서는 이를 State Space, 또는 Problem Space라고 부른다.

State Space는 결국 하나의 Graph다.

Node
→ 문제에서 가능한 State

Edge
→ 한 State에서 다른 State로 이동할 수 있는 Action

예를 들어

A → B → C
     ↓
     D → Goal

이라는 구조가 있다면

A, B, C, D, Goal은 각각 State이고
화살표는 가능한 Action을 의미한다.

즉,

문제를 그래프로 바꾸고, 그래프에서 Initial State부터 Goal State까지의 경로를 찾는 것

이 Search Problem이라고 볼 수 있다.

---

Romania Route Finding

강의에서는 이러한 구조를 설명하기 위해
루마니아의 도시 지도를 사용한다.

예를 들어 현재 위치가

Arad

이고 목적지가

Bucharest

라고 해보자.

그러면 문제를 다음과 같이 정의할 수 있다.

Initial State
= Arad

States
= 각 도시

Actions
= 연결된 도시로 이동

Goal
= Bucharest

Path Cost
= 도시 간 거리

그러면 문제는 완전히 그래프 탐색 문제가 된다.

Arad
↓
Sibiu
↓
Fagaras
↓
Bucharest

같은 경로를 찾을 수 있다.

물론 이 경로가 항상 가장 짧은 경로라는 의미는 아니다.

이후 어떤 Search Strategy를 사용하느냐에 따라
찾게 되는 경로가 달라질 수 있다.

---

8-Puzzle도 결국 Graph 문제다

다음 예제는 8-Puzzle이다.

3×3 칸 안에서 하나의 빈칸을 이동시키면서
숫자를 목표 배열로 만드는 퍼즐이다.

처음 보면 그래프와 별로 관련이 없어 보인다.

하지만 이것도 State Space로 표현할 수 있다.

하나의 퍼즐 배치를

State

라고 생각한다.

그리고 빈칸을

Left
Right
Up
Down

으로 움직이는 것을 Action으로 생각한다.

그러면

현재 퍼즐
↓
빈칸 이동
↓
새로운 퍼즐

이 된다.

즉 각각의 퍼즐 배치가 Node이고
한 번의 이동이 Edge인 거대한 Graph가 만들어진다.

Goal Test는

현재 퍼즐 == 목표 퍼즐

이고,

한 번 움직일 때 비용을 1이라고 두면

Path Cost = 이동 횟수

가 된다.

처음에는 완전히 다른 문제처럼 보이지만
추상화하고 나면 결국 같은 그래프 탐색 문제라는 점이 재미있다.

---

Graph란 무엇인가?

여기서 그래프의 기본 개념도 다시 다뤘다.

그래프는 크게

Node(Vertex)
Edge

로 구성된다.

Node는 하나의 State를 나타내고
Edge는 Node 사이의 연결 관계를 의미한다.

강의에서는 주로 Directed Graph를 기준으로 설명한다.

A → B

가 있다고 해서 반드시

B → A

가 존재하는 것은 아니다.

그리고 연결된 Node들을 따라가는 순서를 Path라고 한다.

예를 들어

A → B → C → D

가 하나의 Path다.

Edge가 3개이므로 이 경로의 길이는 3이고
포함된 Node의 개수는 4개다.

---

Search Graph와 Search Tree는 다르다

여기에서 개인적으로 다시 한번 정리할 만했던 부분이 있었다.

바로

State Space Graph

와

Search Tree

의 차이다.

State Space Graph에서는
하나의 State는 기본적으로 한 번만 존재한다.

하지만 Search Tree에서는 같은 State가 여러 번 등장할 수 있다.

왜냐하면 Search Tree의 Node는 단순히 State 하나를 표현하는 것이 아니라

그 State에 도달하기까지의 전체 경로

를 표현하기 때문이다.

예를 들어

S → A → C

와

S → B → C

가 있다고 해보자.

State Space Graph에서는 C라는 Node가 하나만 존재한다.

하지만 Search Tree에서는

S-A-C

S-B-C

라는 서로 다른 경로가 있기 때문에
C가 두 번 등장할 수 있다.

따라서 Search Tree에는 상당히 많은 중복 구조가 생길 수 있다.

---

State Node와 Tree Node도 다르다

State 자체와
Search 과정에서 사용하는 Tree Node도 구분해야 한다.

State는 말 그대로

현재 세계의 상태

다.

하지만 Tree Node는 탐색 알고리즘을 수행하기 위해 사용하는 자료구조이기 때문에
다음과 같은 정보도 가지고 있을 수 있다.

State
Parent
Children
Depth
Path Cost
Action

즉,

State ≠ Search Tree Node

라고 이해하면 된다.

---

Search의 핵심, Frontier

Search Algorithm에서 매우 중요한 개념이 하나 등장한다.

바로 Frontier, 또는 Fringe다.

Frontier는

아직 탐색해야 할 후보 Node들의 집합

이라고 생각하면 된다.

탐색 과정을 굉장히 단순하게 표현하면 다음과 같다.

Start Node를 Frontier에 넣는다.

while Frontier가 비어있지 않다면

    Frontier에서 Node 하나를 선택한다.

    Goal인지 확인한다.

    Goal이라면 종료한다.

    아니라면 Neighbor들을 Frontier에 넣는다.

여기서 정말 중요한 부분은

Frontier에서 "어떤 Node를 먼저 선택할 것인가?"

이다.

이 선택 방식이 바로 Search Strategy가 된다.

---

Search Strategy를 평가하는 기준

탐색 알고리즘은 단순히

답을 찾았는가?

만으로 평가하지 않는다.

강의에서는 네 가지 기준을 사용한다.

Completeness

해답이 존재한다면 반드시 찾을 수 있는가?

Time Complexity

얼마나 많은 Node를 생성하고 탐색해야 하는가?

Space Complexity

얼마나 많은 Node를 메모리에 저장해야 하는가?

Optimality

찾은 답이 최소 비용의 최적해인가?

이 네 가지 기준으로
각 탐색 알고리즘의 특징을 비교할 수 있다.

---

Uninformed Search

이번 강의에서 다루는 탐색 전략은
주로 Uninformed Search다.

말 그대로 추가적인 정보 없이
문제 정의에 주어진 정보만으로 탐색한다.

대표적인 방법은 다음과 같다.

Breadth-First Search
Uniform-Cost Search
Depth-First Search
Depth-Limited Search
Iterative Deepening Search

---

BFS : Breadth-First Search

먼저 코딩테스트에서 정말 자주 등장하는 BFS다.

BFS는

가장 얕은 Node부터 탐색한다.

예를 들어 다음 Tree가 있다고 해보자.

        A
      /   \
     B     C
    / \   / \
   D   E F   G

BFS의 탐색 순서는

A
↓
B, C
↓
D, E, F, G

가 된다.

즉,

A → B → C → D → E → F → G

처럼 Level 단위로 탐색한다.

---

BFS는 왜 Queue를 사용할까?

BFS에서는 먼저 들어온 Node를 먼저 탐색해야 한다.

따라서 FIFO(First In First Out) 구조가 필요하다.

바로 Queue다.

Queue

A 삽입

A 제거
B, C 삽입

B 제거
D, E 삽입

C 제거
F, G 삽입

이런 방식으로 탐색한다.

그래서 BFS 구현을 보면 거의 항상

queue<Node> q;

가 등장한다.

---

BFS의 장점

BFS의 가장 중요한 특징은

Edge의 비용이 모두 같다면 최단 경로를 찾을 수 있다는 것

이다.

예를 들어 모든 이동 비용이 1이라면

한 번 이동
두 번 이동
세 번 이동
...

순서로 탐색하기 때문에
Goal을 처음 발견했을 때의 경로가 가장 짧다.

그래서

미로 최단 거리
게임 맵 최단 거리
최소 이동 횟수

같은 문제에서 BFS를 많이 사용한다.

최근 프로그래머스의 게임 맵 최단거리 문제를 풀면서
DFS로 접근했다가 효율성 테스트에서 시간 초과가 났던 이유도 이것과 연결된다.

최단 경로를 찾는 문제인데 모든 경로를 끝까지 확인하려고 했던 것이다.

---

BFS의 단점

문제는 Memory다.

BFS는 같은 Level의 Node들을 모두 Frontier에 저장해야 한다.

Branching Factor를 b,
가장 가까운 해답의 깊이를 d라고 하면
탐색해야 하는 Node의 수는 대략 지수적으로 증가한다.

1
+ b
+ b²
+ b³
+ ...
+ bᵈ

따라서 시간뿐만 아니라
메모리 사용량이 매우 커질 수 있다.

강의에서도 BFS에서 특히 Space Complexity가 큰 문제라고 강조했다.

---

DFS : Depth-First Search

다음은 DFS다.

DFS는 BFS와 완전히 반대다.

현재 갈 수 있는 곳까지 최대한 깊게 들어간다.

예를 들어 같은 Tree가 있다고 해보자.

        A
      /   \
     B     C
    / \   / \
   D   E F   G

더 아래에 Node가 존재한다고 가정하면
DFS는 대략

A
↓
B
↓
D
↓
D의 자식
↓
...

처럼 한쪽 끝까지 내려간다.

더 이상 갈 곳이 없으면 다시 돌아와
다른 경로를 탐색한다.

---

DFS는 왜 Stack을 사용할까?

DFS에서는 가장 최근에 발견한 Node를 먼저 탐색한다.

따라서

LIFO
Last In First Out

구조가 적합하다.

즉 Stack이다.

그리고 재귀 함수도 내부적으로 Call Stack을 사용하기 때문에
DFS를 재귀로 구현하는 경우가 굉장히 많다.

void dfs(int node) {

    visited[node] = true;

    for (int next : graph[node]) {

        if (!visited[next]) {
            dfs(next);
        }
    }
}

나도 그래프 문제를 보면 가장 먼저 떠오르는 방식이
이 재귀 DFS인 것 같다.

---

DFS의 장점

DFS의 가장 큰 장점은 메모리다.

BFS는 각 Level의 Node를 대부분 보관해야 하지만
DFS는 현재 탐색 중인 경로 중심으로 정보를 가지고 있으면 된다.

그래서 일반적으로 BFS보다 훨씬 적은 메모리를 사용할 수 있다.

또한 정답이 깊은 위치에 있고
운 좋게 해당 방향부터 탐색한다면 매우 빠르게 답을 찾을 수도 있다.

---

DFS의 단점

하지만 DFS에는 중요한 문제가 있다.

먼저 최단 경로를 보장하지 않는다.

예를 들어

A → B → C → D → E → Goal

이라는 경로를 먼저 발견했더라도

실제로는

A → F → Goal

이라는 훨씬 짧은 경로가 존재할 수 있다.

DFS는 첫 번째 Goal을 찾았다고 해서
그것이 최적이라는 보장이 없다.

또한 Cycle이 존재하는 Graph에서 방문 처리를 하지 않으면

A → B → C → A → B → C → ...

처럼 무한히 반복될 수도 있다.

그래서 실제 구현에서는 보통

visited[]

를 사용한다.

---

BFS와 DFS를 비교해보면

둘의 차이를 가장 단순하게 표현하면 다음과 같다.

BFS	DFS
넓게 탐색	깊게 탐색
Queue	Stack / Recursion
얕은 Solution에 유리	깊은 Solution에 유리할 수 있음
동일 비용에서 최단 경로 보장	최단 경로 보장 X
메모리 사용량이 큼	상대적으로 메모리 효율적

결국

DFS와 BFS 중 무엇이 더 좋은 알고리즘인가?

라는 질문은 의미가 없다.

문제가 무엇을 요구하는지를 먼저 봐야 한다.

---

Uniform Cost Search

여기에서 BFS의 한계가 하나 등장한다.

BFS는 이동 횟수가 가장 적은 경로를 찾는다.

하지만

이동 횟수가 적다
=
비용이 가장 작다

는 항상 성립하지 않는다.

예를 들어

A → B → Goal

이라는 경로의 비용이

A → B = 100
B → Goal = 100

Total = 200

이라고 해보자.

반면

A → C → D → Goal

은 이동 횟수는 더 많지만

10 + 10 + 10 = 30

일 수도 있다.

BFS는 이동 횟수만 보면 첫 번째 경로를 선택할 수 있다.

하지만 진짜 최소 비용 경로는 두 번째다.

이 문제를 해결하는 것이 Uniform Cost Search(UCS)다.

---

Uniform Cost Search의 핵심

UCS는 Frontier에서

가장 Path Cost가 작은 Node

부터 선택한다.

따라서 일반 Queue가 아니라
Priority Queue를 사용한다.

Frontier

Path Cost 3
Path Cost 7
Path Cost 12

가 있다면 항상 Cost 3부터 탐색한다.

즉,

지금까지 들어간 비용이 가장 작은 경로부터 확장한다.

모든 Step Cost가 동일하다면
UCS는 BFS와 동일하게 동작한다.

그리고 적절한 양의 Step Cost 조건에서는
최소 비용의 Optimal Solution을 찾을 수 있다.

---

Depth-Limited Search

DFS의 가장 큰 문제 중 하나는

끝없이 깊게 들어갈 수 있다.

는 것이다.

그래서 아예 깊이에 제한을 둘 수 있다.

이것이 Depth-Limited Search다.

예를 들어

Depth Limit = 3

이라고 하면

Depth 0
Depth 1
Depth 2
Depth 3

까지만 탐색하고
그 아래는 탐색하지 않는다.

쉽게 말하면

DFS에 최대 깊이 제한을 추가한 방식

이다.

---

Iterative Deepening Search

그런데 Depth Limit을 얼마로 설정해야 할까?

1?
3?
10?
100?

정답이 어디에 있는지 모르기 때문에
적절한 값을 미리 결정하기 어렵다.

그래서 나온 방법이 Iterative Deepening Search(IDS)다.

아이디어는 매우 단순하다.

Depth Limit = 0으로 DFS

없으면

Depth Limit = 1로 DFS

없으면

Depth Limit = 2로 DFS

없으면

Depth Limit = 3로 DFS

...

정답이 나올 때까지 Depth Limit을 계속 증가시킨다.

---

그런데 같은 Node를 계속 다시 탐색하는 것 아닌가?

나도 이 부분을 보고 처음에는

"이거 너무 비효율적인 것 아닌가?"

라는 생각이 들었다.

예를 들어 Depth 3까지 가려면

Depth 1 탐색
Depth 2 탐색
Depth 3 탐색

을 반복하므로
위쪽 Node를 여러 번 방문하게 된다.

그런데 Tree 탐색에서는 보통
가장 마지막 Level의 Node 수가 압도적으로 많다.

예를 들어 Branching Factor가 10이면

Depth 0 → 1개
Depth 1 → 10개
Depth 2 → 100개
Depth 3 → 1,000개
Depth 4 → 10,000개

가 된다.

즉 상위 Level을 몇 번 반복하는 비용보다
가장 깊은 Level을 탐색하는 비용이 훨씬 크다.

그래서 생각보다 반복 탐색의 손해가 크지 않다.

---

IDS는 BFS와 DFS의 장점을 섞는다

Iterative Deepening의 목적은 꽤 명확하다.

DFS의 낮은 Memory 사용량

+

BFS의 얕은 Solution 탐색 능력

을 함께 얻는 것이다.

강의에서도

DFS의 Space Advantage와 BFS의 Shallow-Solution Advantage를 함께 얻는 방식

으로 설명했다.

Step Cost가 동일한 경우
IDS 역시 얕은 Goal부터 발견하기 때문에 Optimal Solution을 찾을 수 있다.

---

결국 Search Strategy의 차이는 무엇일까?

여기까지 보고 나니 탐색 알고리즘들이
사실 완전히 다른 알고리즘처럼 느껴지지 않았다.

기본 구조는 거의 동일하다.

Frontier에서 Node를 하나 꺼낸다.
↓
Goal인지 확인한다.
↓
Neighbor를 추가한다.
↓
반복한다.

달라지는 것은 딱 하나다.

Frontier에서 어떤 Node를 먼저 꺼낼 것인가?

이다.

BFS는

가장 얕은 Node

DFS는

가장 깊은 Node

Uniform Cost Search는

현재까지 비용이 가장 작은 Node

를 선택한다.

이 선택 기준이 달라지면서
알고리즘의 성질도 완전히 달라진다.

---

Search Algorithm 비교

강의 마지막에는 지금까지 다룬 Search Algorithm을
Completeness, Time, Space, Optimality 관점에서 비교했다.

큰 특징만 정리하면 다음과 같다.

Algorithm	Complete	Optimal	핵심 특징
BFS	O	Step Cost가 동일하면 O	얕은 Node부터 탐색
Uniform Cost	O	O	Path Cost가 작은 순서로 탐색
DFS	일반적으로 X	X	깊게 탐색, Memory 효율적
Depth-Limited	Limit에 따라 결정	X	DFS에 최대 깊이 설정
Iterative Deepening	O	Step Cost가 동일하면 O	DFS의 Memory + BFS의 장점

결국 어떤 알고리즘을 사용할지는
문제가 무엇을 요구하느냐에 따라 달라진다.

---

수업을 듣고 나서

이번 Lesson은 개인적으로 다른 단원보다 훨씬 익숙했다.

학교에서 컴퓨팅 문제와 알고리즘 과목을 들으며
Graph, Tree, BFS, DFS 같은 내용을 이미 공부했기 때문이다.

그때는 주로

DFS 구현하기
BFS 구현하기
최단 경로 찾기
그래프 탐색하기

같은 알고리즘 자체에 집중했던 것 같다.

하지만 이번 강의에서는 조금 더 상위 개념에서 접근했다.

현실의 문제
↓
State와 Action으로 추상화
↓
State Space 구성
↓
Graph로 표현
↓
Search Strategy 선택
↓
Solution 탐색

이라는 전체 흐름으로 바라본다.

그래서 예전에는

"그래프가 주어졌으니까 BFS를 사용한다."

정도로 생각했다면,

이번에는

"현실의 문제 자체를 State Space로 표현하면 결국 Graph Search Problem으로 바꿀 수 있구나."

라는 생각을 하게 되었다.

이 차이가 생각보다 컸다.

---

특히 BFS와 DFS를 다시 생각하게 됐다

코딩테스트를 풀다 보면
DFS와 BFS 문제를 정말 많이 만나게 된다.

그런데 막상 문제를 보면 나도 가끔

그래프 문제네?
→ 일단 DFS?

처럼 습관적으로 접근할 때가 있다.

최근 프로그래머스의 게임 맵 최단거리 문제에서도
처음에는 별 생각 없이 DFS 재귀를 작성했다.

정답 자체는 나왔지만
모든 경로를 계속 탐색하다 보니 효율성 테스트에서 시간 초과가 발생했다.

문제에서 요구한 것은

도착 가능한가?

가 아니라

최소 몇 칸을 지나야 하는가?

였다.

즉 동일한 비용의 Graph에서 최단 경로를 찾는 문제였고
이 경우에는 Level 순서대로 탐색하는 BFS가 훨씬 자연스러운 선택이었다.

이번 강의를 들으면서 다시 느꼈다.

알고리즘을 구현할 줄 아는 것도 중요하지만,
문제의 특성을 보고 어떤 Search Strategy를 선택해야 하는지를 판단하는 것이 훨씬 중요하다.

---

마무리

이번 Lesson 3의 핵심을 한 문장으로 정리하면 다음과 같다.

Problem Solving은 결국 가능한 State들을 탐색하면서 Initial State에서 Goal State까지의 경로를 찾는 과정이다.

그리고 많은 문제를

State
Action
Goal
Cost

로 추상화하면
Graph Search Problem으로 표현할 수 있다.

그 Graph를 어떤 순서로 탐색하느냐에 따라

BFS
DFS
Uniform Cost Search
Depth-Limited Search
Iterative Deepening Search

와 같은 서로 다른 Search Strategy가 만들어진다.

예전에 배웠던 DFS와 BFS를 다시 복습한 단원이기도 했지만,
이번에는 단순한 알고리즘 구현을 넘어

왜 Search가 문제 해결의 기본 구조가 되는가

를 이해할 수 있었던 단원이었다.