2026-04-20 TIL (40일차)

알고리즘

• 참고 강의: 알고리즘 강의

정렬 알고리즘

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말합니다. 일반적인 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됩니다.

• 선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다.

시간 복잡도

• 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다.
• 구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같습니다. \(N + (N - 1) + (N - 2) + ... + 2\)
• 이는 $(N^2 + N - 2) / 2$ 로 표현할 수 있는데, 빅오 표기법에 따라서 $O(N^2)$이라고 작성합니다.

• 삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다. 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 효율적으로 동작합니다.

1. 첫번째 데이터는 그 자체가 정렬되어있다고 판단하고 두번째 데이터부터 어떤 위치(왼쪽,오른쪽)으로 들어갈지 판단하는 로직입니다.

시간 복잡도

• 삽입 정렬의 시간 복잡도는 $O(N^2)$이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용됩니다.
• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작합니다.
  • 최선의 경우 $O(N)$의 시간 복잡도를 가집니다.(이미 정렬되어 있는 상태)
  • 이유: 삽입 정렬은 자신의 자리를 찾을 때 ‘왼쪽 원소들’과 차례대로 비교합니다. 만약 배열이 이미 오름차순으로 완벽히 정렬되어 있다면, 타겟이 되는 원소는 자신의 바로 왼쪽 원소와 1번만 비교해 보고 “내가 더 크니까 제자리에 가만히 있으면 되겠구나” 하고 내부 반복문(탐색)을 즉시 종료합니다(Break).
  • 즉, $N$개의 원소가 각각 단 1번의 비교만 수행하므로 전체 연산 횟수가 $N$번으로 최적화되어 $O(N)$의 빠른 속도를 냅니다.

• 퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법입니다.
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다.
• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다.
• 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정합니다.

Tip: 퀵 정렬은 내부적으로 재귀 함수(Recursive Function)를 활용하여 구현됩니다.

[동작 과정]

1. 피벗 설정: 배열의 첫 번째 원소를 피벗(기준값)으로 설정합니다.
2. 탐색 시작:
   • 왼쪽에서 오른쪽으로: 피벗보다 큰 데이터를 찾을 때까지 이동합니다.
   • 오른쪽에서 왼쪽으로: 피벗보다 작은 데이터를 찾을 때까지 이동합니다.
3. 교환 (Swap): * 찾은 두 원소의 위치를 서로 바꿉니다.
   • 이 과정을 두 탐색 위치가 서로 엇갈릴 때까지 반복합니다.
4. 분할 (Partition/엇갈림 발생): * 왼쪽 탐색 위치와 오른쪽 탐색 위치가 서로 엇갈리게 되면(왼쪽 인덱스 > 오른쪽 인덱스), 피벗과 엇갈린 두 원소 중 더 작은 값(오른쪽 탐색 위치의 값)의 위치를 교환합니다.
5. 재귀적 수행:
   • 이제 피벗은 배열의 중간쯤 위치하게 되며, 피벗을 기준으로 왼쪽 묶음은 모두 피벗보다 작고, 오른쪽 묶음은 모두 피벗보다 큰 상태가 됩니다. (이를 분할이라고 합니다.)
   • 나누어진 왼쪽 묶음과 오른쪽 묶음에 대해 위 과정을 각각 독립적으로 다시 수행(재귀 호출)하여 전체 배열을 정렬합니다.

시간 복잡도

• 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 $O(N \log N)$을 기대할 수 있습니다.
  • 너비 X 높이 = $N \times \log N = N \log N$
• 퀵 정렬은 평균의 경우 $O(N \log N)$의 시간 복잡도를 가집니다.
• 하지만 최악의 경우 $O(N^2)$의 시간 복잡도를 가집니다.
• 이유: 가장 기본적인 퀵 정렬은 ‘첫 번째 원소’를 피벗으로 삼습니다. 만약 데이터가 이미 오름차순(또는 내림차순)으로 정렬되어 있는 상태라면, 첫 번째 원소는 항상 배열 내의 ‘최솟값(또는 최댓값)’이 됩니다.
  • 이 최솟값을 기준으로 분할을 시도하면, 피벗보다 작은 왼쪽 묶음은 0개, 피벗보다 큰 오른쪽 묶음은 $N-1$개로 극단적으로 치우친 분할이 일어납니다. 절반씩 쪼개지는 $\log N$ 깊이의 트리가 아니라, 매번 데이터가 1개씩만 줄어드는 깊이 $N$짜리 일자형 트리가 되어버립니다.
  • 따라서 탐색 연산이 $N + (N-1) + (N-2) + … + 1$ 번 일어나게 되어 결국 $O(N^2)$의 속도 저하가 발생합니다.

