B트리 (B-Tree)정의B트리는 자가 균형 다진 트리(M-ary tree)이다. 즉, 모든 리프의 노드가 같은 depth 를 가지며, 내부 노드가 여러 자식을 가질 수 있다.m은 B트리의 차수이다. 각 노드는 최대 m개의 자식을 가질 수 있다.ㄴ 3차 B트리라고 한다면, m은 3이고 최대 3개의 자식을 가질 수 있다는 것.  구조와 속성루트 노드: (트리가 비어있지 않을 때) 2개 이상, m개 이하의 자식을 가진다. 내부 노드: ⌈m/2⌉개 이상, m개 이하의  자식을 가진다.리프노드: 모든 리프 노드는 동일한 레벨에 있다. 균형 유지노드의 키: 각 노드는 ⌈m/2⌉개 이상, m-1개 이하의 키를 가진다. 정렬된 상태를 유지하고 있어 효율적 탐색이 가능하다.  장단점장점자동으로 균형을 유지하여 검색, ..

[level 3] 섬 연결하기 - 42861문제 링크성능 요약메모리: 72.3 MB, 시간: 0.76 ms구분코딩테스트 연습 > 탐욕법（Greedy）채점결과정확성: 100.0합계: 100.0 / 100.0제출 일자2024년 11월 14일 02:17:48문제 설명n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.제한사항섬의 개수 n은 1 이상 100 이하입니다.costs의..

[level 2] 영어 끝말잇기 - 12981문제 링크성능 요약메모리: 78.6 MB, 시간: 0.22 ms구분코딩테스트 연습 > Summer／Winter Coding（～2018）채점결과정확성: 100.0합계: 100.0 / 100.0제출 일자2024년 11월 12일 04:05:05문제 설명1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.이전에 등장했던 단어는 사용할 수 없습니다.한 글자인 단어는 인정되지 않습니다.다음은 3명이 끝말잇기를 하는 ..

트랜잭션(Transaction)이란?DBMS에서 일련의 연산을 논리적인 작업 단위로 묶어 처리하는 개념. 여러 작업을 하나의 단위로 처리.데이터베이스의 무결성 유지를 위함.무결성 : 데이터의 정확성, 일관성, 유효성을 유지하는 것예시) 은행 시스템계좌 A에서 계좌 B로 돈을 이체할 때, A의 잔고 감소와 B의 잔고 증가가 하나의 트랜잭션으로 처리되어야 한다.만약 하나라도 실패하면 전체 트랜잭션이 롤백되어야 한다.    트랜잭션의 특성 (ACID)Atomicty / All or nothing (원자성)트랜잭션의 연산은 모두 성공하거나 모두 실패해야한다.Consistency (일관성)트랜잭션이 수행 결과는 항상 일관되어야 한다.Isolation (고립성/독립성)트랜잭션이 수행되는 동안 다른 트랜잭션의 작업이..

[Gold V] 집합의 표현 - 1717문제 링크성능 요약메모리: 91408 KB, 시간: 3024 ms분류자료 구조, 분리 집합제출 일자2024년 11월 12일 03:42:39문제 설명초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오.입력첫째 줄에 $n$, $m$이 주어진다. $m$은 입력으로 주어지는 연산의 개수이다. 다음 $m$개의 줄에는 각각의 연산이 주어진다. 합집합은 $0$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$가 포함되어 있는 집합과, $b$가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가..

완전이진트리(Complete Binary Tree)란?완전이진트리는 이진트리의 일종으로 최대 2개의 자식노드를 가질 수 있다.마지막 레벨을 제외한 모든 레벨이 꽉 차있어야 한다.마지막 레벨은 왼쪽부터 채워져 있어야 한다.완전 이진트리의 예올바른 예틀린 예마지막 레벨을 제외한 모든 레벨이 꽉 채워져 있음.마지막 레벨은 왼쪽부터 채워져 있음.마지막 레벨을 제외한 모든 레벨이 꽉 채워져 있음.하지만 노드 2의 오른쪽 자식이 비워져있음.  완전이진트리 특성노드의 개수: 레벨 h에 있는 노드의 최대 개수는 2^h이다.예를 들어, 루트 레벨(레벨 0)에는 최대 1개의 노드가 있고, 레벨 1에는 최대 2개의 노드, 레벨 2에는 최대 4개의 노드가 있을 수 있다.트리의 높이: 노드의 개수가 n인 완전 이진 트리의 ..

[level 3] 다단계 칫솔 판매 - 77486문제 링크성능 요약메모리: 134 MB, 시간: 48.18 ms구분코딩테스트 연습 > 2021 Dev－Matching： 웹 백엔드 개발자（상반기）채점결과정확성: 100.0합계: 100.0 / 100.0제출 일자2024년 11월 06일 03:47:14문제 설명민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다.민호는 center이며, 파란색 네모는 여덟 명의 판매..

이진탐색트리란?이진탐색트리(Binary Search Tree, BST)는 이진 트리의 일종으로 데이터를 효율적으로 저장, 검색, 삽입 및 삭제할 수 있도록 설계된 자료구조이다. 이진탐색트리는 다음과 같은 특징을 가지고 있다.각 노드가 최대 두개의 자식 노드를 가지고 있다.왼쪽 서브트리의 모든 노드의 값은 루트 노드의 값보다 작다.오른쪽 서브트리의 모든 노드의 값은 루트 노드의 값보다 크다.중복 요소는 허용하지 않는다.왼쪽 및 오른쪽 서브트리도 각각 이진탐색트리여야 한다.  이진탐색트리의 연산탐색 (Search)root 노드부터 탐색 시작현재 위치의 값과 비교하여 찾고자 하는 key 가 작으면 왼쪽 서브트리로, 오른쪽 서브트리로 재귀.일치하는 값을 찾을 때까지 절차 반복.리프노드에 도달할 때 까지 검색 값..

[level 2] 예상 대진표 - 12985문제 링크 성능 요약메모리: 67.7 MB, 시간: 0.04 ms구분코딩테스트 연습 > 2017 팁스타운채점결과정확성: 100.0합계: 100.0 / 100.0제출 일자2024년 11월 04일 17:28:35문제 설명△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다..