오늘 학습 진행 내용
코드카타
📌문자열 탐색 문제 디버깅 & 성능 개선
🔍 문제 상황
keymap과 targets가 주어졌을 때,
각 target 문자열을 만들기 위해 필요한 최소 키 입력 횟수를 구하는 문제를 풀이했다.
초기 접근은:
target의 각 문자마다
keymap 전체를 순회하며 find()로 위치 탐색
최소 인덱스를 더하는 방식
❌ 1. Segmentation Fault 발생 원인
문제 코드 (핵심)
int min_count = *min_element(counts.begin(), counts.end());원인 분석
어떤 문자 c가 keymap 어디에도 없으면
counts 벡터는 비어 있음
빈 벡터에 min_element 호출 후 역참조 → UB (Segmentation Fault)
핵심 교훈
STL 알고리즘 사용 전에는 컨테이너가 비어있는지 반드시 확인해야 한다
❌ 2. 예외 케이스 (논리적 오답)
잘못된 판정 방식
int checks = 0;
// ...
if (checks < s.length()) answer.push_back(-1);왜 문제인가?
checks는 “문자를 찾은 횟수”이지
“모든 문자를 입력할 수 있는지”를 보장하지 않음
한 문자가 여러 keymap에 있으면 checks가 과도하게 증가함
실제 오답 예시
keymap = {"AB", "AB"}
targets = {"AC"}
'A' → checks += 2
'C' → 못 찾아서 break
checks == s.length() → 잘못된 정상 처리 ❌
해결 방법
bool ok 플래그로 불가능 상태를 명확히 관리
if (counts.empty()) {
ok = false;
break;
}
⏱️ 3. 시간 초과 원인 분석 (알고리즘 관점)
초기 풀이 시간복잡도
문자 하나 처리할 때:
keymap 전체 순회
string::find() 호출
전체 시간복잡도:
O( targets 길이 × keymap 개수 × keymap 문자열 길이 )
👉 입력이 커지면 TLE 위험 매우 큼
✅ 4. 성능 개선 핵심 아이디어 (전처리)
핵심 전략
“각 문자를 치는 데 필요한 최소 입력 횟수”를 미리 계산
전처리
best[c] = keymap 전체에서 c의 최소 (index + 1)
keymap 전체를 한 번만 순회
target 처리
각 문자를 best에서 바로 조회
없으면 즉시 -1
🚀 최종 개선된 코드 (정석 풀이)
vector<int> solution(vector<string> keymap, vector<string> targets) {
const int INF = 1e9;
vector<int> best(26, INF);
// 전처리
for (const string& k : keymap) {
for (int i = 0; i < k.size(); i++) {
best[k[i] - 'A'] = min(best[k[i] - 'A'], i + 1);
}
}
vector<int> answer;
for (const string& s : targets) {
int sum = 0;
bool ok = true;
for (char c : s) {
if (best[c - 'A'] == INF) {
ok = false;
break;
}
sum += best[c - 'A'];
}
answer.push_back(ok ? sum : -1);
}
return answer;
}🧠 오늘의 핵심 정리
✔ 디버깅 관점
STL 알고리즘은 빈 컨테이너 체크 필수
“나중에 예외 처리”는 크래시를 막아주지 않는다
✔ 알고리즘 관점
find()를 반복해서 쓰면 대부분 시간초과로 이어짐
전처리 + O(1) 조회 패턴은 문자열 문제의 정석
✔ 설계 관점
상태 판정은 카운트 누적이 아니라 명확한 플래그로
TA 수업
Shader & Rendering Pipeline 정리
🎨 Shader란 무엇인가?
Shader는 GPU에서 실행되는 작은 프로그램으로,
3D 오브젝트의 색상, 질감, 빛 반사, 투명도 등 시각적 효과를 계산하는 역할을 한다.
과거에는 단순히 색을 입히는 수준이었지만,
현재는 다음과 같은 다양한 그래픽 연출의 핵심 요소로 사용된다.
| 구분 | 설명 |
|---|---|
| 정의 | GPU에서 실행되는 소형 프로그램 |
| 실행 위치 | GPU |
| 목적 | 색상, 조명, 질감, 투명도 등 시각 효과 계산 |
| 특징 | 병렬 처리, 픽셀/정점 단위 연산 |
| 활용 | 라이팅, 머티리얼, 파티클, 애니메이션, 스타일링 |
👉 즉, “GPU에서 실행되는 그래픽 연산 로직”이 Shader이다.
🧩 렌더링 파이프라인(Rendering Pipeline)
Rendering Pipeline이란?
3차원 공간의 데이터를
➡ 2차원 화면의 픽셀 이미지로 변환하는 GPU 처리 과정
쉽게 말해
3D 객체를 2D 모니터 화면에 출력하기까지의 단계적 절차
🧠 CPU vs GPU 역할 분리
| 구분 | 역할 |
|---|---|
| CPU | 씬 구성, 카메라/조명 설정, 리소스 준비, 드로우콜 생성 |
| GPU | 정점 처리, 픽셀 처리, 조명 계산, 프레임버퍼 출력 |
🛠️ GPU 렌더링 파이프라인 단계
| 순서 | 단계 | 개발자 관점 설명 | 주요 작업 |
|---|---|---|---|
| 1 | Input Assembler | 정점 데이터 결합 | Vertex/Index Buffer → 삼각형 |
| 2 | Vertex Shader | 정점 변환 | 좌표계 변환, 데이터 전달 |
| 3 | Tessellation (선택) | 곡면 세분화 | HS → Tessellator → DS |
| 4 | Geometry Shader (선택) | 정점 증감 | 파티클, 리본 생성 |
| 5 | Rasterizer | 픽셀화 | 삼각형 → Fragment |
| 6 | Pixel Shader | 색상 계산 | 조명, 텍스처 샘플링 |
| 7 | Output Merger | 최종 출력 | Z-Test, Blending |
[Vertex Data] → VS → Rasterize → PS → Screen
📐 좌표 변환 흐름 요약
| 단계 | 공간 | 설명 |
|---|---|---|
| 1 | Local | 모델 고유 좌표 |
| 2 | World | 월드 기준 좌표 |
| 3 | View | 카메라 기준 좌표 |
| 4 | Clip | 투영 적용 공간 |
| 5 | NDC | z 나누기 후 정규화 |
| 6 | Viewport | 화면 픽셀 좌표 |
💡 Viewport 변환을 응용하면
마우스 클릭 → 월드 좌표 충돌 판정 같은 기능도 구현 가능
🧩 HLSL 기본 구조 — 데이터 흐름
정점 ↔ 픽셀 데이터 전달 구조
| 구조체 | 역할 | 주요 Semantic |
|---|---|---|
VertexInput | CPU → Vertex Shader 입력 | POSITION, TEXCOORD, NORMAL |
VertexOutput | VS → PS 전달 | SV_POSITION, TEXCOORD |
HLSL 전역 리소스
| 구분 | 타입 | 역할 | 레지스터 |
|---|---|---|---|
| 상수 버퍼 | cbuffer | 변환 행렬, 파라미터 | b0 |
| 텍스처 | Texture2D | 이미지 데이터 | t0 |
| 샘플러 | SamplerState | 샘플링 방식 | s0 |
🧊 Vertex Shader vs Pixel Shader
| 구분 | Vertex Shader | Pixel Shader |
|---|---|---|
| 처리 단위 | 정점 | 픽셀(Fragment) |
| 주요 역할 | 좌표 변환, 데이터 전달 | 색상 결정, 조명 계산 |
| 입력 | Vertex Buffer | Rasterizer 보간 결과 |
| 출력 | 클립 공간 좌표 | 최종 색상 |
| 실행 빈도 | 정점 개수 기준 | 화면 해상도 기준 |
| 성능 영향 | 상대적으로 낮음 | 상대적으로 큼 |
⚠️ 정점 데이터 오류 유형
| 오류 유형 | 원인 | 결과 |
|---|---|---|
| UV 깨짐 | UV 레이아웃 불일치 | 텍스처 찢어짐 |
| 라이팅 이상 | 노멀 벡터 오류 | 빛 반사 왜곡 |
| 노멀맵 오류 | 탄젠트/바이노멀 불일치 | 표면 쉐이딩 깨짐 |
📌 모델링 단계(UV, 노멀 정리)가 렌더링 품질에 직접적인 영향을 줌
🧱 Object vs Mesh 개념 비교
| 구분 | Mesh | Object |
|---|---|---|
| 의미 | 기하 데이터 | 씬 상의 인스턴스 |
| 구성 | 정점, 인덱스 | Mesh + Transform + Material |
| 재사용성 | 매우 높음 | Mesh 공유 가능 |
| 역할 | 형태 정의 | 배치 및 표현 |
🔦 렌더링 기법 비교
Forward vs Deferred Rendering
| 구분 | Forward | Deferred |
|---|---|---|
| 조명 계산 시점 | 즉시 | 후처리 |
| 라이트 수 | 적을수록 유리 | 많아도 안정 |
| 투명 오브젝트 | 매우 적합 | 부적합 |
| 메모리 사용 | 적음 | 큼 (GBuffer) |
| 구현 난이도 | 낮음 | 높음 |
| 주 사용 플랫폼 | 모바일, NPR | PC, 콘솔 |
Deferred Rendering 구조 요약
| 단계 | 내용 |
|---|---|
| Geometry Pass | 표면 정보 기록 |
| GBuffer | Albedo, Normal, Roughness 등 |
| Lighting Pass | 조명 계산 |
| Post Process | 후처리 |
| Output | 최종 화면 |
📌 투명 머티리얼은 Forward로 별도 처리 (Hybrid 구조)
🎭 렌더링 스타일 비교
PBR vs NPR
| 구분 | PBR | NPR |
|---|---|---|
| 목표 | 현실 물리 기반 | 스타일 표현 |
| 조명 모델 | 물리 기반 | 커스텀 |
| 표현 방향 | 사실적 | 만화/아트 |
| 대표 사용 | AAA 게임 | 서브컬쳐 게임 |
🧪 PBR 주요 파라미터
| 파라미터 | 의미 | 범위 |
|---|---|---|
| Base Color | 기본 색상 | 0 ~ 1 |
| Metallic | 금속성 | 0 ~ 1 |
| Roughness | 거칠기 | 0(매끈) ~ 1(거침) |
| Specular | 반사 강도 | 0 ~ 1 |
🔁 PBR 워크플로우 비교
| 워크플로우 | 특징 |
|---|---|
| Roughness 기반 | 현대 표준 |
| Specular / Glossiness | 고전적 방식 |
| 관계 | Glossiness = 1 - Roughness |
🧠 핵심 요약 한 눈에
| 개념 | 핵심 |
|---|---|
| HLSL 구조 | VS → PS 데이터 전달 |
| VS | 위치 변환 |
| PS | 색상/조명 |
| Forward | 단순, 투명 강점 |
| Deferred | 다중 라이트 강점 |
| PBR | 현실 기반 |
| NPR | 스타일 기반 |
