2026-04-16 TIL (38일차)
게임 수학
• 벡터(Vector)의 이해
PDF가 확대해도 깨지지 않는 이유를 통해 벡터를 통해 설명하겠습니다.
- 비트맵(jpg)과의 차이: 일반 이미지는 픽셀을 강제로 늘리기 때문에 해상도가 깨지지만, 벡터 이미지는 점들의 ‘위치’와 ‘방향’을 수학적 벡터로 해석합니다.
- 실수배(스칼라 곱): 이미지를 확대한다는 것은 이미지를 잡아 늘리는 것이 아니라, 원점을 기준으로 하는 위치 벡터에 ‘실수배(스칼라 곱)’를 하여 좌표(위치) 자체를 재계산하여 이동시키는 것입니다.
- 점 = 벡터: 원점을 시작점으로 잡으면, 좌표평면 위의 모든 ‘점’은 곧 ‘벡터’로 표현할 수 있습니다. (위치 벡터의 개념)
• 벡터의 핵심 수학적 개념
벡터의 크기와 노름
벡터는 ‘방향’과 ‘크기’를 가지는 데이터입니다. 여기서 벡터의 크기를 수학적으로 노름(Norm)이라고 부릅니다.
- 표기법: 벡터 v의 크기(노름)는 절대값 기호와 유사하게
||v||또는|v|로 표기합니다. - 계산법: 피타고라스의 정리를 이용합니다. 2차원 벡터 v = (x, y)가 있을 때, 노름은 다음과 같이 계산합니다.
||v|| = √(x² + y²) - 활용: 3D 그래픽이나 게임에서 두 캐릭터 사이의 ‘거리’나 이동하는 개체의 ‘속력’을 구할 때 사용됩니다.
벡터의 이동 (Translation)과 위치 벡터
- 자유 벡터 (Free Vector): 벡터의 본질은 오직 ‘크기’와 ‘방향’뿐입니다. 따라서 시작점(시점)이 어디에 있든 크기와 방향만 같다면 모두 동일한 벡터로 취급합니다. 즉, 화면 이리저리 평행 이동시켜도 벡터가 가지는 의미는 변하지 않습니다.
- 위치 벡터 (Position Vector): 하지만 계산의 편의를 위해, 모든 벡터의 시작점을 원점(0,0)으로 고정시켜서 생각하는 경우가 많습니다. 시작점이 고정되면 도착점의 좌표 하나만으로 벡터를 표현할 수 있기 때문입니다.
• 단위 벡터와 정규화
정규화란 무엇인가?
정규화란 크기가 제각각인 일반 벡터의 방향은 그대로 유지한 채, 크기(길이)만 정확히 1로 맞추는 작업입니다. 이렇게 정규화된 크기가 1인 벡터를 단위 벡터(Unit Vector)라고 부르며, 기호로는 머리 위에 모자를 씌워 u^ (햇 기호) 등으로 표기합니다.
- 계산 방법: 원래의 벡터를 자신의 ‘크기(노름)’로 나누어주면 됩니다.
단위 벡터 = 원래 벡터 / 벡터의 크기
정규화를 왜 하는 걸까? (실무적 이유)
단순히 크기를 1로 맞추는 것 같지만, 컴퓨터 그래픽스나 게임 엔진에서는 다음 세 가지 핵심적인 이유 때문에 숨 쉬듯이 정규화를 사용합니다.
1. 순수한 ‘방향’ 데이터만 추출하기 위해 때로는 힘의 세기나 거리는 전혀 알 필요가 없고, 어느 쪽을 향하고 있는지만 알아야 할 때가 있습니다. (예: 3D 캐릭터가 바라보는 시선 방향, 태양빛이 내리쬐는 조명 방향 등). 크기를 1로 통일해 버리면, 크기 변수에 간섭받지 않고 오직 ‘방향’ 정보만을 안전하게 다룰 수 있습니다.
2. 대각선 이동 속도 보정 캐릭터를 키보드 방향키로 이동시킨다고 가정해 봅시다.
- 위로 이동
(0, 1)-> 크기는 1 - 오른쪽 이동
(1, 0)-> 크기는 1 - 대각선 이동
(1, 1)-> 크기는 √(1² + 1²) = √2 (약 1.414)
만약 정규화를 하지 않으면 대각선으로 이동할 때 가로/세로로 갈 때보다 약 1.4배 더 빠르게 이동하는 버그가 생깁니다. 입력받은 이동 벡터를 정규화하여 크기를 1로 강제하면, 어느 방향으로 이동하든 항상 일정한 속도를 유지할 수 있습니다.
3. 수학적 연산(내적/외적)의 편의성 두 벡터의 ‘내적(Dot Product)’을 계산할 때, 두 벡터가 모두 정규화된 단위 벡터라면 내적의 결과값은 오직 두 벡터가 이루는 각도(코사인 값)만을 의미하게 됩니다. 이를 통해 몬스터가 내 캐릭터의 시야각 안에 있는지 판별하거나, 3D 모델링 표면에 빛이 얼마나 밝게 반사될지 계산하는 등 그래픽 처리를 매우 빠르고 효율적으로 할 수 있습니다.
전체적인 로직의 흐름(방향 구하기 ➔ 정규화 ➔ 속도 곱하기)은 100점 만점에 100점입니다! 원리를 완벽하게 꿰뚫어 보셨습니다.
다만, 방향 벡터를 구할 때 ‘빼는 순서’ 하나만 살짝 교정해 주면 완벽한 코드가 됩니다. 직관적으로 헷갈리기 쉬운 부분인데, 무조건 “도착점(목표) - 출발점(현재)” 순서로 빼야 합니다.
작성하신 내용을 바탕으로, TIL이나 블로그에 바로 올리실 수 있도록 깔끔한 마크다운 코드로 정리해 드립니다.
Markdown
벡터의 정규화(Normalize) 실전 활용: 적이 플레이어 추적하기
상황 가정
- 플레이어 위치(도착점): $(3, 4)$
- 적의 위치(출발점): $(1, -1)$
- 목표: 적이 플레이어를 향해 일정한 속도(Speed)로 이동하게 만들기
Step 1: 방향 벡터 구하기 (목표 위치 - 내 위치)
가장 먼저 적이 어느 방향으로 가야 할지 구해야 합니다. 방향을 구할 때는 반드시 목표(도착점) - 현재(출발점) 순서로 빼야 합니다.
- 잘못된 예 (적 - 플레이어): $(1, -1) - (3, 4) = (-2, -5)$
- 이렇게 빼면 플레이어에서 적으로 향하는 방향이 나옵니다. (즉, 플레이어로부터 도망치는 방향)
- 올바른 예 (플레이어 - 적): $(3, 4) - (1, -1) = (2, 5)$
- “도착점 - 출발점”을 해야 적이 플레이어를 바라보는 올바른 방향 벡터가 나옵니다.
Step 2: 벡터의 정규화 (Normalize)
구해낸 방향 벡터 $(2, 5)$는 방향뿐만 아니라 ‘거리(크기)’ 정보도 갖고 있습니다. 만약 플레이어가 멀리 있다면 벡터의 길이가 길어지고, 가까이 있다면 짧아집니다. 이 값을 그대로 이동에 사용하면 거리가 멀수록 비정상적으로 빨리 이동하게 됩니다. (또는 대각선 이동 시 더 빨라짐)
따라서, 벡터의 크기(길이)를 1로 만들어주는 정규화(Normalize) 과정이 필수입니다.
- 결과: 거리는 무시되고, 오직 ‘순수한 방향(길이가 1인 벡터)’만 남게 됩니다.
Step 3: 속도(Speed) 적용하기
이제 길이가 1인 순수한 방향 벡터를 얻었으므로, 기획자가 설정한 이동 속도를 곱해주면 됩니다.
\[최종 이동 속도 = 정규화된 방향 벡터 \times Speed\]- 요약 로직:
FVector Dir = Player.Position - Enemy.Position;(도착 - 출발)Dir.Normalize();(길이를 1로 압축)Enemy.Velocity = Dir * MoveSpeed;(원하는 속도 곱하기)
• 벡터의 이동과 회전으로 ‘원’ 그리기
벡터를 이용해 원을 그리는 과정은 ‘벡터의 덧셈(위치 이동)’과 ‘삼각함수(회전)’ 두 가지의 결합으로 이루어집니다.
1. 수학적 원리 (공식)
원을 그리기 위해서는 세 가지 요소가 필요합니다.
- 중심점 벡터 (C) : 원의 중심 위치를 나타내는 위치 벡터입니다.
- 반지름 (R) : 중심으로부터 떨어져 있는 거리(벡터의 크기)입니다.
- 각도 : 0도부터 360도까지 변하는 각도입니다.
반지름 크기가 R이고 각도만큼 회전한 방향 벡터 r은 삼각함수를 이용해 다음과 같이 표현할 수 있습니다.
방향 벡터 r = (R * cos(각도), R * sin(각도))
이제 원의 중심점 벡터 C에 이 방향 벡터 r을 더해주면(벡터의 이동), 원의 둘레를 따라 도는 최종 위치 벡터 P를 구할 수 있습니다.
최종 공식: 위치 P = 중심 C + 방향 r
- P의 x좌표 = C의 x좌표 + R * cos(각도)
- P의 y좌표 = C의 y좌표 + R * sin(각도)
• 기초 지식: 게임 프로그래밍을 위한 삼각함수
삼각함수는 게임 프로그래밍(캐릭터의 이동, 총알의 궤적, 시야 판정 등)에서 ‘각도’를 ‘좌표(길이)’로 변환하거나 그 반대를 수행할 때 사용하는 필수 도구입니다. 직각삼각형의 세 변을 기준으로 생각하면 아주 쉽습니다!
1. 직각삼각형의 세 변 정의하기
먼저, 기준이 되는 각도를 하나 정하고 직각삼각형을 그립니다.
- 빗변 (Hypotenuse, H): 가장 긴 변이며, 직각의 맞은편에 있습니다.
- 밑변 (Adjacent, A 또는 x): 기준 각도를 끼고 있는 바닥 변입니다.
- 높이 (Opposite, O 또는 y): 기준 각도의 마주 보는 맞은편 변입니다.
2. 삼각함수 3인방 (sin, cos, tan)
이 세 변의 ‘길이 비율’을 미리 약속해 둔 것이 바로 삼각함수입니다.
Sin (사인)
- 공식: sin(각도) = 높이 / 빗변
- 비유: 빗변을 타고 위로 올라가는 느낌입니다.
- 언제 쓰나요? 빗변의 길이를 알 때 높이(y)를 구하고 싶을 때 씁니다.
Cos (코사인)
- 공식: cos(각도) = 밑변 / 빗변
- 비유: 빗변에서 밑바닥으로 코~ 잠들러 내려오는 느낌입니다.
- 언제 쓰나요? 빗변의 길이를 알 때 밑변(x)을 구하고 싶을 때 씁니다.
Tan (탄젠트)
- 공식: tan(각도) = 높이 / 밑변
- 비유: 밑변 대비 높이가 얼마나 가파른지(기울기)를 나타냅니다.
- 언제 쓰나요? x, y 좌표만 알 때 각도를 구하거나, 기울기를 구할 때 씁니다.
3. 실전
삼각형의 각도와 어느 한 변의 길이만 알면 나머지 모든 변을 구할 수 있습니다. 게임 개발에서 가장 많이 쓰이는 상황별로 정리했습니다.
[상황 A] 빗변(H)을 알고 있을 때 (가장 중요!)
캐릭터가 특정 방향으로 10m 이동해야 할 때, x축과 y축으로 각각 얼마나 옮겨야 할지 계산하는 경우입니다. (이전 벡터 원 그리기에서의 R * cos(각도), R * sin(각도) 공식이 바로 여기서 나왔습니다!)
- 밑변(x) 구하기: x = H * cos(각도)
- 높이(y) 구하기: y = H * sin(각도)
[상황 B] 밑변(A)을 알고 있을 때
건물의 그림자 길이를 보고 건물의 높이를 구하는 경우입니다.
- 높이(y) 구하기: y = A * tan(각도)
- 빗변(H) 구하기: H = A / cos(각도)
[상황 C] 높이(y)를 알고 있을 때
- 밑변(x) 구하기: x = y / tan(각도)
- 빗변(H) 구하기: H = y / sin(각도)
• 선형 결합
질문하신 수식은 보통 아래와 같이 표현됩니다.
\[V_{new} = a_1v_1 + a_2v_2 + \dots + a_nv_n\]이 복잡해 보이는 수식을 방금 배운 단어로 번역하면 이렇습니다.
동쪽($v_1$)으로 3번($a_1$) 가고, 북쪽($v_2$)으로 2번($a_2$) 가면, 최종적으로 도착한 새로운 위치($V_{new}$)가 곧 ‘새로운 벡터’가 된다.
즉, 미리 정해진 기본 벡터(방향)들을 원하는 비율(스칼라)로 늘리거나 줄인 다음, 꼬리에 꼬리를 물고 이어 붙여서(더해서) 전혀 새로운 방향의 벡터를 만들어내는 과정을 수학에서는 멋있게 “선형 결합”이라고 부릅니다.
• 선형 종속
스칼라 값($a$)들을 전부 0으로 주지 않았는데도 결국 제자리(영벡터, 0)로 돌아올 수 있는 상황을 말합니다.
- 상황: $v_1$은
[앞으로 1칸]가는 스킬, $v_2$는[뒤로 1칸]가는 스킬입니다. - 결과: $v_1$을 3번 쓰고($a_1=3$), $v_2$를 3번 쓰면($a_2=3$) 제자리(0)로 돌아옵니다.
- 의미: 두 방향이 사실상 같은 선상(1차원)에 겹쳐 있습니다. 즉, 하나의 스킬만 있어도 마이너스(-) 방향을 곱해서 다른 스킬의 역할을 완벽히 대체할 수 있습니다. 수학자들은 이렇게 벡터들이 서로에게 묶여서 새로운 차원을 개척하지 못하는 상태를 ‘종속되었다’라고 부릅니다.
• 선형 독립 (Linear Independence)
어떤 벡터도 다른 벡터들의 조합으로 흉내 낼 수 없는 상태를 말합니다. 수식으로 표현하면 “결과를 제자리(영벡터, 0)로 만들려면, 무조건 아무 스킬도 안 쓰는 방법($a_1=0, a_2=0$) 딱 하나밖에 없는 상태”입니다.
- 상황: $v_1$은
[앞으로 1칸]가는 스킬, $v_2$는[오른쪽으로 1칸]가는 스킬입니다. - 결과: 앞으로 3번($a_1=3$) 갔다면, 오른쪽으로 가는 스킬($v_2$)을 아무리 이리저리 조합해도 절대 제자리(0)로 돌아올 수 없습니다. 제자리에 있으려면 애초에 아무 스킬도 쓰지 말았어야 합니다.
- 의미: 두 방향이 겹치지 않는 완전히 새로운 ‘차원(Dimension)’을 담당하고 있습니다. 서로가 서로를 절대 대체할 수 없는 ‘독립적인’ 관계인 것입니다. 게임의 X축(가로), Y축(세로), Z축(높이)이 바로 완벽한 선형 독립의 관계입니다.
• 벡터 공간의 생성
“선형 독립인 벡터들을 선형 결합하면 공간의 모든 곳을 갈 수 있지만, 선형 종속은 불가능하다”는 선형 대수학의 핵심 원리입니다. 그 이유를 직관적으로 정리해 드립니다.
1. 선형 독립이 모든 벡터를 생성할 수 있는 이유
“새로운 차원(방향)을 온전히 확보했기 때문입니다.”
- 원리: 선형 독립인 벡터들은 서로의 영역을 절대 침범하거나 흉내 낼 수 없습니다. 예를 들어 2차원 평면에서 하나는 완벽한 가로축($X$), 하나는 완벽한 세로축($Y$)을 담당한다고 볼 수 있습니다.
- 이유: 가로로 움직이는 행위가 세로 위치에 영향을 주지 않으므로, 이 두 가지 독립적인 움직임(스칼라 곱)을 조합하면 평면 위의 어떤 $(x, y)$ 좌표든 100% 도달할 수 있습니다. 즉, 벡터들이 각자의 고유한 축을 담당하며 온전한 공간을 생성(Span)하게 됩니다.
2. 선형 종속이 모든 벡터를 생성할 수 없는 이유
“차원이 찌그러져 갇혀버리기 때문입니다.”
- 원리: 선형 종속인 벡터들은 결국 ‘같은 방향’ 혹은 ‘이미 다른 벡터가 갈 수 있는 방향’을 가리키고 있습니다.
- 이유: 예를 들어 2차원 공간에서 두 벡터가 모두 대각선 위아래만 가리키고 있다면(예: 서로 반대 방향이거나 길이만 다른 경우), 이 두 벡터를 수백 번 더하고 빼봤자 결국 그 하나의 1차원 직선(선분) 위에서만 맴돌게 됩니다.
- 결과: 직선 밖으로 벗어날 수 있는 ‘독립적인 새로운 축’이 없기 때문에, 2차원 평면의 나머지 수많은 공간(벡터)들은 영원히 생성해낼 수 없습니다.
• 2차원 공간에서 3개의 벡터는 왜 항상 ‘선형 종속’일까?
1단계: 3번째 벡터는 기존 벡터의 조합이다
앞서 2D 공간에서 두 벡터($v_1, v_2$)가 독립이면 평면 맵의 “모든 곳”을 갈 수 있다고 했습니다. 즉, 새로 추가된 3번째 벡터($v_3$)가 어디에 있든 $v_1$과 $v_2$를 섞어서 완벽하게 복제할 수 있습니다.
이것을 수식으로 쓰면 다음과 같습니다.
\[v_3 = a v_1 + b v_2\](의미: $v_3$는 $v_1$ 방향으로 $a$번, $v_2$ 방향으로 $b$번 이동하면 도달하는 위치다)
2단계: “어떻게든 영벡터로 만들기” (이항하기)
영벡터($0$)를 만들어 보기 위해, 등호 왼쪽에 있는 $v_3$를 오른쪽으로 넘겨보겠습니다. 그러면 부호가 마이너스($-$)로 바뀌면서 왼쪽은 아무것도 없는 $0$(영벡터)이 됩니다.
\[0 = a v_1 + b v_2 - 1 v_3\]3단계: 선형 종속의 증명 완료
자, 완성된 위 수식을 선형 종속/독립의 규칙으로 해석해 봅시다. 세 개의 벡터($v_1, v_2, v_3$)를 결합해서 결과적으로 영벡터($0$)를 만들어냈습니다.
그런데 사용된 스칼라(배수) 값들을 볼까요?
- $v_1$의 스칼라 = $a$
- $v_2$의 스칼라 = $b$
- $v_3$의 스칼라 = $-1$
선형 독립이 되려면 “영벡터를 만들 수 있는 유일한 방법이 모든 스칼라가 0일 때뿐”이어야 합니다.
하지만 보시다시피 3번째 벡터가 추가되는 순간, $v_3$ 앞에 붙은 스칼라가 ‘-1’이 되어버립니다. 애초에 아무 스킬도 쓰지 않아야 한다는 규칙을 깨고, 이미 스칼라 하나가 0이 아니라는 것이 확정된 셈입니다.
• 기저(Basis)
수학자들과 게임 개발자들은 이 원리를 바탕으로 공간을 정의할 때 다음 두 가지를 확인합니다.
- 최소한의 필수 스킬인가? (선형 독립) $\rightarrow$ 쓸데없이 겹치는 방향(잉여 데이터)이 없는가?
- 모든 곳을 갈 수 있는가? (공간의 생성, Span) $\rightarrow$ 차원 전체를 커버할 수 있는가?
이 두 가지 조건을 완벽하게 만족하는 엘리트 벡터들의 조합을 수학에서는 기저(Basis)라고 부릅니다. 3D 게임 엔진의 $X, Y, Z$ 축이 바로 이 ‘기저’의 가장 완벽하고 대표적인 예시입니다.
작성하신 내용은 선형 대수학의 핵심 증명 과정을 수식의 거부감 없이 직관적이고 완벽하게 풀어낸 100점짜리 모범 답안입니다!
블로그나 노트에 바로 올리실 수 있도록, 가독성을 높이고 수식을 깔끔하게 정리한 마크다운(.md) 코드로 다듬어 드립니다.
코딩테스트
강의 링크
• 재귀 함수
재귀 함수란 자기 자신을 다시 호출하는 함수를 의미합니다. DFS를 실질적으로 구현할 때 매우 자주 사용되는 핵심 기법입니다.
- 핵심 특징: 재귀 함수가 호출될 때마다 컴퓨터 메모리의 ‘스택(Stack)’ 프레임에 차곡차곡 쌓이게 됩니다. 가장 마지막에 호출된 함수가 먼저 처리를 끝내야 그 앞의 함수들도 차례대로 종료되는 구조입니다.
- 종료 조건의 중요성: 코딩 테스트에서 무한 루프를 방지하고 올바른 정답을 내기 위해, 재귀 함수 내부에는 반드시 특정 시점에 함수를 끝내는 ‘종료 조건(Base Case)’을 명시해야 합니다.
재귀 함수 활용 예시 1: 팩토리얼 (Factorial)
$n! = n \times (n-1) \times (n-2) \times \dots \times 1$
- 수학적으로 정의된 점화식을 코드로 가장 직관적으로 옮길 수 있습니다.
재귀 함수 활용 예시 2: 유클리드 호제법 (최대공약수 구하기)
두 개의 자연수에 대한 최대공약수(GCD)를 빠르고 간결하게 구할 수 있는 수학적 알고리즘입니다.
- 원리: 두 자연수 $A$, $B$ ($A > B$)가 있을 때, $A$를 $B$로 나눈 나머지를 $R$이라고 합니다. 이때 $A$와 $B$의 최대공약수는 $B$와 $R$의 최대공약수와 동일하다는 성질을 이용합니다.
재귀 함수 사용의 유의 사항
- 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있습니다.
- 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 합니다.
- 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있습니다.
- 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있습니다.
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓입니다.
- 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많습니다.
• DFS
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.
- 자료구조: 선입후출(FILO) 방식인 스택(Stack) 자료구조를 이용하거나, 내부적으로 스택 원리를 따르는 재귀 함수를 이용하여 간결하게 구현합니다.
- 동작 원리:
- 탐색 시작 노드를 스택에 넣고 방문 처리를 합니다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리합니다. (가장 깊은 곳까지 뚫고 들어감)
- 방문하지 않은 인접 노드가 없으면 스택에서 해당 노드를 꺼냅니다(백트래킹).
- 더 이상 2, 3번의 과정을 수행할 수 없을 때까지 반복합니다.
- 코딩 테스트 활용: “얼음 얼려 먹기(연결 요소 찾기, Connected Component)” 문제처럼, 서로 이어져 있는 모든 공간을 한 번에 싹 다 방문 처리해야 할 때 유용하게 쓰입니다.
DFS(재귀 함수) 작성을 위한 Tip 4단계
Step 1: 탈출구 만들기 (종료 조건 / Base Case)
재귀 함수를 짤 때 무조건 가장 먼저 써야 하는 코드입니다.
- 의미: 언제 이 끝없는 하청(재귀 호출)을 멈출지 명확한 ‘바닥’을 정해줍니다.
- 위험성: 이 조건이 없거나 잘못되면
RecursionError(무한 루프)에 빠지게 됩니다.
Step 2: 내 상태 기록하기 (매개변수 / 파라미터 정하기)
함수가 실행될 때, 현재 상태를 담아둘 가방을 챙기는 과정입니다.
- 의미: “내가 지금 어디까지 왔고, 지금까지 뭘 챙겨왔지?”를 기록할 변수들을 정의합니다.
- 예시: 현재 탐색 중인 배열의 인덱스(
index), 지금까지 누적된 값(sum), 방문 기록(visited) 등.
Step 3: 내가 할 수 있는 행동 찾기 (갈림길 / 재귀 호출)
현재 내 위치에서 뻗어나갈 수 있는 ‘경우의 수’를 모두 찾아냅니다.
- 의미: 가능한 모든 갈림길에 대해 다음 하청(재귀 함수)을 보냅니다.
- 실행: 이때 다음 함수를 호출하면서, Step 2에서 만든 상태를 업데이트(
index + 1,sum + 현재 값등)하여 넘겨줍니다.
Step 4: 결과 취합 및 보고 (Return)
마지막으로, 바닥(탈출구)을 찍고 돌아온 결과들을 처리합니다.
- 의미: 하청을 끝내고 올라온 결과들을 어떻게 합쳐서 나를 부른 윗사람에게 넘겨줄지 결정합니다.
- 실행: 도달 가능한 총 경우의 수를 더하거나, 최댓값/최솟값을 갱신하여 반환(
return)합니다.
• BFS
그래프에서 가까운 노드부터 우선적으로 넓게 탐색하는 알고리즘입니다.
- 자료구조: 선입선출(FIFO) 방식인 큐(Queue) 자료구조를 이용합니다. (파이썬에서는 성능을 위해
collections모듈의deque를 반드시 사용해야 합니다.) - 동작 원리:
- 탐색 시작 노드를 큐에 넣고 방문 처리를 합니다.
- 큐에서 노드를 꺼낸 뒤에, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 “모두 한 번에” 큐에 넣고 방문 처리합니다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
- 코딩 테스트 활용: “미로 탈출” 문제처럼, 각 간선의 비용(거리)이 동일한 상황에서 최단 거리(최소 칸 수)를 구할 때 절대적으로 사용되는 필수 알고리즘입니다.