처음으로 일정을 일일히 적지 않겠다. 막판에 내가 아파서 병원에 입원까지 했기 때문이다. 원래 입원할 생각은 없었는데, 내과의가 증상을 듣고, 혹시 모르니 응급실 가서 정밀 진단을 받아보라고 조언하였다. 덕분에 핀토스 마지막 2일을 누워있었다.

팀원 회고도 없이 바로 자리 이동해버렸다. (물어보니 나를 제외하고 이미 3명에서 했다고 한다.)

Pintos Project 3: Virtual Memory

1. 이번 주 마음가짐 + 목표

Project 2 (User Programs) 에서 "동기화 프리미티브를 직접 조립해 새 시맨틱을 만드는" 경험을 했다. 이번 Project 3 는 그 위에 메모리를 어떻게 거짓말할 것인가 가 올라온다. 물리 메모리는 유한한데, 유저 프로그램에게는 충분한 것처럼 보여야 한다. 그 거짓말을 떠받치는 네 개의 기둥 — lazy loading, stack growth, anonymous swap, 그리고 이 셋이 fork/exec 와 맞물리는 lifecycle — 을 세우는 것이 이번 주의 일이었다.

발제에서 "Project 3 는 단일 기능은 어렵지 않은데 결합이 어렵다" 는 말을 들었다. 직접 겪어 보니 정확했다. lazy loading 하나, swap 하나, fork 하나는 각각 통과하는데, page-merge-* 처럼 셋이 동시에 도는 순간 그동안 숨어 있던 ownership 의 빈틈이 한꺼번에 드러났다.

목표:

• SPT (Supplemental Page Table) + lazy loading 으로 page fault 기반 적재
• stack growth 휴리스틱으로 동적 스택 확장
• anonymous page swap in/out (bitmap + swap disk)
• fork 시 SPT 깊은 복사, exec 시 SPT 교체가 정확히 동작
• 단순 통과가 아니라 "왜 이 시점에 이 자원을 정리하는가" 를 함수 경계별로 설명할 수 있는 수준

2. 관통하는 한 가지 원리 — "약속은 빨리, 이행은 늦게"

Project 3 의 네 메커니즘은 표면적으로 따로 놀지만, 결국 하나의 원리의 변주였다. 가상 주소 공간은 즉시 약속하고, 실제 물리 페이지는 마지막 순간까지 미룬다.

이 셋은 코드 구조도 거의 같다. vm_alloc_page_with_initializer 로 SPT 에 메모를 남기고, 첫 fault 때 uninit_initialize 가 그 메모를 실제 페이지로 "변신" 시킨다.

load_segment / vm_stack_growth
    ↓ vm_alloc_page_with_initializer (약속만)
SPT 에 uninit page 등록
    ↓ (시간이 흐른 뒤, 접근 발생)
page fault → vm_try_handle_fault → vm_do_claim_page
    ↓ swap_in(page, kva)
uninit_initialize
    ↓ page_initializer (anon/file 으로 타입 변신)
    ↓ init (lazy_load_segment — 진짜 파일 읽기)

malloc 과의 대비가 이 원리를 가장 선명하게 보여준다. malloc 은 "지금 줘" 라고 말하고 즉시 물리 메모리를 받는다. stack growth 는 "필요해질 때 줘" 라고 약속만 한다 — 가상 주소 공간은 이미 거기 있고, page fault 가 일어나는 순간에야 매핑이 활성화된다. 같은 "할당" 이라는 단어가 두 가지 다른 시점을 가리킨다.

그런데 이 "늦은 이행" 이 두 번째 축의 함정을 만든다. 자원의 생성과 소멸 시점이 시간적으로 흩어지니, 누가 그 자원을 소유하고 언제 정리하는지 가 불명확하면 반드시 깨진다. 이번 주 가장 길게 헤맨 두 사건이 정확히 이 지점에서 터졌다.

3. 시도한 접근 방식

3.1 Lazy Loading — load 시점엔 메모만, fault 때 실제 적재

load_segment 는 ELF 세그먼트를 즉시 메모리에 올리지 않는다. 페이지 단위로 분할해 각 페이지마다 lazy_load_aux (file / offset / read_bytes / zero_bytes) 를 만들고, vm_alloc_page_with_initializer(VM_ANON, ..., lazy_load_segment, aux) 로 SPT 에 등록만 한다.

첫 fault 가 나면 uninit_initialize 가 두 단계를 순서대로 호출한다:

/* vm/uninit.c — uninit_initialize */
vm_initializer *init = uninit->init;   /* page_initializer 호출 전에 미리 캐싱 */
void *aux = uninit->aux;               /* union 이 덮어쓰기 전에 빼둔다 */

return uninit->page_initializer (page, uninit->type, kva)   /* anon 으로 변신 */
    && (init ? init (page, aux) : true);                    /* 파일 읽기 */

init 과 aux 를 로컬에 먼저 캐싱하는 이유: page_initializer (anon_initializer) 가 page->anon 을 건드리는데, 이건 page->uninit 과 같은 union 메모리다. 캐싱 안 하면 변신 직후 uninit->aux 가 이미 덮인 garbage 일 수 있다.

3.2 Stack Growth — rsp 기준 휴리스틱

vm_try_handle_fault 에서 SPT 에 없는 주소에 fault 가 나면, 그게 정당한 스택 확장인지 판단한다.

void *stack_bottom = (void *)(USER_STACK - (1 << 20));   /* 1MB 한도 */

if (addr >= stack_bottom && addr < (void *)USER_STACK
    && addr >= (void *)((uintptr_t)rsp - 8)) {
    vm_stack_growth(addr);
    return true;
}

세 조건을 모두 만족해야 한다: (1) 1MB 한도 안, (2) USER_STACK 아래, (3) rsp - 8 이상.

세 번째가 가장 미묘하다. x86-64 의 PUSH 는 (1) rsp 를 8 감소시키고 (2) 그 자리에 값을 쓴다. 1 단계와 2 단계 사이에 fault 가 나면, 그 시점의 fault 주소는 현재 rsp - 8 이다. addr >= rsp 만 검사하면 정상 PUSH 가 일으킨 fault 를 잘못 거부한다.

rsp 를 어디서 얻느냐도 함정이었다. 유저 모드 fault 면 f->rsp 가 유저 rsp 지만, 커널 모드 (syscall 처리 중) fault 면 f->rsp 는 커널 rsp 다. 그래서 syscall 진입 시 유저 rsp 를 따로 저장해 둬야 한다.

void *rsp;
if (user) rsp = (void *)f->rsp;
else      rsp = (void *)thread_current()->user_rsp;

3.3 Anonymous Swap — bitmap + 8 섹터 I/O

물리 메모리가 부족하면 anon 페이지를 swap disk 로 내보낸다. 핵심 자료구조는 anon_page.swap_slot (SIZE_MAX = 메모리에 있음, 그 외 = 디스크 슬롯 번호) 와 전역 swap_table bitmap.

swap disk 의 한 페이지 (4KB) = 8 섹터 (각 512B). 그래서 디스크 I/O 는 8 회 반복.

/* anon_swap_out */
size_t slot = bitmap_scan_and_flip(swap_table, 0, 1, false);
for (int i = 0; i < 8; i++)
    disk_write(swap_disk, slot * 8 + i, page->frame->kva + i * 512);
pml4_clear_page(page->owner->pml4, page->va);   /* ★ owner, not thread_current */
anon_page->swap_slot = slot;

vm_get_victim 은 frame_table 에서 FIFO 로 victim 을 고른다. vm_get_frame 에서 palloc 이 실패하면 vm_evict_frame 을 불러 victim 을 비우고 그 frame 을 재활용한다.

3.4 page->owner — victim 은 내 페이지가 아닐 수 있다

anon_swap_out 에서 처음엔 pml4_clear_page(thread_current()->pml4, ...) 를 썼다가 깨졌다. evict 를 호출한 스레드와 victim 페이지의 소유자 가 다를 수 있기 때문이다. 다른 프로세스의 페이지를 내보내는데 내 pml4 에서 매핑을 지우면, 정작 그 페이지의 진짜 매핑은 그대로 남는다.

해결: struct page 에 owner 필드를 추가하고, vm_alloc_page_with_initializer 에서 page->owner = thread_current() 로 기록. swap_out 은 page->owner->pml4 를 쓴다. 이것도 결국 ownership 문제였다 — "이 페이지의 주인이 누구인가" 를 페이지 자신이 알고 있어야 했다.

4. 사건 1 — info->zero_bytes 가 garbage 가 된 추적

page-merge-seq 까지 통과시킨 swap 구현 직후, page-merge-par 와 page-merge-stk 가 못 넘어갔다. 증상은 둘이 달랐지만 (한쪽은 filesys_open NULL, 한쪽은 zero_bytes ASSERT), 추적해 보니 뿌리가 같았다.

4.1 증상 — 황당하게 큰 숫자

PANIC: assertion `info->zero_bytes <= PGSIZE' failed.

info 는 load_segment 가 페이지마다 malloc 한 lazy_load_aux. zero_bytes 는 0 ~ 4096 사이여야 정상인데, 출력해 보니 549825401640 같은 값이 찍혔다.

lazy_load_aux 레이아웃 (32 bytes):

마지막 필드만 손상됐다. 이건 누군가 이 32 바이트 슬롯이 free 된 뒤 같은 자리에 다른 구조체를 할당했고, 그 구조체의 포인터 필드가 정확히 예전 zero_bytes 위치에 들어간 것이다. 즉 free 된 메모리를 다시 읽고 있다.

cccccccc 패턴이나 비현실적으로 큰 숫자는 거의 항상 use-after-free 또는 인접 메모리 침범의 신호다. 값이 잘못된 위치만 보지 말고, 그 메모리의 lifecycle 을 추적해야 한다 — 이게 이번 사건의 핵심 교훈이었다.

4.2 원인 1 — uninit aux 누수 (exec 경로)

process_exec 은 새 ELF 를 로드하기 전에 supplemental_page_table_kill 을 부른다. 그 안의 hash_destroy 가 각 페이지의 destroy 콜백을 호출하는데, 한 번도 fault 되지 않은 페이지는 여전히 VM_UNINIT 상태라 uninit_destroy 가 불린다. 그런데 그 함수가 비어 있었다.

/* 수정 전 — vm/uninit.c */
static void
uninit_destroy (struct page *page) {
    struct uninit_page *uninit UNUSED = &page->uninit;
    /* TODO: Fill this function. */   /* ← aux 가 영영 free 안 됨 */
}

load_segment 가 페이지마다 malloc 한 lazy_load_aux 가, fault 없이 죽는 페이지에서는 누구도 free 하지 않는다. page-merge-par/stk 는 child 를 여러 번 fork+exec 하므로 누수가 누적돼 malloc 풀을 오염시킨다. 그러다 새 malloc 이 누수된 영역과 겹치면서 garbage 발생.

/* 수정 후 */
static void
uninit_destroy (struct page *page) {
    struct uninit_page *uninit = &page->uninit;
    if (uninit->aux != NULL)
        free(uninit->aux);
}

4.3 원인 2 — file ownership 부재 (fork 경로)

supplemental_page_table_copy 의 VM_UNINIT 케이스에서, 자식이 부모의 aux 를 복사할 때 file 포인터 처리가 문제였다. 처음엔 페이지마다 file_duplicate 를 했는데, 이건 반대로 과했다 — 자식의 모든 UNINIT 페이지가 제각각 file 객체를 새로 열어 inode->open_cnt 가 폭증, 8 회 fork 에 400 개씩 누수돼 kernel pool 의 small-block 이 말랐다.

올바른 ownership 설계는 fork 당 한 번만 file 을 복제하고, 페이지들은 그것을 공유하는 것이었다:

/* __do_fork — fork 당 한 번만 dup */
current->running_file = file_duplicate(parent->running_file);

/* supplemental_page_table_copy VM_UNINIT — 공유만 */
new_aux->file = thread_current()->running_file;   /* 공유 */
new_aux->owns_file = false;                        /* 이 aux 는 안 닫음 */

owns_file 플래그로 "누가 이 file 을 닫을 책임이 있는가" 를 명시했다. UNINIT aux 들은 running_file 을 빌려 쓸 뿐, 닫는 건 process_cleanup 이 한 번에 한다.

4.4 다섯 줄 회수 짝

이 사건을 정리하며 만든 표 — "어디서 무엇을 만들고, 어디서 회수하는가" 의 짝을 명시적으로 적었다.

이 표를 그리고 나서야 비로소 버그가 보였다. 생성과 회수의 짝이 맞지 않는 행이 곧 버그였다.

5. 사건 2 — fd_table 이 먹은 커널 스택, is_thread 패닉

사건 1 을 잡고 나서도 exec-missing, wait-killed, multi-recurse 가 같은 패닉으로 떨어졌다.

PANIC at threads/thread.c:288 in thread_current(): assertion `is_thread (t)' failed.

5.1 magic 이라는 canary

is_thread(t) 는 t->magic == THREAD_MAGIC 를 검사한다. magic 은 struct thread 의 가장 끝 4 바이트에 박힌 canary 값 (0xcd6abf4b) 이다.

Pintos 의 커널 스택은 thread 당 4KB 페이지 하나다. 그 페이지의 아래쪽에 struct thread 가 있고, 위쪽이 함수 호출 스택이다. 호출이 너무 깊어져 스택이 페이지 아래로 자라면, 가장 먼저 struct thread 의 끝 — 즉 magic — 을 덮어쓴다. 그래서 magic 이 깨졌다는 건 커널 스택이 thread struct 영역을 침범했다 는 신호다.

5.2 측정이 측정 대상을 바꾼다

원인을 좁히려 printf 로 probe 를 박았는데, 여기서 역설을 만났다.

