반응형 분류 전체보기453 B-트리 (B-Tree) B-트리 (B-Tree) B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. B-트리는 디스크 환경에서 사용하기에 적합한 외부 다진 검색 트리이다. B-트리는 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 대수 시간으로 할 수 있다. 최대 M개의 자식을 가질 수 있는 B-트리를 M차 B-트리라고 한다. 노드는 최대 M개의 자식 노드를 가질 수 있다. ex) 3차 B-트리라면 최대 3개의 자식 노드를 가질 수 있다. 노드에는 최대 M-1개의 KEY를 가질 수 있다. ex) 3차 B-트리라면 최대 2개의 KEY를 가질 수 있다. 각 노드는 최소 ⌈M/2⌉개의 자식.. 2023. 10. 3. 레드 블랙 트리 (Red-Black Tree) 레드 블랙 트리 (Red-Black Tree) 이진 탐색 트리에서 트리의 모양이 균형을 이루지 못 할 경우가 있다. 균형이 깨질 경우 O(n)에 근접한 시간이 소요되는데, 균형을 잘 맞추기 위해 고안된 것이 레드-블랙 트리이다. 레드-블랙 트리는 자가 균형 이진 탐색 트리이다. 리프 노드가 개입될 때 특수 처리를 하지 않아도 된다는 편리함이 있다. 레드-블랙 트리는 다음과 같은 조건들을 만족한다. 1. 루트 노드는 검은색이다. 2. 모든 노드는 레드 혹은 블랙이다. 3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null, 자료를 갖지 않고 트리의 끝을 나타내는 노드) 4. 레드 노드의 자식은 블랙이다. (레드 노드가 연속으로 나올 수 없다) 5. 리프노드에서 루트 노드까지 가는 경로에서 만나.. 2023. 10. 2. 이진 탐색 트리 (BST : Binary Search Tree) 이진 탐색 트리 (BST : Binary Search Tree) 이진 탐색 트리(BST: Binary Search Tree)는 다음과 같은 속성이 있는 이진 트리 자료 구조이다. 1. 각 노드에 중복되지 않는 키(key)가 있다. 2. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두개의 자식 노드를 갖는다. 3. 왼쪽 서브 트리는 부모 노드의 키보다 작은 키를 갖는다. 4. 오른쪽 서브 트리는 부모 노드의 키보다 큰 키를 갖는다. 이진 탐색 트리에서의 검색 1. 루트노드로 부터 시작한다. 2. 검색하려는 값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽으로 가서 찾는다. 3. 노드를 비교하면서 내려가다가 일치하는 값이 나오면 해당 노드를 반환한다. 4. 더이상 비교할 노드가 없으면 검색이 실패했음을 알.. 2023. 10. 2. 선택 (Select) 알고리즘 선택 (Select) 알고리즘 정렬되지 않은 리스트나 배열에서 가장 작은 k번째 수를 찾는 알고리즘이다. 간단한 방법은 최소 숫자들을 오름차순으로 정렬한 후, k번째 숫자를 찾는 것이 있는데, 이러한 알고리즘은 O(nlogn)의 수행 시간이 걸린다. 이보다 효율적인 해결을 위하여 분할 정복 개념을 활용할 수 있다. 일부 과정이 퀵 정렬과 비슷하여 Quick-Select 알고리즘이라고도 한다. "평균"선형 시간 안에 k번째 작은 수를 찾을 수 있다. 부분문제의 크기가 일정하지 않은 크기가 감소하는 형태의 분할 정복 알고리즘이다. 만일 피봇이 입력을 너무 한 쪽으로 치우치게 분할하면, 알고리즘의 수행시간이 길어진다. 두 그룹 중 하나의 크기가 입력 크기의 3/4과 같거나 그보다 크면 bad 분할이고, 그 반.. 2023. 10. 2. Sort 계수 정렬 (Counting Sort) 알고리즘 [Sort] 계수 정렬 (Counting Sort) 알고리즘 계수 정렬은 데이터의 키에 따라 객체를 수집 정렬 하는 정렬 알고리즘이다.비교 연산을 하지 않는 정렬 알고리즘이다.키의 다양성이 데이터의 수보다 상당히 크지 않은 상황에서 유용하다.O(n)의 시간 복잡도를 가진다.데이터 중 가장 작은 값과 가장 큰 값을 기준으로 하는 공간 크기가 필요하다. (1~10의 경우 10개의 공간이 필요하지만 1과 10000이 들어 있는 데이터에서는 10000의 배열 크기가 필요하다.)특정한 값이 몇번 등장했는지에 따라 정렬을 수행한다.계수를 다 카운팅 한 후에 앞에서 부터 차례대로 배열에 넣는다. 정렬 과정10000개의 공간에 1 ~ 10까지의 정수가 무작위로 들어가 있다고 가정한다.최솟값 최댓값을 알고 있을 때, 각.. 2023. 10. 1. Sort 기수 정렬 (Radix Sort) 알고리즘 [Sort] 기수 정렬 (Radix Sort) 알고리즘 기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다.공간을 나눠 알맞은 데이터를 놓는 방법이 버킷 정렬 (Bucket Sort)과 비슷하다.* 버킷 소트(bucket sort)는 배열의 원소를 여러 버킷으로 분산하여 작동하는 정렬 알고리즘이다. 특징데이터를 구성하는 기본 요소(Radix)를 이용하여 정렬을 진행하는 방식이다.비교연산을 수행하지 않아 조건이 맞는 상황에서 빠른 정렬 속도를 보장하는 알고리즘이다. 자릿수가 존재하지 않는 데이터를 기수정렬로 정렬하는 것은 불가능하다.전체 데이터의 기수를 위한 버킷이라는 추가적인 메모리 공간이 필요하다. 10 진수인 데이터들을 정렬하기 위해서는 0~9 를 저장할 10.. 2023. 10. 1. 스털링 근사 (Stirling's approximation) 스털링 근사 (Stirling's approximation) 수학에서 스털링 근사(영어: Stirling’s approximation) 또는 스털링 공식(영어: Stirling’s formula)은 큰 계승을 구하는 근사법이다. 나아가 실수와 복소수까지 확장시켜 감마 함수에 대한 근삿값을 구할 수 있도록 한다. 계승(팩토리얼: factorial)이란 기호로 간단하게 n!로 나타내며 1부터 n까지의 자연수를 모두 곱하는 것을 의미한다. 일반적으로 확률과 통계, 수학 과목에서는 n! = 1×2×3×⋯⋯×(n−1)×n 으로 배운다. (n부터 1씩 빼면서 곱하는 것) 아래 표는 20까지의 팩토리얼 값을 정리한 것이다. 이처럼 n이 커질 수록 해당 값이 기하급수적으로 증가하게 되는데 이 때 스털링의 근사식을 응용.. 2023. 10. 1. C++ 프로그래머스 Lv5 집합과 쿼리 [C++] 프로그래머스 Lv5 집합과 쿼리 2023년 현대모비스 알고리즘 경진대회 예선 문제이다.본 게시글의 풀이는 58.3점으로 해결하지 못한 문제로 남아있다. 문제 설명정수 0 ~ n-1을 담고 있는 크기가 n인 1차원 정수 배열 a가 있습니다. 배열의 각 원소마다 하나의 집합을 이루고 있습니다. 당신은 여기에 다음 쿼리들을 실행하려고 합니다. [1, x, y] 형태의 쿼리가 주어집니다.y가 포함된 집합의 원소들을 모두 x가 포함된 집합으로 옮깁니다.x와 y가 같은 집합에 속해있다면 해당 쿼리는 실행하지 않습니다.[2, x, y] 형태의 쿼리가 주어집니다.새로운 집합을 생성합니다.x와 y가 포함된 집합에서 x와 같거나 늦게 집합으로 들어왔으면서 y와 같거나 빠르게 집합으로 들어온 원소들을 새로 생성한.. 2023. 9. 22. 자료구조 트리(Tree) 구조 [자료구조] 트리(Tree) 구조 개념자료구조 Tree는 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아서 트리 구조라고 부른다.자료구조 Tree는 그래프의 여러 구조 중 무방향 그래프의 한 구조이다.트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다.트리 구조는 데이터를 순차적으로 나열시킨 선형 구조가 아니라,하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다.트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없다.트리 구조는 루트라는 하나의 꼭짓점 데이터를 시작으로, 여러 개의 데이터를 간선으로 연결한다.트리 구조는 각 데이터를 노드라고 하며, 두 개의 노드가 상하계층으로 연결되면 부모/자식 관계를 가.. 2023. 9. 22. Sort 힙 정렬(Heap Sort) 알고리즘 [Sort] 힙 정렬(Heap Sort) 알고리즘 힙(Heap)이란?힙이란 완전 이진 트리의 형태로 만들어진 자료구조이다.돌 더미, 장작 더미 처럼 위로 갈수록 노드의 수가 줄어드는 모습을 하고 있다. 완전 이진 트리(Complete Binary Tree)란?완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 가지고 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있는 자료구조이다. 최하단 레벨의 노드는 좌측 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 하며, 노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입해야 한다. 힙 정렬(Heap Sort)이란 ?힙 정렬(Heap sort)이란 최대 힙(부모 노드 > 자식 노드) 트리나 최소 힙(부모 노드 트리를 구성해 정렬을 하는 방법이다.힙(.. 2023. 9. 19. C++ BAEKJOON 28278번 : 스택2 [C++] BAEKJOON 28278번 : 스택2 시간 제한메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초1024 MB67742693225940.622%문제정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 다섯 가지이다.1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.3: 스택에 들어있는 정수의 개수를 출력한다.4: 스택이 비어있으면 1, 아니면 0을 출력한다.5: 스택에 정수가 있다면 맨 .. 2023. 9. 18. C++ 프로그래머스 Lv3 하노이의 탑 [C++] 프로그래머스 Lv3 하노이의 탑 문제 설명하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다. 한 번에 하나의 원판만 옮길 수 있습니다. 큰 원판이 작은 원판 위에 있어서는 안됩니다. 하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다. 1번 기둥에 있는 원판의 개수 n이 매개변수로.. 2023. 9. 16. 이전 1 ··· 25 26 27 28 29 30 31 ··· 38 다음 반응형
