삐에로의 지식창고

개요 앞 편은 아래로 내려가는 방향이었다. 페이지 테이블, TLB, 권한 비트, Copy-on-Write까지 갔다. 이번 편은 그 위에 올라서서 판단하는 쪽이다. 요청이 10,000개 들어오는 서버에 스레드를 10,000개 띄우면 무엇이 먼저 무너지는가 이 질문에 RAM이라고 답했다가 걸렸다. 그리고 걸린 지점이 계산 실수가 아니라 숫자의 종류를 잘못 읽은 것이었다. 8MB × 1,000 = 8GB라는 계산은 맞는데, 그 8GB가 RAM 8GB가 아니다. 이번 편은 그 구분에서 시작해서 동시성 모델, 스레드 하나가 죽으면 프로세스가 죽는 이유, 그리고 Unity가 워커 스레드의 API 호출을 막는 이... Read More

개요 구술 대비 복습을 계속하고 있다. 프로세스와 스레드는 이론 정리 - < 프로세스, 스레드, 데드락 >에서 정의를 적었고, 이론 정리 - < 데이터 레이스, 뮤텍스, 아토믹 >에서 Stack과 Heap의 소속을 거꾸로 잡고 있던 걸 고쳤다. 그런데 09-07 편은 무엇이 공유되는가까지였다. 표는 세웠는데, 그 공유와 분리를 실제로 만들어내는 게 무엇인지는 안 적어뒀다. 그래서 이번엔 같은 주제를 한 층 아래로 끌고 내려가봤다. 시작 질문은 이거다. 프로세스와 스레드는 각각 무엇의 단위인가 여기서 출발해 페이지 테이블, TLB, 권한 비트, Copy-on-Write까지 갔다. ... Read More

개요 연결 리스트 단원을 끝내고 후속 실습 문제 두 개를 풀었다. 당근 선별기와 주차장. 둘 다 파이썬으로 먼저 설계하고 돌려본 뒤에 C++로 다시 짰는데, 이번 편은 파이썬 쪽과 단원에서 정리한 개념까지다. C++로 옮기면서 겪은 것 — 출력이 아예 안 나와서 30분을 태운 이야기 — 는 C++ - < 3 >에 따로 적었다. 먼저 단원 내용부터 정리하고 문제로 간다. 연결 리스트 — 배열 list와 뭐가 다른가 파이썬 list는 이름은 리스트인데 안은 배열이다. 원소가 메모리에 붙어 있어서 arr[3]을 바로 집을 수 있는 대신, 중간에 끼워 넣거나 빼면 뒤쪽 원소를 전부 밀어야 한다. ... Read More

개요 연결 리스트 단원 후속 실습 두 문제를 파이썬으로 풀고 나서, 같은 문제를 C++로 최적화한 과정이다. 연결 리스트 개념 정리와 파이썬 쪽 설계는 Python - < 7 >에 있다. 로직은 이미 파이썬으로 맞춰놓은 상태였으니 옮기기만 하면 될 줄 알았다. 그런데 이번 학습 시간의 절반은 컴파일도 되고 실행도 되는데 화면에 아무것도 안 나오던 시간이다. 당근 — 첫 코드가 세 군데 어긋나 있었다 문제부터. 당근을 수확한 순서대로 크기를 적어둔 기록이 주어진다. 이 기록에서 연속으로 크기가 커지는 구간 중 가장 긴 것의 당근 개수를 구한다. 커지는 구간이 하나도 없으면 답은 1이다. ... Read More

개요 오늘 배운 완전탐색과 부분집합, 그중에서도 부분집합을 만드는 세 가지 방법( 반복문·재귀·바이너리 카운팅 )과 가지치기, 그리고 비트 연산까지 적은 기록이다. 앞서 풀던 SWEA 2115. 벌꿀 채취가 정확히 이 부분집합 문제였다. 일꾼이 맡은 M칸 중 어느 칸을 채취할지 고르는 부분이 부분집합 열거인데, 거기서 막혀 있었다. 진행 방식은 강사 역할의 AI가 먼저 질문하고 내가 답한 뒤 피드백을 받는 식이었다. 틀린 답도 같이 적어둔다. 맞은 것만 남기면 왜 그쪽으로 갔는지가 사라진다. 같은 문제를 C++로 짜면서 임시 객체에 막힌 이야기는 C++ - < 2 >에 따로 적었다. 탑을 쌓... Read More

개요 SWEA 2115. 벌꿀 채취를 C++로 직접 짰다. 같은 문제를 파이썬으로 정리하고 이론 쪽을 붙인 건 Python - < 6 >에 있다. 문제부터. N×N 격자의 각 칸에 꿀이 든 벌통이 하나씩 있다. 일꾼 두 명을 보내는데, 각 일꾼은 한 행에서 가로로 붙어 있는 M칸을 맡는다. 두 일꾼이 맡은 칸은 겹치면 안 된다. 맡은 M칸을 전부 채취하지는 못하고, 통 용량이 C라 꿀 양의 합이 C 이하가 되도록 골라 담는다. 수익은 채취한 칸의 제곱합이다. 두 일꾼 수익의 합을 최대로 만든다. 정할 게 두 겹이다. 구간 두 개를 어디에 놓을지( 겹치지 않게 ), 그리고 각 구간 안에서 어느 칸을 ... Read More

개요 앞의 세 편(복잡도, iterator와 해시, 탐색과 그래프)은 자료구조를 하나씩 봤다. 이번 편은 방향이 다르다. 몬스터를 100마리 생성했더니 FPS가 급락한다. 무엇부터 의심하겠는가? 자료구조를 고르는 문제가 아니라 순서를 말할 수 있느냐를 보는 질문이다. 그리고 이 순서는 지난주에 유니티 프로젝트에서 이미 밟아본 것이기도 하다. 14편과 16편에서 좀비를 잔뜩 띄워놓고 가설을 세우고 재고 기각하기를 이틀 반복했는데, 그때는 순서를 의식하지 않고 손에 잡히는 대로 했다. 그래서 이번 편은 앞의 세 편과 반대다. 앞에서는 알고 있다고 생각한 게 계속 어긋났는데, 여기서는 대체로 답이 나왔고 ... Read More

개요 앞 편에서 unordered_map이 평균 O(1)을 받는 대신 순서를 포기한다는 데까지 왔다. 이번 편은 순서를 지키면서 O(log N)을 받는 쪽이다. 그리고 마지막에 그래프 탐색이 나오는데, 여기서 이론 정리 - < Big-O, 정렬, DFS/BFS >를 또 열게 됐다. 첫 편에서 Big-O 절의 문장 하나를 고쳤는데, 같은 글의 DFS/BFS 절에도 손볼 데가 두 군데 있었다. 이번 편은 앞의 두 편과 결이 조금 다르다. 앞에서는 모르던 이름이 붙는 쪽이 많았는데, 여기는 대부분 이미 알고 문제도 풀어본 것들이었다. 그런데 설명해보라니까 절차만 나오고 이유가 안 나왔다. 절차는 ... Read More