2026-04-14 TIL (36일차)
코딩테스트
강의
• 알고리즘 성능평가
시간제한이 1초인 문제를 만났을 때, 데이터의 개수(N)에 따른 일반적인 기준은 다음과 같습니다. 이 기준을 바탕으로 어떤 알고리즘을 설계해야 할지 미리 유추할 수 있습니다.
- N의 범위가 500인 경우: 시간 복잡도가 $O(N^3)$인 알고리즘을 설계하면 문제를 풀 수 있습니다.
- N의 범위가 2,000인 경우: 시간 복잡도가 $O(N^2)$인 알고리즘을 설계하면 문제를 풀 수 있습니다.
- N의 범위가 100,000인 경우: 시간 복잡도가 $O(N \log N)$인 알고리즘을 설계하면 문제를 풀 수 있습니다.
- N의 범위가 10,000,000인 경우: 시간 복잡도가 $O(N)$인 알고리즘을 설계하면 문제를 풀 수 있습니다.
• 알고리즘 문제 해결과정
일반적인 알고리즘 문제 해결 과정은 다음과 같은 순서로 진행됩니다. 무작정 키보드부터 잡기보다, 이 단계를 거치는 습관을 들이는 것이 중요합니다.
- 지문 읽기 및 컴퓨터적 사고 (문제 파악)
- 요구사항(복잡도) 분석 (제한 시간과 N의 범위를 보고 알고리즘 유추하기)
- 문제 해결을 위한 아이디어 찾기
- 소스코드 설계 및 코딩
코테 출제자의 의도 파악하기 일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한다면, 간결하게 소스코드를 작성할 수 있는 형태로 문제를 출제합니다. (만약 코드를 짜다가 너무 지나치게 길어지거나 예외 처리가 끝도 없이 나온다면, 나의 ‘접근 방식(아이디어)’이 잘못되었을 확률이 높으니 다시 2번, 3번 단계로 돌아가 보는 것이 좋습니다.)
프로그래머스 타켓 넘버 (DFS 연습)
게임 수학
강의
• 공리(Axiom)
증명할 필요없는 자명한 명제
세상을 이해하거나 게임을 만들 때 사용하는 절대적인 약속과 같습니다.
1. “왜?”라고 묻는 것을 멈추는 지점
우리가 어떤 사실을 증명하려면 다른 근거가 필요합니다.
- Q. “삼각형 내각의 합은 왜 180도야?”
- A. “평행선의 성질을 이용해서 증명할 수 있어.”
- Q. “그럼 평행선의 성질은 왜 그런데?”
- A. “그건… 음…”
이렇게 계속 “왜?”라고 꼬리에 꼬리를 물고 내려가다 보면, 더 이상 설명할 수 없는 최하단의 기초 바닥에 도달하게 됩니다. 이 바닥이 바로 공리입니다. 즉, “이건 너무 당연해서 증명할 수도 없고, 그냥 그렇다고 치고 다음 논의를 시작하자!”라고 약속하는 지점입니다.
2. 게임 엔진으로 비유하자면? (Unreal / Unity)
개발자 관점에서 게임 엔진에 비유하면 이해가 훨씬 빠릅니다.
- 게임 로직 (정리): “캐릭터가 점프를 하면 중력 때문에 떨어진다.” (코드로 구현 및 증명 가능)
- 엔진의 물리 법칙 (공리): “이 가상 세계에서 중력이라는 힘은 항상 아래로 작용한다.”
게임 안에서 “중력이 왜 아래로 작용해?”라고 물으면 “엔진이 원래 그렇게 설계됐으니까”라고 답할 수밖에 없죠? 이처럼 어떤 시스템을 만들기 위해 가장 먼저 설정하는 ‘무조건적인 규칙’이 공리입니다.
3. 공리의 대표적인 예시
수학에서 가장 유명한 공리 몇 가지를 살펴보면, “이걸 굳이 증명해야 해?”라는 생각이 드실 겁니다.
- “두 점을 잇는 직선은 단 하나뿐이다.”
- “임의의 중심과 반지름을 가진 원을 그릴 수 있다.”
- “전체는 부분보다 크다.”
이걸 증명하려고 하면 오히려 논리만 더 복잡해집니다. 이 당연한 사실을 그냥 받아들이고, 여기서부터 출발하여 삼각형도 만들고 사각형도 만들어 나가는 것입니다.
4. 왜 공리가 중요한가요?
공리가 흔들리면 그 위에 쌓아 올린 모든 지식이 무너집니다.
- 논의의 시작점 공리가 없으면 우리는 영원히 “왜?”라는 질문만 하다가 어떤 논의도 시작하지 못합니다.
- 모순 없는 체계 구축 “A는 A다” 같은 확고한 공리가 있어야만, 그 뒤에 파생되는 복잡한 공식들이 서로 충돌하지 않고 단단한 시스템으로 유지될 수 있습니다.
• 공간공간에 대한 수학
벡터 공간 (Vector Space)
게임이 사용하는 가상 공간의 본질입니다. 단순히 눈에 보이는 3D 세계가 아니라, 수의 체계를 기반으로 차곡차곡 쌓아 올린 ‘다차원의 데이터 집합’입니다.
물리학 vs 수학에서의 벡터와 스칼라
- 물리학적 관점 (직관적 이해)
벡터(Vector): 크기와 방향을 모두 가진 대상 (예: 속도, 힘)스칼라(Scalar): 크기만 있는 물리량 (예: 온도, 질량)- 우리는 이 물리학적 법칙을 게임 엔진에 구현하여 캐릭터를 움직이게 합니다.
- 수학적 관점 (시스템적 이해)
벡터: 벡터 공간을 구성하는 원소스칼라: 체(Field) 집합의 원소 (단순한 ‘수’)- 수학에서 벡터와 스칼라는 덧셈과 곱셈 같은 연산 법칙이 만들어내는 거대한 시스템의 부품들입니다. 이를 먼저 이해하는 것이 중요합니다.
• 변환과 행렬 (Transformation & Matrix)
선형 변환 (Linear Transformation)
수학적으로는 ‘선형성을 가진 변환’이지만, 쉽게 말해 “공간을 찌그러뜨리지 않고 규칙적으로 늘리고, 줄이고, 회전시키는 작업”입니다.
고무판 비유로 이해하는 선형 변환 격자무늬가 그려진 고무판을 상상해 보세요.
- 이 고무판을 좌우로 쫙 늘리거나 (크기 변환/Scale)
- 고무판 전체를 빙글 돌리거나 (회전 변환/Rotation)
- 한쪽 모서리만 잡고 평행사변형 모양으로 기울이는 것 (전단 변환/Shear)
단, 고무판의 중심점(원점)은 고정되어 있어야 하고, 격자의 직선들은 변환 후에도 휘어지지 않고 직선을 유지해야 합니다. 이것이 선형 변환입니다!
렌더링 파이프라인의 공간 변환 체제
우리가 만든 3D 모델이 모니터 화면에 그려지기까지는 여러 공간을 거치는 변환 과정이 필요합니다.
로컬 공간(모델 고유의 공간)- ⬇️ (모델링 변환)
월드 공간(게임 맵 전체의 절대 공간)- ⬇️ (뷰 변환)
뷰 공간(카메라 기준의 공간)- ⬇️ (원근 투영 변환)
사영 공간(2D 화면으로 납작하게 누르기 전의 공간)
행렬 (Matrix)의 역할
위에서 말한 복잡한 공간 변환 과정(모델링 ➡️ 뷰 ➡️ 원근 투영)을 컴퓨터에게 빠르게 수행하도록 지시하는 ‘수학적 명령어’가 바로 행렬입니다. 각 변환 단계는 특정한 행렬 하나씩에 대응됩니다.
• 평면의 방정식과 절두체 (Frustum)
평면의 방정식: $ax + by + cz + d = 0$
평면의 방정식을 여러 개 결합하면 3D 공간 안에 자신만의 영역을 깎아서 구축할 수 있습니다. 구축된 영역 안에서 어떤 작업을 할지 수학적으로 판별하게 됩니다.
카메라 절두체 (Frustum) 컬링
대표적으로 렌더링에 사용되는 카메라의 시야 영역인 ‘절두체(Frustum)’가 있습니다.
- 절두체는 피라미드 윗부분을 자른 모양으로, 6개의 평면으로 이루어져 있습니다.
- 최적화의 마법: 이 6개의 평면 방정식을 이용하여, 현재 카메라의 시야(절두체) 내부에 있는 물체만 걸러내어 렌더링하고, 시야 밖의 물체는 무시(Culling)합니다.
- 이러한 수학적 필터링 매커니즘 덕분에 게임은 초당 60프레임(60fps)이라는 빠른 실시간 렌더링이 가능해집니다.
핵심 요약 (Conclusion)
게임 개발을 위한 수학의 핵심 흐름은 다음과 같습니다.
- 수의 체계와 벡터 공간의 본질을 이해한다.
- 선형 변환과 행렬을 사용하여 가상 공간이 어떻게 조작되고 변화하는지 이해한다.
- 이를 바탕으로 렌더링 파이프라인과 최적화 기법을 게임에 적용한다.
[6번 과제] 구현 완료
“클린 코드(Clean Code) 원칙을 유지하며 핵심 액터 로직 구현 완료”