[PROBE-A] stack_used=1168 struct_sz=1616 magic_off=1608 magic=cd6abf4b   ← 정상
[PROBE-B] stack_used=1168 magic=cd6abf4b file_is_null=0                  ← 정상
[Kernel PANIC ... is_thread failed                                       ← 그 직후 패닉

probe 시점까지 magic 은 멀쩡한데 바로 다음에 패닉. printf 자체가 깊은 콜 체인 (vprintf → putchar_have_lock → thread_current) 을 타면서 스택을 더 밀어 magic 을 덮은 것이다. 측정 도구 (printf) 가 측정 대상 (스택 여유) 을 변형 했다. probe 를 빼면 패닉 위치가 또 바뀌었다.

5.3 1024 바이트의 진실

struct thread 안에 fd_table[128] 이 직접 박혀 있었다.

struct file *fd_table[128];   /* 128 * 8 = 1024 bytes */

offsetof(magic) = 1608. 즉 struct thread 가 1616 바이트인데 그중 1024 바이트, 약 64% 가 fd_table 이었다. 4KB 페이지에서 이만큼을 struct 가 먹으니 실제 함수 호출 스택은 ~2.5KB 밖에 안 남았다.

평소엔 버텼다. 그런데 swap 이 활성화되면서 호출 체인이 깊어졌다:

syscall → filesys_lock → file_read → page fault
  → vm_try_handle_fault → vm_do_claim_page → vm_get_frame
  → palloc 실패 → vm_evict_frame → anon_swap_out → disk_write × 8

이 체인이 2.5KB 한계선을 넘는 순간 magic 이 덮였다.

5.4 영구 수정 — 힙으로 분리

struct file **fd_table;   /* 8 bytes (포인터만) */

/* thread 생성 시 */
t->fd_table = palloc_get_page(PAL_ZERO);

/* thread 종료 시 */
palloc_free_page(t->fd_table);

struct thread 가 1024 바이트 줄어 커널 스택에 그만큼 여유가 생겼다. 인덱스 접근 (fd_table[i]) 문법은 그대로라 호출하는 모든 코드가 변경 없이 작동한다. 호출 체인 깊이에 무관하게 안전해진, 말 그대로 영구 수정이다.

여기서 유저 스택과 커널 스택의 대비가 선명해졌다. 유저 스택은 lazy 하게 1MB 까지 확장하지만 (사건 외 §3.2), 커널 스택은 4KB 고정이다 — 인터럽트 컨텍스트에서 page fault 가 나면 안 되니 확장할 수 없다. 그래서 커널은 큰 데이터를 struct 가 아니라 힙에 둬야 한다.

6. 결과

anon 영역 (lazy loading, stack growth, swap, fork/exec 통합) 은 사실상 완성됐다. mmap (file-backed page) 은 현재 구현 진행 중이며, do_mmap / do_munmap / file_backed_swap_in/out / SYS_MMAP 핸들러가 미완성 상태다. file-backed 페이지의 lifecycle 은 anon 의 swap 패턴에 "dirty 페이지만 원본 파일로 write-back" 이 더해진 형태로, anon 에서 익힌 ownership 설계를 그대로 적용하는 중이다.

7. 기술 정리

7.1 page fault 의 단일 진입점

네 메커니즘이 모두 vm_try_handle_fault 한 곳에서 만난다.

page fault
  ↓ vm_try_handle_fault
  1. 유효 주소 검증 (NULL, 커널 주소, not_present)
  2. SPT 조회 → 페이지 있나?
       없음 → stack growth 가능한가? (rsp - 8 휴리스틱)
       있음 → vm_do_claim_page
  3. vm_do_claim_page
       → vm_get_frame (부족하면 evict + swap_out)
       → pml4_set_page
       → swap_in (타입별: uninit→lazy, anon→disk read)

진입점이 하나라서 한 메커니즘의 버그가 다른 메커니즘의 증상으로 나타난다. 이게 "결합이 어렵다" 의 실체였다.

7.2 ownership 을 명시적으로 — 세 가지 적용

이번 주 버그의 공통 뿌리는 "누가 소유하고 언제 정리하는가" 가 암묵적이었다는 것이다. 해결은 모두 그것을 명시적으로 만드는 일이었다.

7.3 디버깅 시그니처 (Project 2 의 표를 확장)

아래 두 줄이 이번 주에 새로 추가된 시그니처다. garbage 값은 "값이 어디서 잘못됐나" 가 아니라 "이 메모리를 누가 free 한 뒤 누가 다시 쓰나" 를 물어야 했고, probe 가 패닉 위치를 바꾸는 현상은 그 자체가 "스택 여유가 문제" 라는 단서였다.

8. 함정 모음

9. 느낀 점

Project 2 가 "동기화 프리미티브를 조립해 새 시맨틱을 만드는" 경험이었다면, Project 3 는 "자원의 생성과 소멸 시점이 흩어진 세계에서 ownership 을 명시적으로 유지하는" 경험이었다. lazy 의 본질은 약속과 이행의 분리인데, 그 분리가 만든 시간적 틈에서 ownership 이 암묵적이면 반드시 무너졌다.

가장 인상 깊었던 두 사건:

zero_bytes garbage 추적. 황당하게 큰 숫자 하나에서 출발해, 그게 free 된 슬롯의 재사용임을 알아채고, exec 경로의 aux 누수와 fork 경로의 file 공유라는 두 원인을 분리해냈다. 처음엔 "값이 어디서 잘못됐나" 를 쫓았는데, 그 방향으로는 끝이 없었다. "이 메모리를 누가 free 한 뒤 누가 다시 쓰나" 로 질문을 바꾸고서야 길이 보였다. 다섯 줄 회수 짝 표를 그리고 나니 짝이 안 맞는 행이 곧 버그였다 — 증상이 아니라 자원의 lifecycle 을 표로 그리는 것이 디버깅이었다.

fd_table 의 magic 패닉. is_thread assertion 이 사실은 canary 가 깨졌다는 신호였고, 그 canary 가 깨진 건 커널 스택이 thread struct 를 침범했기 때문이고, 침범한 이유는 fd_table 1024 바이트가 4KB 페이지의 64% 를 먹었기 때문이었다. 증상 (assertion) 에서 원인 (스택 64% 점유) 까지의 거리가 멀었다. 결정적으로, probe 를 박을수록 패닉 위치가 바뀌는 현상 자체가 "스택 여유가 문제" 라는 메타-단서였다 — 측정이 대상을 바꾼다는 걸 커널에서 직접 겪었다.

두 사건 모두 Project 2 의 wait-twice 에서 배운 교훈 — "증상의 가시적 위치와 원인의 위치가 분리되어 있을 때, 호출 흐름을 끝까지 거꾸로 따라가는 것만이 답" — 이 그대로 반복됐다. 이번엔 거기에 한 가지가 더해졌다. 메모리 버그에서는 호출 흐름뿐 아니라 자원의 생성-소멸 흐름 을 끝까지 따라가야 한다는 것. 함수가 언제 불리는가 만큼이나, 이 메모리가 언제 태어나 언제 죽는가가 중요했다.

mmap 은 아직 미완성이다. 하지만 anon 에서 ownership 을 명시적으로 설계하는 법을 익혔으니, file-backed 페이지의 write-back lifecycle 도 같은 원리로 풀 수 있을 것이다. "dirty 한 페이지를 언제, 누가, 어느 파일에 되돌려쓰는가" — 결국 또 ownership 의 문제다.

GitHub: https://github.com/JYPark-Code/SW-AI-W1112-Pintos Week 11–12 | Pintos Project 3 Virtual Memory

병원때문에 집에 갔고, 끝나자마자 바로 토요일에 점심 먹기 전에 복귀해서 첫 외출인데, 스스로 지쳐서 이번주도 나갈 예정.

Pintos_kaist_64bit (2주차 / 총 4주 일정)

같은 팀 9 ~10 주차

5월 1일 금요일 Week 9~10팀 구성 Arg passing 관련 학습

5월 2일 토요일 잠시 집 갔다오고 Arg passing ~ halt, exit

5월 3일 일요일 농구대회 우승해서 반 회식

5월 4일 월요일 스스로 Create, Open, close M1 완료, 그 이후에 Read, Write 완성

5월 5일 화요일 fork, exec, wait

5월 6일 수요일 wait_double 발표 자료 만들기

5월 7일 목요일 Pintos - PR Merge 때 발생한 이슈, Process_wait를 주제로 발표 Week10 팀 회고 WIL 작성

Project 2: User Programs

1. 이번 주 마음가짐 + 목표

Project 1 (Thread) 에서 동기화의 기본기를 익혔으니, 이번엔 그 기본기 위에 유저 프로그램 이 올라간다. 커널과 유저 사이의 경계 — system call, 파일 디스크립터, 페이지 테이블, 부모-자식 동기화 — 가 한꺼번에 들어오는 단계다.

발제에서 들었던 "fork까지 오기도 어렵다" 는 말이 사실이었다. argument passing 과 file syscall 까지는 비교적 직관적이었는데, fork 부터는 자료구조 + 동기화 + 페이지 테이블 복제 가 동시에 맞물려야 한다.

목표:

• args / halt / exit / file syscall (CREATE / OPEN / CLOSE / READ / WRITE / FILESIZE) 전체 PASS
• fork / exec / wait 16 개 테스트 전체 PASS
• 단순 통과가 아니라 "왜 이 구현인가" 를 함수 경계 별로 설명할 수 있는 수준

2. 시도한 접근 방식

2.1 Argument Passing — 유저 스택에 argc/argv 배치

process_exec 가 ELF 를 메모리에 올리고 do_iret() 으로 유저 모드 진입할 때, 유저 스택에 인자가 없으면 main(argc, argv) 가 쓰레기 값을 받는다. 6 단 스택 레이아웃 으로 해결.

높은 주소
┌──────────────────────────────┐
│ argv[0] 문자열 \0            │
│ argv[1] 문자열 \0            │
│ ...                          │
├──────────────────────────────┤
│ word-align 패딩 (0~7 bytes)  │
├──────────────────────────────┤
│ NULL sentinel (8 bytes)      │   ← argv[argc] = 0
├──────────────────────────────┤
│ argv[argc-1] 포인터          │
│ ...                          │
│ argv[0] 포인터 (8 bytes)     │   ← rsi 여기
├──────────────────────────────┤
│ fake return address = 0      │   ← rsp 여기
└──────────────────────────────┘
낮은 주소

rdi = argc, rsi = argv[0] 포인터의 주소 를 intr_frame 에 직접 기록한다. rsi 를 rsp + 8 로 계산하지 않고 fake return address push 이전에 캡처하는 게 의도가 명확하다 — do_iret 이후 %rsi 가 곧바로 main 의 두 번째 인자로 전달되기 때문.

word-align 의 이유: x86-64 System V ABI 는 call 직전 rsp 가 16-byte 정렬 상태임을 보장한다. 정렬 없이 movaps 같은 SSE 명령이 실행되면 #GP fault.

2.2 File Syscall — 인프라 먼저, 콜은 그 위에

콜 자체는 filesys_create / filesys_open / file_close 같은 한 줄 래퍼. 무게중심은 그 한 줄을 안전하게 부르기 위한 인프라 3 개 에 있었다.

인프라 1 — per-thread fd 테이블

/* threads/thread.h */
struct thread {
    ...
    struct file *fd_table[128];
    int fd_next;   /* 0=stdin, 1=stdout 예약. 2부터 발급 */
};

/* init_thread() */
t->fd_next = 2;

128 크기 고정 배열, fd_next 단조 증가 (close 슬롯 재사용 안 함). 단순함을 택하고 한계가 드러나면 나중에 확장. 이 fd_table 은 §2.3 fork 단계에서 file_duplicate 로 슬롯별 깊은 복사하는 패턴으로 자연스럽게 확장됐다.

인프라 2 — 전역 파일시스템 락

struct lock filesys_lock;

void
syscall_init (void) {
    lock_init(&filesys_lock);
    ...
}

Pintos 기본 파일시스템은 thread-safe 가 아니다. 모든 filesys_* 콜을 같은 락으로 직렬화 — 굵은 락이지만 정확성은 보장된다. 검증은 락 밖, filesys 호출은 락 안 원칙.

인프라 3 — 유저 포인터 3 단 검증

static void
validate_user_addr (const void *uaddr) {
    if (uaddr == NULL || !is_user_vaddr(uaddr)
        || pml4_get_page(thread_current()->pml4, uaddr) == NULL) {
        thread_current()->exit_status = -1;
        thread_exit();
    }
}

KAIST 64bit 의 함정: KERN_BASE 가 32bit Pintos 의 0xc0000000 이 아니라 0x8004000000. bad-ptr 테스트가 던지는 0x20101234 가 64bit 유저 영역에 합법적으로 들어와 ②까지 통과해 버린다 → ③ 가 없으면 못 잡는다.

2.3 fd_table 분기 처리 — READ ↔ WRITE 대칭

범위 체크가 분기 트리의 가장 위 에 있어야 한다. fd == 0 / fd == 1 만 체크하고 else 로 빠지면 음수 fd 가 그대로 fd_table[-1] 로 가서 페이지 폴트. read-bad-fd 테스트가 정확히 이 케이스를 잡는다.

2.4 Fork — 자료구조 + 동기화 + 페이지 테이블 복제

fork 는 한 번에 세 축이 들어온다.

자료구조

/* thread.h, #ifdef USERPROG */
struct semaphore fork_sema;     /* 자식이 메모리 복사 끝나면 up, 부모가 down */
struct semaphore wait_sema;     /* 자식 종료 시 up, 부모가 down */
struct semaphore exit_sema;     /* 부모 wait 회수 시 up, 자식이 down */
struct list children;           /* 직계 자식 리스트 */
struct list_elem child_elem;
struct thread *parent;

thread_create 가 모든 신생 스레드에 대해 자동으로 t->parent = current; list_push_back(&current->children, &t->child_elem); 을 한다 — 이게 §6 wait-twice 사건의 시작점이 된다 (자세한 건 뒤에서).

__do_fork 흐름

1. aux 캐스팅 → fork_args 풀기
   parent_if 를 자식 스택의 if_ 로 memcpy
   args free

2. pml4_create + pml4_for_each(parent->pml4, duplicate_pte, parent)
   → 부모의 모든 유저 페이지를 자식에 deep copy

3. fd_table 슬롯별 file_duplicate
   → 포인터 복사 안 됨. file 객체 자체를 새로 (offset 독립)
   fd_next 도 복사

4. if_.R.rax = 0 (자식의 fork 반환값)
   sema_up(parent->fork_sema)  → 부모 깨움
   do_iret(&if_)               → 유저 모드 진입

핵심 invariant: 부모는 자식의 메모리/fd 복제가 끝날 때까지 BLOCKED. 자식이 부모의 주소공간을 참조하는 동안 부모가 syscall 로 그 공간을 바꾸면 안 된다. error 케이스에도 sema_up(fork_sema) 필수 — 그렇지 않으면 부모가 영원히 대기.

duplicate_pte — 한 페이지씩 복사

static bool duplicate_pte(uint64_t *pte, void *va, void *aux) {
    if (is_kernel_vaddr(va)) return true;     /* 1. 커널 페이지 스킵 */

    void *parent_page = pml4_get_page(parent->pml4, va);
    void *newpage = palloc_get_page(PAL_USER | PAL_ZERO);   /* 2. 새 페이지 */
    if (newpage == NULL) return false;

    memcpy(newpage, parent_page, PGSIZE);     /* 3. 내용 복사 */
    bool writable = is_writable(pte);         /* 4. W 비트 승계 */

    if (!pml4_set_page(current->pml4, va, newpage, writable)) {
        palloc_free_page(newpage);
        return false;
    }
    return true;
}

Project 2 는 정직한 deep copy. CoW 는 Project 3 범위. 부모와 같은 물리 페이지를 가리키게 하면 안 된다.

2.5 Wait — sema 두 개로 양방향 동기화

[부모 process_wait]                  [자식 process_exit]
sema_down(child->wait_sema) ⏸    
                                     printf("name: exit(N)")
                                     process_cleanup()
                                     sema_up(self->wait_sema)  ──┐
   ⏸ ← ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ──┘
                                     sema_down(self->exit_sema) ⏸
status = child->exit_status         (BLOCKED — struct alive)
list_remove(&child->child_elem)
sema_up(child->exit_sema) ──┐
                              └→ ⏸ 깨어남
return status                     return → thread_exit
                                  → do_schedule(DYING)
                                  → struct 해제

핵심 invariant:

• 부모가 child->exit_status 를 읽는 시점에 자식은 exit_sema 에서 BLOCKED 로 thread struct 가 살아있음 → use-after-free 방지
• 부모의 sema_up(exit_sema) 이후에야 자식이 die 가능
• 같은 child_tid 로 두 번째 wait 호출 시 list_remove 로 검색 실패 → -1

2.6 EXEC — exec-missing 통과까지 7 회 시행착오

다른 콜과 달리 테스트 한 개 (exec-missing) 통과에 압도적으로 오래 걸렸다. load — process_exec — SYS_EXEC — initd 네 곳이 동시에 한 시맨틱 을 향해 정렬되어야 함을 깨닫는 과정. 자세한 시행착오는 §3 에 별도로 정리.

핵심 시맨틱: exec 실패 = "현재 프로세스 교체 실패" = 호출자 자체가 죽음. 유저에게 -1 을 반환하는 read / write 와 시맨틱이 다르다.

3. exec-missing 시행착오 7 회 — 함수 4 곳의 정렬

3.1 7 회의 연대기

각 시도마다 증상 과 그 자리에서 본 원인 을 한 줄로.

시도 1 — process_exec 실패 시 단순 return -1

• 증상: page fault at 0x400b86
• 원인: process_exec 진입부에서 이미 process_cleanup 으로 pml4 destroy. -1 반환 후 유저 모드 가도 코드 페이지 없음

시도 2 — process_cleanup 을 load 이후로 이동

• 증상: page fault (do_iret 직후)
• 원인: cleanup 이 새로 load 한 pml4 까지 destroy. 같은 thread 의 pml4 슬롯이라 "기존" 과 "새것" 을 구분 못함

시도 3 — process_cleanup 완전 제거

• 증상: 일반 exec 통과, exec-missing 만 page fault
• 원인: load 실패 시 새 pml4 가 thread 에 남아있음. 기존 유저 프로그램 페이지가 거기엔 없음

시도 4 — load 에서 old_pml4 백업/복원, NULL 체크는 t->pml4

• 증상: initd 첫 호출 시 즉시 goto done
• 원인: t->pml4 == NULL 체크인데, initd 에선 old_pml4 가 NULL → 의미가 어긋남

시도 5 — NULL 체크 변수를 new_pml4 로 분리

• 증상: load 자체는 통과. exec-missing 출력은 exit(0) 으로 끝남 (기대는 exit(-1))
• 원인: 시맨틱 불일치. exec 실패는 유저에게 -1 반환 이 아니라 호출자 자체가 종료

시도 6 — SYS_EXEC 에서 thread_exit() 호출

• 증상: initd 의 PANIC("Fail to launch initd") 발동
• 원인: exec-missing 부팅 시점에 initd 도 process_exec 호출. 우리 변경이 initd 의 PANIC 을 그대로 타격

시도 7 — initd PANIC 을 NOT_REACHED() 로 교체

• 증상: 같은 자리에서 NOT_REACHED PANIC 발동
• 원인: NOT_REACHED 는 매크로상 도달하면 panic — 이름만 바뀐 것. initd 단계의 실패는 진짜 비정상이라 panic 이 맞음

3.2 최종 수정 — 4 곳 동시 수정

7 회가 가르쳐 준 것: load / process_exec / SYS_EXEC / initd 가 한 사슬이라 한 곳만 고치면 다른 곳에서 터진다. 네 곳을 동시에 정렬해야 한다.

(1) load() — old_pml4 백업 + new_pml4 NULL 체크 + 실패 시 복원

static bool
load (const char *file_name, struct intr_frame *if_) {
    struct thread *t = thread_current();
    uint64_t *old_pml4 = t->pml4;            /* 백업 */
    uint64_t *new_pml4 = pml4_create();
    if (new_pml4 == NULL)                    /* ★ new_pml4 기준 */
        goto done;
    t->pml4 = new_pml4;
    process_activate(t);
    /* ELF 파싱 / 세그먼트 적재 */

done:
    file_close(file);
    if (!success) {
        if (t->pml4 != old_pml4)
            pml4_destroy(t->pml4);
        t->pml4 = old_pml4;
        pml4_activate(old_pml4);
    }
    return success;
}

(2) process_exec() — process_cleanup 제거

int
process_exec (void *f_name) {
    /* ★ process_cleanup() 호출 삭제 — load 가 pml4 를 교체한다 */
    success = load (argv[0], &_if);
    if (!success) {
        palloc_free_page(file_name);
        return -1;
    }
    argument_stack(argv, argc, &_if);
    palloc_free_page(file_name);
    do_iret(&_if);   /* 성공 시 영원히 안 돌아옴 */
    NOT_REACHED();
}

(3) SYS_EXEC — 실패 시 exit(-1)

case SYS_EXEC: {
    const char *filename = (const void *) f->R.rdi;
    validate_user_addr(filename);

    /* process_exec 는 palloc 페이지를 기대 — 유저 포인터 그대로 못 넘김 */
    char *fn_copy = palloc_get_page(PAL_ZERO);
    strlcpy(fn_copy, filename, PGSIZE);

    int result = process_exec(fn_copy);
    /* 여기까지 왔으면 무조건 실패 */
    thread_current()->exit_status = -1;
    thread_exit();
    NOT_REACHED();
}

fn_copy 가 필요한 이유: process_exec 가 내부에서 palloc_free_page(file_name) 으로 입력 페이지를 해제한다. 유저 스택의 포인터를 그대로 넘기면 free 단계에서 죽고, malloc 으로 받은 포인터를 넘겨도 wrong allocator 로 해제 시도하다 죽는다.

(4) initd() — PANIC 유지

if (process_exec(f_name) < 0)
    PANIC("Fail to launch initd\n");

initd 의 exec 실패는 진짜 부팅 실패라 panic 이 맞다.

3.3 핵심 통찰

process_exec 가 성공하면 절대 돌아오지 않는다 (do_iret). 따라서 호출자 (SYS_EXEC, initd) 의 "그 다음 코드" 는 실패 경로 전용 이다. 이 사실을 못 받아들이면 SYS_EXEC 의 thread_exit() 가 불필요해 보인다.

process_exec 흐름:
  ┌─ 인자 파싱 → load(argv[0]) ┐
                                ├─ 실패 → palloc_free_page → return -1
                                │             ↓
                                │         호출자로 복귀
                                │         (SYS_EXEC: exit(-1))
                                │         (initd:    PANIC)
                                └─ 성공 → argument_stack
                                       → palloc_free_page
                                       → do_iret → 유저 모드, 절대 안 돌아옴

"성공 = 안 돌아옴" 이라는 비대칭이 시도 5 의 시맨틱 차이의 뿌리다.

4. wait-twice 디버깅 — 자료구조 corruption 한 줄

EXEC 까지 들어와 fork/exec/wait 16 개 테스트 중 15 개가 통과했는데 wait-twice 하나가 끈질기게 TIMEOUT 으로 떨어졌다. 시도 6 회 끝에 원인이 콜 로직이 아니라 list 자료구조 invariant 위반 이었음을 확인한 사건.

4.1 테스트가 요구한 것

pid_t pid = fork(...);
if (pid == 0) exec("child-simple");        /* 자식: child-simple 로 교체 후 exit(81) */
int s1 = wait(pid);                        /* 1차: 81 기대 */
int s2 = wait(pid);                        /* 2차: -1 즉시 기대 */

기대: wait() = 81 다음 wait() = -1. 실제: wait() = 81 후 영원히 TIMEOUT.

4.2 진짜 원인 — child_elem 이중 등록

thread_create (threads/thread.c) 가 새 스레드를 부모 children 리스트에 이미 등록한다.

/* threads/thread.c — thread_create() */
t->parent = thread_current();
list_push_back(&thread_current()->children, &t->child_elem);   /* 1 회 등록 */

그런데 __do_fork (userprog/process.c) 가 같은 child_elem 을 한 번 더 push_back 했다.

/* userprog/process.c — __do_fork() (수정 전) */
current->parent = parent;
list_push_back(&parent->children, &current->child_elem);       /* 2 회째, 중복 */

같은 list_elem 을 두 번 list_push_back 하면 elem 의 prev / next 가 자기 자신을 가리키도록 깨진다 (self-referential). pintos list_insert 의 다음 줄들이 자기 자신을 두 번 참조하기 때문.

elem->prev      = before->prev;     /* 1 회째: 정상.   2 회째: before->prev == elem 자신 */
elem->next      = before;
before->prev->next = elem;          /* 2 회째: elem->next = elem 사이클 */
before->prev    = elem;

4.3 깨진 list 가 일으킨 이중 실패

1차 wait():
  ─ children 순회 → child 찾음 (깨져도 첫 탐색은 동작)
  ─ sema_down(child->wait_sema) → 자식이 sema_up 했으니 통과
  ─ exit_status = 81 회수
  ─ list_remove(&child->child_elem)
        elem->prev->next = elem->next   (양쪽이 elem 자신이라 no-op)
        elem->next->prev = elem->prev   (역시 no-op)
      → ★ remove 가 무력화, child 는 리스트에 그대로 남음

2차 wait():
  ─ children 순회 → child 또 찾음 (remove 가 안 됐으니까)
  ─ sema_down(child->wait_sema) → 카운트 0, 자식은 이미 종료 → ★ 영원히 BLOCKED
  → TIMEOUT

self-referential elem 에서는 list_remove 가 no-op 이 된다 가 한 줄짜리 결론.

4.4 다른 fork 테스트가 무사했던 이유

15 / 16 통과했다는 사실 자체가 함정이었다 — 버그가 잠복할 수 있는 유일한 테스트가 wait-twice 한 개 였고, 자료구조 corruption 의 전형적인 "한 번은 동작, 두 번째에 무너진다" 패턴이 그대로 들어맞았다.

4.5 시도 6 회 — 모두 증상을 거치고, 원인은 비껴감

원인이 등록 지점 이중화에 있다는 걸 모른 상태에서 6 가지 다른 가설을 거쳤다.

시도 1 — process_exit 에서 parent != NULL 일 때만 sema_down(exit_sema)

• 가설: 자식이 exit_sema 에서 막힌다
• 실패 이유: thread_create 가 모든 신생 스레드의 parent 를 세팅 → 조건이 사실상 무력. 진짜 막혀 있는 건 자식이 아니라 2 차 wait 의 sema_down(wait_sema)

시도 2 — wait_called 플래그로 동기화

• 가설: 부모가 wait 호출했는지 자식에게 알려주자
• 실패 이유: 자식이 sema_up(wait_sema) 직후 wait_called 체크하는데, 부모가 아직 세팅 못 한 race condition

시도 3 — thread_create 의 list_push_back 제거

• 가설: 등록 한 곳에서만 하자
• 실패 이유: init.c 의 run_task() 가 process_wait(initd_tid) 를 호출. thread_create 가 등록 안 하면 initd 가 main 의 children 에 없어서 즉시 -1 → Pintos 가 시작도 못함. 남길 곳을 잘못 골랐다

시도 4 — process_exec 에서 parent = NULL

• 가설: exec 시점에 부모 관계 끊기
• 실패 이유: fork 자식이 exec 하는 패턴 (wait-twice 가 정확히 이 패턴) 에서 부모 관계가 끊기면 wait 가 -1 반환

시도 5 — initd() 에서 parent = NULL

• 가설: initd 만큼은 부모 없음
• 실패 이유: 정합성 보강은 맞지만 wait-twice 의 부모는 initd 가 아니라 wait-twice 자기 자신 이라 TIMEOUT 의 원인 아님

시도 6 — 부모 process_exit 에서 자식들 exit_sema sema_up

• 가설: 자식이 영원히 안 막히게
• 실패 이유: 자식 쪽 보강은 맞지만 wait-twice 는 부모가 wait_sema 에서 막히는 문제 — 자식 sema 풀어줘도 부모 sema 는 아무도 안 풀어줌

4.6 최종 수정 — 한 줄 삭제

 /* userprog/process.c — __do_fork() */
 current->parent = parent;
-list_push_back(&parent->children, &current->child_elem);

current->parent = parent; 는 thread_create 의 값과 같지만 명시성을 위해 남겼다. 삭제한 건 단 한 줄, list_push_back 뿐 — 이 한 줄이 self-referential corruption 의 원천이었다.

4.7 시도들이 공유한 함정

6 회 시도 모두 process_exit 의 sema_down 이 막히는 증상 에 집중했다. 하지만 진짜 원인은 한 단계 위 — process_wait 의 list_remove 가 깨져서 2 차 wait 가 일어나선 안 될 sema_down 을 호출하고 있던 것.

증상의 가시적 위치 (process_exit 의 블록) 와 원인의 위치 (process_wait 의 list_remove 무력화) 가 분리되어 있었다. 그래서 가시적 위치에서 한 손씩 가설을 짜는 동안 진짜 원인은 손도 못 댐.

호출 순서를 끝까지 따라가서, "왜 이 sema_down 이 호출되었는가" 를 역으로 추적 했어야 했다.

5. 결과

6. 기술 정리

6.1 시스템 콜 골격 — 인프라 위에 콜이 올라간다

유저 프로그램
  ↓ syscall instruction (rax = sysno)
syscall_entry (asm) → syscall_handler (C)
  ↓ switch (sysno)
case SYS_*:
  1. 인자 추출 (intr_frame.R.rdi 등)
  2. 유저 포인터 검증 (락 밖)
  3. lock_acquire(&filesys_lock)
  4. filesys_*  /  file_*  /  process_*  호출
  5. f->R.rax 에 반환값 세팅
  6. lock_release(&filesys_lock)
  break;

진짜 일하는 줄은 filesys_create / file_read 같은 한 줄. 나머지는 그 한 줄을 호출 가능한 상태로 만드는 일.

6.2 fd_table 접근의 일반 패턴

/* 1단: 범위 체크 — 배열 인덱스로 쓰기 전에 */
if (fd < 0 || fd >= 128) return -1;

/* 2단: 슬롯 NULL 체크 — 닫힌/미할당 fd 가드 */
struct file *file = thread_current()->fd_table[fd];
if (file == NULL) return -1;

/* 이제 안전하게 file_* 호출 */

CLOSE / READ / WRITE / FILESIZE 모두 이 골격. 배열 인덱스로 쓰일 값은 가드를 가장 먼저 가 핵심 — 그 뒤로는 안전하다고 가정.

6.3 fork / wait 동기화 — 세 sema 의 역할

invariant 핵심:

• 모든 sema 는 성공·실패 양쪽 경로에서 정확히 한 번 up
• error 케이스의 sema_up(fork_sema) 누락 → 부모가 영원히 대기 (함정)
• 부모가 child->exit_status 읽는 시점에 자식은 exit_sema 에서 BLOCKED 로 thread struct 살아있음

6.4 EXEC 의 시맨틱 — read/write 와 다르다

read/write 실패: 유저에게 -1 반환 (호출자 살아있음)
exec 실패     : 호출자 자체를 -1 로 종료 (프로세스 교체 시도가 실패하면 원본도 끝)

이 차이를 못 보면 시도 5 의 exit(0) 출력 같은 시맨틱 어긋남 발생. exec 는 "이미지 교체" 라는 의미상 실패 시 호출자가 살 자리가 없다.

6.5 자료구조 corruption 시그니처

wait-twice 는 1 번째 시그니처. 16 개 fork/exec/wait 테스트 중 wait-twice 만 다른 패턴은 "같은 pid 로 wait 두 번" 이었고, 그게 자료구조 의심의 출발점.

6.6 한 시맨틱이 여러 함수에 걸쳐 정렬되어야 할 때

exec-missing 7 회의 본질: "exec 실패 = 현재 프로세스 종료" 라는 한 시맨틱을 만들기 위해 4 함수가 정확히 정렬되어야 했다.

load()        → 자기 실패는 자기가 정리 (pml4 복원)
process_exec  → 호출자에게 -1 (state 보존)
SYS_EXEC      → -1 받으면 exit(-1) (시맨틱 결정)
initd()       → 실패는 PANIC (다른 컨텍스트)

각 함수는 자기 책임만 보지만, 한 시맨틱을 따라가려면 모두 같은 방향을 봐야 한다. 하나만 어긋나도 전체가 작동 안 함.

7 회의 본질은 "이 시맨틱을 어디까지 가져가야 하는지" 를 함수 경계 별로 발견해 가는 과정이었다. 처음엔 load() 한 곳만 고치면 될 줄 알았다.

7. 함정 모음

8. 느낀 점

Project 1 이 "남이 만든 동기화 프리미티브 안에서 정확히 동작하도록 수정하는" 경험이었다면, Project 2 는 "동기화 프리미티브를 직접 조립해서 새 시맨틱을 만드는" 경험이었다. fork/exec/wait 세 콜을 위해 sema 세 개와 list 한 개를 깔고, 그 위에서 부모-자식 관계를 일관되게 유지하는 invariant 를 직접 설계해야 했다.

가장 인상 깊었던 두 사건:

exec-missing 7 회. 처음엔 "load 한 함수만 잘 짜면 끝" 이라고 생각했는데, 시도가 거듭될수록 문제가 4 함수에 걸쳐 있다는 게 드러났다. 시도 5 에서 시맨틱 자체가 잘못됐을지도 모른다는 의심이 처음 들었고, 시도 6 에서 initd 가 호출 컨텍스트가 다르다는 걸 깨달았고, 시도 7 의 PANIC ↔ NOT_REACHED 가 사실상 같다는 것까지 확인하고서야 네 곳을 동시에 정렬할 수 있었다. 국소 수정의 한계 를 가장 또렷하게 본 사건.

wait-twice 한 줄. 콜 로직 다 맞고, sema 패턴 다 맞고, 함수 경계 다 맞았는데, list_push_back 두 곳 분산이 self-referential corruption 을 만들었다. 6 회의 시도는 모두 "process_exit 가 sema_down 에서 막힌다" 는 증상에 집중했지만, 진짜 원인은 한 단계 위인 process_wait 의 list_remove 무력화였다. 증상의 가시적 위치와 원인의 위치가 분리되어 있을 때, 호출 흐름을 끝까지 거꾸로 따라가는 것만이 답이라는 걸 이번에 몸으로 배웠다.

Project 1 의 회고에서 진도가 너무 빠르고, 이해를 제대로 하는지? 라는 P 가 있었다. 이번 주는 AI 를 설계 이해의 대화 상대로 쓰되 시행착오는 직접 거치려고 했다. exec-missing 7 회와 wait-twice 6 회의 시도가 그 결과다. 시도마다 증상-원인 한 줄을 직접 정리한 게 §3 / §4 의 단서가 됐다.

다른 사람의 디버깅 패턴을 따라하는 것보다 자기 시도의 흔적을 정리하는 게 훨씬 오래 남는다. AI 가 즉시 답을 줘도 그 답이 왜 답인지를 직접 시도한 7 회 / 6 회 위에 얹어야 진짜 이해가 됐다.

GitHub: https://github.com/JYPark-Code/SW-AI-W0910-Pintos Week 10 | Pintos Project 2 User Programs

9. 회고(KPT)

Keep

각자 진도 상황 공유 good — 스크럼 시 오늘 할 일을 명확히 잡고 각자의 페이스에 맞춰 진행 상황을 잘 공유함 팀 회의 내용 녹음 및 기록 — 회의 기록을 빠르게 정리하고 공유하는 흐름이 자리잡음 음성 AI 서비스 사용 — 회의 정리 / 토론 기록의 정확도 향상 마감 기한을 잘 지킨 점 — 팀 단위 deadline 준수 막혀도 그냥 넘기지 않은 태도 — 모르는 지점을 붙잡고 다시 확인하는 습관, 완벽하지 않아도 일단 시도하고 틀리면 돌아와 수정하는 흐름 코어타임 토론에서 살아난 포인트들 — validate_user_addr vs validate_user_string 차이, 승현이의 close testcase 통과 과정 — pintos 본체에 집중한다고 그냥 넘어갔던 포인트들을 코어타임에서 잘 잡아준 게 가장 좋았음

Problem

커뮤니케이션 unclear — 진행 상황 공유는 단순·명료했지만, 결정 근거나 구현 방향에 대한 논의는 명확하지 않은 순간이 있었음 지각 이슈 — 팀원 단위로 시간 약속이 흔들린 회차가 있었음 개념이 계속 혼동됨 — 지난주 (Project 1) 의 퀴즈 형식이 사라지면서 핵심 개념을 점검할 기회가 줄었고, 같은 개념에서 반복적으로 헷갈리는 일이 생김 막힌 지점 기록 부족 — 어디서부터 헷갈렸는지 기록을 안 남기면 나중에 같은 부분에서 다시 시간을 쓰게 됨. 그 시간이 가장 아까웠음 개별 진행 속도 차이 — 진도 페이스가 달라서 머지 타이밍이 자연스럽지 못한 순간이 있었음 코드 리뷰 준비 부족 — PR 머지 시점에 충분한 리뷰가 이뤄지지 못함

Try

A+B, C+D 방식이 결국 안 지켜진 점 보완 — Project 1 발표 포인트로 잡았던 협업 구조가 결국 "순차적으로 4개 합치기" 가 되어 버렸음. 다음 주에는 2 인 페어 머지 구조를 처음부터 더 명확하게 약속 1 일 1 코드 머지로 토론 주제가 줄어든 점 보완 — 1 주차 때처럼 1 problem / 1 topic 퀴즈 형식 부활. 머지 흐름과 별개로 개념 점검 시간 따로 확보 PR 머지 시 적극적 토론 — 머지 직전이 가장 자연스러운 코드 리뷰 시점. 통과시키기 위한 머지가 아니라 이해를 확인하는 머지 시간 약속 엄수 — 지각 / 회의 시작 / 머지 deadline 단위로 약속 회복

회고에서 가장 인상적이었던 두 포인트

발표에도 포함되었던 validate_user_addr 와 validate_user_string 차이 그리고 승현이의 close testcase 통과 과정. 둘 다 pintos 본체 코드 짜는 데만 집중하다 보면 그냥 그렇구나 하고 넘어갈 포인트들이었는데, 코어타임에서 팀원이 잘 잡아준 덕분에 깊이 이해할 수 있었음. 혼자 코드 짜는 시간만큼이나, 팀이 같은 코드를 같이 들여다보는 시간이 단단한 학습을 만든다 는 걸 다시 확인.

또 1달이 지나서 집에 갔다 왔다. 머리도 자르고, 그리고 이번 주도 롤러코스터 향연인거 같다. 정글 공식 일정이 많았다. 생활 교육 + 농구대회 (우리 반 우승) + 전 정글 코치 카이스트 박사 + 그리고 장병규 크래프톤 이사장님 방문 면담. 그리고 Pintos 첫 주여서 굉장히 좀 빡셌다고 해야하나.. 이제 5월이다. 시간이 지나간 속도가 너무나도 빠르다.

Pintos_kaist_64bit (1주차 / 총 4주 일정)

• 같은 팀 9 ~10 주차

4월 24일 금요일

• Week 9~10팀 구성
• 농구 대회 및 생활 교육
• Alarm Clock

4월 25일 토요일

• Priority Scheduler A+B, C+D 페어 프로그래밍

4월 26일 일요일

• 집 갔다 옴

4월 27일 월요일

• 정주원 박사님 강의
• Priority Scheduler A+B, C+D 페어 프로그래밍

4월 28일 화요일

• 장병규 이사장님 전체 면담
• 퀴즈
• Priority Donation 완성

4월 29일 수요일

• 학습한 코드 전체 정리 및 PR 정리
• 발표 자료 만들기

4월 30일 목요일

• Pintos - Semaphore, Condvar를 주제로 발표
• Week9 팀 회고
• WIL 작성

Project 1: Thread

1. 이번 주 마음가짐 + 목표

수요코딩회가 없어진 첫 주였다. 대신 목요일 각각 2분 발표로 대체됐고, 그 발표 준비가 이번 주의 축이었다.

Pintos는 예고된 난이도였다. 발제에서 들었던 "AI 코드 생성 금지, 깨부 당하고 버텨보시길"이라는 코멘트가 실제였다. 지난 주 Proxy Lab과 malloc lab 때 고생했던 경험이 그나마 버팀목이 됐다.

목표:

• alarm clock, priority scheduler, priority donation 18개 테스트 전부 PASS
• 단순 통과가 아니라 "왜 이 구현인가"를 설명할 수 있는 수준까지 이해

담당 파트: alarm clock, priority-sema, priority-condvar (synch.c)

2. 시도한 접근 방식

Alarm Clock

기존 timer_sleep()은 busy waiting 방식이었다. 틱이 될 때까지 while 루프로 CPU를 점유하는 구조.

/* 기존: busy waiting */
void timer_sleep(int64_t ticks) {
    int64_t start = timer_ticks();
    while (timer_elapsed(start) < ticks)
        thread_yield();  // CPU 계속 점유
}

수정 방향은 명확했다. 잠들 때 깨어날 틱을 기록하고 thread_block()으로 재운 뒤, 타이머 인터럽트마다 깨어날 때가 됐는지 확인해서 thread_unblock()하는 구조.

sleep_list를 wake_tick 오름차순으로 정렬해서 관리했다. 매 인터럽트마다 리스트 전체를 순회하지 않고, 맨 앞만 확인하면 됐다. 맨 앞이 아직 안 됐으면 뒤는 볼 필요 없다.

Priority Scheduler — sema_up() 수정

문제: 기본 sema_up()은 waiters 리스트에서 list_pop_front()를 호출한다. waiters가 도착 순서(FIFO)로만 정렬되어 있어서, priority 63이 나중에 도착했으면 priority 1보다 나중에 깨어난다. priority scheduler를 아무리 잘 만들어도 sema에서 막히면 의미가 없다.

수정: list_pop_front() 대신 list_min(cmp_priority)으로 가장 높은 priority waiter를 찾아 꺼낸다.

여기서 함정이 있었다. cmp_priority는 priority가 높을수록 true를 반환하는 내림차순 less 함수다. list_max를 쓰면 의미가 뒤집혀 priority 최솟값이 나온다. list_min을 써야 최댓값이 나온다.

처음에 직관적으로 list_max를 썼다가 priority 1짜리가 계속 깨어나는 버그를 만났다. 함수 이름이 주는 직관과 실제 동작이 정반대였던 것.

cmp_priority는 원래 ready_list 정렬을 위해 만든 함수였다. list_insert_ordered()로 삽입 시점에 정렬을 유지할 때 쓰던 함수를 sema_up에서 재사용했고, 그 순간 list_min을 쓸 수밖에 없는 구조가 됐다.

인터럽트 컨텍스트 주의: sema_up()은 인터럽트 핸들러에서도 호출된다. thread_unblock() 이후 바로 thread_yield()를 호출하면 커널 패닉이 발생한다. 인터럽트 핸들러는 어떤 스레드의 실행 흐름을 잠깐 가로채서 처리하는 중인데, 이 상태에서 컨텍스트를 바꾸려 하면 CPU 상태가 꼬인다. intr_context() 체크 후 인터럽트 상황이 아닐 때만 yield가 동작하도록 방어 로직을 추가했다.

Priority Scheduler — cond_signal() 수정

sema_up()만 수정하면 priority-sema는 PASS되지만 priority-condvar는 여전히 FAIL이다.

이유는 구조에 있다. cond->waiters에는 스레드가 직접 들어 있지 않다. struct semaphore_elem이 들어 있고, 그 안의 세마포어 waiters에 실제 스레드가 있다.

cond->waiters
  └─ semaphore_elem  ← cond_signal()이 여기서 뽑음
       └─ semaphore.waiters
            └─ struct thread  ← priority가 여기에 있음

이 구조가 된 이유가 있다. 조건 변수는 "선별해서 깨운다"는 목적을 가진다. cond_signal()은 대기 중인 스레드 중 하나만 골라서 깨운다. 모두가 하나의 세마포어에 몰려 있으면 특정 스레드만 깨울 방법이 없다. 그래서 cond_wait()을 호출하는 스레드가 자기 전용 세마포어를 직접 만들고 그 안에서 잠든다. semaphore_elem 하나당 thread가 정확히 1개인 건 이 설계의 필연적인 결과다.

cond_signal()이 올바른 semaphore_elem을 고르려면 두 단계 간접 참조가 필요했다. semaphore_elem → semaphore.waiters → thread → priority. 이 경로를 탐색하는 전용 비교 함수 cmp_sem_priority를 새로 설계하고, list_min(cmp_sem_priority)으로 교체했다.

핵심 통찰: 스케줄링의 본질은 결국 thread->priority를 읽는 것이다. 어떤 동기화 객체를 쓰든 최종적으로 스레드에 닿아야 한다. 그 경로가 몇 단계인가, 즉 참조 깊이가 비교 함수 설계를 결정하고 그게 스케줄링 결과를 결정한다.

Priority Donation — priority inversion 해결

문제 인식: Priority Inversion

처음엔 테스트 이름만 보고 "donation이 뭔데?"라고 생각했다. 직접 마주치고 나서야 심각성을 알았다.

L(priority 1)이 lock을 들고 있고, H(priority 31)가 그 lock을 기다리는 상황. 여기에 M(priority 16)이 등장하면 M이 L을 선점한다. L이 실행을 못 하니 lock을 못 놓고, H는 lock을 기다리며 영원히 blocked 상태가 된다. H가 M보다 priority가 높은데 M 때문에 간접적으로 밀리는 역전 현상이다.

해결 방향: 임시 priority 위임

H가 lock_acquire()를 호출할 때, lock holder(L)의 priority를 H의 priority(31)로 임시로 올려준다. L이 M보다 높아지면 선점 안 당하고 빠르게 lock을 반환한다. lock 반환 순간 original_priority로 복원.

구현하면서 만난 함정들

donation_elem vs elem 분리가 가장 먼저 걸렸다. donor thread는 동시에 두 리스트에 들어가야 한다. lock의 sema->waiters에는 elem으로, holder의 donations에는 donation_elem으로. 처음에 elem 하나로 두 리스트에 넣으려 했다가 리스트가 깨지는 버그를 만났다. intrusive linked list에서 하나의 list_elem은 한 리스트에만 속할 수 있다.

wait_on_lock 세팅 순서도 처음에 틀렸다. sema_down() 이후에 세팅하면 nested donation에서 chain이 끊긴다. donate_priority()가 wait_on_lock을 따라가며 chain을 추적하는데, sema_down()으로 block되기 전에 세팅이 끝나 있어야 한다.

/* 올바른 순서 */
wait_on_lock = lock;              /* 먼저 세팅 */
list_insert_ordered(&donations, ...);
donate_priority();                /* chain 추적 */
sema_down(&lock->semaphore);      /* 이후 block */
wait_on_lock = NULL;              /* 깨어난 후 초기화 */

lock_release()에서 list_clear() 대신 remove_with_lock()을 쓴 이유도 처음엔 몰랐다. lock A, lock B를 동시에 들고 있는 스레드가 lock A를 놓을 때 donations 전체를 비우면 lock B의 donor 정보까지 사라진다. 해당 lock에 연관된 donor만 선별해서 제거해야 multiple donation이 올바르게 동작한다.

refresh_priority()에서도 list_min + cmp_donation_priority 조합이 등장했다. sema_up에서 만났던 그 패턴이 여기서도 반복됐다. 내림차순 less 함수에서 list_min이 최댓값을 반환한다는 걸 이미 알고 있었기 때문에 이번엔 바로 맞출 수 있었다.

effective priority가 lock에서 필요한 이유

sema_up()은 thread->priority 필드를 직접 읽어서 누구를 깨울지 결정한다. donate_priority()가 이 필드를 실제로 갱신해놓지 않으면, sema_up은 원래 priority 1짜리 L을 보고 다른 스레드를 먼저 깨운다. priority 필드가 "지금 이 스레드가 실제로 받아야 할 CPU 시간"을 의미해야 ready_list, sema, lock 세 곳의 정렬이 모두 일관성을 유지한다.

3. 결과

4. 팀 회고 (KPT)

Keep

• 팀원들이 정한 룰대로 진행함
• 개인 학습 시간 많아서 좋았다
• 진지한 태도 및 학습 분위기 좋았다
• 1-topic, 1-quiz 구조 좋았다
• 피드백 반영이 빨랐다

Problem

• 발표 시 팀 내 트러블 슈팅 또는 이슈 공유가 부족했다
• 몇몇 팀원들의 AI 의존성이 높았다
• 머지 전략이 아쉬웠다

Try

• quiz 대신 코드 리뷰 for merge
• 시행착오 기반으로 더 정밀한 plan
• merge 전략 구체화
• 코드리뷰 및 많은 소통과 토론

5. 기술 정리

Pintos 동기화 구조

세마포어 (Semaphore)

• sema->waiters: struct thread가 직접 들어 있는 리스트
• 참조 깊이: 1 Depth
• 비교 함수: list_min(cmp_priority)

조건 변수 (Condition Variable)

• cond->waiters: struct semaphore_elem이 들어 있는 리스트
• 각 semaphore_elem 안의 세마포어에 스레드 1개씩
• 참조 깊이: 2 Depth
• 비교 함수: list_min(cmp_sem_priority) — 전용 함수 필요

결론: 동기화 객체가 대기열을 관리하는 내부 구조(참조 깊이)를 완벽히 이해해야 정확한 우선순위 스케줄링 로직을 설계할 수 있다.

Priority Donation

Priority Inversion 문제: L(priority 1)이 lock 보유 → H(priority 31)가 기다림 → M(priority 16)이 L을 선점 → L이 실행 못 해서 lock을 못 놓음 → H가 M보다 높은데도 M 때문에 간접적으로 밀림.

Donation 해결: H가 lock_acquire() 호출 시 holder(L)의 priority를 H의 priority(31)로 올려줌. L이 M보다 높아져서 선점 안 당하고 lock을 빠르게 반환. lock 반환 후 원래 priority로 복원.

구현 시 핵심 포인트:

donation_elem vs elem 분리 — donor thread는 동시에 두 리스트에 들어간다. lock의 sema->waiters에 elem으로, holder의 donations에 donation_elem으로. 같은 elem을 두 리스트에 넣으면 자료구조가 손상된다.

wait_on_lock 세팅 순서 — sema_down() 호출 전에 반드시 wait_on_lock = lock을 세팅해야 한다. nested donation에서 chain 추적이 wait_on_lock을 따라가기 때문에, 순서가 바뀌면 chain이 끊긴다.

remove_with_lock vs list_clear — lock_release() 시 donations 전체를 비우면 안 된다. 다른 lock의 donor까지 사라진다. 해당 lock과 연관된 donor만 선별해서 제거해야 multiple donation이 정확하게 동작한다.

list_min + cmp_donation_priority — refresh_priority()에서도 sema와 동일한 패턴. 내림차순 less 함수를 쓰면 list_min이 최댓값을 반환한다.

Pintos list 구조

Pintos의 struct list는 intrusive linked list다. 객체 자체를 담는 게 아니라 객체 안에 박혀있는 list_elem을 체인으로 연결한다. list_entry() 매크로로 list_elem에서 원래 객체를 역참조할 수 있다.

/* list_elem에서 struct thread로 역참조 */
struct thread *t = list_entry(e, struct thread, elem);

6. 느낀 점

Proxy Lab와 Malloc Lab 둘은 "빈 종이에서 설계하는 경험"이었다면, Pintos는 "남이 만든 구조 안에서 정확히 이해하고 수정하는 경험"이었다. 그리고 처음으로 팀으로 활동하는 액티비티였다.

가장 인상 깊었던 통찰은 condvar의 두 겹 구조였다. 처음엔 그냥 복잡해 보였는데, "선별해서 깨운다"는 목적에서 출발하면 전용 세마포어가 필연적이고, 전용 세마포어를 관리하면 두 겹이 필연적이라는 게 보였다. 설계는 항상 목적에서 온다.

list_min과 list_max의 함정도 기억에 남는다. 이름이 주는 직관을 믿었다가 버그를 만들었다. 함수 이름이 아니라 인자로 넘기는 비교 함수의 방향성을 먼저 파악해야 한다는 걸 몸으로 익혔다.

9주차 회고에서 "AI 의존성이 높았다"는 P가 있었다. 이번 주는 AI를 설계 이해의 대화 상대로 쓰되, 코드 구현을 하지 않을려고 의식적으로 노력했다. 그리고 "왜 이 구현인가"를 스스로 설명할 수 있는 수준으로 학습하려고 노력했다.

GitHub: https://github.com/JYPark-Code/SW-AI-W09-Pintos Week 10 | Pintos Project 1 Thread | 전체 18개 PASS

이번 주는 Proxy lab을 하면서, 저번 Malloc lab과는 달리 개념적으로 정해진 길을 가야하고, 그거에 대한 학습이 요구되는 한 주였다. CGI를 배우면서, 현재는 CGI→FastCGI→각 언어에 탑재된 Http 라이브러리의 진행도를 배웠고, 그럼에 CGI를 배운건 OS process 흐름대로 Http request를 parsing하고 재조립해서 보낸다는 것에 의의를 두었다.

C Programming (2주차 / 총 3주 일정)

• CS:APP Proxy lab
• Carnegie Mellon University CS 213: Proxy Lab: Writing a Caching Web Proxy

4월 17일 금요일

• Week 8팀 구성
• Echo 서버 작성

4월 18일 토요일

• Tiny 서버 작성

4월 19일 일요일

• Tiny 서버와 아키텍처 학습

4월 20일 월요일

• Tiny 서버 연습예제
• Proxy Sequential, Concurrency

4월 21일 화요일

• Proxy Cache 완성
• 수요 코딩회 Preview

4월 22일 수요일

• 수요코딩회 - API 서버 만들기 (전 SQL parser와 B+트리 자료구조 연동)
• 수요코딩회 - 팀 리딩 및 PM (동적 스레드 풀, 및 단위 테스트, ThreadSanitizer CI 추가 등등)
• 개발 및 시연 정리

4월 23일 목요일

• 수요코딩회 개발한 것 발표
• Week8 팀 회고
• WIL 작성

1. 이번 주 마음가짐 + 목표

이번 주가 역대급 컨디션 난조였어서, 스스로도 힘들었다.

https://github.com/JYPark-Code/SW-AI-W08-Web-proxy-Lab

Tiny까지는 책에 있어서, 쳐보면서 이해하는 방식으로 접근했다. 내장 함수 하나하나 눌러보고, 주석도 달아보고, AI 서포트도 받아가면서 이해도를 높였다. Proxy는 달랐다 — 책에 코드가 없었다. 빈 종이에서 설계하는 첫 경험이었다.

Proxy Lab 학습 목표

• HTTP 프록시 서버의 동작 원리 이해 — 브라우저와 서버 사이에서 요청을 중계하는 구조를 직접 구현하며 체득한다.
• 네트워크 소켓 프로그래밍 체화 — socket, bind, listen, accept, connect 6개 API와 RIO 패키지의 동작 원리를 손으로 익힌다.
• 동시성(Concurrency) 실전 경험 — pthread, race condition, rwlock을 단순히 배우는 것이 아니라 "왜 이 선택인가"를 설명할 수 있는 수준까지 이해한다.
• 캐시 설계 — LRU 자료구조와 Readers-Writers 동기화를 조합해 멀티스레드 환경에서 안전한 캐시를 만든다.

2. 시도한 접근 방식

Proxy Lab

Part 1: Sequential Proxy (순차 처리)

Tiny 코드를 기반으로 시작했지만, doit 함수의 역할이 완전히 달라야 한다는 걸 일찍 깨달은 게 컸다.

parse_uri는 이름만 같고 알고리즘이 완전히 다른 함수였다. Tiny의 parse_uri는 /cgi-bin/adder?n1=15213을 받아 정적/동적 판별을 했다면, Proxy는 http://host:port/path를 세 조각으로 분해해야 했다.

설계에서 두 가지 결정이 있었다:

① / 먼저 찾고 : 나중에 찾기 : 먼저 찾으면 포트 생략된 URL에서 NULL 케이스를 분리해야 해서 복잡하다. /를 먼저 기준선으로 그으면 남은 host:port 영역에서만 :을 찾으면 된다. 영역을 먼저 제한한 뒤 내부를 쪼개는 순서.

② strchr 대신 범위 제한 for 루프 path 안에 :이 있을 수 있어서, 원본 uri를 수정하지 않고 hostbegin부터 hostend 범위 내에서만 순회.

build_requesthdrs에서 가장 크게 배운 건 루프 내/외 분리였다. 처음엔 모든 로직을 while 루프 안에 넣었다가 User-Agent와 Connection 헤더가 헤더 수만큼 반복 추가되는 버그를 만들었다. 헤더 분류를 "수용(Host) / 거부(UA·Connection·Proxy-Connection) / 기본값(나머지)"의 3단 게이트로 재구성하고서야 해결됐다.

응답 전달에 Rio_readnb를 쓰는 이유도 체득했다. driver.sh의 basic 테스트에 godzilla.jpg와 tiny 실행 바이너리가 포함돼 있다. readlineb로 전달하면 이미지 바이트 중 0x0A를 줄 끝으로 오인해 diff에서 실패한다. 바이너리 데이터는 readnb로 덩어리째 전달해야 한다.

driver.sh Basic 40/40 통과.

Part 2: Concurrent Proxy (동시성)

Sequential proxy의 한계는 명확했다. doit()이 끝나야 다음 accept가 가능하다. nop-server 같이 응답 없는 서버에 요청이 막히면 다른 모든 요청도 멈춘다.

해결 방법으로 멀티스레딩을 선택했다. fork(멀티프로세싱) 대신 thread를 고른 이유:

1. 생성 비용: thread는 μs 단위, fork는 ms 단위
2. 캐시 공유: Part 3 캐시가 모든 스레드에서 공유돼야 한다. fork는 IPC가 필요
3. 자원 효율: 같은 주소 공간 내에서 가벼운 컨텍스트 전환

이번 파트의 핵심 이슈는 race condition이었다.

/* 위험한 코드 */
while (1) {
    int connfd = Accept(listenfd, ...);        // 지역 변수
    pthread_create(&tid, NULL, thread, &connfd); // 주소 전달
}

시각  메인                         스레드 1
────  ──────────────────         ──────────
t=0   connfd = 4 (A 요청)
t=1   pthread_create(&connfd)
t=2                               시작됨, 아직 *vargp 안 읽음
t=3   (다음 루프)
t=4   connfd = 5 (B 요청) ← 덮어쓰기!
t=6                               *vargp 읽음 → 5 ❌

pthread_create는 비동기 호출이다. 스레드가 언제 실행될지 OS 스케줄러가 결정한다. 메인이 다음 루프에서 connfd를 덮어쓰는 순간 그걸 보고 있는 스레드가 잘못된 fd를 받는다.

해결은 힙 복사:

int *connfdp = Malloc(sizeof(int));   // 매번 다른 힙 주소
*connfdp = Accept(...);
Pthread_create(&tid, NULL, thread, connfdp);

void *thread(void *vargp) {
    int connfd = *((int *)vargp);
    Pthread_detach(Pthread_self());
    Free(vargp);                       // 힙 해제는 스레드가
    doit(connfd);
    Close(connfd);
    return NULL;
}

Malloc은 매번 다른 힙 주소를 반환한다. 스레드 1의 주소(0x55aa1000)와 스레드 2의 주소(0x55aa2000)는 겹치지 않는다.

pthread_join 대신 pthread_detach를 쓴 이유: join은 메인이 기다려야 해서 다음 accept를 못 한다. 동시성이 깨진다. detach는 OS에게 자원 정리를 맡기고 메인은 즉시 다음 요청으로.

Signal(SIGPIPE, SIG_IGN)은 클라이언트가 갑자기 끊을 때 프로세스 전체가 죽는 걸 막는다. 동시성 서버에서 한 요청 때문에 모든 스레드가 죽는 건 치명적이다.

driver.sh Concurrency 15/15 통과. 누적 55/70.

Part 3: Caching Proxy (캐시)

캐시의 목적: 같은 URL 재요청 시 백엔드 왕복 없이 메모리에서 즉시 응답. driver.sh 캐시 테스트가 이 개념을 영리하게 검증한다 — Tiny를 kill하고 같은 파일을 다시 요청해서, 캐시에서 나오면 성공.

자료구조: 이중 연결 리스트 기반 LRU

MAX_CACHE_SIZE / MAX_OBJECT_SIZE = 1,049,000 / 102,400 ≈ 최대 10개 엔트리

최대 10개라 linear search도 O(1)과 실질적 차이 없다. 배열은 중간 제거 시 O(n) shift가 필요하지만, 이중 연결 리스트는 head 삽입/tail 제거/중간 이동 모두 O(1)로 처리 가능.

cache_find에서 LRU 이동을 뺀 이유 — 동기화 트레이드오프

처음엔 cache_find에 LRU 갱신(찾은 노드를 head로 이동)을 넣었다. 문제는 동기화 패턴과 충돌이었다.

• cache_find를 호출하는 컨텍스트는 rdlock (다중 reader 동시 허용)
• 하지만 LRU 이동은 리스트 구조 변경 = 쓰기 작업
• rdlock 상태에서 쓰기를 하면 두 스레드가 동시에 같은 노드를 이동시키며 리스트 깨짐

선택: cache_find에서 LRU 이동 제거 (순수 읽기). insert-order 기반 근사 LRU로 대체. driver.sh 채점엔 영향 없고, 동시 읽기 성능 유지.

교훈: 동기화 정책이 자료구조 설계를 제약한다. 정확도와 동시성 중 의도적으로 동시성을 선택했다.

동기화: pthread_rwlock

캐시 접근 패턴이 "읽기 >> 쓰기"다. 뮤텍스로 전 구간을 직렬화하면 동시 읽기를 못 해 동시성 의미가 거의 사라진다. rwlock은 여러 reader가 동시 진입을 허용하고 writer만 단독 접근한다.

사실 rwlock은 원시 동기화가 아니라 mutex + 세마포어 + 카운터의 조합이다. CSAPP 12.5가 세마포어 두 개로 직접 구현하는 방식을 보여주는데, 그게 rwlock의 내부 구조다. pthread_rwlock이 이를 표준 POSIX로 제공한다.

/* 캐시 조회 — rdlock (다중 reader 허용) */
pthread_rwlock_rdlock(&cache.lock);
cache_entry_t *cached = cache_find(&cache, uri);
if (cached != NULL) {
    Rio_writen(clientfd, cached->data, cached->size); // 락 안에서 전송
    pthread_rwlock_unlock(&cache.lock);
    return;
}
pthread_rwlock_unlock(&cache.lock);

/* 캐시 저장 — wrlock (단독) */
pthread_rwlock_wrlock(&cache.lock);
cache_insert(&cache, uri, cache_buf, cache_size);
pthread_rwlock_unlock(&cache.lock);

HIT 시 응답 전송도 락 안에서 해야 한다. 락 풀고 전송하면 그 사이 다른 스레드가 evict로 해당 노드를 제거할 수 있다 — use-after-free.

cache_insert의 공간 확보 루프를 if가 아닌 while로 쓴 이유: 새 객체 하나 넣으려고 여러 개 evict가 필요할 수 있다. if로 한 번만 제거하면 크기 초과가 발생할 수 있다.

driver.sh Cache 15/15 통과. 최종 70/70.

Part 3 WIL 추가: Bulk Insert ↔ Reverse Proxy 대응

이번 주 가장 흥미로운 발견은 지난 수요코딩회에서 했던 Bulk Insert 최적화와 Reverse Proxy 최적화가 같은 원리의 다른 표현이라는 것이었다.

관통하는 메타 원칙: "비싼 경계를 덜 넘고, 반복은 캐싱하고, 작은 건 묶는다."

우리가 만든 캐시는 이 중 ② 하나이지만, 실무 Nginx는 다섯 개를 다 한다.

3. 수요코딩회 (B+ 트리 인덱스)

이 섹션은 별도 채팅방에서 작성 예정이므로 기존 내용을 그대로 유지합니다.

4. 결과

Proxy Lab

5. 팀 회고 (KPT)

Keep

• 지용: 동현이의 Quality&Deep한 질문 +High expectation(모든 팀원에게). 팀원들 역량이 모두 좋았다. 빠르게 목표를 잡은 게 좋았다.
• 동현: 개인 공부 시간 많았고, 수요코딩회 너무 편안했다. 개개인의 작업의 Merge가 딱딱 맞은 건 너무 신기하다. 실무 환경과 유사하게 해서, 스스로의 업무 성향 파악은 잘됐어서, 좋았다.
• 승진: 동현님의 질의 방식이 스스로의 관점의 확장에 도움이 됐다.
• 용 형님: 개인 공부 시간 있어서, 전체적인 이해도 ↑ / Issue ↓ / 스스로의 업무 스타일 마지막은 항상 있었다.

Problem (아쉬운점)

• 금주 내용이 다소 낮기 부족했고, 현업과의 거리감도 느끼고 있었는데, 다른 주에 비해 몰입도가 낮았다.
• 정답에 정해져 왔었고, 다른 변칙이 용납 안된 시점에서, 순수 공부만 한 느낌이다.
• 나태해지는 포인트들이 몇몇 있었으나. 수요코딩회에서 회복했다.
• PM의 실무 분담은 능력 별로 나누는 것 이해하나, 각자 하고 싶은 일을 못한 거 같다. 그 외도 코드양이 너무 많아서, AI도 느려지고, 일일히 볼 수 없었다. 협업 규약으로 인해, 수정할 수 있는 코드가 한정적이었고, 그로 인해 다소 수동적으로 접근할 수밖에 없었다.
• 미리 잡은 코어 타임 2일이 아쉬웠고 그것이 팀원과의 소통이 부족함으로 이어져서, 아쉬웠다.

Try

• 같이 한 Activity가 부족해서, 약간 너무 4명에서 사무적이지 않지 않았나.
• PM의 역할을 한번 해보고 싶다.
• 커리큘럼에 (±α)를 해서, 자신을 특화하는 게 필요.

6. 기술 정리 (WIL용 핵심 개념)

소켓 프로그래밍

• 파일 디스크립터(fd): 프로세스가 열어둔 자원을 가리키는 정수 인덱스. 소켓도 fd.
• 서버: socket → bind → listen → accept 4단계 (bind = 주소 고정, listen = 대기 모드)
• 클라이언트: socket → connect 2단계 (bind 생략, OS가 임시 포트 자동 할당)
• TCP 4-tuple: (출발IP, 출발포트, 도착IP, 도착포트)로 연결 고유 식별. 서버 포트 하나에 수천 연결이 가능한 이유.

RIO (Robust I/O)

• Short count 처리: read가 요청보다 적게 반환해도 루프로 보완
• Buffered I/O: 8KB 내부 버퍼로 시스템 콜 횟수 최소화 (= DB Bulk Insert의 batching 패턴과 동일 원리)
• readlineb: 텍스트 한 줄 읽기 (HTTP 헤더)
• readnb: 바이너리 덩어리 읽기 (HTTP 바디, 이미지, 실행 파일)

HTTP 구조

• 요청/응답 모두 시작라인 + 헤더 + \r\n\r\n + 바디 구조
• 헤더 끝 신호: 빈 줄 (\r\n\r\n)
• HTTP/1.0: Connection: close 강제 → 응답 끝이 곧 연결 종료 → Content-Length 파싱 불필요

동시성

• Race condition: 실행 순서에 따라 결과가 달라지는 상황. 재현이 어렵다(하이젠버그).
• 해결 원칙: "공유하지 말거나, 공유하면 동기화하라"
• connfd 힙 복사: "공유 안 하기" 선택. 매번 다른 힙 주소 → 각 스레드 독립
• pthread_detach: OS에 정리 위임. join 쓰면 기다려야 해서 동시성 파괴

동기화 계층

하드웨어 원자 연산 (CAS, test-and-set)
    ↓
OS 커널 대기 큐 (futex)
    ↓
Mutex (한 명) + Semaphore (N명)   ← 기본 원시
    ↓
RWLock = Mutex + Semaphore + 카운터   ← 조합 추상화

• Mutex: 상호 배제, 소유권 있음 (잠근 스레드만 풀 수 있음)
• Semaphore: 카운터 기반, 소유권 없음, 이벤트 알림에 적합
• RWLock: 읽기 다수/쓰기 하나. 읽기 많은 워크로드에 최적

CGI 원리

• fork + dup2 + execve 조합
• dup2(fd, STDOUT_FILENO): 자식의 stdout을 소켓으로 리다이렉트
• CGI 프로그램이 printf만 해도 네트워크로 전송되는 이유
• CGI → FastCGI → 내장 HTTP 라이브러리로 발전한 역사

7. 느낀 점

Tiny까지는 "책을 따라가는 학습"이었다. Proxy부터는 달랐다. parse_uri를 직접 설계하고, race condition 시나리오를 시간순으로 그려보고, LRU 이동과 동시 읽기 사이에서 트레이드오프를 의식적으로 선택했다.

가장 인상 깊었던 통찰: RIO의 buffered I/O와 DB Bulk Insert가 같은 원리다. "비싼 경계를 묶어서 한 번에 넘는다"는 batching 패턴이 도메인을 가로질러 반복된다. 이걸 발견하는 순간 새 기술을 배울 때마다 "어디서 본 패턴이지?"라고 물을 수 있게 됐다.

다음 주 PintOS가 시작한다. "AI 코드 생성 금지, 깨부 당하고 버텨보시길"이라는 코멘트가 벌써 부담스럽지만 — 이번 주 Proxy에서 빈 종이를 채워본 경험이 그 부담을 조금은 덜어준다.

GitHub: https://github.com/JYPark-Code/SW-AI-W08-Web-proxy-Lab

8. 차주 계획

PintOS 시작

1. 그 유명한 PintOS가 시작한다. 스탠포드에서 만들고 카이스트가 64bit 대응한 버전
2. 발제에서 들은 코멘트: AI 코드 생성은 하지 말 것. 깨부 당하고 버텨보시길.

수요코딩회는 이제 없다.

• 쭉 이어서 공부하고 목요일날 모두 다 발표 (KDT 수료 조건)

목표

1. 항상 과하지 않게 목표에 충실하게 공부
2. 열심히 공부하기 & 건강 챙기기

이번 주는 malloc lab을 하면서, 다양한 시도를 해볼 수 있었던, 즐거운 한 주였지만, 감기가 100% 낫지 않아서, 몸이 오락가락했고, 날씨는 쌀쌀한 봄 날씨에서 무더운 여름으로 변했다. 벚꽃도 피고, 지금 꽃잎이 떨어지고 있고 있다.

내 주변에 일어난 일들 때문에, 스스로 맘 고생한 거 같은데, handling 할 수 없는 이슈라, 그냥 포기하기로 했다. (그리고 공부과는 무관한 일이다.) 햇살도 강해서, 더위 먹을까 교육장 온도가 29도까지 올라가서, WIL 쓰는 금일 16일, 전 교육장 에어컨 틀어주고 있다. 기숙사는 키면 꺼지는 거 같던데, 안내를 기달려야 하겠다.

C Programming (2주차 / 총 3주 일정)

• CS:APP Malloc Lab
• Carnegie Mellon University CS 213: Writing a Dynamic Storage Allocator Assignment

4월 10일 금요일

• Week 7팀 구성
• Implicit first fit

4월 11일 토요일

• Explicit first fit

4월 12일 일요일

• Seglist first fit
• Seglist best fit

4월 13일 월요일

• realloc 함수 refactoring
• prev_blkp 매크로 -> 함수로 교체
• allcoated 블록 footer 제거

4월 14일 화요일

• realloc heap 끝에 ptr 존재할 때 케이스
• mini-slab, pool 만들고 점수 낮아져서 rollback (기존 92 -> 90) pool을 만들어서 오버헤드가 늘어서 점수가 떨어지는 항목 생김.
• 수요 코딩회 Preview

4월 15일 수요일

• 수요코딩회 - B+트리 자료구조 (전 SQL parser와 연동)
• 수요코딩회 - 팀 리딩 및 PM (B+트리 코어, Git 관리, )
• 개발 및 시연 정리

4월 16일 목요일

• 수요코딩회 개발한 것 발표
• Week7 팀 회고
• WIL 작성

WIL

1. 이번 주 마음가짐 + 목표

생각보다 Malloc Lab CS:APP 9장에 스포일러가 많았다.

https://github.com/JYPark-Code/SW-AI-W07-Malloc-Lab

시작하기 앞서, 담당 코치의 저번 주 발제의 의견을 존중해서, 다른 주보다도 AI 생성은 절대 하지 말고, 직접 구현을 권장해서, 나는 책도 안 보기로 했다. 그러면 어떻게 코드를 짰냐?

Claude에게 *소크레테스 대화법을 사용해서 Malloc Lab을 Implicit first fit부터 Seglist best fit 그리고 최적화의 모든 과정을 부탁했고, 다행히도 하루에 1개씩 진행하였다. 이 대화법을 적용하면 Claude는 이 악물고, 코드를 안 알려준다. 그래서 매크로나 mm_init()부터 보면 다른 사람들의 코드와 많이 다르다.

*소크라테스 대화법(산파술)은 질문과 답변을 반복하여 상대방 스스로 모순을 깨닫고 진리에 도달하도록 돕는 대화 방식입니다. 자신이 모른다는 사실을 인지하는 ‘무지의 지’에서 시작하며, 비판적 사고, 자기 인식 강화, 스스로 결론에 도달하는 논리적 탐구를 목적으로 하는 교육 및 상담 기법입니다. "출처 yes24"

Malloc Lab 학습 목표

• 동적 메모리 할당기의 원리 이해 — malloc, free, realloc이 내부적으로 어떻게 동작하는지, 힙 구조(header, footer, epilogue)와 coalesce 메커니즘을 직접 구현하며 체득한다.

• 공간 효율(Util)과 시간 효율(Throughput)의 트레이드오프 탐색 — Implicit → Explicit → Segregated Free List → Best Fit으로 단계적으로 구조를 발전시키며, 각 설계 결정이 점수에 어떤 영향을 주는지 실험을 통해 파악한다.

• C 포인터와 비트 연산에 대한 실전 감각 확보 — prev_alloc 비트 관리, char** 이중 포인터 조작, memmove 타이밍, GDB로 헤더 raw 값 읽기 등 저수준 디버깅 능력을 기른다.

수요코딩회 프로젝트 목표

• 실제 DBMS 인덱스 구조 구현 — 메모리 기반 B+ 트리를 C로 직접 구현하고, leaf split / internal split / root split 전 과정을 손으로 짜며 트리 성장 원리를 체득한다.

• SQL 처리기와의 실전 연동 — Week 6에서 만든 파서·실행기에 인덱스를 붙여 WHERE id = ? 시 O(log n) 탐색, 그 외 필드는 기존 선형 탐색으로 분기하는 실제 DBMS 동작 방식을 구현한다.

• 100만 건 데이터로 성능 차이 직접 증명 — 대용량 레코드 삽입 후 인덱스 탐색 vs 선형 탐색의 속도 차이를 수치로 측정하고, O(log n)과 O(n)의 차이가 실제로 어떻게 드러나는지 확인한다.

2. 시도한 접근 방식

1. Malloc Lab

Implicit Free List (First Fit) — 가장 기본적인 구조로 시작. 힙 전체를 순회하며 첫 번째 맞는 블록을 찾는 방식. 67점.

Explicit Free List (Address-Ordered) — free 블록의 payload에 prev/next 포인터를 저장해 doubly linked list로 관리. free 블록만 순회하도록 개선. 84점.

Segregated Free List + Best Fit — 크기별로 20개 버킷으로 분리하고, 버킷 내에서 best fit 탐색 + diff==0 조기 종료 추가. 90점.

Footer 제거 + prev_alloc 비트 — 헤더 bit1에 이전 블록 할당 여부를 저장해 allocated 블록의 footer를 제거. 메모리 효율 소폭 개선. 90점.

버킷 세분화 + realloc 고도화 — 24~576 구간을 16단위로 촘촘하게 세분화. realloc에서 인접 블록 병합, 힙 끝 직접 확장 케이스를 추가해 불필요한 malloc+memcpy+free를 최소화. 92점.

Slab-style Pool (시도 후 롤백) — binary trace의 외부 단편화를 잡기 위해 24/72/120바이트 전용 pool을 구현. 구현은 완성했으나 pool 선점 할당으로 util이 오히려 하락해 브랜치로 보존 후 롤백. 90점

Claude한테 받은 피드백은 다음과 같다.

질문의 질이 높았어요. "LIFO랑 address-ordered 중 뭐가 낫냐"처럼
단순히 구현을 묻는 게 아니라 설계 결정의 근거를 물었고, 그게 결국
92점까지 이어졌다고 생각해요. 그냥 코드 받아서 넣는 사람이었으면 
이 점수 못 나왔어요.

WIL이나 README에 "안 된 것"을 솔직하게 기록한 것도 인상적이었어
요. Slab Pool이 실패했다고 숨기지 않고 왜 떨어졌는지 분석해서 문
서화한 게 좋았어요.
구조를 단계적으로 발전시키면서 각 단계에서 "왜"를 놓치지 않았어요.
Implicit에서 Explicit으로 넘어갈 때, Explicit에서 Seglist로 
넘어갈 때마다 점수 변화와 이유를 스스로 설명할 수 있었던 게 이번
학습의 핵심이었다고 봐요.

2. 수요코딩회 (B+ 트리)

작성할 게 많아 일단 링크로 대체하겠다.

https://github.com/JYPark-Code/jungle_w7_BplusTree_Index_DB/blob/main/docs/WIL_project_approaches.md

열심히 하다가 터진 이슈(?!) : 마우스 포인터가 옆 모니터로 안넘어감 -> 껐다 키니, 윈도우 업데이트.

3. 수요코딩회 (B+ 트리 인덱스)

1. 프로젝트 소개

지난 주 SQL 파서는 "결과를 stdout에만 출력하는 프린터"였다. 다른 함수가 결과를 받아 쓸 수 없으니 JOIN·집계·subquery의 길이 막혀 있었다.

이번 주는 그 위에 B+ 트리 인덱스를 얹었다 — Week 6 SQL 처리기를 베이스로, 실제 DBMS가 인덱스를 쓰는 방식 그대로 구현하는 것이 목표였다.

주제는 C로 만드는 파일 기반 미니 DBMS + B+ 트리 인덱스.

• Week 6 SQL 처리기 그대로 계승 (파서·executor·storage·RowSet 인프라)
• id 자동 부여 + B+ 트리 인덱스 자동 등록
• WHERE id = ? → O(log n) 탐색, WHERE id BETWEEN A AND B → O(log n + k) range scan
• WHERE 다른 필드 = ? → 기존 선형 탐색 유지
• 100만 건 벤치마크 + 선형 vs 인덱스 비교
• Python stdlib HTTP 중계 서버 + 결제 로그 장애 구간 조회 웹 데모

2. 팀 구성과 협업 방식

• 4명 팀 (지용 / 정환 / 민철 / 규태)
• 지용 (나): bptree.c 코어 + bptree.h 인터페이스 확정 + 레포/Makefile + PM + 머지 결정
  • Round 3: INSERT 10,000× 가속 (append FP / schema / path / meta 캐시 + BULK_INSERT_MODE) + 고정폭 바이너리 저장 레이어
• 정환: executor.c — WHERE id = ? 분기 + WHERE id BETWEEN range 경로 + 테스트
• 민철: storage.c — auto-increment id + bptree_insert 연동 + DELETE/UPDATE 후 인덱스 rebuild 동기화 + 테스트
• 규태: bench/benchmark.c 100만 건 벤치 + 선형 vs 인덱스 비교 + 웹 데모 (Porsche 오마주 UI)

협업에서 못 박은 것:

• include/types.h, include/bptree.h 는 절대 수정 금지 — 인터페이스 계약 파일
• MP1(bptree.h 확정) 머지 전까지 팀원 작업 시작 X
• 기능 완성 후 AI에게 unit test 생성 위임 → 통과 확인 후 PR
• 담당 파일 외 수정 금지 (병렬 작업 충돌 방지)
• 막히면 1시간 이내 지용에게 알릴 것

3. 기술적으로 배운 것

3-1. 인터페이스 계약을 먼저 못 박으면 병렬 작업이 가능하다

bptree.h 다섯 함수 시그니처를 MP1으로 먼저 확정하고 전원에게 배포한 뒤 작업을 시작했다.

BPTree *bptree_create(int order);
void    bptree_insert(BPTree *tree, int id, int row_index);
int     bptree_search(BPTree *tree, int id);   // row_index 반환, 없으면 -1
int     bptree_range(BPTree *tree, int from, int to, int *out, int max_out);
void    bptree_destroy(BPTree *tree);

정환(executor)과 민철(storage)은 stub 함수만 있는 상태에서 병렬로 작업을 시작할 수 있었다. 지난 주 경험의 반복 — 붙일 모양을 먼저 정해놓고 그 안에서 각자 자유롭게 작업. 머지 충돌이 거의 없었다.

3-2. B+ 트리의 핵심 — split이 트리를 자라게 한다

B 트리와 다른 두 가지가 손에 잡혔다.

첫째, 실제 레코드 포인터는 리프 노드에만 있다. 내부 노드는 검색 경로를 안내하는 separator key만 가진다. 둘째, 리프 노드들이 linked list로 연결되어 있어 range scan이 O(log n + k)로 가능하다.

split 구현 순서는 leaf → internal → root 였다. leaf split이 핵심이었고 포인터 조작 순서가 정확해야 했다:

// leaf split 포인터 순서
// 1. 새 리프 노드 할당
// 2. 키 절반을 새 노드로 복사
// 3. next 포인터 연결 (linked list 유지) ← 이게 빠지면 range scan 깨짐
// 4. 중간 키를 부모로 올림

root split만 예외였다 — 새 루트를 할당하고 기존 루트가 자식이 된다. 트리 높이가 이때 증가한다.

3-3. 예상치 못한 병목을 계층별로 추적해 10,000배 가속

100만 건 INSERT가 60초 안에 2,716건밖에 안 들어가는 문제가 발생했다. time 명령으로 측정하니 user+sys 0.7s인데 real 14.8s — 93%가 I/O wait이었다.

mount 명령으로 원인을 추적했다:

Windows Host → WSL2 → Docker Desktop → devcontainer
   └── /workspaces 폴더 = C:\ 를 9p 프로토콜 + dirsync 마운트

fopen 한 번에 약 0.3ms. 행당 6회 호출하면 1.8ms, 100만 건이면 30분. 아래 5단계로 해결했다:

교훈: "내 로컬에선 빠른데요?"가 가장 위험한 말이다. 같은 알고리즘이 FS 레이어 때문에 100× 차이 날 수 있다. syscall 예산을 선언적으로 관리해야 의미 있는 최적화가 된다.

3-4. 측정 레벨 3개를 분리해서 숫자의 의미를 명확히 했다

같은 "선형 vs 인덱스"인데 배율이 크게 달랐다:

웹 레벨 배율이 낮은 이유는 subprocess 모델에서 매 쿼리마다 트리를 rebuild하는 고정비(~1.8s) 때문이다. PostgreSQL 같은 상주 데몬이면 한 번 빌드된 인덱스가 메모리에 상주해 두 번째 질의부터는 make bench 수치에 가까워진다 — 영속 데몬이 왜 필요한지 수치로 이해했다.

3-5. K/N 비율에 따른 인덱스 효과의 역전

결과 행 수(K)를 달리하며 측정한 결과:

K가 클수록 인덱스 이득이 감소하다 교차점 이후 역전된다. 이것이 PostgreSQL / MySQL query planner가 selectivity가 낮으면 Index Scan 대신 Seq Scan을 선택하는 이유와 정확히 같다. 교과서에서 읽은 내용을 직접 수치로 확인했다.

3-6. 고정폭 바이너리 저장 레이어 — O(N) 접근의 구조적 한계 해결

CSV는 가변 길이라 N번째 행 접근이 O(N)이다. 같은 데이터를 고정폭 바이너리로도 저장해서 fseek로 O(1) 접근을 가능하게 했다:

/* 기존 CSV: N번째 행을 찾으려면 처음부터 개행 세기 */
for (int i = 0; i < N; i++) read_csv_line(fp);   // O(N)

/* 바이너리: 정확한 offset으로 직접 seek */
fseek(fp, row_idx * ROW_BYTES, SEEK_SET);          // O(1)
fread(buf, ROW_BYTES, 1, fp);

1M 행 WHERE id BETWEEN 질의 기준: CSV만(8.06s) → CSV+BIN(2.22s).

4. 결과

5. 팀 회고 (KPT)

Keep

• 지용: Malloc Lab assignment 연결, 최선의 케이스 찾기 훈련, 스스로의 타임라인이 만족스러웠다
• 규태: 수요코딩회 interface 포함 협업 규약이 도움이 됬고, 정환의 CS :APP 스터디 학습 공유 좋았다, 팀장이 내 학습에 큰 도움이 됐다
• 정환: PM의 역할이 매우 좋았고, junior 개발자의 느낌이 들었다
• 민철: 규태님 발표 support이 너무 좋았고, 집중이 잘 안 될 수 있었지만 잘 됐다. 집중이 잘 됐다

Problem

• 지용: 팀원들이 책을 읽은 대비, 코드 구현이 전체만큼 부족 (Timeline의 문제)
• 규태: Core time 외 팀 결합도 좀 낮았던 것 같다 (진행사항 공유가 안 됨)
• 정환: 수요코딩회 B+ 트리 일부 학습량이 충족되지 않아 공부했으면 좋겠다
• 민철: 공부한 것이 자기 스스로 내재화가 됐는지 불확실

Try

• 지용: 팀원 역량 차이 시 대응 방법 강구
• 규태: 팀원 Status check를 Slack으로 공유
• 정환: 타임라인 잘라서 좀 더 열심히 공부
• 민철: 스스로 공부법 개선

6. 프로젝트 회고

잘 된 것

지난 주 회고에서 "인터페이스 먼저, 구현은 그 안에서"를 교훈으로 적었고, 이번 주는 그대로 적용했다. bptree.h MP1을 먼저 못 박고 팀원이 병렬로 작업한 결과 머지 충돌이 거의 없었고 발표할 때 "여기까지가 의도, 여기까지가 구현"의 경계가 명확했다.

예상 밖의 수확은 INSERT 병목 추적이었다. 알고리즘이 아니라 FS 레이어가 원인이었다는 것, 그리고 syscall 예산을 계층별로 분해해서 보는 시각을 처음으로 가졌다.

새로 배운 것

B+ 트리 split     ─── leaf → internal → root 순서로 짜면 패턴이 반복된다
linked list 리프  ─── range scan이 O(log n + k)인 이유가 구조에 있다
FS 레이어 병목    ─── 같은 알고리즘이 환경에 따라 100× 차이 날 수 있다
측정 레벨 분리    ─── "1,842×" 와 "2.3×" 는 둘 다 참이고 
                     측정 범위가 다를 뿐이다
query planner     ─── K/N 비율이 임계값 넘으면 인덱스보다 선형이 빠르다 
                       — 수치로 확인

아쉬운 것

• B+ 트리 영속화(프로세스 간 인덱스 유지)를 구현하지 못했다. 현재는 프로세스 종료 시 트리가 소멸해 다음 쿼리에서 cold start로 rebuild한다. 상주 데몬 모드나 인덱스 사이드카 파일로 확장하면 웹 레벨 배율도 크게 올라갈 것이다. (근데 대부분 다른 팀들도 이렇게 구현한 것 같았다.)
• (규태님 포인트) Core time 외에는 진행 사항 공유가 충분하지 않았다. 각자 작업에 집중하다 보니 팀 전체 맥락이 공유되지 않는 순간이 있었다.

7. 느낀 점

실패 → 회고 → 다음 주 적용의 사이클이 이번 주도 정확히 돌았다. "인터페이스 먼저"는 지난 주 교훈을 바로 적용한 것이었고, INSERT 병목 추적은 "알고리즘만으로 충분하지 않다"는 새 교훈을 남겼다.

B+ 트리를 직접 짜보니 DBMS가 왜 그 구조를 선택했는지가 코드 레벨에서 이해됐다. 교과서에서 "O(log n)"이라고 읽을 때와 직접 1,842배를 측정할 때의 느낌은 완전히 다르다.

GitHub 링크: https://github.com/JYPark-Code/jungle_w7_BplusTree_Index_DB

4. 차주 계획

C언어 주간

1. 소켓을 이용하여, 요청과 응답을 하는 간단한 클라이언트/서버를 만들어봅니다.
2. CS:APP 11장 학습

수요코딩회

• DB (Phase 3 — Web Server)

목표

1. 항상 과하지 않게 목표에 충실하게 수요 코딩회
2. 열심히 공부하기 & 건강 챙기기

C Programming 시작 (1주차 / 총 3주 일정)

• LinkedList
• Stack & Queue
• Binary Tree
• BST

4월 3일 금요일

• Week 6팀 구성
• LL 1문제 & CS:APP 스터디 참관
• 자체 팀 코어 타임 1 : LL 1번 풀이
• 목 아파서 저녁 타임 직전에 이비인후과 갔다옴

4월 4일 토요일

• 반에 많은 애들 집 갔다온다고 외출을 많이 써서 상당히 비어있던 날
• LL All & S&Q 2문제
• 자체 팀 코어 타임 2 : malloc, **(Double Pointer)

4월 5일 일요일

• 사실상 뭐 BST 마지막 문제 빼고 모두 Solved, 반에 5명 정도 밖에 없어서 매우 집중이 잘 됬었고, 중간에 점심 먹으러 나갔다 왔는데도 널널했음.
• C로 알고리즘 주간 문제 구현 느낌이라 나쁘지 않았음.

4월 6일 월요일

• BST 마지막 문제 Solved
• CS:APP 요약본 읽기
• NotebookLLM으로 C언어 복습
• 자체 팀 코어 타임 3 : LL 6번 예정 (재귀)

4월 7일 화요일

• 동석 코치 Pintos 대비 C언어 강의
• 수요 코딩회 Preview

4월 8일 수요일

• 수요코딩회 - SQL Parser - C로 개발
• 수요코딩회 - 팀 리딩 및 PM (Parser 영역 직접 구현)
• 개발 및 시연 정리

4월 9일 목요일

• 수요코딩회 개발한 것 발표
• Week6 팀 회고
• WIL 작성

WIL

1. 이번 주 목표

이번주부터는 이제 4로 고정이다. 우리 반에 한 명이 저번주 화요일 랜덤 런치 기준으로 나가신 걸로 안다. (3-3-4-3-3-4), 저번주와 동일하게, 수요코딩회는 비슷하게 준비하였고, (변수가 좀 존재하면 update)

C를 안 본지 너무 오래됬고, malloc, pointer 모두 무서웠던 개념인데, 학부 때와 다르게 지금은 AI도 있고, 모르는 건 다 물어보면 되서 개념적으로 학부 때에 비해 안정성이 매우 올라갔다. project는 docker에 ubuntu 24.04 환경으로, devcontainer로 실행해서 프로젝트 진행중이다.

이번 주는 새로운 챕터로 넘어가는 주이기에 운영 방침은 팀원들과 상의 하고, 코어 타임에 각자 부족한 것 배운 것에 대해서 나누기로 했다.

C언어 학습 목표

• 구조체와 Malloc, 포인터에 대한 이해.
• 메모리 할당할 시 초기 변수 초기화와 다 쓴 후, free()로 메모리 초기화하기
• Python과 다른 내장 함수 구현.

수요코딩회 프로젝트 목표

• 3주차에 걸쳐 최종 목표는 작동하는 mini-MySQL이라 하여, 확장성을 고려한 설계
• 개발 단에 개입은 하되, 각자 할당량에 맡게 역할 분담.
• 마지막 통합 때 정리하기

4월 7일 화요일 동석 코치 강의

4월 7일 동석 코치 강의

컴파일러가 컴파일은 해주는데, 에러는 코드 작성자에게 맡기는 부분이 있기에
segment fault가 뜬다.
-> 수시로 뜨고, 어디서 왜 떴는지 알려주지 않아서 난감했다.

파이썬만 하더라도 number int 1개가 28byte다.
C는 int type 기준 4byte라고 다들 알고 있겠지만,
사실상 C는 타입의 크기를 정해두지 않았다.
대신 64bit 운영 체제에서 얼추 4byte 된다 이런 것.
그래서 sizeof을 써야 제일 정확하다.

C에서 array는 사실상 syntax sugar이다. 파이썬의 List와 다르다. 그 점 인지.
strlen = python len
사실상 문자열은 마지막이 '\0'이 있는데
사실상 사이즈값이 sizeof 또는 strlen() + 1이 실제 크기.
"jungle" 이 있을 때 strlen이 6이 뜨는데 실제론 7이 사이즈다.

C는 3개의 속성이 있다고 기억하면 된다.

* 주소값 (&a)
* value
* size

값을 변경하고 싶을 때 포인터로 접근 해서 갱신해야 값이 바뀐다.

등등

2. 시도한 접근 방식

1. C언어 학습

4섹션 7, 7, 8, 5로 총 27문제였고, 처음부터 보니까 좀 생소하고 뭐하고, 라는 말이 바로 나올 법 했지만, pdf를 보면서 푸니까, 영어 + 중국어 힌트로 꽤나 풀만 했다. "CE1007/CZ1007 Data Structures" 이게 NTU - Singapore, 난양공과대학교 교육과정에서 쓰는 코드를 그대로 가져온거 같다. 난 학부 때 아래와 같이 처음부터 끝까지 다 짰었는데 약간 충격이긴 했다.

#include <stdio.h>
#include <stdlib.h>

int main(){
}

// 또는

int main(int argc, char *argv[]){
}

이번주는 Claude를 사용해서, Claude한테 받은 피드백은 다음과 같다.

강점

개념을 파이썬이랑 비교해서 이해하는 속도가 빠르고, 직관이 대체로 맞아요
"왜 이렇게 되는지"를 계속 물어보는 습관이 좋아요 — 그냥 코드 복붙하지 않고요
막히면 말로 먼저 설명하고 코드로 옮기는 방식이 효과적이에요

개선할 부분

포인터 타입 실수가 자주 나왔어요
("(" vs '(', int vs char 등) — C에서 타입에 더 주의가 필요해요
free 타이밍이나 malloc 초기화를 빠뜨리는 경우가 있었어요 —
새 자료구조 만들 때 체크리스트처럼 습관화하면 좋을 것 같아요
엣지 케이스(NULL 체크, 홀수/짝수 크기 등)를
나중에 발견하는 경우가 많았어요 —
코드 짜기 전에 먼저 생각하는 습관을 들이면 좋을 것 같아요

malloc은 오랜만이라, 그리고 기억도 잘 안나긴 했다.

2. 수요코딩회 (SQL Parser)

C 로 5종 SQL (CREATE / INSERT / SELECT / UPDATE / DELETE) 을 직접 토크나이즈 → 파싱 → 실행하는 미니 DBMS, SQL Parser를 만들었다. 나는 PM 겸 Parser 영역(parser.c, ast_print.c, json_out.c, sql_format.c, main.c)을 직접 구현했고, 석제님이 SELECT/CREATE storage 를, 원우님이 INSERT/DELETE/UPDATE storage 를 맡았다. 세인님은 원우님과 같이 경쟁 브랜치로 하다가, 마지막으로 CLI Design을 맡았다. 오전에 1차 완성을 끝낸 다음, 같은 날 오후에 같은 팀으로 후속 리팩토링까지 한 번 더 돌렸다.

3. 수요코딩회 (SQL Parser)

1. 프로젝트 소개

지난 주 React 프로젝트는 "내가 만든 추상화를 게임에 끼워 맞추다 어긋난" 경험이었다. 이번 주는 정반대로 갔다 — 목표를 작게 잡고, 인터페이스 계약을 먼저 못 박고, 거기에 맞춰 영역을 나누는 방식.

주제는 C 로 만드는 파일 기반 미니 DBMS.

• CREATE / INSERT / SELECT / UPDATE / DELETE 5 종 SQL
• 토크나이저 + 재귀 하강 파서 + AST + executor + 파일 백엔드
• CLI 6 플래그 (--debug / --json / --tokens / --format / --help / --version)
• Python stdlib HTTP 중계 서버 + CodeMirror 기반 브라우저 뷰어

3 주짜리 프로젝트의 1 주차였기 때문에, 확장 가능한 구조 가 더 중요했다.

2. 팀 구성과 협업 방식

• 4 명 팀 (지용 / 석제 / 원우 / 세인)
• 지용 (나) : Parser, AST/JSON/format, CLI, PM, CI, 머지 결정
• 석제 : storage_select, storage_create, CSV 파서, WHERE/LIKE/ORDER BY
• 원우 : storage_insert, storage_delete, storage_update + 단위 테스트 48
• 후속 리팩토링은 3 명 (지용 + 석제 + 원우) 으로 dev2 브랜치에서 진행

협업에서 못 박은 것:

• include/types.h 의 storage_* 시그니처는 절대 변경 금지 — 인터페이스 계약
• 각자 자기 함수 본문만 채움 → 머지 충돌 최소화
• executor.c 는 dispatcher 만 — 한 명이 망쳐도 나머지 작업 가능
• 모든 PR 은 pull_request_template.md 양식 + GitHub Actions CI + PM 코드 리뷰 후 머지
• main / dev / dev2 는 브랜치 보호 (직접 push 차단, admin 만 우회)

3. 기술적으로 배운 것

3-1. 인터페이스 계약을 먼저 못 박으면 병렬 작업이 가능하다

include/types.h 한 파일에 모든 자료구조 (ParsedSQL, WhereClause, ColumnType) 와 함수 시그니처를 다 박아두고, 그걸 PR 1 개로 먼저 머지 한 다음에 셋이 동시에 작업을 시작했다.

[D. 인터페이스 계약 PR — 지용]
              ↓ (먼저 머지)
   ┌──────────┼──────────────────────┐
   ↓          ↓                      ↓
[Parser]    [SELECT storage]      [DML storage]
 (지용)      (석제)                 (원우)

지난 주 React 때처럼 "각자 만들고 나중에 붙이자" 가 아니라, 붙일 모양을 먼저 정해놓고 그 안에서 각자 자유롭게 작업. 머지 충돌이 거의 0 이었다.

3-2. 1차 완성 → 사용/리뷰 → 후속 리팩토링 (저녁 이후)

오전에 끝낸 1차 완성을 직접 써보면서 약점이 드러났다.

발표용 main 을 안정 상태로 보존한 채 새 통합 브랜치 dev2 를 따고, 같은 팀으로 한 번 더 작업했다. 1주차 호환 0 회귀 가 핵심 제약 — 후속 리팩토링 후에도 1차 단위 테스트 201 개가 모두 통과해야 했다.

3-3. N-ary WHERE — 이중 포인터로 푼 가장 임팩트 큰 변화

1주차 코드는 parse_where 가 2칸짜리 배열을 미리 잡아놓고 for(i<2) 하드코딩 으로 돌고 있었다. 결합자도 char where_logic[8] 한 칸뿐.

/* 리팩토링 전 — include/types.h */
WhereClause *where;
int          where_count;    /* 0~2 */
char         where_logic[8]; /* "AND" 또는 "OR" — 단 하나만 */

/* 리팩토링 전 — src/parser.c */
static void parse_where(TokenList *t, ParsedSQL *sql) {
    sql->where = calloc(2, sizeof(WhereClause));
    for (int i = 0; i < 2; i++) {              /* 하드코딩 */
        const char *col = advance(t);
        const char *op  = advance(t);
        /* ... */
    }
}

/* 리팩토링 전 — DML 가드도 단일 조건만 통과 */
if (where_count != 1 || where == NULL) {
    return -1;
}

후속 리팩토링은 char **where_links 이중 포인터 로 풀었다. N개 조건 사이에 N-1 개 결합자가 들어가는 가변 길이 배열.

/* 리팩토링 후 — include/types.h */
WhereClause *where;
int          where_count;
char       **where_links;   /* N-1 개 결합자 ("AND"/"OR") */

/* 리팩토링 후 — parse_where (개념 발췌) */
static void parse_where(TokenList *t, ParsedSQL *sql) {
    while (!at_stop(t)) {
        sql->where = realloc(sql->where,
                             sizeof(WhereClause) * (sql->where_count + 1));
        /* col / op / value 파싱 */
        sql->where_count++;

        const char *link = peek(t);
        if (eq_ci(link, "AND") || eq_ci(link, "OR")) {
            sql->where_links = realloc(sql->where_links,
                                       sizeof(char*) * sql->where_count);
            sql->where_links[sql->where_count - 1] = strdup(advance(t));
        } else break;
    }
}

이중 포인터가 무섭게 느껴졌는데, 막상 짜보니 "포인터를 가리키는 포인터" 가 결국 가변 길이 배열을 위한 도구 라는 게 손에 잡혔다. realloc 으로 슬롯을 늘리고, 각 슬롯에 strdup 으로 문자열을 붙이고, free 할 때 거꾸로 푼다. malloc/free 를 짝 맞춰 짜는 습관이 처음으로 자연스럽게 들었다.

3-4. 데이터 / 표시 분리 — RowSet 인프라

1차 완성의 storage_select 는 결과를 화면에 출력만 하는 "프린터" 였다. 후속 리팩토링에서 storage_select_result() 를 신설해서 결과를 메모리 RowSet 으로 반환 하게 만들었다.

typedef struct {
    int     row_count;
    int     col_count;
    char  **col_names;
    char ***rows;       /* ⭐ 또 다른 이중/삼중 포인터 */
} RowSet;

int  storage_select_result(const char *table, ParsedSQL *sql, RowSet **out);
void print_rowset(FILE *out, const RowSet *rs);
void rowset_free(RowSet *rs);

char ***rows — 행을 가리키는 포인터의 포인터의 포인터. 처음 봤을 때 멍했는데, "행 배열 → 행 → 셀(문자열)" 로 한 단계씩 풀어서 그리니까 자연스러웠다. 이게 생기면서 향후 JOIN / GROUP BY / subquery 의 길이 다 열렸다.

기존 storage_select 는 storage_select_result → print_rowset → rowset_free 를 호출하는 얇은 wrapper 로 리팩토링. 외부 동작 변화 0 — 1주차 테스트 그대로 통과.

3-5. 시그니처 통일 — SELECT 와 동일 패턴

/* Before — 1주차 */
int storage_delete(const char *table, WhereClause *where, int where_count);
int storage_update(const char *table, SetClause *set, int set_count,
                   WhereClause *where, int where_count);

/* After — 후속 리팩토링 */
int storage_delete(const char *table, ParsedSQL *sql);
int storage_update(const char *table, ParsedSQL *sql);

호출부 (executor.c) 는 한 줄씩만 바뀌었다. API 가 일관되니 호출하는 쪽이 깔끔해지고, N-ary 결합자 같은 새 필드가 자연스럽게 흘러갔다.

3-6. valgrind 누수 0 — malloc/free 의 짝을 맞추는 훈련

1차 완성부터 후속 리팩토링까지 5 개 바이너리 모두 valgrind 누수 0 을 유지했다.

• sqlparser (메인)
• test_runner (parser/AST/JSON/format 단위 테스트)
• test_storage_insert / test_storage_delete / test_storage_update

C 를 처음 제대로 만진 주에 valgrind 0 을 찍은 게 의외로 큰 자신감이 됐다. "malloc 한 거 free 안 했구나" 를 valgrind 가 정확히 짚어주니까 디버깅이 무섭지 않았다.

4. CI / PR / 머지 워크플로

4-1. GitHub Actions

.github/workflows/build.yml 가 모든 push/PR 에 자동으로 돌았다.

- gcc/make/valgrind 설치
- make CFLAGS="-Werror"           # 경고도 빌드 실패 처리
- make test                        # 단위 테스트 (227)
- valgrind --leak-check=full ./test_runner
- valgrind --leak-check=full ./sqlparser query.sql

PR 페이지에 빨간/초록이 자동으로 떴고, CI 가 깨진 PR 은 머지 안 함 을 원칙으로 박았다. 후속 리팩토링 시작할 때 dev2 trigger 가 누락된 걸 발견해서 한 줄 fix 한 일도 있었다.

4-2. 머지 패턴 3 가지

이번 주에 3 가지 다른 머지 패턴을 직접 운영해봤다.

세 패턴 공통 원칙:

• 작업자의 시간/노력은 항상 존중 (탈락해도 피드백, 미머지여도 cherry-pick + 크레딧)
• 머지 결정의 기준은 테스트 + 메모리 안전 + 인터페이스 일관성
• "우선권을 가지는 코드" 를 PM 이 명시 (예: Phase 1 storage.c 보호)

특히 옵션 B Mixed Merge 는 처음 시도한 패턴이었다. 원우님 PR #32 와 석제님 PR #33 이 같은 parser 영역에서 5 군데 충돌했는데, 보통 같으면 한 명만 채택하고 한 명은 탈락이지만 — 함수 단위로 옆에 놓고 비교했다.

parse_where:        석제 (단일 while, 결합자 정규화, 깔끔)
parse_select stop:  석제 (신규 기능, 원우 없음)
ast_print:          석제 (inline 결합자 직관적)
json_out:           원우 (emit_str_array 헬퍼 재사용)
sql_format:         원우 (NULL 안 반환, robust)
test_parser.c:      두 사람 케이스 합집합

mixed merge commit 하나에 양쪽 Co-Authored-By 를 다 붙였다. 두 사람 작업 모두 살아남고, 결과 코드 품질도 함수마다 더 나은 쪽으로 올라갔다.

4-3. PR = 책임 소재 + 점수

PR 은 단순한 코드 묶음이 아니라 누가 / 어디까지 / 왜 를 동시에 기록한다. 이번 주 핵심 PR 3 개:

PR #18 이 1차 SELECT 의 책임 소재가 석제임을 영구히 기록한 덕분에, 후속 단계에서 같은 영역을 N-ary 로 확장할 때 누구한테 리뷰 청할지 자명했다.

5. 결과 — 1차 완성 vs 후속 리팩토링

6. 팀 피드백

6-1. 브라우저 뷰어 피드백

"파싱 결과는 잘 나오는데 SELECT 결과가 표 형태로 보이면 좋겠다."

처음엔 카드 + JSON 토글로만 보여줬는데, 피드백 받고 진짜 HTML <table> 그리드로 렌더하게 고쳤다. 다크 테마 (Dracula) 와 기존 카드 UI 를 해치지 않는 선에서 조화롭게 — 컬럼 헤더 강조, 행 zebra striping.

6-2. PM 으로서의 자기 피드백

지난 주 React 때 "구현 먼저 → 설명 끼워 맞추기" 의 함정에 빠졌던 걸 의식하며, 이번 주는 의도적으로 "인터페이스 먼저 → 구현은 그 안에서" 순서로 갔다. 결과: 머지 충돌이 거의 0, 발표할 때 "여기까지가 의도, 여기까지가 구현" 의 경계가 명확했다.

7. 팀 회고 (6조)

Pros.

원우: GitHub Actions CI 자동 테스트 덕에 의견 수렴이 훨씬 수월했다 — 감 아닌 초록/빨강으로 판단할 수 있었다 석제: PR 리뷰 문화 + types.h 인터페이스 설계 덕에 memory alignment 이슈까지 팀 전체가 같이 잡을 수 있었다. 원우·석제 양쪽 다양한 풀이를 보는 것도 좋았다 지용: 멋진 팀원들 (feat. Zoom). 코어타임이 있어서 각자 어려웠던 점을 공유할 수 있었고, Anti-AI 작성 원칙 덕에 다양한 시각으로 자세한 코드 리뷰가 됐다 세인: 코어타임에 다양한 내용을 다룰 수 있었다

Cons.

세인: 코어타임에 팀원들에게 선뜻 얘기를 꺼내지 못했다 석제: 수요코딩회에서 low 레벨로 더 깊이 내려갔더라면 어땠을까 하는 아쉬움이 있다 원우: (석제와 동일) 지용: 세인이가 좀 더 자신감을 가지고 적극적으로 참여했으면 좋겠다

Feedback

석제: 세인님 기능 분담을 추가로 드리는 것 + low 레벨 구현까지 도전해보는 것 제안

Try.

다음 주 phase 2 (B+트리 / JOIN) 도 같은 패턴 — 인터페이스 먼저 박고 영역 분리 세인 팀원이 더 적극적으로 기여할 수 있도록 역할 분담 재조정 수요코딩회에서 low 레벨 구현까지 도전하는 방향 검토

8. 다시 프로젝트 회고

잘 된 것

지난 주 React 회고에서 "custom React(수단)로 잘 작동하는 것(목표)을 먼저 선택" 이라는 교훈을 적었었다. 이번 주는 그 교훈을 그대로 적용했다 — "수단(C 파일 백엔드)으로 잘 작동하는 목표(파일 기반 SQL 5 종)" 부터 잡고, 그 안에서 점진적으로 확장.

결과: 1주차 호환 0 회귀로 후속 리팩토링까지 같은 날에 돌렸다. 지난 주의 "구현 먼저 → 설명 끼워 맞추기" 함정을 한 주 만에 뒤집었다는 게 가장 의미 있었다.

새로 배운 것

이중 포인터 (char **)  ─── 가변 길이 배열을 위한 도구일 뿐 — 무서워할 게 없다
삼중 포인터 (char ***) ─── "행 배열 → 행 → 셀" 한 단계씩 풀면 자연스럽다
malloc/free 짝         ─── valgrind 가 무서웠는데, 짚어주니까 오히려 친구
인터페이스 계약        ─── 시그니처를 먼저 박으면 병렬 작업이 가능해진다
PR + CI                ─── PR 페이지가 코드 리뷰의 객관적 근거 + 책임 소재 영구 기록

그럼에도 아쉬운 것

• 1차 완성 단계에서 silent error 를 처음부터 stderr 분리했어야 했다 — 후속에서 손이 더 간 부분
• 후속 리팩토링을 같은 날에 끼워넣은 건 모험이었다 — 하지만 했죠?

9. 느낀 점

CI와 PR 리뷰를 도입해서 조금 더 현업 느낌이 날 수 있도록, 작업한 거 같다. 팀원들 모두가 만족스러워하는 부분이 좋았던거 같다.

팀 역할 분배 + PR + branch 전략 + CI 의 조합이 처음으로 자연스러웠다.

실패 → 회고 → 다음 주 적용 의 사이클이 한 번 돌았다는 게 가장 큰 수확.

GitHub 링크: https://github.com/JYPark-Code/jungle_w6_mini_mysql_sql_parser

4. 차주 계획

C언어 주간

1. malloc랩

수요코딩회

• DB 개발 (Phase 2 — B+트리) 예상

목표

1. 항상 과하지 않게 목표에 충실하게 수요 코딩회
2. 열심히 공부하기 & 건강 챙기기

알고리즘 주제

• DP
• 그리디

3월 27일 금요일

• Week 5팀 구성
• 경기대 배상원 교수(KAIST 出) DP와 프로그램적 접근 방법
• 베이직 문제 모두 Solved
• 코어 타임 - 계단 오르기

3월 28일 토요일

• 일정 종료 후, 집에 돌아갔던 날..
• 하, 중 문제 모두 Solved
• 코어 타임 - 집 도둑

3월 29일 월요일

• 오전에 복귀
• 외판원순회 문제 Solved
• 리드 현수 코치 커피챗
• 코어 타임 - 단어 쪼개기

3월 30일 화요일

• 알고리즘 리뷰(그 동안 푼 문제 리뷰)
• 멀티탭스케쥴링 문제 Solved
• CSAPP 퀴즈 + DP 관련
• CSAPP 책 리뷰
• 수요 코딩회 Preview
• 코어 타임 : 삼각형

3월 24일 수요일

• 수요코딩회 - React state, component, hook, useState, useEffect, useMemo 알고리즘 개발
• 수요코딩회 - FE 개발 담당
• 개발 및 시연 정리

3월 25일 목요일

• 수요코딩회 개발한 것 발표
• Week5 팀 회고
• WIL 작성

WIL

1. 이번 주 목표

5주차는 또 다시 3명이었는데(3-3-4-3-3), 이번에는 수요코딩회 때 팀원을 믿고 맡길라고, 역할군은 어느 정도 잘 잘라놨다. 그리고 팀원 둘 다 열심히 하고, 전반적인 코어 타임도 유익하게 흘러간거 같다.

알고리즘은 DP와 그리디로 2중 DP와 그리디와 DFS가 섞이는 경우나, 비트바이트(외판원 문제)를 제외하곤 비슷한 패턴이었던 것 같다.

이번 주도 운영 방침은 팀원들과 상의 하에 저번 주 내 운영과 동일하게 하였다.

1. 각자 코드는 열심히 풀고 코어 타임때 푼 방향이나 로직에 대해서 설명하기.
2. 마지막 날에는 어떻게 풀었는지 모니터를 번갈아 보면서 코드 구성 확인하기.
3. 코어 타임 전에 예비 문제를 제공 대신, 풀지 말지는 본인 선택.

3/30 알고리즘 강의 노트

3/27 알고리즘 강의
배상원 교수
재귀에 이어서 강의
---
문제 해결 기법

Divide and Conquer (분할 정복) : 큰 덩어리를 자르는 것.
Backtracking
DP : Dynamic Programming (동적 계획법)
Greedy Algorithms
---

교수님: 모두 재귀를 깔고 한다.

---
D&C는 일정 비율로 줄어들 때 이용 (1/n) - 교수님피셜 일반적인 재귀 문제와 뭐 다를께 있나 싶다.
반으로 잘라서 그 배열에 가장 큰 수를 찾는 문제 시간 복잡도 O(N)
T(N) = 2T(n/2) + O(1) : 시간복잡도 점화식
T(N) = O(N)

cf : merge sort와 매우 유사하다. 

Binary Search
이것도 D&C 이고, 시간 복잡도 = O(log n)
T(n) = T(n/2) + O(1)

곱셈
곱셈도 반으로 잘라서 가능하다. 근데 결국 O(n^2)
2자리수 곱셈이 가능하면 4자리 수도 가능
   a | b
x  c | d
--------
(10^4)(a*c) + (10^2)(b,c) + (10^2)(a*d) + b*d
10^2m * ac + 10^m (bc + ad) + bd

빠른 곱셈.
(bc + ad) 를 ac+bd-(a-b)(c-d)
로 바꿔서 4번 연산하던 것을 3번으로 연산함.
이러면 O(n^log2의3) = n^1.5XXX
n^2 = log2의4로..

이것보다 더 빠른 알고리즘이 계속 나옴.. 결국 2019년에서 O(nlogn)이 나옴.
하지만 앞의 상수 n이 엄청 크고 복잡하면, 의미가 없을 수도 있고, 
대부분 최적화된 것들은 구현 난이도도 높고, 실제로 사용한 케이스는 있지 않을수도 있다.
---
DP - 스마트한 Recursion
테이블 채우는게 중요한게 아니라 점화식을 잘 찾는게 중요하다.
교수님은 bottom-up 방식을 채용 밑에서부터 올려가는 것으로 강의. = 이것은 수학적 귀납법과 유사하다.

그리드에서 최단경로 개수 세기
(2차배열) (0,0)에서 (m,n)까지의 최단거리 경로의 수?

베이스 케이스 

p(i,j) = 1 -> i = 0 or j = 0
else
p(i,j) = p(i-1,j) + P(i, j-1)
---
LCS - Longest Common Subsequence (subsequence : 부분열)
Kinds of String match Problem.

A와 B는 배열 방식
A[1...m], B[1...n]
동일한 배열 방식.

L(i,j)를 A[1..i]와 B[1..j] 사이의 lcs의 길이로 정의한다.
base case : i==0 or j ==0: return 0
A와 B의 배열에서 맨끝에서 pop하고 이걸 재귀(2중 for문으로)로 호출하고, 
A[i] == B[j]일때
max( L(i-1, j) , L(i, j-1))
A[i] != B[j]일때
max( L(i-1, j) , L(i, j-1), L(i-1, j-1) +1))

