TIL 2026-04-13

게시 2026/04/13

By GoldBoll

11 분읽는 시간

TIL 2026-04-13

2026-04-13 TA 수업 & 백준

백준 1157 — map vs int 배열

알파벳 대소문자로 이루어진 단어에서 가장 많이 사용된 알파벳을 대문자로 출력. 단, 대소문자 구분 없이 집계. 동률이면 ? 출력.

map 접근 방식 — range-for로 순회

  
map<char, int> m;
for (char c : str)
{
    if (c >= 'a' && c <= 'z')  // 소문자이면 대문자로 변환
        c = c - 'a' + 'A';     // ASCII 차이(32) 이용
    m[c]++;
}

int maxVal = 0;
char maxChar = '?';
bool dup = false;

for (auto& [key, val] : m)  // int 인덱스 대신 key/value 직접 순회
{
    if (val > maxVal)        { maxVal = val; maxChar = key; dup = false; }
    else if (val == maxVal)  { dup = true; }
}

cout << (dup ? '?' : maxChar) << "\n";

더 효율적인 방법 — int[26] 배열

  
int cnt[26] = {};               // A~Z 인덱스 0~25
for (char c : str)
    cnt[toupper(c) - 'A']++;    // 'A'=0, 'B'=1, ..., 'Z'=25

int maxVal = 0, maxIdx = -1;
bool dup = false;
for (int i = 0; i < 26; i++)
{
    if (cnt[i] > maxVal)        { maxVal = cnt[i]; maxIdx = i; dup = false; }
    else if (cnt[i] == maxVal)  { dup = true; }
}

cout << (dup ? "?" : string(1, 'A' + maxIdx)) << "\n";

	map 버전	int[26] 버전
접근 속도	O(log n)	O(1)
메모리	동적 할당	고정 104 bytes
순회 방법	range-for (key/value 쌍)	index for

toupper()

#include <cctype> 필요. 소문자 → 대문자 변환, 나머지는 그대로 반환.

  
toupper('a')  // 'A'
toupper('Z')  // 'Z'  (이미 대문자 → 그대로)
toupper('3')  // '3'  (숫자 → 그대로)

// if문 — ASCII 차이(32) 직접 이용
if (c >= 'a' && c <= 'z')  c = c - 'a' + 'A';

// toupper — 동일한 동작, 더 간결
c = toupper(c);

'a'(97) - 'A'(65) = 32 차이 이용. 반대는 tolower(c)

심화반 테스트 풀이 복기

1번 — 팰린드롬 판별

문자열 s가 팰린드롬이면 1, 아니면 0 반환.

  
int solution(const string& s) {
    if (s.empty()) return 0;
    if (s.size() == 1) return 1;

    int left = 0;
    int right = (int)s.size() - 1;

    while (left < right) {
        if (s[left] != s[right]) return 0;
        left++;
        right--;
    }
    return 1;
}

시간복잡도: O(n) — 문자열 절반만 순회
s.size()는 unsigned형이므로 -1 연산 시 (int) 캐스팅 주의

2번 — 섬의 개수 세기 BFS

N×M 격자에서 상하좌우로 연결된 땅(1)의 덩어리 수 반환.

// BFS: queue 사용, 방문 표시는 grid[r][c] = 0 덮어쓰기

방법	자료구조	특징
BFS	`queue`	가까운 칸부터 탐색, 반복문으로 구현
DFS (재귀)	호출 스택	깊은 곳 먼저 탐색, 스택 오버플로우 위험

queue(힙 메모리)를 쓰면 격자가 매우 커도 스택 오버플로우 없이 안전 시간복잡도: O(N × M)

3번 — 반사 벡터 계산

입사 벡터 D, 법선 벡터 N이 주어질 때 반사 벡터 R을 구하시오. (내적 활용)

반사 벡터 공식 유도

D를 법선(N) 방향 성분과 접선 방향 성분으로 분해
법선 방향 성분 = (D·N)N
접선 방향 성분 = D - (D·N)N
반사 = 접선 성분 유지, 법선 성분 반전

→ R = D - 2(D·N)N

  
struct Vector3 {
    float x, y, z;

    float dot(const Vector3& o) const {
        return x*o.x + y*o.y + z*o.z;
    }
    Vector3 operator-(const Vector3& o) const { return {x-o.x, y-o.y, z-o.z}; }
    Vector3 operator*(float t)           const { return {x*t,   y*t,   z*t};   }
};

// D: 입사 벡터, N: 법선 단위 벡터
// R = D - 2*(D·N)*N
Vector3 reflect(const Vector3& D, const Vector3& N) {
    return D - N * (2.0f * D.dot(N));
}

D·N = 내적 → 입사 벡터의 법선 방향 성분 크기 추출
N은 반드시 단위 벡터(크기=1) 이어야 공식 성립
언리얼: FVector::MirrorByVector() 내부가 이 공식 그대로 구현됨

4번 — virtual 소멸자

  
class Base {
public:
    ~Base() {}  // virtual 없음!
};
class Derived : public Base {
public:
    int* data;
    Derived() { data = new int[100]; }
    ~Derived() { delete[] data; }
};

Base* obj = new Derived();
delete obj;  // Derived::~Derived() 미호출 → 메모리 누수

