Jungle
크래프톤 정글 합격 후기
입학 시험부터 면접까지, 지원하며 겪은 것과 앞으로의 목표
깊이 몰입하고,
함께 성장하는 시간.
알고리즘부터 시스템까지. 정글에서 공부한 것들을 모았습니다.
WEEK 00
주차별 기록 ↗WEEK 01
주차별 기록 ↗
Jungle
1주차 - 정글 에세이
정글에 입소하며 적어본 과거, 목표, 자세, 그리고 되고 싶은 모습에 대한 짧은 에세이.
Jungle
1주차 - 헬스장 현황 대시보드 JUMGLE_GYM
2박 3일 팀 프로젝트에서 만든 것과, 구조를 잡으며 부딪힌 문제들
WEEK 02
주차별 기록 ↗
Operating System
2주차 - 버퍼 오버플로우, 가상 메모리 관점에서 보기
C에는 배열 경계 검사가 없다는 사실에서 출발해서, 스택과 힙에서 버퍼 오버플로우가 실제로 어떤 메모리를 덮어쓰는지 가상 메모리 구조로 정리.
Garbage Collection
2주차 - Unity가 쓰는 보수적 GC, 포인터인지 정수인지 어떻게 구분할까
타입 정보가 없는 C/C++ 환경에서 BDWGC가 스택과 힙을 워드 단위로 훑어 포인터로 의심되는 값을 마킹하는 방식과, 그로 인해 생기는 오탐 문제를 정리.
Garbage Collection
2주차 - Java의 GC는 왜 세대로 나뉘어 있을까
Eden/S0/S1/Old로 나뉜 Java의 세대별 힙 구조와 Minor/Full GC의 동작, identity hash code로 객체 동일성을 보증하는 방식, TLAB 덕분에 new()가 malloc()보다 빠른 이유까지.
Data Structure & Algorithm
2주차 - Mark & Sweep, GC는 도달 가능성을 어떻게 판단할까
Mark & Sweep 알고리즘이 루트에서 시작해 도달 가능한 객체를 표시하고 나머지를 회수하는 원리와, 루트가 될 수 있는 세 부류를 정리.
Python
2주차 - 파이썬은 Call by Value도 Reference도 아니다
재할당과 객체 수정(mutation)을 구분해서, 파이썬의 인자 전달 방식(Call by Object Reference)이 실제로 어떻게 동작하는지 정리.
Garbage Collection
2주차 - 파이썬 GC는 어떻게 작동할까
참조 카운팅이 주력이고 추적 GC가 보조인 파이썬 GC 구조를, CSAPP의 가비지 컬렉터 정의부터 순환 참조와 세대별 수집까지 정리.
Python
2주차 - 파이썬은 상속 없이도 서브클래스 관계가 된다
super()는 부모가 아니라 MRO상 다음 클래스를 가리킨다는 것부터, ABCMeta의 __subclasshook__과 register()로 상속 없이 서브클래스 판정이 이뤄지는 원리까지.
WEEK 03
주차별 기록 ↗
Data Structure & Algorithm
3주차 - 재귀로 짜는 이진 트리 순회, 그리고 BST가 성능을 보장하는 이유
전위/중위/후위 순회를 재귀로 구현하며 결과 배열을 함수 밖에 두는 대신 중첩 함수로 감싸는 방법부터, 이진 트리 구조 자체는 탐색 성능을 보장하지 않는다는 것, 균형이 무너지면 O(log n)이 O(n)이 되는 이유, 캐시 지역성 때문에 DB가 이진 트리 대신 B+트리를 쓰는 이유까지.
Operating System
3주차 - 리눅스 커널이 쓰는 버디 시스템, 2의 거듭제곱으로만 메모리를 관리하는 이유
seglist의 크기 클래스에 물리적 제약을 더한 버디 시스템 — 반으로 쪼개고, XOR 한 번으로 O(1)에 짝을 찾아 병합하고, 그 대가로 최대 50%까지 내부 단편화를 감수하는 구조를 seglist와 비교하며 정리.
Data Structure & Algorithm
3주차 - DP는 재귀가 반복하는 일을 기억해두는 것, 피보나치와 계단 오르기로 확인
재귀가 같은 하위 문제를 계속 반복 계산할 때 memo로 기억해두는 하향식(탑다운) DP와, 밑바닥 값부터 채워 올라가는 상향식(바텀업) DP를 피보나치 수열과 계단 오르기 문제로 각각 구현.
Data Structure & Algorithm
3주차 - 그래프 탐색, BFS와 DFS를 직접 구현하며 비교
인접 리스트로 무방향/방향 그래프를 만드는 것부터, Queue로 너비 우선 탐색하는 BFS와 재귀로 깊이 우선 탐색하는 DFS를 각각 구현하고 장단점을 비교. 시간 복잡도는 둘 다 O(V+E).
Data Structure & Algorithm
3주차 - Greedy는 매 순간의 최선이 전체 최선이 되는 상황, 거스름돈과 회의실 배정으로 확인
매번 가장 큰 동전을 고르는 거스름돈 문제와, 종료 시간이 가장 빠른 회의부터 고르는 회의실 배정 문제로 그리디 알고리즘이 '순간의 최선'을 반복하는 원리를 확인.
Computer Architecture
3주차 - HDD는 왜 느리고 SSD는 왜 빠를까
HDD는 기계적으로, SSD는 반도체로 동작한다는 차이에서 출발해서 Platter/Track/Sector 구조와 NAND Page/Block 구조, Wear Leveling까지 정리.
Data Structure & Algorithm
3주차 - LCS(최장 공통 부분수열)를 DP 테이블로 구하기
두 문자열을 각각 행과 열에 두고, 같으면 대각선 위에 1을 더하고 다르면 위/왼쪽 중 최댓값을 가져오는 방식으로 LCS 길이를 채워나가는 DP 테이블 구현.
Operating System
3주차 - 가용 블록을 어떻게 관리할까: Implicit / Explicit / Segregated Free List
동적 메모리 할당기가 가용 블록을 관리하는 세 가지 방식을 검색 범위가 좁아지는 순서로 정리 — 크기 필드로 유추하는 implicit부터, pred/succ 포인터로 연결하는 explicit, 크기 클래스별로 리스트를 쪼개는 seglist까지.
C & Compiler
3주차 - Pointer Aliasing 때문에 컴파일러가 최적화를 포기하는 순간
포인터 두 개가 같은 메모리를 가리킬 수 있다는 가능성 하나가 어떻게 레지스터 캐싱, 명령어 재배치, SIMD 벡터화까지 막는지, 그리고 지역 변수와 restrict가 그 가능성을 어떻게 없애는지 정리.
Data Structure & Algorithm
3주차 - 트리가 한쪽으로 쏠리는 것을 막는 균형 이진 트리, RB트리
BST가 데이터 쏠림으로 O(n)까지 느려질 수 있다는 문제에서 출발해서, RB트리의 색 규칙과 Black Height, 그리고 Rotation·Recoloring으로 Double Red를 복구하는 과정을 정리.
Data Structure & Algorithm
3주차 - 위상 정렬, 순서 관계와 위상이 같은 개념인 이유
위상 수학의 '위상'이 순서 관계와 일대일 대응한다는 것에서 출발해서, DAG의 모든 간선 (u,v)에서 u가 v보다 앞에 오도록 정렬하는 위상 정렬을 구현하고 장단점을 정리.
Computer Architecture
3주차 - 음수는 왜 2의 보수로 표현할까
1의 보수는 0이 2개 생긴다는 한계에서 출발해서, 2의 보수가 왜 덧셈 회로 하나로 뺄셈까지 처리하는지, 그리고 carry를 버려도 되는 이유를 Modulo 연산 관점으로 정리.
Graphics
3주차 - JPEG, PNG, GIF는 왜 다르고, 손실은 어디서 생길까
JPEG/PNG/GIF 세 포맷의 장단점을 정리하고, 손실은 부호화가 아니라 색상 양자화 단계에서 생긴다는 것부터 색 밴딩·디더링·하이라이트 클리핑까지.
WEEK 04
주차별 기록 ↗
C & Compiler
4주차 - 프로시저의 스택 할당과 지역 변수의 레지스터 승격
프로시저가 별도의 스택 공간을 할당하지 않는 경우와 GCC 최적화 수준에 따른 지역 변수의 저장 위치를 살펴보고, red zone과 레지스터 승격을 정리.
WEEK 05
주차별 기록 ↗
Operating System
5주차 - 스레싱(Thrashing)이란
가상 메모리에서 페이지 교체가 실제 작업보다 많아지는 이유를 LRU 예시로 살펴보고, 워킹 셋 모델과 CPU 사용량만으로 시스템을 판단할 때의 한계를 정리했다.
WEEK 06
주차별 기록 ↗
Operating System
Week 6 Malloc Lab의 Place 함수 개선
Place 함수의 블록 배치 방향을 바꿔 91점에서 94점으로 개선한 과정과 임계값 최적화가 Util 향상으로 이어지지 않는 이유.
Operating System
CSAPP 9.10 - 가비지 컬렉션과 보수적 Mark & Sweep
도달 가능성으로 가비지를 구분하는 원리부터 Mark & Sweep, C의 포인터 판별 한계와 블록 검색용 균형 트리까지 한 흐름으로 정리했다.
Operating System
CSAPP 9.11 - C 프로그램에서 만나는 메모리 버그 10가지
잘못된 역참조, 초기화 누락, 경계 초과, 포인터 연산, 수명과 해제 문제까지 메모리 버그의 원인과 증상이 멀어지는 이유를 정리했다.
Operating System
CSAPP 9.9.11 - 경계 태그로 인접한 가용 블록 합치기
헤더와 푸터로 앞뒤 블록을 찾는 방법, 가용 블록을 연결하는 네 가지 경우, 푸터를 생략할 때 필요한 정보를 정리했다.
Operating System
CSAPP 9.9.12 - 간단한 동적 메모리 할당기 구현 읽기
memlib의 가상 힙부터 블록 매크로, mm_init, extend_heap, coalesce, mm_malloc까지 묵시적 가용 리스트 할당기의 흐름을 따라갔다.
Operating System
CSAPP 9.9.13 - 명시적 가용 리스트와 pred·succ 포인터
가용 블록만 연결해 탐색 범위를 줄이는 원리와 LIFO·주소 순서 정책, 포인터 두 개가 최소 블록 크기에 미치는 영향을 정리했다.
Operating System
CSAPP 9.9.14 - 분리 가용 리스트와 버디 시스템
크기 클래스별로 가용 블록을 관리하는 simple segregated storage, segregated fit, 버디 시스템의 할당·반환 과정을 비교했다.
WEEK 07
주차별 기록 ↗
Git
Github PR Template 설정
GitHub PR 템플릿을 등록하고 Pintos 팀 프로젝트에 사용할 공통 양식을 설정하는 방법.