알고리즘 학습 목표

• DP와 그리디 문제 풀이
• DP의 점화식 세팅하기
• Case by case로 맞는 로직 세팅하기

수요코딩회 프로젝트 목표

• 팀원 둘과 잘 조율해서, 완성하는 게 목표
• 개입 최소화 팀원 리딩 스킬 키우기
• 마지막 통합 때 정리하기

2. 시도한 접근 방식

1. 알고리즘 학습

DP 그리디 이렇게 되서 평소 문제들보다 적었지만, 특정 문제에 있어서 시간이 좀 많이 소요되기도 하였다.

문제 풀이법이 저번주와 유사하게 최대한 취지에 맞게 풀이법을 맞출려고 했다. 간단한 DP는 쉬웠지만, 어려운 건 좀 머리를 싸매야했다.

DP 풀면서 아 이걸 예전엔 그냥 구현으로 도전했으니까 실패했겠구나 하는 문제를 엄청 많이 보게 되었다. 그냥 작은 수를 골라서 계속 더해볼까? 그런 고민들은 그냥 케이스 by 케이스로 점진적으로 하면 되는 거였다.

GPT한테 받은 이번 주 피드백은 다음과 같다.

이번 주 흐름을 보면, 단순 구현보다 문제 유형을 먼저 판단하고 
접근하려는 시도가 분명히 보입니다.
특히 DP에서는 점화식을 바로 쓰기보다 상태를 정의하려고 고민한 점,
Greedy에서는 정렬 기준과 선택 기준을 의식하려고 한 점이 좋았습니다.