• 계수 정렬

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘입니다.
• 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능합니다.
• 데이터의 개수가 $N$, 데이터(양수) 중 최댓값이 $K$일 때 최악의 경우에도 수행 시간 $O(N + K)$를 보장합니다.

[동작 과정]

1. 데이터 범위 파악 및 카운팅 리스트 생성
   • 데이터 범위 확인: 정렬할 데이터 중 가장 작은 수와 가장 큰 수의 범위를 확인합니다.
   • 리스트 초기화: [최소값 ~ 최대값]의 모든 숫자를 포함할 수 있는 크기의 빈 리스트(카운팅 배열)를 생성합니다.
     • 인덱스(Index): 데이터의 값 자체를 의미합니다.
     • 값(Value): 해당 데이터가 등장한 횟수(계수)를 저장합니다.
2. 데이터 개수 세기 (Counting)
   • 데이터를 하나씩 확인하면서, 데이터의 값과 동일한 인덱스의 숫자를 1씩 증가시킵니다.
   • 예: 데이터 3을 확인하면 카운팅 리스트의 3번 인덱스 값을 +1 합니다.
3. 정렬된 결과 출력 (Output)
   • 카운팅 리스트의 첫 번째 인덱스부터 마지막 인덱스까지 순서대로 확인합니다.
   • 리스트에 기록된 계수(갯수)만큼 해당 인덱스 번호를 반복해서 출력합니다.
   • 인덱스 자체가 이미 오름차순으로 정렬되어 있기 때문에, 기록된 횟수대로 뽑아내기만 하면 정렬이 완료됩니다.

시간 복잡도

• 계수 정렬의 시간 복잡도와 공간 복잡도는 모두 $O(N + K)$입니다.
• 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있습니다.
  • 데이터가 0과 999,999로 단 2개만 존재하는 경우를 생각해 봅시다.
• 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있습니다.
  • 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적입니다.

• 정렬 알고리즘 비교

알고리즘	평균 시간 복잡도	공간 복잡도	핵심 특징
선택 정렬	$O(N^2)$	$O(N)$	아이디어가 매우 간단하고 구현이 쉬움.
삽입 정렬	$O(N^2)$	$O(N)$	데이터가 거의 정렬되어 있을 때 압도적으로 빠름.
퀵 정렬	$O(N \log N)$	$O(N)$	대부분의 상황에서 가장 적합하며 충분히 빠름.
계수 정렬	$O(N+K)$	$O(N+K)$	데이터 크기가 제한된 경우에 한해 매우 빠름.

코딩 테스트 Tip: 문제에서 특정한 정렬 알고리즘을 직접 구현하라고 요구하지 않는다면, 최악의 경우에도 $O(N \log N)$을 보장하는 언어별 내장 표준 정렬 라이브러리를 사용하는 것이 가장 안전하고 효율적입니다.

---

TA

1. IK와 FK의 이해

• FK (Forward Kinematics, 순운동학)
  • 원리: 부모 관절에서 자식 관절로, 앞에서부터 차례대로 각도를 계산해 나가는 방식입니다. (어깨 👉 팔꿈치 👉 손목)
  • 특징: 어깨를 돌리면 팔 전체가 따라 도는 직관적인 방식입니다. 하지만 캐릭터의 손이 ‘정확히 특정 물체를 잡게’ 하거나 ‘발이 땅에 정확히 닿게’ 만드는 등 목표 지점이 있을 때는 계산하기가 매우 까다롭습니다.

• IK (Inverse Kinematics, 역운동학)
  • 원리: 자식 관절(끝점, Tip)의 최종 목표 위치(Target)를 미리 정해두고, 그 위치에 도달하기 위해 필요한 중간 관절들의 각도를 수학적으로 역산(Inverse)하여 구하는 방식입니다.
  • 특징: 캐릭터의 발이 울퉁불퉁한 계단 높이에 맞춰 자연스럽게 꺾이거나, 문고리에 정확히 손을 가져다 댈 때 사용되는 필수적인 기능입니다.

