728x90 분류 전체보기58 [자료구조] B-Tree & Set ADT 기존 Binary Search Tree의 문제점기존 BST는 균형이 맞는다는 가정 하에 logN의 시간에 탐색이 가능하다는 장점이 있었지만, 특정 조건 [ex) 일렬로 정렬된 경우]에서 O(n)의 시간복잡도를 갖게 되는 문제점이 발생하기도 한다. 이를 해결하기 위한 Search Tree중 하나가 B-tree다. B-Tree 규칙B-tree는 아래의 규칙을 만족하여야 한다 1. root Node는 최소 하나의 요소를 갖을 수 있다. 이외 모든 다른 Node는 최소 MINIMUN의 요소를 갖어야 한다.* MINIMUN : B-트리를 설계할 때 정해둔 최소 허용 요소 수를 의미하며, 보통 B-트리 차수(order) m에 대해 ⌈m/2⌉−1 또는 ⌈m/2⌉처럼 정의한다.** 여기서 차수 M이라는 것은 한 Nod.. 2025. 6. 2. [자료구조] Heap & Priority Queue ADT Heap이란?Heap은 다음 두 규칙을 따르는 이진 트리의 일종이다.각 node가 가지고 있는 값은 각 node의 자식 node들이 가지고 있는 값보다 크거나 같아야 함(최대 힙의 경우)트리는 완전 이진 트리를 유지해야 하는데, 즉 가장 아래 레벨을 제외한 모든 레벨이 가능한 한 꽉 차 있어야 함.최대, 최소 값을 빠르게 찾기 위한 자료구조이므로 BST랑 비교했을 때 비슷하다고 생각할 수도 있지만 Heap은 왼쪽 오른쪽 상관없이 상하 관계에 따라서만 크기 결정이 된다는 차이점이 있다. Heap을 이용한 우선순위 큐(priority queue) ADTHeap 구조를 이용하는 우선순위 큐는 다음의 룰을 만족하면 된다.각 요소는 우선순위가 더 높은 상태로 유지가 되어야 한다.(부모 노드가 자식 노드보다 높은.. 2025. 5. 29. [자료구조] 이진탐색트리(Binary Search Tree) 이진탐색트리(BST)란?이진 트리의 한 종류로, 아래의 특징을 만족한다.각 node는 뚜렷한 데이터 값을 갖는다.더 작거나 또는 더 큰 값으로 key 값이 분류될 수 있다.모든 node는 오른쪽 서브 트리보다 작고, 왼쪽 서브 트리보다 크다. node 탐색하기node를 탐색하는 방법은 간단하다.현재 node가 target이 아니라면, 크기 비교를 한다.작다면 왼쪽 서브 트리로, 크다면 오른쪽 서브 트리로 이동한다.만약 해당 노드가 leaf노드라면 false를 반환한다.위 과정을 반복하면서 target을 찾는다. node 추가하기node를 추가하는 방법도 쉽다.탐색하는 방법과 유사하게 tree를 내려가면서 해당 값이 들어갈 자리를 찾아서 추가해주면 된다. 예를 들어 16이라는 값을 추가한다고 하면45 v.. 2025. 5. 29. [자료구조] Binary Tree(이진트리) Binary Tree특징root 라는 특별한 노드가 존재오직 왼쪽 / 오른쪽 두가지 child node만 가질 수 있음각 node는 정확히 1개의 부모 node를 갖음트리의 깊이 : leaf node 중 가장 깊은 node의 깊이 Full Binary tree(정 이진트리)모든 leaf node가 같은 깊이를 갖으면서, 모든 잎이 아닌 node가 2개의 자손이 있는 것Complete Binary Tree (완전 이진 트리)가능한 먼 노드들을 왼쪽부터 채워나가는 이진 트리Array representation of Complete Binary Tree완전 이진트리는 배열을 이용해서 구현할 수 있다.위와 같은 형태의 완전 이진 트리가 있다고 가정해보자.그럼 임의의 배열 arr에 아래와 같이 저장할 수 있다. .. 2025. 5. 27. [C++][백준] 2096 내려가기 문제N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성.. 2025. 5. 11. [ BIOS ] 앱 초보자의 팀 프로젝트 기획하기 - 2 지난시간에는 앱 프로젝트를 진행하게된 경위와몇 가지 간단한 개요와 대략적인 기능에 대해 소개해보았다.이번에는 나의 프로젝트 팀에 대해 먼저 소개해보고프로젝트 기능 중 로그인 워크플로우에 대해 작성해보고자 한다.Team : 001LAB 어떤 팀인가? 게임 & 웹 & 앱 개발 & 디자인 & 기획 등 다양하게 찍먹해본숭실대 컴퓨터학부생 3명이 모인 프로젝트 팀이다. 팀명의 이유?원래는 프로젝트의 방향성이 '001에 있는 소모임들을 위한 앱 개발' 이었기에가제로 001LAB이라는 이름을 붙여보았는데생각보다 괜찮은 이름이라고 생각해 팀명이 되어버렸다. (TMI : 우측에 보이는 로고는 글쓴이가 아르바이트 하다가 쉬는 시간에 만든 로고이다.)APP 이름 : BIOS앱의 이름은 BIOS로 결정되었다.지난 글을 잘 본.. 2025. 1. 26. 이전 1 2 3 4 5 6 7 ··· 10 다음 728x90 반응형