다만 아직은 한 단계 부족한 부분이 있습니다.
👉 DP는 “풀려고 하기 전에 상태 정의를 끝내는 습관”이 필요하고,
👉 Greedy는 “이게 왜 항상 최적인지 반례로 검증하는 과정”이 
조금 더 필요합니다.

피드백 한 줄로 정리하면:

접근 방향은 맞는데, 풀기 전에 ‘정의와 검증’을 끝내는 습관만 
붙이면 실력이 한 단계 올라갑니다.

뭔가 열심히 했는데 GPT의 피드백을 보면 급했던 게 좀 보이는거 같다.

2. 수요코딩회 (React state, component hook, useState, useEffect, useMemo)

React 파트는 팀원들한테 맡기고, TS로 구성할 것이고, jsx를 쓰지 않고, app.jsx에서 Functional Component 구현한 것을 보여줄 것이다.

3. 수요코딩회 (물리 테트리스 + Custom React useState/useEffect/useMemo)

1. React 3번째 프로젝트 소개

지난 주에 Mini React(VDOM + Diff + Fiber)를 구현했다면, 이번 주 우리 팀의 목표는 그 구현체를 실제 게임에 연결하는 것이 목표였다.

주제로 물리 기반 테트리스를 골랐고, 일반 테트리스와 다르게 블록이 회전하고, 기울어진 채로 쌓이고, 라인 클리어가 블록을 수평으로 절단하고 블럭을 산산히 조각내도록 하였다.

