삐에로의 지식창고

개요 오늘 배운 완전탐색과 부분집합, 그중에서도 부분집합을 만드는 세 가지 방법( 반복문·재귀·바이너리 카운팅 )과 가지치기, 그리고 비트 연산까지 적은 기록이다. 앞서 풀던 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

개요 앞 편 5번에서 재할당이 일어나면 기존 원소의 수명이 끝난다는 데까지 왔다. 그럼 그 원소를 가리키고 있던 iterator는 어떻게 되는가 — 이번 편이 그 자리다. 여기서 두 번 걸렸다. 하나는 무효화의 기준을 주소로 보고 있었다는 것이고, 다른 하나는 iterator를 포인터의 다른 이름으로 보고 있었다는 것이다. 설명해보라고 해서 답했다가 둘 다 어긋났는데, 쓰다 보니 두 오해가 같은 뿌리였다. 후반부는 unordered_map 쪽이다. 여기서도 “key를 해시해서 값에 바로 접근한다”는 그림을 들고 있었는데, 한 단계가 빠져 있었다. 주소로 설명하면 반쯤만 맞는 것 — iterator도, ... Read More

개요 이론 정리 - < SOLID 다섯 원칙 > 마지막에 다음은 자료구조 쪽이고 첫 질문은 이거라고 적어뒀다. std::vector와 std::list 둘 다 순회가 O(N)인데 왜 실제로는 vector가 훨씬 빠른 경우가 많은가 넥토리얼 대비로 CS를 훑는 중인데, 지난 나흘은 메모리와 OOP 쪽이었고 오늘부터 자료구조·알고리즘으로 넘어간다. 깊이 파기보다 범위를 넓히는 쪽을 골랐다. 곧 50분짜리 모의 면접을 한 번 보기로 해서, 한 주제를 오래 붙잡는 것보다 빈 칸을 먼저 없애는 게 낫다고 봤다. 방식은 AI에게 설명하고 틀린 데를 짚어달라고 하는 식으로 갔다. 눈으로 읽으면 다 아는... Read More

개요 이론 정리 - < 상속과 다형성, 가상 함수 > 마지막에 다음은 SOLID라고 적어뒀다. 그 다음 편이다. 거기서는 “계약을 안 지킨 클래스로는 객체를 못 만든다”까지 왔었다. 순수 가상 함수를 안 채우면 추상 클래스로 남는다는 이야기였다. 그래서 다음은 계약을 지킨 척하는 구현을 볼 차례라고 적어뒀는데, 그게 이번 편의 L 자리다. 솔직히 SOLID는 약자 외우기가 제일 걸렸다. S, O, L, I, D 다섯 글자에 원칙 이름을 붙이는 것까지는 되는데, 그게 코드 앞에서 무슨 쓸모인지가 안 잡혔다. 그래서 이번에는 정의를 외우는 대신 각 글자를 질문 하나로 바꿔서 갔다. 변경이 생겼을... Read More

개요 이론 정리 - < const, 레퍼런스, 이동 의미론 > 마지막에 다음은 virtual, override, 가상 소멸자, 상속과 다형성 쪽이라고 적어뒀다. 그 다음 편이다. 상속은 예전에 C# - <2>에서 한 번 정리했고, 지난주에는 유니티 프로젝트에서 SpawnerBase 상속 계층을 직접 세워봤다. 그래서 이번 편은 아는 걸 C++ 문법으로 옮기기만 하면 되는 회차라고 생각하고 들어갔다. 결과부터 적으면, 옮겨진 건 절반이었다. 나머지 절반은 답은 맞는데 이유가 틀린 것들이었다. 결과는 맞고 이유가 틀린 것 — virtual 없는 호출에서 부모 함수가 불린다는 건 맞췄는... Read More