정답: Derived의 소멸자가 호출되지 않아 메모리 누수 발생

Base::~Base()에 virtual이 없으면 delete obj 시 컴파일 타임 타입(Base*) 기준으로 소멸자 결정 → Derived::~Derived() 미호출 → data 메모리 해제 안 됨

  
virtual ~Base() {}  // virtual 추가 → 런타임에 Derived::~Derived() 호출

상속 구조에서 기반 클래스 소멸자는 항상 virtual 로 선언

5번 — volatile과 멀티스레드

정답: volatile은 컴파일러 최적화를 막지만, CPU 명령어 재정렬(reordering)은 막지 못한다

	volatile	std::atomic
컴파일러 레지스터 캐싱 방지	✅	✅
CPU 명령어 재정렬 방지	❌	✅
원자적(atomic) 접근 보장	❌	✅
멀티스레드 안전	❌	✅

volatile = “항상 메모리에서 읽어라” 만 보장 멀티스레드 공유 변수에는 std::atomic<T> 또는 mutex 사용

6번 — 캐시 지역성

정답: A — C++은 행 우선(row-major) 저장 방식이라 A가 연속된 메모리를 순서대로 접근

arr[0][0] arr[0][1] arr[0][2] | arr[1][0] arr[1][1] ...
←────── 연속된 메모리 ──────────────────────────────→

코드	접근 패턴	결과
A: `arr[i][j]` (i 고정, j 증가)	연속 메모리 순서 접근	캐시 히트 ✅
B: `arr[i][j]` (j 고정, i 증가)	행을 건너뛰며 접근	캐시 미스 ❌

캐시 라인(보통 64바이트)에 인접한 데이터가 미리 로드됨 열 방향 접근(B)은 매번 캐시 라인 교체 → 성능 저하

7번 — 피보나치 시간복잡도

정답: O(2ⁿ)

  
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);  // 매 호출마다 2개로 분기
}

fib(n) 호출 시 두 갈래로 분기 → n번 반복 → 호출 횟수 ≈ 2ⁿ

방법	시간복잡도	공간복잡도
순수 재귀	O(2ⁿ)	O(n) 스택
메모이제이션 (Top-Down DP)	O(n)	O(n)
반복문 (Bottom-Up DP)	O(n)	O(1)

재귀 호출이 2개로 분기되면 시간복잡도는 지수적으로 증가 실무/코테에서 피보나치는 반드시 DP 로 풀 것

8번 — 스마트 포인터와 순환 참조

  
struct Node {
    shared_ptr<Node> next;
    shared_ptr<Node> prev;
};
auto a = make_shared<Node>();  // ref count = 1
auto b = make_shared<Node>();  // ref count = 1
a->next = b;  // b ref count = 2
b->prev = a;  // a ref count = 2
// a, b 소멸 시 ref count 2 → 1 → 영원히 0이 안 됨 → 메모리 누수

해결: weak_ptr 사용

weak_ptr은 참조 카운트를 증가시키지 않는 약한 참조.

  
struct Node {
    shared_ptr<Node> next;  // 강한 참조 (앞방향)
    weak_ptr<Node>   prev;  // 약한 참조 (뒤방향) ← 변경
};

	shared_ptr	weak_ptr
참조 카운트 증가	✅	❌
객체 수명 연장	✅	❌
순환 참조 유발	가능	해결책

양방향 연결(이중 연결 리스트, 부모↔자식)에서는 한쪽을 반드시 weak_ptr 로 사용

9번 — 데이터 지향 설계 DOD

수천 개의 Enemy를 매 프레임 위치만 업데이트하는 상황에서 AoS vs SoA 비교.

  
// 설계 A: AoS (Array of Structures)
struct Enemy { FVector pos; float hp; float speed; };
TArray<Enemy> enemies;
// 메모리: [pos|hp|speed][pos|hp|speed]...

// 설계 B: SoA (Structure of Arrays)
struct EnemyData {
    TArray<FVector> positions;  // [pos][pos][pos]...
    TArray<float>   hps;        // [hp][hp][hp]...
    TArray<float>   speeds;     // [speed][speed][speed]...
};

정답: SoA(설계 B)가 유리

	AoS	SoA
위치만 업데이트 시	hp·speed도 캐시에 함께 로드 → 낭비	positions만 연속 접근 → 캐시 효율 ✅
캐시 히트율	낮음	높음

특정 필드만 반복 접근할 때는 SoA가 캐시 효율 우세
언리얼 Mass Entity / ECS 아키텍처가 SoA 기반으로 설계된 이유

TIL, 2026-04

daily til

TIL 2026-04-13

2026-04-13 TA 수업 & 백준

목차

백준 1157 — map vs int 배열

map 접근 방식 — range-for로 순회

더 효율적인 방법 — int[26] 배열

toupper()

심화반 테스트 풀이 복기

1번 — 팰린드롬 판별

2번 — 섬의 개수 세기 BFS

3번 — 반사 벡터 계산

4번 — virtual 소멸자

5번 — volatile과 멀티스레드

6번 — 캐시 지역성

7번 — 피보나치 시간복잡도

8번 — 스마트 포인터와 순환 참조

9번 — 데이터 지향 설계 DOD

인기 태그