단순히 게임을 만드는 게 아니라 "왜 React가 이렇게 설계됐는가"를 게임으로 시연하는 것이 핵심이었다.

2. 팀 구성과 협업 방식

• 3명 팀
• 팀원 1 : VDOM + Diff + Patch + FunctionComponent
• 팀원 2 : useState + useEffect + useMemo + Batching + Fiber 스케줄러
• 나 : 물리 엔진(테트리스 로직), Flamegraph 메트릭 패널, 통합 + 버그 잡기

협업에서 도전한 부분:

• contracts.ts로 공유 인터페이스를 먼저 정의해서 병렬 개발 중 충돌 방지
• Git 전략: feat/core, feat/physics, feat/app → dev PR → main 최종 병합
• 팀원 코드를 건드리지 않고 통합하는 것이 목표였는데, 인터페이스가 잘 맞아떨어짐

3. 기술적으로 배운 것

3-1. 왜 Matter.js를 쓰다가 순수 TypeScript로 바꾸려 했나

처음엔 Matter.js(Box2D 기반 물리 라이브러리)를 사용했다. 중력, 충돌, 회전이 바로 작동해서 편했지만 문제가 생겼다.

Matter.js의 물리 상태는 라이브러리 내부 mutable 객체다.

// Matter.js 방식 — 외부 상태, custom React 연결 불가
Matter.Engine.update(engine, dt);  // 내부 상태 변경
const pos = body.position;         // 내부 객체 직접 접근

custom React의 useState는 순수 함수 패턴을 요구한다.

// custom React 방식
setGameState(prev => nextTick(prev, dt));
// nextTick: (state) => newState 순수 함수여야 함

라이브러리 내부 상태는 prev => newState 패턴으로 다룰 수 없다. 그래서 Matter.js의 핵심 물리 로직을 순수 TypeScript 함수로 포팅을 시도했다. 그러나 충돌 해소 버그가 계속 발생했고, 결국 Matter.js로 복귀했다.

3-2. 순수 함수 물리 엔진 시도 — SAT 충돌 감지

포팅 과정에서 SAT(Separating Axis Theorem)을 직접 구현했다.

// engine.ts — 순수 함수, 사이드 이펙트 없음
export function checkCollision(va: Vec2[], vb: Vec2[]): Collision {
  const axes = [...getAxes(va), ...getAxes(vb)];
  for (const axis of axes) {
    const [minA, maxA] = project(va, axis);
    const [minB, maxB] = project(vb, axis);
    // 분리축 발견 → 충돌 없음 (조기 종료)
    if (maxA < minB || maxB < minA) return { colliding: false, depth: 0 };
  }
  return { colliding: true, depth: minDepth, normal: minNormal };
}

순수 함수로 만들자 setState와 연결은 됐지만, impulse 해소 로직의 버그로 블록이 공중에 뜨거나 겹치는 문제가 반복됐다.

3-3. custom React 연결 — 실제로 작동하는 곳

최종적으로 custom React diff/patch가 작동하는 영역은 Score UI다.

// Matter.js 결과 → setProps → diff → patch
function updateScoreDisplay(): void {
  scoreBoardComp.setProps({
    score: gameState.score,
    level: gameState.level,
    lines: gameState.linesCleared,
  });
}

score가 바뀔 때만 diff/patch가 실행되고 Flamegraph에 기록된다. Canvas는 React 바깥 영역이므로 직접 그린다.

3-4. hookIndex — 순서가 꼬이면 상태가 엉킨다

export const useState = (initialValue) => {
  const index = current.hookIndex++;  // 호출 순서로 슬롯 결정
};

렌더링마다 hookIndex를 0으로 리셋하지 않으면 같은 훅이 다음 렌더링에서 다른 슬롯을 읽게 된다.

1번째 렌더링: hookIndex 0 → 1 → 2
2번째 렌더링: hookIndex 3 → 4 → 5  ← 완전히 다른 슬롯
  → hooks[3] = undefined → 상태 초기화 반복

조건문 안에 훅을 쓰면 안 되는 이유가 정확히 이것이다.

3-5. useEffect cleanup — 없으면 루프가 2개 돌아간다

useEffect(() => {
  if (!isRunning) return;
  let id = 0;
  const loop = (t: number) => {
    setGameState(prev => nextTick(prev, dt, keys));
    id = requestAnimationFrame(loop);
  };
  id = requestAnimationFrame(loop);
  return () => cancelAnimationFrame(id);  // cleanup 없으면 루프 중복
}, [isRunning]);

cleanup 없이 START를 두 번 누르면 루프가 2개 돌아서 블록이 2배 빠르게 떨어졌다. cleanup이 왜 필요한지 몸으로 이해했다.

3-6. 라인 클리어 — Sutherland-Hodgman 다각형 절단

클리어 판정은 Shoelace formula로 실제 다각형 면적을 계산해서 1024 × 8.1 = 8294.4 px² (보드 너비의 81%)을 초과하면 클리어한다.

4. 코치 피드백

"Canvas에 그렸다면 DOM을 조작하지 않은 것인데, 미니 React 프로젝트에 맞나요? 그냥 테트리스면 모르겠지만, 이건 mini React에 적합한 프로젝트가 아닌 것 같습니다."

정확한 지적이다. 솔직히 내 착오로 인한 완벽한 미스였다. (+물리 엔진을 쓴건 발표에서 뺐기도 한다. 나중에 코치에게 직접 말하긴 했지만..)

5. 팀 회고 (6조)

발표 직후 팀원들과 진행한 칠판 회고 내용이다.

Pros.

• 코어 타임 전 연습 문제로 학습하며 코치 이해도가 높아졌다
• 다들 열심히 공부해서 전반적인 분위기가 좋았다
• 발표 준비를 끝까지 함께 도와줬다
• 다른 팀원들의 다양한 의견을 공유할 수 있어서 좋았다

Cons.

• 수요코딩회 스스로 너무 무리한 게 좀 컸다 (나)
• 수요 코딩회 주제 추진을 좀 더 가볍게 생각하고 시작했으면 좋았을 것
• 막히는 부분을 스스로 팀원과 많이 공유하지 않았다 (소통 부족)

Feedback

• 좀 더 스스럼없이, 적절하게 검증하고 시작하자

Problem

• CSSAP 책읽기와 DP, Greedy 밸런스를 팀원들이 버거워하는 것 같았다
• 수동적인 자세가 느껴졌다

Try.

• 다같이 코드리뷰 & LCS처럼 코드로 직접 이해하는 시간 갖기
• AI가 만든 코드를 직접 뜯어보는 연습 하기
• 코어 타임 문제는 차례대로 풀이 공유하기

6. 다시 프로젝트 회고

무엇이 어긋났는가

처음 목표는 custom React를 실제로 작동시키는 것이었다. 그 증명 수단으로 물리 테트리스를 선택했는데, 이 선택이 목표와 어긋났다.

custom React가 잘 맞는 것      물리 테트리스가 요구한 것
─────────────────────────      ────────────────────────
DOM 상태 변화                   Canvas 렌더링 (DOM 밖)
텍스트/속성 업데이트             실시간 물리 시뮬레이션
사용자 이벤트 반응              60fps 게임 루프

정적 테트리스를 선택했더라면:

블록 이동    → setState → diff → CSS transform으로 DOM 업데이트
라인 클리어  → setState → diff → 해당 row div 삭제
Score 변경   → setState → patch → 텍스트 노드만 변경

모든 게 custom React diff/patch로 처리되고, "custom React가 어디서 작동하나요?" 질문에 완벽하게 답할 수 있었을 것이다. 욕심을 부리다가 본래 목적에서 벗어났다.

개발 과정에서 실제로 일어난 일

1. Matter.js 도입 → 물리는 잘 작동했지만 custom React와 연결 불가
2. 순수 TypeScript 포팅 시도 → 연결은 됐지만 충돌 버그 반복
3. Matter.js 복귀 → 물리는 Matter.js, custom React는 Score UI와 테트리스 보드판만 랜더링.
4. 초기에 작성 이후, 수정하지 않고 진행한 발표 자료

• 발표에서 "useState로 블록 이동, useEffect로 게임 루프, useMemo로 충돌 캐싱"이라고 설명했지만,

• 실제 코드에서 블록 이동과 충돌은 Matter.js가 처리했고 useState/useEffect/useMemo는 Score UI와 게임 루프 생명주기에만 사용됐다. 코드의 일부가 발표자료에 나오면서. Canvas를 쓴 것이 아닌가 질문을 받았다. 따라 코치가 "앞뒤가 안 맞는다"고 느꼈을 것이다.

• 구현을 먼저 하고 거기에 설명을 끼워 맞춘 결과였다. 다음에는 설명할 수 있는 것만 구현하거나, 구현한 것만 설명해야 한다.

결국 게임의 핵심인 Canvas와 물리 엔진은 custom React 밖이었다.

이번 경험에서 배운 것

이번 실수: 물리 테트리스(목표) → custom React(수단)를 억지로 연결
올바른 순서: custom React(수단)로 잘 작동하는 것(목표)을 먼저 선택

Canvas는 React가 관여하지 않는 영역이라는 것, 라이브러리 내부 상태는 순수 함수 패턴과 맞지 않는다는 것을 직접 부딪히고 나서야 알게 됐다.

의도가 틀렸다는 느낌을 감지했더라면, 자주 시도하는 정적 테트리스를 선택했을 것이다.

그럼에도 의미있었던 것

• useEffect cleanup 없으면 루프 2개가 돌아간다는 걸 직접 겪었다
• hookIndex 리셋이 없으면 상태가 엉키는 이유를 코드로 이해했다
• Matter.js가 왜 custom React와 구조적으로 맞지 않는지 깨달았다
• 열심히 노력했고, 실패하여서, 더 많은 점을 배울 수 있었다.

7. 아쉬운 점

• 바뀌는 주제 선택을 깊게 검증하지 않고 진행해서 중간에 구조를 여러 번 갈아엎었다
• custom React는 개발했지만 적절한 주제를 고르지 못하였다.

GitHub 링크: https://github.com/JYPark-Code/jungle_w5_react_tetris

7. 느낀 점

팀 역할 분배를 잘 나눠서 했고, PR을 받아주고, branch를 효과적으로 사용했다. 그리고 열심히 시도하다가, 실패하고, 다시 돌아가는 선택을 처음으로 한 주인거 같다.

4. 차주 계획

C언어 주간

1. C 언어 시작
2. Docker로 환경통일

수요코딩회

• SQL Parser 개발

목표

1. 항상 과하지 않게 목표에 충실하게 수요 코딩회
2. 간만에 하는 C언어인 만큼 다시 감을 찾는 주로 보내기
3. 열심히 공부하기 & 건강 챙기기

알고리즘 주제

• 이진트리
• 이진검색트리
• 그래프
• BFS/DFS
• 위상정렬

3월 20일 금요일

• Week 4 팀 구성
• 경기대 배상원 교수(KAIST 出) 재귀와 프로그램적 접근 방법
• 베이직 문제 모두 Solved
• 코어 타임 - 트리

3월 21일 토요일

• 303반 담임 코치님 (이동석 코치)의 전체 반 번개 커피챗
• 하, 중 문제 일부 Solved
• 코어 타임 - 이진 검색 트리

3월 22일 월요일

• 중 문제 모두 Solved
• 코어 타임 - 그래프

3월 23일 화요일

• 상 문제 1개 + 금주 알고리즘 리뷰 + React 내용 공부
• 코어 타임 : 팀원 의견 조율 이후 pass

3월 24일 수요일

• 수요코딩회 - React VDOM, Diff 알고리즘 개발
• 개발 및 시연 정리

3월 25일 목요일

• 수요코딩회 개발한 것 발표
• Week4 팀 회고
• WIL 작성

WIL

1. 이번 주 목표

4주차는 다시 3명이었는데(3-3-4-3), 코어타임 2번째까지 일정이 잘 가다가, 팀원 1명이 (안하던 운동을 하고 그 다음날 술 마셔서) 입원하는 바람에 팀은 2명이 되었다. (4주 연속 팀장 비슷한 것(?)을 하고 있다.)

알고리즘은 BFS/DFS, 위상정렬은 계속 비슷한 패턴이 문제마다 존재하였고, 문제별로 무엇을 재귀로 돌릴 것인지, 아니면, 큐에 무엇을 넣고 뺄지 그것만 반복하는 그런 패턴이었다.

저번 주와 골조는 같다.

1. 각자 코드는 열심히 풀고 코어 타임때 푼 방향이나 로직에 대해서 설명하기.
2. 마지막 날에는 어떻게 풀었는지 모니터를 번갈아 보면서 코드 구성 확인하기.
3. 코어 타임 전에 예비 문제를 제공 대신, 풀지 말지는 본인 선택.

팀원 중 한 명이 2일만 같이하고 입원하게 되면서, 2명 팀으로 운영이 되었는데, 다른 팀원이 계속 밖에 나가서 혼자 공부하는 타입이어서 나도 거의 개인주의(?)로 교육장에 혼자 앉아서 공부하게 되었다. 그래도 피드백은 많이 도와줘서 고맙다였고, 나에게 대한 별다른 피드백은 없었다.

3/20 알고리즘 강의 노트

