웨일의 블로그 웨일의 블로그

책: Database Internals 목차 Part 1 Storage Engines 1. Introduction and Overview DBMS Architecture Memory-Based vs Disk-Based DBMS Durability in Memory-Based Stores Column-oriented vs Row-oriented DBMS Row-Oriented Data Layout Column-Oriented Data Layout Distinctions and Optimizations Wide Column Stores Data Files and Index Files Data FIles Index Files Primary Index as an Indirection Buffering, Immu..

문제 - 양과 늑대 문제링크 문제 설명 이렇게 생긴 이진트리가 주어집니다. 0번 루트노드부터 탐색을 시작하는데, 노드에 양이 있으면 양 누적 카운트를 + 1 해주고, 늑대가 있으면 늑대 누적 카운트를 + 1 해줍니다. 그런데 [양 누적 1 해서 일단 왼쪽 양을 구한 후, 1->0->8->7->8->9 이렇게 이동해서 우측 서브트리의 양까지 다 구할 수 있습니다. 지금까지의 카운트는 양:4마리, 늑대:1마리이므로, 4번, 6번 늑대까지 방문해도 4대3으로 아직 괜찮습니다. 그래서 5번 양까지 구할 수 있습니다. 제한사항 트리의 노드 개수는 최대 17입니다. 풀이 과정 일단, 어떻게든 트리를 순회하면서 양과 늑대를 카운트해서 최대로 구할 수 있는 양을 구해야 합니다. 그리고, 한번 방문한 노드를 다시 방문할..

문제 - 타겟 넘버 문제링크 문제 설명 이렇게 numbers와 target이 입력으로 주어지면, numbers의 모든 숫자들을 각각 더하든지 빼든지 해서 target값을 만들어내는 경우의 수를 구하는 문제입니다. 첫번째 예시 입력에 대해 다음과 같은 경우의 수들이 있습니다. 이런식으로 각 숫자 앞에 +를 붙일건지 -를 붙일건지 선택해서 다 계산한 결과가 target이면 됩니다. 풀이 과정 각 숫자에는 부호가 할당되어야 합니다. 그리고 각 숫자마다 붙는 부호는 다른 숫자들과 독립적입니다. 이러면 각 숫자마다 +-의 두가지 경우가 있습니다. 모든 숫자에 대해 +-를 붙이는 경우의 수를 구하는 데 좋은 알고리즘은 DFS가 있습니다. """ 각 숫자에 대해 -, + 할당 dfs(order, val) """ de..

머지소트는 분할 정복 카테고리에 속합니다. 숫자로 이루어진 수열이 반씩 나눠지며 하나만 남게 되는 과정이 분할이고, 각 파티션끼리 합쳐지는 과정이 정복입니다. 머지 소트의 시간복잡도는 O(NlogN)이라고 잘 알려져 있습니다. 왜 O(NlogN)일까요? 우선, 분할과정을 살펴봅시다. 단순히 생각해서 7개의 숫자로 이루어진 수열에서 숫자를 하나씩 떼어내려면 총 6번을 하나씩 떼어내야 합니다. 7보다 1만큼 작은 이유는 마지막에 숫자 두개만 남았을 때 한번만 떼어내면 되기 때문입니다. 숫자가 N개 있으면 N-1번 떼어내야 합니다. 따라서 N에 대해 선형적이므로 분할 과정은 O(N)입니다. 이제 정복 과정을 살펴봅시다. 정복은 같은 레벨의 파티션들을 쌍을 이룬 후, 정렬하며 하나의 파티션으로 병합하는 과정입니..

오늘 배운 점 갑자기 떠오른 아이디어가 실마리가 될 수 있습니다. 빠를거라고 예상한 풀이가 예상외로 느릴 수 있습니다. 문제 - 디펜스 게임 문제링크 문제 설명 병사 n명으로 enemy([n1, n2, n3,...])을 상대해야 합니다. 1라운드에는 n1, 2라운드에는 n2... 이런식으로 각 라운드마다 상대해야 하는 적의 수가 enemy에 담겨 있습니다. 그리고 병사와 적은 1대1 교환비로 적을 처리할 수 있습니다. k개의 무적권이 주어지는데, 무적권 1개를 사용하면 해당 라운드는 병사를 사용하지 않고 다음 라운드로 넘어갈 수 있습니다. 이때, 승리할 수 있는 최대 라운드를 구하면 됩니다. 제약 조건 n이 10억인 점은 문제가 되지 않지만 enemy가 100만이기 때문에 O(N)이나 O(NlogN) 과..

문제 - 등산코스 정하기 문제링크문제 설명산이 있고 산에는 지점들이 있습니다. 지점은 여러 개의 출발지와 여러 개의 정상, 그리고 일반 지점들이 있습니다. 출발지에서 시작해서 정상을 찍고 다시 원래 출발지로 돌아오는 경로가 있을 때, 해당 경로는 시작 출발지와 끝 출발지는 같고, 중간에 다른 출발지를 거치지 않고, 정상은 무조건 한번만 거쳐야 합니다. 이때, 위 조건을 만족하는 모든 경로 각각에서 각 지점을 건너는데 걸리는 시간 중 가장 긴 시간이 있을텐데 이를 intensity라 하고, 모든 경로를 통틀어 최소 intensity를 구하는 문제입니다. 풀이 과정처음에는 같은 지점을 여러번 반복해서 방문할 수 있으므로, 비트마스킹을 이용헤서 중복 경로 체크를 해야 하는 줄 알았습니다. 하지만 이전에 방문한..

문제 - 무인도 여행 문제링크 문제 설명 2차원 격자 maps가 주어지고, 격자는 바다를 의미하는 'X'와 1~9 사이의 숫자로 이루어져 있습니다. 해당 칸이 숫자라면 땅을 의미하고, 상하좌우로 서로 연결된 땅은 하나의 섬입니다. maps 내의 모든 섬에 방문할 때, 각 섬에 적혀있는 모든 숫자를 다 더한 값을 담아 반환하면 됩니다. 풀이 과정 일반적인 BFS 섬 찾기 문제입니다. maps를 2중 for 문 순회하며 섬을 찾아 마킹하며 숫자를 더한 후 BFS가 끝나면 더한 값을 저장해 놓다가 모든 순회가 끝나면 반환하면 됩니다. from collections import deque def solution(maps): answer = [] n = len(maps) m = len(maps[0]) dx = [..

문제 - 택배상자 문제링크 오늘 배운 점스택의 활용도는 무궁무진하고 어렵습니다. 획기적인 풀이가 답이 될 수 있는 이유를 알고 넘어가는건 재밌습니다. 문제 설명메인 컨베이어 벨트에 1부터 n의 번호가 달린 상자가 n,n-1,...3,2,1 이런식으로 정렬되어 왼쪽에서 오른쪽으로 이동하고 있습니다. 그리고, 택배원은 자기가 생각한 순서대로 상자를 트럭에 실어야 합니다. 택배원은 보조 컨베이어벨트에 상자를 차곡차곡 옮길 수도 있습니다. 보조 컨베이어벨트는 스택같은 LIFO 구조라고 보면 됩니다. 이때 택배원은 최대 몇개의 상자를 트럭에 실을 수 있는지 구하는 문제입니다. 풀이 과정세 가지 경우로 나누어 풀이했습니다. 1. 메인 컨베이어 벨트의 맨 앞 상자가 자신이 처리해야 하는 상자와 같을 때 2. 보조 컨..