1. 화성학을 왜 배우는가?화성학을 알면 곡의 구조를 예측할 수 있음처음 듣는 곡도 코드나 악보를 보면 사용할 수 있는 음을 어느 정도 예상할 수 있음결과적으로 타브악보를 그대로 따라 치는 의존도를 줄이고, 귀로 듣고 바로 연주하는 능력을 키울 수 있음 2. 장(Major)와 단(Minor)의 차이C → E = 4반음 → 장3도 (Major)C → E♭ = 3반음 → 단3도 (MInor)즉 메이저는 마이너보다 3음이 반음 낮음메이저마이너C - E - GC - E♭ - G밝음어두움장3도 (3-4, 7-8)단3도 (2-3, 6-7) 3. 코드 구성음C (Major)C E G1 3 5Cm (Minor)C Eb G1 ♭3 5C7C E G Bb1 3 5 ♭7Cmaj7 (Seventh Major)C E G B1 3..

1. 개요순서가 정해져 있는 작업을 차례대로 나열하는 알고리즘위상 정렬은 반드시 방향성이 있고 사이클이 없는 그래프인 DAG(Directed Acyclic Graph)에서만 수행 가능방향성(Directed): 작업의 선후 관계(화살표)가 명확해야 함비순환성(Acyclic): 사이클(순환)이 없어야 함 2. 작동 원리 (진입차수 기준)위상 정렬을 구현할 때는 진입차수(Indegree)라는 개념을 사용진입차수란 나에게 들어오는 화살표의 개수(즉, 내가 시작하기 전에 먼저 끝내야 하는 선행 작업의 개수)를 의미알고리즘 단계그래프의 모든 정점의 진입차수를 계산진입차수가 0인 정점(선행 작업이 없어 바로 시작할 수 있는 정점)을 큐(Queue)에 모두 넣음큐가 빌 때까지 다음 과정을 반복큐에서 정점을 꺼내 정렬 ..

1. 개요가중치 그래프에서 모든 정점을 포함하면서, 간선들의 가중치 합이 최소가 되는 트리 형태의 서브그래프를 의미사이클 미존재: 트리 구조이므로 정점이 V개일 때 간선의 수는 반드시 V - 1개가 되며 순환하는 경로 존재하지 않음연결성: 그래프의 모든 정점이 어떻게든 서로 연결되어 있어야 함최소 비용: 가능한 다양한 신장 트리(Spanning Tree) 중에서 간선 가중치의 총합이 가장 작음 2. 대표적인 알고리즘MST를 구하는 알고리즘은 크게 두 가지가 있으며, 둘 다 그리디(Greedy, 탐욕) 알고리즘을 기반으로 작동크루스칼 알고리즘 (Kruskal's Algorithm)간선(Edge)을 중심으로 MST를 찾아나가는 방식.모든 간선을 가중치 기준으로 오름차순 정렬가중치가 가장 낮은 간선부터 하나씩..

1. KD 트리의 핵심 원리2차원, 3차원, 혹은 그 이상의 다차원 공간에 있는 포인트들을 효율적으로 분할하고 탐색하기 위해 설계된 이진 탐색 트리KD 트리는 각 레벨마다 번갈아가며 다른 축(Dimension)을 기준으로 데이터를 분할예를 들어, 2차원 좌표 (x, y$ 데이터들을 KD 트리에 삽입한다고 가정하면루트 노드 (레벨 0): x축을 기준으로 정렬한 뒤, 중간값(Median)을 기준으로 공간을 왼쪽, 오른쪽으로 반으로 나눔자식 노드 (레벨 1): 이번에는 y축을 기준으로 정렬한 뒤, 중간값을 기준으로 위, 아래로 반을 나눔손자 노드 (레벨 2): 다시 x축을 기준으로 나눔이 과정을 데이터가 하나씩 남을 때까지 번갈아가며 반복데이터 셋: A(2,3), B(5,4), C(9,6), D(4,7), E..

1. 개요데이터베이스와 파일 시스템에서 가장 널리 사용되는 대표적인 균형 트리(Balanced Tree) 자료구조방대한 양의 데이터를 효율적으로 저장하고 검색하기 위해 설계일반적인 이진 트리(Binary Tree)는 하나의 노드에 하나의 데이터만 가질 수 있고, 자식 노드를 최대 2개까지만 가질 수 있음데이터가 많아지면 트리의 깊이(Height)가 너무 깊어져서 데이터를 찾을 때 내려가야 하는 단계가 많아짐데이터베이스처럼 데이터가 외장 메모리에 저장되어 있는 경우, 디스크에서 데이터를 읽어오는 속도는 RAM보다 훨씬 느림즉, 핵심은 트리의 높이를 최대한 낮추기 위해 자식 노드의 수도 여러 개로 늘리는 방식 2. B 트리의 주요 특징다원 트리 (Multi-way Tree): 자식 노드의 개수가 2개 이상이..

1. AVL 트리의 핵심 - 균형 인수 (Balance Factor)일반 이진 탐색 트리(BST)가 데이터 삽입 순서에 따라 한쪽으로 치우쳐 성능이 떨어지는 문제를 해결하기 위해 고안AVL 트리는 트리의 균형이 깨졌는지 판단하기 위해 균형 인수(BF, Balance Factor)라는 개념을 사용BF = (왼쪽 서브트리의 높이) - (오른쪽 서브트리의 높이)AVL 트리는 모든 노드의 균형 인수가 -1, 0, 1 중 하나여야만 함만약 데이터가 삽입되거나 삭제되어 BF가 ±2 이상이 되면, 트리가 한쪽으로 무너졌다고 판단하고 즉시 구조를 재조정 2. AVL 트리의 4가지 회전 (Rotation)LL (Left-Left) 케이스 ➡️ 우회전 (Right Rotation)상황: 왼쪽 자식 노드의 왼쪽에 데이터가 ..