알고리즘 강의 3/20 금요일

경기대 AI컴퓨터공학부 배상원교수 특강

알고리즘은 레시피이다. -> 방법
수행하는 절차와 과정을 단계별로 정확히 기술한 것이다.

알고리즘보다 중요한 건 풀고 싶은 문제를 정확히 정의

문제 & 알고리즘 = 핵심 키워드

결국 함수!

Reduction -> x를 풀기 위해서 y의 알고리즘을 호출함 (함수 호출하는 것)
코드를 작성할 때 마다 할일이 줄어든다. (반복 작업 X) 
이건 블랙박스처럼 생각하라 (안의 내용을 알 필요가 없다.)

sort() -> A[k-1] k번째로 작은 함수 가져오기

lv3: 재귀함수... 라고 생각함.
 * 문제를 해결하려고 함수를 호출하는데(Reduction 관점) 
   다시 같은 재귀호출(재귀호출도 함수호출)을 하는데, 너무 특별하게 생각 X.
---

lv2: 내가 만든 다른 함수 : 블랙박스가 아니라, 화이트박스다. 
 * 함수가 무엇을 해결하는지 정확히 이해하면 상관없지만, 
   확증이 없으면 사용하기 어렵다.
 * input, return 값을 정확히 알고 있어야한다.
 * 주석 : 코드 작성하기 전에 작성해야한다.
---
(여기까지는 숙련도 이슈)
lv1: 남이 만든 함수 라이브러리, 메소드
lv0 : 기본 연산자

교수님 목소리가 잔잔해서, 좀 졸리긴 했다. 마지막 5분은 잠깐 졸았고, 대부분 사람들이 졸음을 버틸려고 노력했다. 1시 반부터 3시 일정인거 같았는데 3시 30분에 종료.

내가 얻어간 것은, 재귀도 함수 호출이니 일단 믿고 던져라! 그리고 본인이 짠 function도 가져다 쓸 때는 blackbox로 생각할 것 blackbox 이론은 "내가 요즘 이렇게 짜도 되나 싶은 그런 느낌"을 확증으로 바꾸어준 순간이었다.

알고리즘 학습 목표

• 트리와 그래프를 기반으로 한 탐색 알고리즘 이해
• BFS/DFS를 상황에 맞게 선택하고 구현
• 위상정렬을 이용한 DAG 문제와 최대 시간 문제 등을 해결

수요코딩회 프로젝트 목표

• 팀원 1명이 메디컬 이슈로 일단 2명이 됬고, 남은 팀원과 상의해본 결과, 내가 혼자서 구현하는 걸 보고 싶다고 말을 해서, 일단 "기획-개발-발표"를 모두 맡게 되는 상황이 되었다.
• 그리고 남은 팀원은 QC와 보조 그리고 약간의 응원 (본인 말로는 "잘 탑승하겠다.")
• 하지만 남은 팀원도 이해시키는 게 목표고, 나 혼자서 하면 이렇게까지 뽑을 수 있다를 시험해보는 처음이자 마지막 기회여서, 결과물을 기대하고 있다.

2. 시도한 접근 방식

1. 알고리즘 학습

이번 주는 그냥 트리/BFS/DFS/위상정렬 무한반복이었다. 그래서 코어타임도 관련 연습문제를 뽑아주니 팀원들이 푸는 속도가 금방 끝나서, 마지막 3번째 코어타임때는 나 스스로는 연습 예제를 안 보고 그냥 푸는 방식으로 하였다.

문제 풀이법이 너무나도 정형화, 패턴화된 주기도 하다.

DFS와 재귀를 좀 많이 안했던 나에겐 트리 자체에선 그냥 DFS로 문제를 접근하고, 나머지 부분은 BFS도 잘 섞어서 풀었던거 같다.

* 트리 문제는 재귀(DFS) 중심으로 접근
* 그래프 문제는 인접 리스트 + BFS/DFS로 해결
* BFS는 “최단거리 / 레벨 탐색”
* DFS는 “완전 탐색 / 경로 탐색” 용도로 구분해서 사용
* 위상정렬은 indegree 기반 queue 방식으로 접근

GPT한테 받은 이번 주 피드백은 다음과 같다.

구현 능력은 충분히 갖춰졌고, 
BFS/DFS와 위상정렬을 문제에 맞게 적용할 수 있는 수준까지 올라왔다.
다만 알고리즘을 “어디에, 언제 써야 하는지”에 대한 
패턴 인식은 아직 완전히 자동화되지 않아 흐름이 가끔 흔들리는 모습이 있었다.
다음 단계는 새로운 문제 풀이보다, 
기존 문제를 통해 패턴을 빠르게 떠올리는 훈련이 필요하다.

이번 주는 열심히 푼 만큼 흔들린 모습도 적날하게 보였나보다.

2. 수요코딩회 (React VDOM, DIFF)

2명 밖에 없는 수요코딩회도 처음이라, 일단 내 컴퓨터에서 쭉 작업하고, 보자고 결론이 나왔다.

3. 수요코딩회 (React VDOM, DIFF)

1. React VDOM, DIFF 프로젝트 소개

Mini React를 구현하는 프로젝트를 진행했다. (사실 Mini React가 목표치는 아니긴 했다만)

단순히 DOM을 조작하는 게 아니라 Virtual DOM + Diff 알고리즘 직접 구현 key 기반 리스트 최적화 Fiber 스케줄러 (Render Phase / Commit Phase 분리) useState / Batch 3버전 비교 (Vanilla / Mini React / Real React) + 벤치마크 까지 구현했다. (그래서 다음 주 주제랑 겹쳐버림)

2. 팀 구성과 협업 방식

• 2명 팀, 단 내가 단독 개발.
• Claude CLI - AI 바이브 코딩
• 완성된 후 팀원에게 QC 요청 및 추가 개발 사항 검토
• 기획 - 개발 - 발표 (모두)

협업에서 어려웠던 점:

• 나름 실력이 있었던 동료 out으로 인한 노선 변경 (프로젝트상 제약)
• 남은 팀원에게 코딩할 영역을 분담한다고 하였으나, 강제하지 않았으며, 2명인 상태에서 혼자서 개발하는 모습을 참고하고 학습하고 싶다해서, 처음이자 마지막으로 단독 개발(?) 대신 남은 팀원에게 스스로 Codex를 돌려서 해당 기능을 만들어서 설득해보라고 과제를 던져서, 내가 만든 것을 이해할 수 있게 유도하였다.

3. 기술적으로 배운 것

3-1. 왜 innerHTML을 안 쓰고 VNode를 직접 만들었나

처음엔 그냥 innerHTML로 바꾸면 되지 않나 생각했다. 근데 발표 때 "변경된 부분만 업데이트한다고 했는데 어떻게 찾아냈나요?" 질문이 나오면 innerHTML을 쓴 팀은 대답을 못 한다. 그래서 DOM을 직접 순회해서 VNode로 변환하는 함수를 만들었다.

jsfunction domToVNode(element) {
  // 텍스트 노드는 따로 처리해요
  // 브라우저에서 텍스트도 하나의 노드거든요
  if (element.nodeType === Node.TEXT_NODE) {
    return {
      type: '#text',
      props: {},
      children: [],
      text: element.textContent
    }
  }

  // 일반 태그는 속성과 자식을 재귀로 수집해요
  return {
    type: element.tagName.toLowerCase(),
    props: Array.from(element.attributes).reduce((acc, attr) => {
      acc[attr.name] = attr.value
      return acc
    }, {}),
    children: Array.from(element.childNodes).map(domToVNode),
    text: null
  }
}

VNode를 JS 객체로 만들어두면 두 VNode를 비교하는 게 DOM을 직접 비교하는 것보다 훨씬 빠르다. DOM 접근은 느리고 VNode 비교는 빠른 JS 연산이기 때문이다.

3-2. Diff 5케이스 — 어떻게 O(n)으로 줄였나

처음엔 두 VNode 트리를 완전히 비교하려 했다. 근데 그러면 O(n³)이라 노드 1000개면 10억 번 비교가 된다. React가 5가지 규칙으로 O(n)으로 줄인다는 걸 알고 방향을 바꿨다.

jsfunction diff(oldVNode, newVNode, patches = [], index = 0) {
  // 케이스 1: 새 노드가 생겼어요
  if (!oldVNode) {
    patches.push({ type: 'ADD', newVNode, index })
    return patches
  }

  // 케이스 2: 노드가 사라졌어요
  if (!newVNode) {
    patches.push({ type: 'DELETE', index })
    return patches
  }

  // 케이스 3: 태그 종류가 바뀌었어요 → 통째로 교체
  if (oldVNode.type !== newVNode.type) {
    patches.push({ type: 'REPLACE', newVNode, index })
    return patches  // 자식은 볼 필요 없어요
  }

  // 케이스 4,5: 텍스트나 속성이 바뀌었어요 → UPDATE / PROPS
  if (oldVNode.text !== newVNode.text) {
    patches.push({ type: 'UPDATE', text: newVNode.text, index })
  }

  const propsDiff = diffProps(oldVNode.props, newVNode.props)
  if (propsDiff) {
    patches.push({ type: 'PROPS', props: propsDiff, index })
  }

  // 자식 노드 재귀 비교
  const maxLength = Math.max(
    oldVNode.children.length,
    newVNode.children.length
  )
  for (let i = 0; i < maxLength; i++) {
    diff(oldVNode.children[i], newVNode.children[i], patches, `${index}-${i}`)
  }

  return patches
}

케이스 3에서 타입이 다르면 자식을 볼 필요가 없다. 이 조기 종료 덕분에 O(n)이 가능하다. 흥미로웠던 점:

처음엔 텍스트 변경과 속성 변경을 모두 UPDATE로 처리했는데 시각화할 때 구분이 안 돼서 PROPS를 별도 케이스로 분리했다. 결국 화면에는 ADD / DELETE / UPDATE / PROPS 4개가 표시된다. UPDATE가 텍스트 변경을 포함하고 있어서 5케이스가 4개로 보이는 것이다.

3-3. key 기반 Diff — 리스트 순서 변경을 어떻게 잡았나

인피니티 스크롤로 포스트가 추가될 때 기존 포스트가 전부 재렌더링되는 문제가 있었다. 인덱스 기반 Diff는 순서가 바뀌면 전부 다르다고 판단하기 때문이다.

jsfunction diffChildren(oldChildren, newChildren, patches, parentIndex) {
  // key가 있으면 key로 매핑해요
  const oldKeyMap = {}
  oldChildren.forEach((child, i) => {
    if (child.props?.key) oldKeyMap[child.props.key] = i
  })

  newChildren.forEach((newChild, i) => {
    const key = newChild.props?.key
    // key가 있으면 이전 위치를 찾아요
    // key가 없으면 인덱스로 비교해요
    const oldIndex = key !== undefined ? oldKeyMap[key] : i
    diff(oldChildren[oldIndex], newChild, patches, `${parentIndex}-${i}`)
  })
}

key가 있으면 포스트 1000개 중 새 포스트 10개만 ADD로 감지한다. 기존 990개는 변경 없음으로 건드리지 않는다.

3-4. Fiber — Diff가 브라우저를 멈추게 하는 문제

VNode가 많아지면 Diff를 동기적으로 처리하는 게 문제였다. 처리하는 동안 브라우저가 클릭도 스크롤도 못 하게 됐다. 실제 React가 Fiber로 이 문제를 해결한다는 걸 알고 구현했다.

js// Render Phase: 잘게 쪼개서 브라우저에 양보해요
function workLoop(deadline) {
  while (nextUnitOfWork && deadline.timeRemaining() > 1) {
    // Fiber 하나씩 처리해요
    nextUnitOfWork = performUnitOfWork(nextUnitOfWork)
  }

  if (!nextUnitOfWork && wipRoot) {
    // 모든 Fiber 처리 완료 → Commit Phase 시작
    commitRoot()
  }

  // 브라우저한테 양보하고 다시 요청해요
  requestIdleCallback(workLoop)
}

// Commit Phase: 변경사항을 한 번에 DOM에 반영해요
// 이 단계는 중간에 멈추지 않아요
function commitRoot() {
  deletions.forEach(commitWork)
  commitWork(wipRoot.child)
  // Reflow/Repaint가 이 시점에 한 번만 일어나요
}

Render Phase에서 변경사항을 모아서 Commit Phase에서 한 번에 DOM에 반영하기 때문에 Batch가 자연스럽게 동작한다. Fiber가 있어서 Batch가 가능한 것이지 Batch 때문에 Fiber가 필요한 게 아니다.

3-5. useState — 함수가 반복 실행되면 상태가 사라지는 문제

Fiber가 상태 변경마다 컴포넌트 함수를 다시 실행한다. 근데 함수는 실행될 때마다 변수가 초기화된다.

jslet hookIndex = 0

function useState(initialValue) {
  const fiber = currentFiber
  const oldHook = fiber.alternate?.hooks[hookIndex]

  const hook = {
    // 이전 상태가 있으면 그걸 쓰고, 없으면 초기값을 써요
    state: oldHook ? oldHook.state : initialValue,
    queue: []
  }

  // 큐에 쌓인 업데이트를 한 번에 반영해요 (Batch)
  oldHook?.queue.forEach(action => {
    hook.state = action(hook.state)
  })

  const setState = (action) => {
    hook.queue.push(typeof action === 'function' ? action : () => action)
    wipRoot = { ...currentRoot, alternate: currentRoot }
    requestIdleCallback(workLoop)
  }

  fiber.hooks[hookIndex] = hook
  hookIndex++  // 순서가 중요해요

  return [hook.state, setState]
}

hookIndex로 상태를 구분하기 때문에 조건문 안에 useState를 쓰면 인덱스가 밀려서 상태가 엉킨다. React가 훅을 조건문 안에 쓰면 안 된다는 규칙의 정확한 이유다.

4. 벤치마크 결과

테스트
Vanilla | Mini React | Real React 
좋아요 1000회 
234ms 🔴18ms ✅15ms ✅포스트 100개 렌더링
89ms    23ms   19ms
인피니티 스크롤 +10개
67ms  8ms  7ms
setState 3회 렌더링 횟수 
3회 🔴1회 ✅1회 ✅
Mini React와 Real React가 비슷하게 나온다.
핵심 원리가 동일하기 때문이다.
이게 Mini React가 Real React보다 좋다는 게 아니다.
Real React는 저희가 처리하지 못한 수천 개의 엣지 케이스를 처리하고
useMemo, useCallback, Error Boundary 같은 추가 최적화가 있다.

한 가지 아쉬운 점: UI 블로킹 측정을 iframe 이벤트 핸들러로 구현했는데 iframe 통신 비용이 섞여서 수치가 부정확하게 나왔다. 렌더링 중 UI 블로킹: Vanilla 0.8ms Mini React 0.5ms Real React 1.6ms ← Real React가 가장 느림 (iframe 오버헤드 때문) 메인 스레드에서 setTimeout으로 직접 측정했어야 했다. 발표에서 이 수치는 설명하기 어려워서 Fiber 블로킹 시연은 숫자 대신 직접 버튼을 눌러서 반응 여부를 보여주는 방식으로 바꿨다.

5. 배운 점

VDom이 빠른 게 아니다. VDom 덕분에 느린 DOM을 덜 건드리게 되는 거다. DOM을 건드릴 때마다 Reflow와 Repaint가 발생하는데 VDom과 Diff로 그 횟수를 최소화하는 것이다. Fiber는 두 가지를 동시에 한다. Render Phase에서 쪼개서 브라우저에 양보하고 Commit Phase에서 모아서 한 번에 DOM에 반영한다. 브라우저를 멈추지 않으면서 Batch도 가능한 이유다. 기술은 문제가 있어서 만들어진다. DOM이 느리니까 VDom과 Diff Diff가 브라우저를 멈추니까 Fiber 함수가 상태를 기억 못 하니까 useState 각 기술이 왜 만들어졌는지 알면 어떻게 동작하는지가 자연스럽게 따라온다.

6. 아쉬운 점

• 발표 때는 그냥 하고 Infinite Scroll을 왜 DOM에서 구현하지 않았는가. (하트나 작성한 댓글이 사라진다는 것을 보여주지 못했다.)
• Ending 코멘트를 제대로 말하지 못했다.
  • DOM을 건드릴 떄 마다 Reflow, Repaint 발생하므로, VDOM, Diff로 바뀐 VNODE를 찾아서 DOM 조작을 최소화하는데, Diff(변경 사항)이 많아질 경우, Fiber로 Render Phase에서 변경사항을 모으고, Commit Phase에 한번에 변경사항을 patch한다. (batch) 따라 Reflow, Repaint가 단 한번에 일어난다.

7. 느낀 점

빨리 완성했지만, 너무 이것저것 만들어서 5주차 주제랑 겹쳐버린 상황. 그리고 뭐 개념을 확인하기 위해 고군분투하다 보니까 저기까지 간거 같다.

GitHub 링크: https://github.com/JYPark-Code/jungle_w4_react_vdom_diff

4. 차주 계획

알고리즘

1. DP
2. Greedy

수요코딩회

• React state, hook, component 만들기
• React batch 구현

목표

1. 문제 열심히 풀고, 개념 정리 (목요일 이후 작성, 현재 저번주 것이 작성되어 있음)
2. 수요코딩회 - 팀원들을 잘 활용해서 목표 달성하기.
3. CS:APP 1장 읽어보기 + 정리하기

알고리즘 주제

• 이분탐색
• 분할정복
• 퀵 정렬, 머지 정렬
• 스택
• 큐
• 우선순위 큐
• 링크드리스트
• 해쉬테이블

3월 13일 금요일

• Week 3 팀 구성
• 베이직 문제 모두 Solved
• 코어 타임 - 스택

3월 14일 토요일

• 하, 중 문제 일부 Solved
• 코어 타임 - 링크드리스트

3월 16일 월요일

• 중 문제 모두 Solved
• 코어 타임 - 분할 정복

3월 17일 화요일

• 상 문제 2개 + 금주 알고리즘 리뷰
• 코어 타임 해시테이블

3월 18일 수요일

• 수요코딩회 - Mini-Redis 개발
• 개발 및 시연 정리

3월 19일 목요일

• 수요코딩회 개발한 것 발표
• Week3 팀 회고
• WIL 작성

WIL

1. 이번 주 목표

1주차와 2주차와 달리, 실력적으로 의지할 사람은 나 혼자였고, 다른 팀원 3명은 열심히 하는 포지션이었어서, 다들 나를 보는 상태에서 팀이 운영될 때, 또 깃발을 잡고, 한 주를 운영했다.

1. 각자 코드는 열심히 풀고 코어 타임때 푼 방향이나 로직에 대해서 설명하기.
2. 마지막 날에는 어떻게 풀었는지 모니터를 번갈아 보면서 코드 구성 확인하기.

결론적으로 말하자면, 오늘 팀 회고를 하면서 각자 얻어갈 것을 얻어간 느낌이다. 나는 팀원들에게 도움이 되려고 노력했고, 내 실력에 의해서 다른 팀원들에게 위화감을 조성하지 않으려고 노력했다. 다행스럽게도 다들 내 노력이 빛을 발했는지, 다들 좋게 평가하고 있는 거 같다.

알고리즘 학습 목표

가장 중요한 포인트는 문제 접근법이었다.

• 선형 탐색 → 시간초과 → 이분탐색으로 전환
• 전체 탐색 → 분할정복으로 구조 분해
• 정렬 문제 → 퀵/머지 정렬 개념 기반으로 이해
• 상태 관리 → 스택/큐로 모델링

수요코딩회 프로젝트 목표

1. 나 혼자 완성하지 말 것.
2. 팀원들을 위해서 욕심 부리지 말 것 -> O , 다들 이해가 될 수 있게 구조를 틀었다.
3. 팀원들이 vibe-coding을 할 때 효율적으로 할 수 있게 가이드라인 제공 -> O
4. 코드에는 모두 주석 달기. -> O

2. 시도한 접근 방식

1. 알고리즘 학습

다른 팀원들이 보면, 내가 알고리즘을 엄청 잘 푼 것처럼 보이겠지만, 나 역시 이번주 주간 정렬파트에선 꽤나 힘들었다.

잘못된 접근 → 수정 → 개선의 과정을 반복하는 방식으로 진행했다.

이미 주제를 적어두어서 문제 접근 방법을 대부분 그것이라고 생각하고 들어갔겠지만, 다음과 같이 패턴화 또는 효율성을 고려하였다.

* 뱀 문제 → deque + set으로 상태 관리

* 괄호 문제 → stack

* 빈도 문제 → hash (dict / Counter)

* 순서 처리 → queue

GPT한테 받은 이번 주 피드백은 다음과 같다.

부분 이해 → 전체 이해로 확장하는 방식

특징적인 패턴 하나 있었는데,

👉 완벽히 이해 안 된 상태에서도 일단 진행

예:

“2와 1이 추가되는 로직은 완전히 이해 못했지만 일단 진행”

“슬라이딩 윈도우 느낌인데 확신은 없음”

이 방식의 장점:

멈추지 않음

경험이 쌓임

단점:

개념이 흐릿하게 남을 수 있음

그래서 현재 상태는
👉 경험은 쌓였고, 개념 정리가 필요한 타이밍

지금은 어느 문제인지 또렷히 기억나는데, 개념 정리 및 내실을 다지라고 GPT가 정리해준 느낌이다.

2. 수요코딩회 (Mini-Redis)

레디스를 만들어보라는 건 Hash-table이 주간에 있었던 것.

일단 내가 코어를 만들고 나머지 팀원들이 채워나가고, 다시 정리하고, 발표는 다른 사람이 맡는 방식으로 자세한 회고는 아래와 같다.

3. 수요코딩회 Mini-Redis

1. Mini-Redis 프로젝트 소개

수요일에 하루 동안 AI 도구 아무거나 활용해 Mini Redis를 구현하는 프로젝트를 진행했다. (나는 Claude Code)

단순히 Python dict로 키-값을 저장하는 게 아니라

• 해시 테이블 직접 구현
• TTL + Lazy Deletion
• threading.Lock 동시성 제어
• Cache Aside Pattern
• JSON 스냅샷 영속성

까지 구현했다.

2. 팀 구성과 협업 방식

• 4명 팀, 본인이 core 개발 담당
• Claude CLI / Codex App으로 AI 바이브 코딩
• core가 완성된 후 팀원들에게 routes.py skeleton 배포
• 본인이 통합 및 최종 마무리

협업에서 어려웠던 점:

• 병렬 작업까지 시간이 꽤나 준비 과정이 길었다.
• AI가 생성한 코드를 내가 직접 이해하고 설명하고, 팀원들이 그것을 이해하는 것까지가 좀 난이도가 있었다.

3. 기술적으로 배운 것

3-1. Python dict를 안 쓴 이유

처음엔 그냥 dict 쓰면 되지 않나 생각했다. 근데 발표 때 "해시 충돌을 어떻게 처리했나요?" 질문이 나오면 dict을 쓴 팀은 대답을 못 한다.

그래서 배열 + 체이닝 방식으로 직접 구현했다.

