MongoDB는여러 유형의 인덱스를 가지고 있다. 5.3부터는 Clutstered Index도 지원한다. Clustered Index의 장점 중 하나인 랜덤 액세스 없이 레코드를 읽는 기능은 빠른 range scan 속도를 자랑한다. 이외에도 다양한 인덱스가 존재한다. 참고: https://www.mongodb.com/docs/manual/indexes/ 그 중에서 MongoDB는 기본적으로 B-Tree를 기본 인덱스 구조로 지향한다. B-Tree의 인덱스 구조가 다른 인덱스의 구조에 비해 다음과 같은 장점이 있다. 1. 각 리프 노드가 동일한 깊이에 있기 때문에 균등한 응답속도를 보장한다. 하나의 컬렉션 내의 도큐먼트가 3~4개의 I/O 이상으로 떨어져 있지 않다. 2. B-Tree는 깊이가 최대 4개..

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 매우매우 유용한 문제였다. 여기서 관건은 물고기의 정보를 어떻게 관리하고, 어떻게 좌우로, 상하로 반복적으로 움직이게 하느냐가 관건이었다. 우선 매번 배열에 물고기의 정보를 저장하고 옮기기엔 불편하다. 그래서 물고기마다 번호를 매겨서 별도의 벡터에 물고기의 정보를 저장해두고, 인덱스로 시간복잡도는 $O(1)$로 정보를 바로 파악할 수 있게 했다. 그리고 2차원 배열에는 살아있는..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 이번에도 구현 문제인데, 문제 자체가 어려운 변수들을 많이 제거한 상태로 출제되었다. 처음에 공기청정기가 위아래 간격이 최소 2칸이 된다는 점을 제대로 안 읽어서 헛발질 할 뻔했다...;; 그렇게 전제조건이 깔리면서 일반적인 경우의 수만 풀어내면 된다. 이러한 구현 문제는 실수를 미연에 방지하는 것이 중요하기 때문에 함수를 최대한 패턴화해서 쪼개는 게 중요하다. 미세먼지의 확산 공기청정기의 위쪽..

https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 앞서 풀었던 주사위 문제와 구조 자체는 비슷하다. 그러나 조금 더 살이 덧붙여져서 이 점까지 고려해야 한다. 예를 들면 더이상 해당 방향으로 진입이 불가능하면 방향을 뒤집거나, 추가적으로 DFS 혹은 BFS를 써서 탐색을 해서 추가점수를 고려해야 한다. 궁극적으로 삼성 SW 역량 테스트를 준비하기 위해 이 문제를 푸는 것이기 때문에, 이에 맞추어 입력을 편하게 받는 방법을 학습했..

https://www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net 무려 이틀에 걸쳐 푼 문제이다. 쌩구현을 해야했는데, 나름 쉽게 풀려면 입체적인 큐브를 상상하면서 규칙을 생성해야 한다. 큐브를 한 번 돌리면 배열에는 크게 2가지 변화가 생긴다. 돌아가는 해당 면의 위치 변경 인접한 면들의 회전 그래서 이를 나누어서 큐브에 반영해준다. 큐브는 정육면체이므로 6개의 배열에 3 by 3 2차원 배열을 넣어 각 방향마다 값들을 옮겨준다. 만약 같은 면을 돌리되 방향만 ..

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 문제의 구현은 생각보다 간단하지만, 시간 초과가 계속 발생해서 문제를 조금 더 효율적으로 풀도록 노력해야 하는 문제이다. 다행히 코드 디자인을 수정하기에 용이하게 해둔 덕분에 수정이 어렵지는 않았다. 여기서 시간이 많이 소요될 수 있는 부분은 다음과 같다. 죽은 나무를 걸러내는 작업 어린 나무부터 정렬하는 작업 문제 질문 게시판을 보면 deque를 쓰는 경우가 많았으나, 나는 이 ..