2. 텍스처와 머티리얼 실전 팁

• AI를 활용한 텍스처 리마스터링

원하는 텍스처를 외부에서 찾기 힘들 때 사용하는 유용한 파이프라인입니다.

1. 언리얼 스타터 콘텐츠(Starter Content) 등에서 형태가 마음에 드는 기본 텍스처를 찾아 우클릭 -> Export (.png)로 추출합니다.
2. 이 이미지를 AI를 통해 원하는 느낌으로 변경이나 생성 가능합니다.

• Default Lit에서 빛 영향 무시하기

• 머티리얼의 셰이딩 모델이 Default Lit(빛의 영향을 받는 기본 상태)일 때, 텍스처 맵을 Base Color와 Emissive Color(발광)에 동시에 연결해 보세요.
• 효과: 어두운 그림자 속에서도 Emissive 값이 색상을 뿜어내어 원래의 텍스처 색상을 선명하게 유지합니다. (반투명 UI나 특수한 카툰 렌더링 요소를 만들 때 유용한 꼼수입니다.)

• 머티리얼 변수 파라미터화

• 단축키 1 + 좌클릭으로 Constant 노드를 만든 후, 우클릭하여 Convert to Parameter로 변경합니다.
• 이유: 이렇게 파라미터로 선언해 두면, 굳이 무거운 머티리얼 에디터를 열지 않고도 ‘머티리얼 인스턴스(Material Instance)’ 창에서 스크롤만으로 실시간 값을 조절할 수 있어 작업이 편해집니다.

• World Position Offset (WPO)

• 원리: 픽셀의 색을 칠하는 픽셀 셰이더 단계가 아니라, 그 이전인 버텍스 셰이더(Vertex Shader) 즉, GPU 단계에서 3D 모델의 정점(Vertex) 좌표 자체를 물리적으로 이동시키는 기능입니다.
• 활용: 깃발이 바람에 펄럭이는 모션, 물결이 치는 바다, 캐릭터가 다가갈 때 풀숲이 밀려나는 효과 등을 애니메이션 없이 수학 공식만으로 구현할 수 있습니다.

개념 및 동작 방식

• World Position Offset (WPO)
  • 처리 주체: GPU (버텍스 셰이더)
  • 이동 방식: 메쉬의 각 버텍스가 개별 이동
  • 특징: 바운딩 박스 그대로! (시각적으로만 이동하며, 충돌/컬링 영역은 따라가지 않음)
• Transform (SetActorLocation)
  • 처리 주체: CPU (게임 로직)
  • 이동 방식: 오브젝트 전체가 통째로 이동
  • 특징: 바운딩 박스도 같이 이동 (충돌/컬링 정상 작동)

성능 및 특성 비교

항목	WPO	Transform
처리 위치	GPU (매 프레임, 매 버텍스)	CPU (호출할 때만)
충돌 판정	반영 안 됨	정상 반영
컬링(LOD)	원래 위치 기준 (문제 발생 가능)	이동 후 위치 기준 (정상)
변형 자유도	버텍스별 개별 변형 가능	오브젝트 단위 (통째 이동)
GPU 비용	버텍스 수 × 셰이더 복잡도	거의 없음
대표 사용처	풀 흔들림, 물결, 바람	캐릭터/오브젝트 이동, 물리
Nanite 지원	UE 5.4+ 부분 지원	Nanite와 무관 (정상 작동)

요약

• WPO = 시각 효과 특화 (GPU)
• Transform = 게임 로직 이동 (CPU)
• 두 기능은 대체 관계가 아니라 역할이 다릅니다.

3. Sine Remapped