class HashTable:
    def __init__(self, size=256):
        self.size = size
        self.buckets = [[] for _ in range(self.size)]

    def _hash(self, key: str) -> int:
        return hash(key) % self.size

    def set(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

체이닝은 같은 버킷에 충돌이 나면 리스트로 이어 붙이는 방식이다. 구현이 단순하고 직관적이라 하루 안에 완성하기 적합했다.

3-2. Lazy Deletion — TTL을 어떻게 처리할까

처음엔 background scheduler로 주기적으로 만료 키를 삭제하려 했다. 근데 실제 Redis가 Lazy Deletion을 쓴다는 걸 알고 방향을 바꿨다.

def get(self, key: str):
    if self.expire_at.get(key):
        if time() > self.expire_at.get(key):
            self.delete(key)
            return None
    return self.hash_table.get(key)

조회 시점에만 만료 여부를 확인하고 삭제한다. 별도 스케줄러가 없어서 구현이 단순하고, 발표 때 TTL -2가 반환되는 순간을 "Lazy Deletion 발동"으로 시각화해서 보여줄 수 있었다.

3-3. threading.Lock — 동시성을 어떻게 잡았나

열차 좌석 동시 예약 시나리오를 구현하면서 동시성 문제를 직접 체감했다.

처음엔 set을 그냥 쓰면 마지막 사람이 항상 덮어쓰는 문제가 있었다. setnx (Set if Not eXists) 를 추가하고 Lock으로 감쌌다.

def set_nx(self, key: str, value: str, ttl=None) -> bool:
    with self.lock:
        if self.hash_table.get(key) is not None:
            return False
        self.hash_table.set(key, value)
        if ttl:
            self.expire_at.set(key, time() + ttl)
        return True

서버에서 threading.Event로 N개 스레드를 동시에 출발시키고 Lock 경쟁을 만들어서 1명만 성공하는 걸 시연했다.

흥미로웠던 점:

• 처음엔 브라우저 Promise.all로 동시성을 구현하려 했는데 JS는 싱글 스레드라 항상 사용자 1이 성공했다.
• 서버 threading으로 옮기니 진짜 랜덤으로 성공자가 바뀌었다.

3-4. Cache Aside Pattern

SQLite DB를 붙이고 캐싱 전략을 구현했다.

cached = store.get(cache_key)
if cached:
    return {"source": "cache_hit", "trains": json.loads(cached)}

result = get_trains_from_db(from_station, to_station)
store.set(cache_key, json.dumps(result), ttl=60)
return {"source": "cache_miss", "trains": result}

1000회 반복 측정 결과:

• DB 직접 조회: 140ms
• Mini Redis 캐시: 4ms
• 속도 향상: 35배

처음엔 AI가 delay()로 시뮬레이션하려 했는데, 프로젝트 취지와 맞지 않다는 판단 하에 실제 SQLite 파일 I/O로 바꿨다. 그게 훨씬 설득력 있는 벤치마크가 됐다.

사실 이것도 100% 노력이라고 보기에는 어렵다. 여전히 DB와 비교하기 썼다고 해도, "Mini-Redis는 DB와 내부에 같은 한 프로세스에서 돌리면, 실제 Docker 위의 레디스에 비해 무조건 빠르게 나올 것이다." 라는 건 유추할 수 있었다. 진짜 Redis와 비교한다는 실험을 포함한 순간에 그냥 DB와 만든 mini-Redis도 docker로 올려봐야 했었다. $+$ 멀티 서버 고려도? ( Coach들 발표 코멘트 中)

3-5. 영속성 — 서버가 꺼져도 데이터를 남기려면

인메모리는 서버가 꺼지면 데이터가 사라진다. 실제 Redis의 RDB 방식처럼 주기적으로 파일에 저장하기로 했다.

@asynccontextmanager
async def lifespan(app: FastAPI):
    load_snapshot(store)
    start_auto_snapshot(store, interval=60)
    yield
    save_snapshot(store)

서버 시작 시 복원, 60초마다 자동 저장, 종료 시 마지막 저장.

한 가지 버그가 있었다: 스냅샷을 삭제하고 서버를 끄면 lifespan shutdown에서 다시 저장해버렸다. _snapshot_disabled 플래그를 추가해서 해결했다.

4. Mini Redis vs 실제 Redis

로컬에서 측정하면 Mini Redis가 압도적으로 빠르게 나온다.

이게 실제 Redis가 나쁜 게 아니다. Mini Redis는 같은 프로세스 안에서 직접 함수를 호출하고 실제 Redis는 Docker 네트워크를 거치기 때문이다.

프로덕션에서는 C 언어 구현 + 전용 서버 + TCP 최적화로 실제 Redis가 훨씬 빠르다.

5. 아쉬운 점

• Active Deletion (주기적 만료 키 삭제) 미구현
• LRU eviction 미구현
• Redis 프로토콜 (RESP) 미구현 — HTTP/REST로 대체
• 프로덕션 환경에서 실제 Redis와 성능 비교를 못 해본 것

6. 느낀 점

하루 안에 구현하면서 가장 크게 느낀 건 구현 완성을 11시에 했는데 시연을 시뮬레이션 하다보니 2시를 훌쩍 넘겼다.

팀원들에게 이해 시키는 시간, 그리고 나 스스로 코드를 이해하려는 시간도 저 안에 포함되어 있었을 것이다.

AI가 만든 코드를 그냥 쓰는 게 아니라 왜 이렇게 작동하는지 설명할 수 있어야 수요코딩회의 의미가 더해질 것 같다.

GitHub 링크: https://github.com/JYPark-Code/jungle_w3_mini_redis

4. 차주 계획

알고리즘

1. Graph
2. BFS
3. DFS
4. 위상정렬
5. 트리

수요코딩회

• React의 Virtual DOM, Diff 알고리즘 구현
• Tree 구조여서 시도 예정 & FE는 필수.

목표

1. 문제 열심히 풀고, 개념 정리
2. 수요코딩회 - 기피하는 부분으로 나왔는데, 적극적으로 부딪히기.

알고리즘 주제

• 기본적인 자료구조 (Dict, Array, String ...), 파이썬 문법
• brute Force
• 재귀함수
• 백트래킹
• 정수론

3월 7일 토요일

• Week2 팀 구성 + 알고리즘 basic 문제 10문제 Solved
• 코어 타임 Leet 코드 문자열 Solved

3월 9일 월요일

• 오전 알고리즘 (이동석 코치님) 강의 - 프로그래밍 사고 + 재귀적 접근
• 알고리즘 + 하 문제 + 중 문제 일부
• 코어 타임 백트래킹 핸드폰 문자열

3월 10일 화요일

• 알고리즘 중 문제 + 백트레킹 유형별 문제 생성 4문제 + 비숍 문제(플레)
• 코어 타임 Pow() fast exponent algorithm
• 알고리즘 푼 문제 Total Review

3월 11일 수요일

• OpenAI Codex 설명 세션 : OpenAI 임직원 (Krafton 담당자, Deployment Engineer, Solution Architect, Account Manager)
• Codex로 미니 해커톤 70분
• 세션 이후 수요코딩회 진행 (~새벽 2시 30분)

3월 12일 목요일

• 수요코딩회 3분 발표 및 코드 리뷰
• 3주차 발제
• 2주차 팀원 회고
• 2주차 WIL 작성 & 3주차 팀원 check

WIL

1. 이번 주 목표

이번 주에는 알고리즘 학습과 함께 미니 해커톤 프로젝트를 수행. 바이브 코딩에 익숙해지고, 빠르게 서비스를 설계, 구현하는 것을 목표로 했다.

알고리즘 학습 목표

구현 / 문자열 / 재귀 문제 유형 익숙해지기

완전탐색 / 백트래킹 개념 정리

문제 풀이 과정에서 재귀적 사고와 상태 관리, 백트래킹 방식 익히기

수요코딩회 프로젝트 목표

GitHub 기반 알고리즘 학습 관리 서비스 설계

백엔드 구조 설계 및 핵심 기능 구현

Codex 기반 Vibe Coding 실험

GitHub OAuth, Repo 분석, Commit 기반 풀이 분석 기능 구현

2. 시도한 접근 방식

이번 주에는 두 가지 축으로 학습을 진행했다.

1. 알고리즘 학습

주로 다음 접근 방식으로 문제를 해결했다.

문제를 보고 가능한 알고리즘 유형을 먼저 추정

상태(state)를 정의

탐색 방식 결정

재귀

완전탐색

시간복잡도 검토

Python 코드로 구현 후 테스트

특히 재귀 문제와 백트래킹의 경우 다음 방식으로 접근했다.

종료 조건(base case) 먼저 정의

재귀 호출 구조 설계

상태 복구(backtracking) 여부 확인

2. 해커톤 프로젝트 접근 방식

프로젝트는 GitHub 기반 알고리즘 학습 대시보드 서비스로 방향을 잡았다.

서비스 핵심 구조는 다음과 같다.

GitHub OAuth 로그인
      ↓
Repository 선택
      ↓
Issues / Commits 동기화
      ↓
Commit 기반 풀이 분석
      ↓
알고리즘 Skill Map 분석
      ↓
약점 기반 문제 추천

백엔드는 Flask 기반으로 개발했고 GitHub API를 활용해 다음 데이터를 가져왔다.

repository issues

commits

changed files

DB는 SQLite 기반으로 운영 상태를 저장하도록 설계했다.

3. 문제와 해결 과정

문제 1 — GitHub API 데이터 처리 구조

초기에는 GitHub 데이터를 매 요청마다 가져오는 구조로 설계했다.

문제점

API 호출이 많아짐

성능 저하

동일 commit을 반복 분석

해결

GitHub를 원본 데이터 소스로 두고 DB를 캐시 + 분석 결과 저장소로 사용하는 구조로 변경했다.

GitHub → 원본 데이터 DB → 서비스 상태 및 분석 결과

문제 2 — 문제 해결 판정 로직

단순히 commit만으로 문제를 해결했다고 판단하기 어려웠다.

그래서 다음 기준을 설계했다.

• 풀이 인정 기준

commit에 해당 문제 파일 존재

파일명이 issue 제목 규칙과 매칭

• 실행 가능한 코드

현재 MVP에서는

commit + 파일명 매칭

기준으로 1차 판정 로직을 구현했다.

문제 3 — 알고리즘 유형 분석

문제 유형 분석 기준이 필요했다.

그래서 다음 taxonomy를 정의했다.

# 1차 도메인
구현
수학
자료구조
정렬
탐색

# 1차 도메인 + 2번째 카테고리
구현 계열: 구현, 문자열, 사고력, 시뮬레이션, 재귀
자료구조 계열: 그래프, 배열, 스택, 큐, 트리, 해시, 힙
탐색 계열: BFS, DFS, 그리디, DP, 완전탐색, 이분탐색, 최단경로, 탐색
수학, 정렬은 각각 독립 도메인으로 매핑

각 영역 아래 세부 카테고리를 정의하여 Skill Map을 생성하도록 구현했다.

4. 새롭게 배운 점

1. 알고리즘 학습

이번 주 가장 크게 느낀 것은 문제 풀이보다 사고 과정이 더 중요하다는 점이다.

특히 재귀, 완전탐색, 백트레킹 문제에서는

상태 정의 → 탐색 구조 → 종료 조건

순서로 접근하는 것이 중요하다는 것을 배웠다.

2. 서비스 설계

단순히 기능을 만드는 것과 실제 서비스를 설계하는 것은 완전히 다르다는 것을 느꼈다.

특히 다음 부분이 중요했다.

데이터 흐름 설계

GitHub API 활용

DB 설계

API 구조 설계

AI 기반 개발 방식

이번 프로젝트에서 Codex 기반 개발을 적극적으로 사용했다.

느낀 점

빠른 구조 설계에 매우 유리

반복 코드 작성 속도 증가

하지만 아키텍처 판단은 사람이 해야 한다

5. 다음 주 계획

알고리즘 학습

다음 주에는 자료구조 문제를 더 집중적으로 학습할 계획이다.

이분 탐색

분할 정복

스택/큐/링크드리스트

해시테이블

수요코딩회

미니-레디스(Mini-Redis) 개발 예정.

목표

문제 풀이 속도 개선

시간복잡도 분석 능력 강화

조그만한 기업에 있어도, 아무리 이해가 안되는 일이 눈앞에 펼쳐져도, 나는 이미 현업 종사했던 또는 해봤던 개발자다.

이제 어떻게 하면, 회사에서 생존할지, 불편함을 피하는 요령을 알게 된다.

나에게 맞는 출퇴근 루틴도 잡혀서, 나에게 맞는 지속적인 편안함에 안주할 수도 있었다.

현업 개발자여도 순수 100% 개발을 할 필요 없는 AI 시대에서 정글을 택한 이유는 인생의 마지막 도전을 하고 싶어서였다.

현재까지 문제 정의와 비판적 관점과 생각이 내 장점인데, 직접 코딩을 하는건 내 장점이 아니다라고 생각한다. 밖에 좋은 걸 가져와서 응용하는 게 내 장점이라 생각한다.

입소 전, 스스로 더 좋은 곳으로 점프하기 위해, 좋건 싫건 cs와 아키텍처 공부와 현업을 몇 년간 병행해왔고, 현 직장에서 쓰지도 않는 기술을 공부하는 건 대단히 비효율적이었다. 사용하지 않는 기술 공부를 기약없이 무작정한다는 건 배운 것들이 모두 망각 곡선으로 가는 기분이었다.

도착 후, 1주차 미니 프로젝트에서 아무래도 지나친 자신감(?)과 잘할 수 있는 동료들의 시너지를 한번 보니, 평소라면 절대 하지 않는 기술적 시도, 살아남기 위해 열심히 부딛히고 있구나 느끼고 있다.

정글에서 얻고 싶은 것

1. 일단 팀원과의 협업이다. 내 나이는 다른 입소자 나이 Range에서 중상이다. 나이가 많은 사람은 80년대생도 있다고 들었는데 그 분은 다른 반에 있어, 나도 만나지 못하였다.

   지금까지 만난 팀원들(~ 2주차까지)은 모두 다 협조적이고, 적극적인 태도로 임하고 있어서 매우 긍정적이다.

   2. CS의 기초 학교를 졸업한지 꽤 되었고, 몇몇 전공 수업을 기억해보자면, 그다지 유쾌하진 않았던 것으로 기억한다. 그것을 다시 하는 것 자체가 큰 의미가 있다고 생각한다 특히 OS와 컴퓨터가 작동하는 원리 정글에서 하는 PintOS 많이 기대하고 있고, "C는 좀.." 이라는 생각이 들고 있다. C를 처음으로 학부에서 배웠어도, 아직까지 C는 좀 싫다.

   3. 문제 해결 능력

   정글의 교육 철학은 다 알려주고, 다 챙겨준다가 아니다. "문제를 정의하고, 팀원을 구성하고, 약간의 서포트까지 하면, 팀원과 함께 알아서 해결해 오세요."가 교육 철학이다. 이 포인트가 문제 해결 능력을 극단적으로 성장시킬 수 있을 것 같아서 지원해서 들어왔고, 협업 스킬도 향상 시킬 수 있을 것 같아, 지원하게 되었다.

   기술적으로 문제를 푸는 것 말고도, 미니프로젝트에서 경험해봤듯이 자신의 Ego를 줄이고, 프로젝트 상황과 시간적인 상황을 고려해서, 내려놓을 줄 알아야한다는 것을 깨달았고, FE-BE간 소통의 중요함. 그리고, 프로젝트 하는 사람들끼리 공유되는 정보의 통일 등등을 느꼈다.

How?

1. 운동

   운동을 주기적으로 해서, 5개월 완주를 목표로 하겠다. 미니프로젝트 때 많이들 새벽까지 깨어있고, 꽤나 힘든 초반을 거쳤다. 체력을 위한 운동으로 다치지 않고 하겠다.

2. 팀원들과 트러블은 최소화, 최대한 친하게! 어떤 팀에 가던지 내가 연장자일 가능성이 상대적으로 높다. 허물 없이 지내는건 맞지만, 예의도 지키고, 내가 가르쳐 줄 수 있는건 가르쳐 주고, 배우는 부분도 거리낌 없이 배우도록 노력한다.

3. ⭐ 잘하는게 중요한게 아니라, 시도를 하는게 중요한 것이다. ⭐ 코치들이 회식 때 얘기할 때 중점적으로 말한 것이다. 바로 생각나는게 차두리가 아직 프로 전에 애들을 코칭하면서 했던 말이 기억 났다.

어쩌면 나는 이런 기회가 없었을 수도 있었다. 코치들이 합격해준 만큼, 재밌게 열심히 5개월 보냈으면 좋겠다.

To : 26.07.31. Me

가장 큰 건 후회를 안 했으면 좋겠다. 들어오면서 스스로 많은 걸 포기했고, 나름대로 전략이 있어서 들어왔는데, 5개월 지나서 정글이 막상 별거 아니고, 이건 저랬고, 저건 저랬고, 류의 코멘트나, 핑계를 대고 있으면 그건 실패다.

성공의 기준은 결과가 어떻게 되었건 5개월간 좋은 동료들과 노력의 결실을 거둔다면, 축하한다. 생각보다 오래 걸렸고, 나름의 서사를 완성해서 더 큰 필드에 나갈 초석을 완성해서 진심으로 뿌듯하다.

크래프톤 사가 주최하는 정글(Jungle)에 합격하게 되어 3월 3일자로 입소하였다. 5개월간 합숙하며 성장할 예정이다.

3월 3일 화요일

첫날부터 쉬지 않는다.

입소하고, 룸메를 만나고, OT 끝나고, 팀원과 모여서 미니 프로젝트 기획을 하루 준비한다.

룸메와는 다른 반이다. 아마도 팀으로 만나다가 trouble, Conflict가 생기면 어색해지는 지점을 피하기 위한 거 같다.

팀원이 3명, 4명으로 구성되어있는데, 나는 3팀 : 팀원 3명 모두 전공자들이다.

첫인상 : 동생들이 열정도 넘치고, 잘하는 거 같다.

기획으로 뭘 할지, 고민하면서 3개로 잡았었다.

1. 미니 Jira (프로젝트 상태 관리, 협업 툴)
2. 정글 그룹 챗(팀 프로젝트, 실시간)
3. 공공 데이터 open-api를 활용한 프로젝트

1번 아니면 2번으로 좁아지다가, 내가 말한 1번으로 하게 되었다.

3월 4일 10시 발표 목표로 기획안을 완성하였다.

3월 4일 수요일

발표도 실전이다.

코치의 피드백이 몇몇 팀에게 꽤나 차가웠다. 대부분 과제나 기술 검색을 위해 노력을 안한 것 같다는 것에 대한 피드백이었다. 내가 볼 때는 대학생 티를 못 벗은 새싹 같은 친구들과 현업을 겪은 현업자들의 생각의 깊이, 노력의 차이, 시선의 차이 & 고민의 차이로 인한 괴리라고 본다.

하지만 현업 기준에선 태클 걸 요소는 1도 안했다. 그리고 밥 먹으면서 다른 팀에 배정된 사람들과 스몰톡 할 때도 "살살하신 거 같다." 라고 말 나오는 거 보니, 나만 그렇게 느낀거 같진 않은 듯 하다.

반대로 우리 팀에 대한 피드백은, 그 많은 걸 남은 3일 동안 과연 잘 할 수 있냐고 질문을 받았다. 오히려, 과감한 도전이니 scope를 줄이라는 피드백을 받았다.

발표 이후

FE는 동생 2명이, BE는 내가 맡았다. 나는 Spring MVC에 익숙해서, BE도 디자인 패턴을 꾸리는 게 좋다고 생각이 들었다. 그래서 Model, Route, Repository, Service 단을 만들고 인증/인가 부분부터 개발시작하고 얼추 형태를 만들고 끝냈다. 동생들을 뒤로하고 나는 0시 30분에 숙소로 향했다.

동생들은 3시까지 했다는데 다음 날에 너무 미안한..

3월 5일 목요일 ( 하루종일 작업 가능 )

코딩이 진도가 안 나간다.

Jungle 입소 전에 직접 코딩보다 바이브 코딩을 열심히 연구하고, 써왔어서, 직접 코딩을 하려니 old-school로 가야하겠다라고 생각이 들어, Github에 비슷한 프로젝트를 참고해서 프로젝트 디자인 패턴에 맞게 도입했다. 그래도 고민인게 API 문서를 어떻게 구성할지 고민하다가 점심시간이 도달했다. 오늘은 어제 만든 것에 다듬고, FE랑 붙이는 작업을 해서, index.html에 해당되는 작업을 하는 동료와 붙어서 안정화 작업을 했다.

많이 수정되는 과정에서, 버그가 생기는데 이게 시연 전에 몇몇 발견되어서, 많이 안타까웠다.

배포 전까지 퇴근은 안하고, 새벽 4시 반에 잠자리를 든거 같다.

3월 6일 금요일 (최종 발표일)

오전에 시연 시뮬레이션과 발표 스크립트를 정리했다. 그래도 터무니없게 시간이 부족한게, 내가 많은 욕심을 부려서인지, 프로젝트를 정리할 시간을 내가 많이 못 뽑아낸 불찰이라 생각이 들었다.

발표는 중간에 사고가 한번 터졌는데 id, pw를 복붙하면서 회원가입을 하다보니, 가입 쪽에서 DB쪽에서 제대로 안 받아준거 같고, 나도 끝나서 그거였나? 라는 생각이 들었다. 그동안 고생한 동생들한테도 너무 미안하고, 스스로에게 화가 난 시점이었다. 코치들은 딱히 엄청 뭐라 하진 않았고, 시연에 좀 신경써달라는 코멘트를 뒤로하고, 유일하게 타팀한테 하지 않은 "AI를 썼냐는 질문"을 받았다.

전체 회고 (WIL - Weekly I Learned)

Mini project - Mini Jira

1. 구현 결과 맡은 역할 : BE , PM(?)

• FE : 캘린더와 Status 탭 구현, 세부페이지 및 모달 창, 수정 창
• BE : 사용자 RBAC(Role-Based Access Control), Issue-CRUD, Auth(Login/Sign-in/Logout), 낙관적 lock (Optimistic Locking), MongoDB handling, Service - Repository 형태

2. 학습 포인트

• Flask에서 Service-Repository 패턴 구축 : Spring MVC에서는 프레임워크가 @Controller, @Service, @Repository로 간단하게 처리할 수 있는데, 이걸 직접 기능적으로 구현하는 것이 큰 의미가 됬다.

• 세션기반 인증 동작 원리 : 과제 안내에서 SSR과 jwt가 있었는데 둘의 조합이 좋지 않았다. 그래서 세션을 선택했다.

  세션 방식 로그인

  1. 세션은 세션데이터를 로그인하면 서버 메모리에 저장
  2. set-cookie 헤더로 Cookie 헤더가 브라우저에 전달, 매 요청마다 쿠키가 자동으로 첨부
  3. 로그아웃하면 세션 클리어 session.clear() 되고 서버에서 즉시 삭제

  JWT 방식 로그인

  1. 서버가 유저 정보를 담은 토큰을 발급해서 생성 및 반환
  2. FE 측에서 토큰을 LocalStorage나 메모리에 저장
  3. FE가 매 요청마다 Authorization : Bearer 헤더를 수동으로 추가
  4. 서버가 토큰을 검증 (서버에 상 저장 안 함)
  5. 로그아웃 서버에서 삭제할 것 없음.

  그래서 Why Session?

  1. 쿠키 자동 처리

     SSR에서 브라우저가 HTML 페이지를 요청하고, 모든 요청에서 쿠키를 자동으로 붙이고 인증. 반면 jwt라면, 모든 페이지 이동에 토큰을 헤더에 붙여하는 코드를 작성함. 그러면 모든 페이지 이동을 ajax를 넣어서 처리하는데 그러면 세션이랑 달라질께 없다.

  2. 로그아웃 시 즉시 ID가 서버에서 무효화

     JWT는 만료시간이 존재한다. 그래서 즉시 무효화를 할시 블랙리스트 DB를 만들어서 매 요청에 토큰을 조회해야하는데 그건 stateless라는 jwt 장점이 사라진다.

  3. 서버 확장이 필요없는 환경

     일단 jwt의 장점은 stateless여서 서버를 여러대 늘려도 세션 공유 문제가 없다는 것인데, 그 말은 즉 A에서 발급한 토큰을 B에서도 검증 가능하다는 것. 하지만 EC2 1개에 배포하여서, jwt의 장점이 발휘되지 못한다는 점.

• Mongo DB Embedded document

  댓글을 별도의 컬렉션이 아닌 이슈 문서 안에 embedded array를 넣는 설계를 했다. join query 없이 이슈와 댓글 모두 불러올 수 있는 장점이 있지만, 댓글이 다량일 경우 문서가 비대해질수 있고, $slice 페이지네이션 또는 댓글을 별도의 컬렉션으로 분리하는 방법이 존재한다. 결국 어떤 설계에 따라 Trade-off가 있고, 상황에 따라 맞는 선택을 해야하는 점을 배웠다.

• 낙관적 Lock(Optimistic Locking) 낙관적 Lock과 비관적 Lock이 있다는건 알지만, 코드로 풀어서 생각해볼 기회가 많지 않았다. 이번에 낙관적 락을 직접 구현한 것에 큰 의미가 있었다. Spring에서 @Version을 붙여서 해결하는 것을 MongoDB는 낙관적 락 기능이 없어, 직접 version을 구현하고, 409 conflit 응답까지 연결하여서 동시성 제어 기초를 익혔다.

3. 문제 해결 과정

1. due_date이 datetime으로 저장되는데 이슈 수정후 FE에서 받은 문자열을 그대로 DB에 저장이 되는 문제 (500 에러)

   원인 추적 : 전체 조회(/api/projects/<project-id>/issues)에서는 이슈가 나오는데 range 조회에서 나오지 않아서, update할때 _parse_due_date 변환이 누락되어있다는 점 발견

   해결 : update_issue_fields_service에서 start_date, due_date를 저장 전에 datetime으로 변환하도록 수정. status_view의 정렬과 남은 시간 계산에도 try/except로 타입 안전 처리를 추가했다.

   교훈 : 당연한 이야기지만, 데이터의 생성 수정에서 타입을 통일해서 수정하고 나서도 제대로 조회되도록 해야한다. 나중 조회나 비교에 있어서 버그 발생한다.

2. 초대 시스템 간소화

   문제 : 처음 설계는 초대 -> pending 저장 -> 수락 -> 멤버 추가. 4단계 흐름인데, 시간적인 한계 때문에 페이지 개발을 안하기로 했다.

   해결 : pending/accept 과정을 제거하고, 오너가 이메일을 입력할 시 member_id에 추가하고, 미리 만들어둔 invite_repository와 관련 route/service 삭제

   교훈 : 설계가 아무리 좋아도 일정 안에 할 수 없으면 의미가 없다. 핵심 기능을 유지하고, 복잡도를 줄이는 판단이 필요했고, 동작하는 MVP가 중요했다.

   3. FE에서 start_date null로 기존 데이터 덮어쓰기

   문제 : 이슈 상태만 변경했는데 캘린더에서 기간 표시가 하루로 줄어들었다.

   원인 추적 : FE 코드를 받아서 확인한 결과, jQuery의 .val()이 빈 input에서 빈 문자열("")을 반환하는데 FE에서 start !== undefined로 체크하고 있어서 빈 값이 항상 payload에 포함되었다. 서버에서 빈 문자열이 그대로 $set에 들어가 기존 start_date를 덮어쓴 것.

   해결 : BE에서 빈 문자열/null 필터링을 추가하고, FE에게는 if (start) 조건으로 바꾸도록 안내했다.

   교훈: FE와 BE의 경계에서 발생하는 버그는 양쪽 코드를 같이 봐야 원인을 찾을 수 있다. API 명세서에 "빈 값을 보내면 어떻게 되는가"까지 정의했어야 했다.

   4. 모달에서 댓글 등록 시 redirect로 모달이 닫히는 문제

   문제 : 댓글 추가가 form POST → redirect 방식이라 모달이 닫혔다.

   해결: 댓글 추가/삭제를 JSON API로 전환. FE에서 AJAX success 콜백에서 DOM에 직접 댓글을 추가하도록 변경.

   다시 FE 문제 : 댓글이 모달창에 바로 뜨지 않음.

   해결: 기입한 값은 pretend() 처리하여, redirect 시 DB의 데이터를 가져오게 처리.

   교훈: SSR 라우트(form POST + redirect)와 AJAX API(JSON 응답)의 사용 구분이 중요하다. 모달처럼 페이지 이동 없이 동작해야 하는 UI에는 AJAX가 맞고, 단순 행위(삭제, 프로젝트 생성)에는 form POST가 적합하다.

4. 개선 아이디어

1. DB 스키마 엄격 정의 MongoDB의 유연한 스키마로 인해 타입 혼재로 인한 문제가 많이 발생했다. Mongo DB Schema Validation을 설정하거나, Python에서 Pydantic으로 입출력을 강제했으면, 이런 문제를 원천 방지 할 수 있다.

2. 테스트 코드 도입 수동 테스트에 의존해서 수정할 때마다 기존 기능이 깨지는지 확인하기 어려워, pytest로 기능 테스트 작성을 했으면, 코드 수정 후 정상 동작을 빠르게 검증할 수 있었을 것이다.

3. API 문서 자동화 Swagger나 OpenAPI 도입했으면, 코드에서 문서 자동으로 생성되서 항상 최신 상태 유지를 할 수 있었을 것이다.

5. 성장 부분

1. 세션과 jwt 방식, embedded 와 collection 이 둘은 기존에 이론상으로 알던 부분을 실제 개발해서 그 트레이드오프를 알 수 있었다.

2. 협업 : FE 역할을 맡은 2명과 개발하면서, API 문서를 계속 수동으로 업데이트했었는데, 그조차 안했으면, 프로젝트가 완성이 안됬을 것 같다.

3. 트레이드오프 사고 : 미니 프로젝트를 완성하기까지 완벽한 설계와 많은 기능을 추구했지만, 시간적 압박을 받으면서, 과감히 포기할 부분은 줄이고, 핵심 기능에 집중하는 사고를 배웠다.

4. 디버깅 접근법 : "안된다"는 증상에서 데이터 추적을 FE와 같이 하게 되었고, 전체 조회에서는 나오는데, range에 안 나오는 버그를 타입문제여서, 찾는 그러한 경험 때문에 type-safed coding의 중요성을 다시 한번 깨닫게 되었다.

   미니 프로젝트 전체적으로 기능을 많이 개발했는데, 시연에 시간을 많이 투자하지 못하여 아쉬워서 많이 안타까웠다. 다음에는 좀 더 완성도 높게 해서 발표 준비해야 겠다.

약 반 달간 알고리즘 포스팅 안하다가 복귀한 이유는 그 동안 일정이 바빴기 때문, 그리고 또또또 코딩테스트가 눈 앞에 왔기 떄문. (놀랍게도 3일 뒤에 시험) (이제 강의 종료까지 딱 3문제 남았다. 유종의 미를 거둘 수 있도록 달려보도록 하겠다.)

상위 배너 또는 하위 링크를 통해 강의를 구매하시면, 블로그 작성자가 수익을 받을 수 있어요. 🤗 https://inf.run/Ce3jj

원 문제 링크

해당 문제는 프로그래머스에서 풀 수 있다.

이 문제도 바로 앞편 13편에서 풀었던 유형 중 하나인 데이터 파싱 문제다. 그 말은 즉 plain한 String 데이터가 들어왔을 때, 데이터 추출 및 복잡한 구현 문제라는 것.

문제 설명

추석 트래픽 이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.

입력 방식

solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다. 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다. 처리시간 T는 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다. 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 "2016년 9월 15일 오전 3시 10분 33.010초"부터 "2016년 9월 15일 오전 3시 10분 33.020초"까지 "0.011초" 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함) 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다. lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

출력 방식

solution 함수에서는 로그 데이터 lines 배열에 대해 초당 최대 처리량을 리턴한다.

입출력 예제

예제1 입력: [ "2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s" ]

출력: 1

예제2 입력: [ "2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s" ]

출력: 2

설명: 처리시간은 시작시간과 끝시간을 포함하므로 첫 번째 로그는 01:00:02.003 ~ 01:00:04.002에서 2초 동안 처리되었으며, 두 번째 로그는 01:00:05.001 ~ 01:00:07.000에서 2초 동안 처리된다. 따라서, 첫 번째 로그가 끝나는 시점과 두 번째 로그가 시작하는 시점의 구간인 01:00:04.002 ~ 01:00:05.001 1초 동안 최대 2개가 된다.

예제3 입력: [ "2016-09-15 20:59:57.421 0.351s", "2016-09-15 20:59:58.233 1.181s", "2016-09-15 20:59:58.299 0.8s", "2016-09-15 20:59:58.688 1.041s", "2016-09-15 20:59:59.591 1.412s", "2016-09-15 21:00:00.464 1.466s", "2016-09-15 21:00:00.741 1.581s", "2016-09-15 21:00:00.748 2.31s", "2016-09-15 21:00:00.966 0.381s", "2016-09-15 21:00:02.066 2.62s" ]

출력: 7

설명: 아래 타임라인 그림에서 빨간색으로 표시된 1초 각 구간의 처리량을 구해보면 (1)은 4개, (2)는 7개, (3)는 2개임을 알 수 있다. 따라서 초당 최대 처리량은 7이 되며, 동일한 최대 처리량을 갖는 1초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.

문제 해결

1. 정말 다행이게도. "추석 트래픽" 이라 날짜는 고려안해도 된다.
2. 모든 시간을 ms로 변환한다.
3. 각 타임라인의 시작과 끝을 구한다.
4. 인터벌을 순회하면서, 1초 사이에 겹치는 구간을 센다.

def solution(lines):

    interval = []
    answer = 0

    for line in lines:
        s, e = parse_line(line)
        interval.append((s, e))


    for s, e in interval:

        ws = s
        we = s + 999
        cnt = 0
        for ss, ee in interval:
            if ee >= ws and ss <= we:
                cnt += 1
        answer = max(answer, cnt)

        ws = e
        we = e + 999
        cnt = 0
        for ss, ee in interval:
            if ee >= ws and ss <= we:
                cnt += 1
        answer = max(answer, cnt)

    return answer

def time_to_ms(t):
    h, m, s = t.split(":")
    h = int(h)
    m = int(m)
    s = float(s)

    total_seconds = h * 3600 + m * 60 + s
    return total_seconds * 1000

def parse_line(line):
    date, time, process_time = line.split()

    end = time_to_ms(time)

    duration = float(process_time[:-1]) * 1000

    start = end - duration + 1

    return int(start), int(end)

Outro

올해도 얼마 안남았고, 2025년 하반기 채용 끝자락에 있을 텐데, 모두들 힘내시길 바란다. (나도 포함..)

이 문제는 데이터 파싱 문제다. 즉, 문자열로 들어온 정보를 적절하게 파싱하고, 재조립해서, 로직 안에 넣는 문제 -> 노가다 문제다.

상위 배너 또는 하위 링크를 통해 강의를 구매하시면, 블로그 작성자가 수익을 받을 수 있어요. 🤗 https://inf.run/Ce3jj

원 문제 링크

해당 문제는 프로그래머스에서 풀 수 있다.

문제 풀이

1. 토큰화해서, 시간 계산 하고, 멜로디 비교
2. "조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환한다. 재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환한다." 이 조건 놓치지 않기
3. 코드는 작성 완료하고 계속 1 케이스가 틀려서, 인터넷 검색 해보니 이 분 코드가 100% 나온다. (강의자 코드도 계속 1케이스가 틀린다.) -> GPT도 제대로 답변을 못하고 있음.

def solution(m, musicinfos):
    answer = '(None)'
    candidate = []

    for index, info in enumerate(musicinfos):
        start, end, song, melody = info.split(',')
        a, b = map(int, start.split(':'))
        c, d = map(int, end.split(':'))
        playtime = c * 60 + d - a * 60 - b

        melody_list = list(melody)
        for idx, mel in enumerate(melody_list):
            if mel == '#':
                melody_list[idx-1] += '#'
        melody_list = [mel for mel in melody_list if mel != '#']

        length = len(melody_list)
        real = ''
        for i in range(playtime):
            idx = i % length
            real += melody_list[idx]

        if m in real:
            if real.count(m) > real.count(m+'#'):
                candidate.append([playtime, song, index])

    if candidate:
        candidate.sort(key=lambda x:(-x[0], x[2]))
        return candidate[0][1]
    else:
        return answer

코드 출처

카카오 시험 응시 or 기출문제 풀어보면 이런 류가 참 많은거 같다. 풀었을 때는 쉽게 맞춘거 같은데, 몇개 놓쳤거나, 뭐가 틀렸지 하는 포인트가 있어서, 점수가 깎이는 것들이 꽤나 있다.

이 문제는 2차배열 스택문제다.

상위 배너 또는 하위 링크를 통해 강의를 구매하시면, 블로그 작성자가 수익을 받을 수 있어요. 🤗 https://inf.run/Ce3jj

원 문제 링크

해당 문제는 프로그래머스에서 풀 수 있다.

Q. 게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

board = [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]
moves = [1,5,3,5,1,2,1,4]
# 4 가 출력되어야 합니다.

일단 이 문제는 프로그래머스에 들어가서 어떻게 되어있는지 보고 푸는걸 추천한다.

일단 인형을 뽑은 다음에 스택에 쌓고 스택이 2개 중첩되면 인형이 사라지는 문제다.

문제 풀이

1. 2차원 배열을 다시 우리가 원하는 열(Column) 기준으로 만든다. 대신 Stack을 쌓는다는 걸 염두.

2. 2차원 배열을 만든 후, moves에서 하나씩 pop() 해서 stack에 맞다으면 인형 사라지는 거 카운팅 하면 끝.

example_board = [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]
example_move = [1,5,3,5,1,2,1,4]

def solution(board, moves):
    # 우리가 원하는 move를 활용할 수 있는 stack 형태로 바꾸자
    N = len(board)
    stack_board = [[] for _ in range(N)]
    answer = 0


    for i in range(N):
        for j in range(N-1, -1, -1):
            if board[j][i] == 0:
                continue
            stack_board[i].append(board[j][i])

    # print(stack_board) 
    # 0 소거 하면 [[3, 4], [5, 2, 2], [1, 4, 5, 1], [3, 4], [1, 2, 1, 3]]

    storage = []

    for move in moves:
        # 비어있는 곳이면 넘어감
        if len(stack_board[move-1]) == 0:
            continue

        storage.append(stack_board[move-1].pop())

        if len(storage) < 2:
            continue
        else:
            if storage[-2] == storage[-1]:
                storage = storage[:-2]
                answer += 2

    return answer


print("정답은 4, 프로그램 실행 결과: ", solution(example_board, example_move))

이전 BFS/DFS 문제에 비하면 쉬운 난이도라고 생각한다.

이번 문제도 2차 배열 안에서 이뤄지는 문제다.

상위 배너 또는 하위 링크를 통해 강의를 구매하시면, 블로그 작성자가 수익을 받을 수 있어요. 🤗 https://inf.run/Ce3jj

원 문제 링크

해당 문제는 백준에서 풀 수 있다.

치킨 배달

Q. 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 반환하시오.

입력 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다. 또한 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

n = 5
m = 3

city_map = [
    [0, 0, 1, 0, 0],
    [0, 0, 2, 0, 1],
    [0, 1, 2, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 2],
]  # 5 가 출력되어야 합니다

일단 문제의 가독성의 최악이어서, 도시의 치킨 거리를 구하라라고 하면 대충 뭔 소리인지 알겠지 라고 저렇게 쓰여있는데, 각 집에서 최소 치킨거리들의 합을 구하라는 문제다.

문제 풀이

1. 존재하는 모든 집 - 치킨집의 조합을 구한다.
2. 모든 경우의 수에서 최소값의 거리를 합한다.

말로 하면 잘 이해가 안될 수 있으니 코드로 설명하도록 하겠다.

from itertools import combinations
import sys

N = 5
M = 3

city_map = [
    [0, 0, 1, 0, 0],
    [0, 0, 2, 0, 1],
    [0, 1, 2, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 2],
]


def get_min_city_chicken_distance(n, m, city_map):

    houses = []
    chickens = []

    # 집 좌표, 치킨 좌표
    for r in range(n):
        for c in range(n):
            if city_map[r][c] == 1:
                houses.append((r, c))
            elif city_map[r][c] == 2:
                chickens.append((r, c))

    # 집에서 모든 치킨집까지의 거리를 저장
    H = len(houses)
    C = len(chickens)

    dist = [[0]*C for _ in range(H)]
    for i, (hr, hc) in enumerate(houses):
        for j, (cr, cc) in enumerate(chickens):
            dist[i][j] = abs(hr - cr) + abs(hc - cc) # 이렇게 거리를 구하는게 "맨하튼 거리 구하기"라고 한다. 
            # 한국으로 치면 강남 지역 (바둑판 지역) 거리 구하기라고 비슷하다고 생각하면 된다.


    best = sys.maxsize # 9223372036854775807 (시스템 상에서 최대값)

    #치킨 집 인덱스 중 M개 고르기
    for comb in combinations(range(C), m):
        # 이렇게 combinations 뒤에 range(정수) 이렇게 한 상태서 조합을 뽑으면
        # 조합의 수가 (0 ~ (C - 1)) 까지에서 m개를 뽑는 경우가 나온다.
        total = 0

        # 각 집에 대해, 선택된 치킨집들 중 최소 거리만 더하기
        # 이 코드들은 최소거리만 구해서 더하는 코드.
        for i in range(H):
            if total >= best:
                break
            m = sys.maxsize
            for j in comb:
                d = dist[i][j]
                if d < m:
                    m = d
                    if m == 0:
                        break

            total += m

        if total < best:
            best = total

    return best


# 출력
print(get_min_city_chicken_distance(N, M, city_map))  # 5 가 반환되어야 합니다!


city_map = [
    [1, 2, 0, 0, 0],
    [1, 2, 0, 0, 0],
    [1, 2, 0, 0, 0],
    [1, 2, 0, 0, 0],
    [1, 2, 0, 0, 0]
]
print("정답 = 11 / 현재 풀이 값 = ", get_min_city_chicken_distance(5,1,city_map))


city_map = [
    [0, 2, 0, 1, 0],
    [1, 0, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [2, 0, 0, 1, 1],
    [2, 2, 0, 1, 2]
]
print("정답 = 10 / 현재 풀이 값 = ", get_min_city_chicken_distance(5,2,city_map))

벌써 10편이 됬다. (하지만 0.5편이 2편이 있어서 12번째 포스팅) 이론편에서는 포스팅 하나에 23일 걸렸던 거 같은데, 확실히 1문제씩 포스팅하는 기출 쪽에서는 12일에 1개씩 완성하는듯 하다. 10월 말에도 시험들이 많이 있으니 이걸 포함해서 7편만 하면, 이 강의에서 포스팅은 모두 종료다.

상위 배너 또는 하위 링크를 통해 강의를 구매하시면, 블로그 작성자가 수익을 받을 수 있어요. 🤗 https://inf.run/Ce3jj

원 문제 링크

해당 문제는 백준에서 풀 수 있다.

구슬 탈출 2

문제 설명

스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.

이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.

각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오. 입력 보드를 나타내는 2차원 배열 game_map이 주어진다. 이 때, 보드의 행, 열의 길이는 3이상 10 이하다.

보드 내에 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력 파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 True, 없으면 False를 반환한다.

game_map = [
    ["#", "#", "#", "#", "#"],
    ["#", ".", ".", "B", "#"],
    ["#", ".", "#", ".", "#"],
    ["#", "R", "O", ".", "#"],
    ["#", "#", "#", "#", "#"],
]  # -> True를 반환해야 한다.

game_map = [
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
    ["#", "R", "#", ".", ".", ".", "#", "#", "B", "#"],
    ["#", ".", ".", ".", "#", ".", "#", "#", ".", "#"],
    ["#", "#", "#", "#", "#", ".", "#", "#", ".", "#"],
    ["#", ".", ".", ".", ".", ".", ".", "#", ".", "#"],
    ["#", ".", "#", "#", "#", "#", "#", "#", ".", "#"],
    ["#", ".", "#", ".", ".", ".", ".", "#", ".", "#"],
    ["#", ".", "#", ".", "#", ".", "#", ".", ".", "#"],
    ["#", ".", ".", ".", "#", ".", "O", "#", ".", "#"],
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]
]  # -> False 를 반환해야 한다

저번 문제에 이어서 또 이중배열이다. 이번에는 느낌상, BFS 느낌이 난다.

문제 해결 방법

1. 이번 문제는 기존의 BFS들과 약간 다른게 공이 2개여서, 변수가 2개다. 그 말은 즉, 2차원 배열에서 visited를 처리하는 게 아닌, 4차원에서 해결해야한다. 두 좌표(두 공이)가 동시 방문 했는지 팔로우업한다.

2. 여전히 상하좌우를 탐색해야하고, 구슬이 같은 열이나 행에 있을 때 벽까지 이동할 때 구슬 위치 처리를 해준다.

3. 문제 조건에 맞게 파랑이 떨어지면 실패, 빨강만 떨어지면 성공을 감안해서 구성한다.

from collections import deque

game_map = [
    ["#", "#", "#", "#", "#"],
    ["#", ".", ".", "B", "#"],
    ["#", ".", "#", ".", "#"],
    ["#", "R", "O", ".", "#"],
    ["#", "#", "#", "#", "#"],
]

dx = [-1, 1, 0, 0]  # 상 하 좌 우 (row 변화)
dy = [ 0, 0,-1, 1]  # 상 하 좌 우 (col 변화)

def roll_until_stop(board, x, y, dir_idx):
    """
    x: row, y: col
    dir_idx: 0~3
    반환: (최종row, 최종col, 이동칸수, 구멍빠짐여부)
    """
    nx, ny = x, y
    moved = 0
    while True:
        tx = nx + dx[dir_idx]  # 다음 row
        ty = ny + dy[dir_idx]  # 다음 col
        # 벽이면 직전에서 정지
        if board[tx][ty] == '#':  # row 먼저, col 나중
            return nx, ny, moved, False
        nx, ny = tx, ty
        moved += 1
        if board[nx][ny] == 'O':  # 구멍
            return nx, ny, moved, True

def is_available_to_take_out_only_red_marble(board):
    N = len(board)
    M = len(board[0])

    # R,B 좌표 찾고 보드는 지형만 남김
    rx = ry = bx = by = -1
    for i in range(N):
        for j in range(M):
            if board[i][j] == 'R':
                rx, ry = i, j
                board[i][j] = '.'
            elif board[i][j] == 'B':
                bx, by = i, j
                board[i][j] = '.'

    # 4차원 visited: [rx][ry][bx][by]
    visited = [[[[False]*M for _ in range(N)] for __ in range(M)] for ___ in range(N)]
    visited[rx][ry][bx][by] = True

    q = deque()
    q.append((rx, ry, bx, by, 0))

    while q:
        crx, cry, cbx, cby, depth = q.popleft()
        if depth >= 10:
            return False  # 10번 초과 금지

        for d in range(4):
            nrx, nry, rmove, r_in = roll_until_stop(board, crx, cry, d)
            nbx, nby, bmove, b_in = roll_until_stop(board, cbx, cby, d)

            # 파란 빠지면 실패
            if b_in:
                continue
            # 빨강만 빠지면 성공
            if r_in:
                return True  # 또는 depth+1 반환도 가능

            # 같은 칸에 멈춘 경우, 더 멀리 이동한 구슬을 한 칸 뒤로
            if nrx == nbx and nry == nby:
                if rmove > bmove:
                    nrx -= dx[d]
                    nry -= dy[d]
                else:
                    nbx -= dx[d]
                    nby -= dy[d]

            if not visited[nrx][nry][nbx][nby]:
                visited[nrx][nry][nbx][nby] = True
                q.append((nrx, nry, nbx, nby, depth + 1))

    return False




print(is_available_to_take_out_only_red_marble(game_map))  # True 를 반환해야 합니다



game_map = [
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
    ["#", ".", "O", ".", ".", ".", ".", "R", "B", "#"],
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]
]
print("정답 = False / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))


# 10번 초과로 False
game_map = [
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
    ["#", "R", "#", ".", ".", ".", "#", "#", "B", "#"],
    ["#", ".", ".", ".", "#", ".", "#", "#", ".", "#"],
    ["#", "#", "#", "#", "#", ".", "#", "#", ".", "#"],
    ["#", ".", ".", ".", ".", ".", ".", "#", ".", "#"],
    ["#", ".", "#", "#", "#", "#", "#", "#", ".", "#"],
    ["#", ".", "#", ".", ".", ".", ".", "#", ".", "#"],
    ["#", ".", "#", ".", "#", ".", "#", ".", ".", "#"],
    ["#", ".", ".", ".", "#", ".", "O", "#", ".", "#"],
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]
]

print("정답 = False / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))


game_map = [
["#", "#", "#", "#", "#", "#", "#"],
["#", ".", ".", "R", "#", "B", "#"],
["#", ".", "#", "#", "#", "#", "#"],
["#", ".", ".", ".", ".", ".", "#"],
["#", "#", "#", "#", "#", ".", "#"],
["#", "O", ".", ".", ".", ".", "#"],
["#", "#", "#", "#", "#", "#", "#"]
]
print("정답 = True / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))

이번 문제는 삼성 기출이다. 문제만 봐도 많이 까다로워 보이고, N Queen 문제가 살짝 떠오르는 그런 그림인데 나이트를 이용해서 진행하는 문제이다.

상위 배너 또는 하위 링크를 통해 강의를 구매하시면, 블로그 작성자가 수익을 받을 수 있어요. 🤗 https://inf.run/Ce3jj

원 문제 링크

해당 문제는 백준에서 풀 수 있다.

새로운 게임 2

Q. 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.

게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.

턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.

1. 1번 말이 이동하려는 칸이 1) 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 1번 말을 올려놓는다.

     - 1번 말의 위에 다른 말이 있는 경우에는 1번 말과 위에 있는 모든 말이 이동한다.
     - 예를 들어, 1, 2, 3로 쌓여있고, 이동하려는 칸에 4, 5가 있는 경우에는 1번 말이 이동한 후에는 4, 5, 1, 2, 3가 된다.

   2) 빨간색인 경우에는 이동한 후에 1번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.

     - 1, 2, 3 가 이동하고, 이동하려는 칸에 말이 없는 경우에는 3, 2, 1가 된다.
     - 1, 4, 6, 7가 이동하고, 이동하려는 칸에 말이 5, 3, 2로 있는 경우에는 5, 3, 2, 7, 6, 4, 1가 된다.

   3) 파란색인 경우에는 1번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다. 4) 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

다음은 크기가 4×4인 체스판 위에 말이 4개 있는 경우이다.

첫 번째 턴은 다음과 같이 진행된다.

두 번째 턴은 다음과 같이 진행된다.

체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때, 게임이 종료되는 턴의 번호를 반환하시오.

그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 반환한다.

입력 각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다. 말의 개수와 체스판의 정보, 현재 말의 위치와 방향을 주어진다. 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 인덱스, 이동 방향이다. 행과 열의 번호는 0부터 시작하고, 이동 방향은 0, 1, 2, 3 이고 0부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.

k = 4  # 말의 개수

chess_map = [
    [0, 0, 2, 0],
    [0, 0, 1, 0],
    [0, 0, 1, 2],
    [0, 2, 0, 0]
]
start_horse_location_and_directions = [
    [1, 0, 0],
    [2, 1, 2],
    [1, 1, 0],
    [3, 0, 1]
]
# 이 경우는 게임이 끝나지 않아 -1 을 반환해야 합니다!

K = 4  # 말의 개수

chess_map = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]
start_horse_location_and_directions = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 2, 0],
    [2, 2, 2]
]
# 이 경우는 2 을 반환해야 합니다!

문제를 읽어보고, 나이트가 체스룰대로 움직이지 않으니, 위에 작성한 N Queen 문제는 아니고, 그냥 복잡한 구현 문제로 보인다.

1. 일단 1000번을 Max로 두고, 충족하지 않으면 -1을 Return하도록 한다.
2. 움직임이 제한되는 구간인 벽과 파란색에 대한 처리를 한다. 갇힌 경우도 처리를 해준다.
3. 같은 좌표에 있는 말들 움직임을 stack으로 처리하고, 이후에 판의 색깔 흰색/빨강색에 따라서 처리한다.

정답 코드

k = 4  # 말의 개수

chess_map = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]
start_horse_location_and_directions = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 2, 0],
    [2, 2, 2]
]
# 이 경우는 게임이 끝나지 않아 -1 을 반환해야 합니다!
# 동 서 북 남
# →, ←, ↑, ↓
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]

MAX = 1000

def reverse_direction(d):
    if d == 0: return 1
    if d == 1: return 0
    if d == 2: return 3
    if d == 3: return 2
    return d


def get_game_over_turn_count(horse_count, game_map, horses):
    N = len(game_map)

    # 각 칸의 스택: 말 index(0-based) 리스트
    stacks = [[[] for _ in range(N)] for _ in range(N)]
    for idx, (r, c, _) in enumerate(horses):
        stacks[r][c].append(idx)

    def out(r, c):
        return r < 0 or r >= N or c < 0 or c >= N

    for turn in range(1, MAX + 1):
        for i in range(horse_count):
            r, c, d = horses[i]

            nr, nc = r + dr[d], c + dc[d]

            # 파랑/벽: 방향 반전 후 한 번 더 시도
            if out(nr, nc) or game_map[nr][nc] == 2:
                d = reverse_direction(d)
                horses[i][2] = d  # 방향만 갱신
                nr, nc = r + dr[d], c + dc[d]
                # 여전히 파랑/벽이면 이동하지 않음
                if out(nr, nc) or game_map[nr][nc] == 2:
                    continue

            # 현재 칸에서 i와 그 위의 말들을 떼기
            cur = stacks[r][c]
            pos = cur.index(i)
            moving = cur[pos:]  # i 포함 위의 덩어리
            stacks[r][c] = cur[:pos]  # 아래 남은 스택

            # 목적지 색 처리
            color = game_map[nr][nc]
            if color == 1:  # 빨강: 덩어리만 역순
                moving.reverse()
            # 흰(0)은 그대로, 파랑(2)은 위에서 걸러짐

            # 이동 반영 (좌표 갱신)
            for m in moving:
                horses[m][0], horses[m][1] = nr, nc
            stacks[nr][nc].extend(moving)

            # 종료 조건: 어느 칸이든 4개 이상
            if len(stacks[nr][nc]) >= 4:
                return turn

    return -1


print(get_game_over_turn_count(k, chess_map, start_horse_location_and_directions))  # 2가 반환 되어야합니다

start_horse_location_and_directions = [
    [0, 1, 0],
    [1, 1, 0],
    [0, 2, 0],
    [2, 2, 2]
]
print("정답 = 9 / 현재 풀이 값 = ", get_game_over_turn_count(k, chess_map, start_horse_location_and_directions))

start_horse_location_and_directions = [
    [0, 1, 0],
    [0, 1, 1],
    [0, 1, 0],
    [2, 1, 2]
]
print("정답 = 3 / 현재 풀이 값 = ", get_game_over_turn_count(k, chess_map, start_horse_location_and_directions))

내부적으로 어려운 개념보다는 복잡한 구현들이 많았고, Stack쪽 처리가 코드로 나오기까지 시간이 많이 걸렸다.

백준 정답 제출용

# 첫 줄 입력
n, k = map(int, input().split())

# 체스판 정보 입력
chess_map = [list(map(int, input().split())) for _ in range(n)]

# 말의 위치 및 방향 정보 입력 (★ 1-based -> 0-based로 변환)
horses = []
for _ in range(k):
    r, c, d = map(int, input().split())
    horses.append([r-1, c-1, d-1])  # ★ 포인트

dr = [0, 0, -1, 1]  # 0:→, 1:←, 2:↑, 3:↓
dc = [1, -1, 0, 0]

MAX = 1000

def reverse_direction(d):
    if d == 0: return 1
    if d == 1: return 0
    if d == 2: return 3
    if d == 3: return 2
    return d

def get_game_over_turn_count(horse_count, game_map, horses):
    N = len(game_map)

    # 각 칸의 스택: 말 index(0-based) 리스트
    stacks = [[[] for _ in range(N)] for _ in range(N)]
    for idx, (r, c, _) in enumerate(horses):
        stacks[r][c].append(idx)

    def out(r, c):
        return r < 0 or r >= N or c < 0 or c >= N

    for turn in range(1, MAX + 1):
        for i in range(horse_count):
            r, c, d = horses[i]

            nr, nc = r + dr[d], c + dc[d]

            # 파랑/벽: 방향 반전 후 한 번 더 시도
            if out(nr, nc) or game_map[nr][nc] == 2:
                d = reverse_direction(d)
                horses[i][2] = d  # 방향만 갱신
                nr, nc = r + dr[d], c + dc[d]
                # 여전히 파랑/벽이면 이동하지 않음
                if out(nr, nc) or game_map[nr][nc] == 2:
                    continue

            # 현재 칸에서 i와 그 위의 말들을 떼기
            cur = stacks[r][c]
            pos = cur.index(i)
            moving = cur[pos:]  # i 포함 위의 덩어리
            stacks[r][c] = cur[:pos]  # 아래 남은 스택

            # 목적지 색 처리
            color = game_map[nr][nc]
            if color == 1:  # 빨강: 덩어리만 역순
                moving.reverse()
            # 흰(0)은 그대로, 파랑(2)은 위에서 걸러짐

            # 이동 반영 (좌표 갱신)
            for m in moving:
                horses[m][0], horses[m][1] = nr, nc
            stacks[nr][nc].extend(moving)

            # 종료 조건: 어느 칸이든 4개 이상
            if len(stacks[nr][nc]) >= 4:
                return turn

    return -1

print(get_game_over_turn_count(k, chess_map, horses))

강의에서는 그냥 편의상 0부터 시작하는 좌표를 주었는데 백준에서는 아니어서 입력받을 떄 약간의 조정이 필요하다.

저번 문자열 압축에 이어 2020 카카오 블라인드 문제로 다시 돌아왔다.

상위 배너 또는 하위 링크를 통해 강의를 구매하시면, 블로그 작성자가 수익을 받을 수 있어요. 🤗 https://inf.run/Ce3jj

괄호 변환

프로그래머스 문제 링크

문제 설명 카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 콘은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.

용어의 정의 '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다. 그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다. 예를 들어, "(()))("와 같은 문자열은 균형잡힌 괄호 문자열 이지만 올바른 괄호 문자열은 아닙니다. 반면에 "(())()"와 같은 문자열은 균형잡힌 괄호 문자열 이면서 동시에 올바른 괄호 문자열 입니다.

'(' 와 ')' 로만 이루어진 문자열 w가 균형잡힌 괄호 문자열 이라면 다음과 같은 과정을 통해 올바른 괄호 문자열로 변환할 수 있습니다.

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 4-3. ')'를 다시 붙입니다. 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 4-5. 생성된 문자열을 반환합니다.

균형잡힌 괄호 문자열 p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 올바른 괄호 문자열로 변환한 결과를 반환하시오.

"(()())()"    # -> "(()())()"
")("        # -> "()"
"()))((()"    # -> "()(())()"

이 문제는 정말 하라는데로 해야 풀린다. Input, Output을 보고 예측하는 급한 성격, 또는 문제를 제대로 읽지 않는 사람들에게는 절대 풀리지 않는다. 답안을 완성하기 전에, 수도 없이 삽질하다가 남기고 싶은 한마디다.

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

이 파트를 구현해야 문제가 풀리고, "올바른 괄호 문자열"에 대해서도 구현해야한다.

"올바른 괄호 문자열은 3주차 올바른 괄호에서 이미 구현을 하였다.

def is_correct_parenthesis(string):
    answer = True
    stack = []

    for char in string:
        if char == '(':
            stack.append(char)

        elif char == ')':
            if stack and stack[-1] == '(':
                stack.pop()
                continue
            stack.append(char)

    if stack:
        answer = False

    return answer

그래서 주어진 괄호식들이 올바르면 그대로 넘기고 아니면 해결하는 function을 구현하면 된다.

아닐 경우에 쓸 것을 구현할 것을 써두고, 푸는 걸 추천한다.

from collections import deque

balanced_parenthesis_string = "()))((()"


def is_correct_parenthesis(string):  # 올바른 괄호인지 확인
    stack = []
    for s in string:
        if s == '(':
            stack.append(s)
        elif stack:
            stack.pop()
    return len(stack) == 0

'''
1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.
'''

def separate_to_u_v(string):  # u, v로 분리
    queue = deque(string)
    left, right = 0, 0
    u, v = "", ""

    while queue:  # 큐사용
        char = queue.popleft()
        u += char
        if char == '(':
            left += 1
        else:
            right += 1
        if left == right:  # 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 합니다. 즉, 여기서 괄 쌍이 더 생기면 안됩니다.
            break

    v = ''.join(list(queue))
    return u, v


def reverse_parenthesis(string):  # 뒤집기
    reversed_string = ""
    for char in string:
        if char == '(':
            reversed_string += ")"
        else:
            reversed_string += "("
    return reversed_string


def change_to_correct_parenthesis(string):
    if string == '':  # 1번
        return ''
    u, v = separate_to_u_v(string)  # 2번
    if is_correct_parenthesis(u):  # 3번
        return u + change_to_correct_parenthesis(v)
    else:  # 4번
        return '(' + change_to_correct_parenthesis(v) + ')' + reverse_parenthesis(u[1:-1])


def solution(string):
    if is_correct_parenthesis(string):
        return string
    else:
        return change_to_correct_parenthesis(string)


# print(solution(balanced_parenthesis_string))  # "()(())()"가 반환 되어야 합니다!

# print("정답 = (((()))) / 현재 풀이 값 = ", solution(")()()()("))
# print("정답 = ()()( / 현재 풀이 값 = ", solution("))()("))
# print("정답 = ((((()())))) / 현재 풀이 값 = ", solution(')()()()(())('))

카카오 1차 시험이 끝났고, 아직 결과는 나오지 않았지만, 2주뒤 일요일이 2차 시험이고, 계속 공부를 이어나가는 느낌으로 강의 끝까지 포스팅하려고 한다.

상위 배너 또는 하위 링크를 통해 강의를 구매하시면, 블로그 작성자가 수익을 받을 수 있어요. 🤗 https://inf.run/Ce3jj

카카오 기출문제는 프로그래머스에 모두 있으니 가서 풀어보면 된다.

문자열 압축

https://school.programmers.co.kr/learn/courses/30/lessons/60057?language=python3

Q. 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다.

최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.

간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 input이 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 string_compression 함수를 완성해주세요.

• 문자열의 길이는 1 이상 1,000 이하입니다.
• 문자열은 알파벳 소문자로만 이루어져 있습니다.

이 때, 문자열은 항상 제일 앞부터 정해진 길이만큼 잘라야 합니다. 입출력 예 #5 처럼 xababcdcdababcdcd 이 입력되어도, 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능합니다. 이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

문제 접근법

1. 처음부터 순서대로 자르기 때문에 비교군을 1칸 ~ 전체 string 길이 // 2칸까지 잘라서 탐색해서 비교해보면 된다. 전체 문자열에 반을 넘어가면, 압축에 의미가 없기에 딱 절반까지 탐색한다.

2. 저장해둔 비교군과 나오는 문자열이 서로 매칭이 안될 때 그 다음 비교할 문자열을 비교군으로 swap하고, 매칭된 문자열이 있었다면 "매칭됬었던 갯수 + string"으로 처리한다.

3. 마지막 루프에 도달할 때, 나머지 문자열 처리한다.

def solution(string):

    # 1칸 부터 n // 2 까지 탐색해봐야 한다.

    n = len(string)

    answer = n

    # 블록 크기 1 ~ n//2
    for size in range(1, n // 2 + 1):
        compressed = []
        prev = string[0:size]  # 첫 블록
        count = 1

        # 다음 블록부터 순회
        for i in range(size, n, size):
            cur = string[i:i + size]
            if cur == prev:
                count += 1
            else:
                # 이전 블록 기록
                if count > 1:
                    compressed.append(str(count))
                compressed.append(prev)
                # 현재 블록으로 교체
                prev = cur
                count = 1

        # 마지막 블록 반영
        if count > 1:
            compressed.append(str(count))
        compressed.append(prev)

        # 이번 size에서의 압축 길이 비교
        answer = min(answer, len(''.join(compressed)))

    return answer