• 기본 Sine 노드: 시간이 지남에 따라 파동을 그리며 -1.0 ~ 1.0 사이의 값을 무한히 반복합니다.
• 문제점: 이 값을 텍스처의 색상이나 모델의 크기에 바로 곱하면, -1이 되는 순간 크기가 뒤집히거나 색이 검은색으로 깨지는 에러가 발생합니다. 단순히 Abs(절댓값)를 씌워 양수로 접어 올리면 파동이 아래로 튕기는(바운스) 형태가 되어 부자연스럽습니다.
• Remap의 역할 (RemapValueRange): * 원본 데이터의 범위(-1.0 ~ 1.0)를 우리가 원하는 안전한 범위(예: 0.0 ~ 1.0 또는 1.0 ~ 1.5)로 비율을 유지한 채 압축/이동(통역)시켜 줍니다.
  • 자연스럽고 부드러운 호흡, 맥동(Pulse) 애니메이션을 만들 때 핵심적으로 사용됩니다.

4. 노멀 맵의 수학적 원리

3D 그래픽에서 가장 중요하면서도 오해가 많은 부분입니다. 우리는 왜 평평한 폴리곤 화면을 보면서 오돌토돌한 입체감을 느낄까요?

4-1. 입체감과 빛, 그리고 법선 벡터

• 입체감의 비밀: 우리가 굴곡을 느끼는 이유는 오직 “빛의 반사량(명암)” 때문입니다. 빛을 정면으로 받으면 밝고, 굴곡 때문에 빛을 비스듬히 받으면 어두워져 그림자가 집니다.
• 법선 벡터(Normal Vector)의 정의: 표면(Surface)에서 수직으로 90도로 뻗어 나가는 “방향 화살표(벡터)”입니다. 즉, “이 픽셀의 표면이 현재 어느 쪽을 바라보고 있는가?”를 나타냅니다.
• 밝기 계산 (내적, Dot Product): 빛이 들어오는 방향 벡터와 표면의 법선 벡터를 내적(Dot Product) 연산합니다. 두 화살표가 마주 보면 밝게 렌더링하고, 어긋날수록 어둡게 렌더링하는 것이 3D 조명 수학의 기초(Lambertian 모델)입니다.

4-2. 노멀 맵은 왜 보라색/푸른색일까? (색상과 벡터의 관계)

폴리곤의 수를 늘리지 않고 디테일을 주려면, 평평한 면 위에 그려진 각각의 픽셀마다 “가짜 법선 벡터(바라보는 방향)”를 저장해야 합니다. 우리는 이 X, Y, Z 벡터 데이터를 이미지 파일에 저장하기 위해 R, G, B 색상 채널에 각각 대응시켰습니다.

• 축의 대응:
  • $X$ 축 (좌우 굴곡) = $R$ (Red)
  • $Y$ 축 (상하 굴곡) = $G$ (Green)
  • $Z$ 축 (앞뒤 돌출) = $B$ (Blue)
• 수학적 변환 (Remap):
  • 벡터의 방향은 -1 ~ 1의 값을 가집니다. 하지만 이미지 색상(RGB)은 음수를 가질 수 없고 오직 0 ~ 1 (또는 0~255)의 값만 가집니다.
  • 따라서 벡터 데이터를 색상 데이터로 저장하기 위해 압축 공식이 사용됩니다.
  • \[Color = \frac{Vector + 1}{2}\]
• 보라색의 탄생 과정:
  • 굴곡이 없는 완벽히 평평한 면의 법선 벡터는 정면(Z축 방향)을 바라봅니다. 즉, 벡터 값은 $(X: 0,\ Y: 0,\ Z: 1)$ 입니다.
  • 이 벡터를 위의 공식에 넣어 RGB 색상으로 변환해 보겠습니다.
    • $R = (0 + 1) / 2 = \mathbf{0.5}$ (빨간색 50%)
    • $G = (0 + 1) / 2 = \mathbf{0.5}$ (초록색 50%)
    • $B = (1 + 1) / 2 = \mathbf{1.0}$ (파란색 100%)
  • 결과: RGB (0.5, 0.5, 1.0)이 됩니다. 이 색상이 바로 미술적으로 섞였을 때 우리가 보는 노멀 맵 특유의 밝은 파란색/연보라색입니다!
  • 즉, 노멀 맵에서 보라색 부분은 평평한 곳이고, 붉거나 초록빛이 도는 곳은 좌우/상하로 꺾인 굴곡진 곳임을 수학적으로 증명할 수 있습니다.

---

게임 수학

CS

정보처리기사

6번과제 완료