Archived(CSE Programming)/자료구조(C++) (16) 썸네일형 리스트형 자료구조 프로그래밍 Lab08) BTree (2-3 Tree) 만들기 자료구조 프로그래밍 Lab08) BTree (2-3 Tree) 만들기 Btree에 대해 이야기하기에 앞서 Multiway Search Tree에 대해 알아야 한다.Multiway search Tree란 기존의 BST에서 데이터를 한 번 가져오기 위해서 접근하는 과정에서 오는 손실을 최소화 하고자 한 노드의 데이터를 여러개를 저장할 수 있도록 degree를 늘인 형태이다. 이때 이, Multiway Search Tree 에서도 마찬가지로 level을 최소화하면 탐색 성능이 더욱 향상할 수 있는데 이를 구현한 것이 Btree 이다. Btree는 Balanced, Boeing, Bayer 의 3가지 의미가 있지만 정확한 이름의 유래는 알려지지 않았다. 이 Btree는 몇가지 조건이 존재한다. - 루트 노드는 .. 자료구조 프로그래밍 Lab07) AVL Tree 만들기 자료구조 프로그래밍 Lab07) AVL Tree 만들기 AVL Tree란 balanced Tree 중에서 가장 초기에 나온 tree이다.BST의 효율성을 증대시키기 위해서 level을 최대한 낮춰야하는데, 이 중 한 방법으로AVL tree가 등장하였다.(AVL인 이유는 이 tree를 고안한 G.M. Adelson-Velskii와 E.M. Landis의 이름들을 따서 지었다) AVL tree는 다음과 같이 왼쪽 subtree의 높이와 오른쪽 subtree의 높이 차를 bf에 저장하여 bf의 절댓값이 1 이하인 경우를 계속 유지해야한다.그래서 재귀적으로 삽입을 수행한 후, 루트까지 오면서 bf를 체크하고 bf의 절댓값이 2인 경우에는 회전을 통하여 균형을 수정한다.그리고 이러한 회전에는 총 4가지가 있는데 .. 자료구조 프로그래밍 Lab06) 이항 힙 만들기 (Binomial Heap) 자료구조 프로그래밍 Lab06) 이항 힙 만들기 (Binomial Heap) 문제 해결 이항 힙은 다음의 과정을 통해 삽입과 삭제가 이루어진다.이항 힙은 이항 트리들의 모임이다.( 2의 n승 값의 노드 수를 지닌 트리)이항 힙은 양방향 형제(lsb, rsb)와 자식노드(child), 계층(degree), 값(data)로 이루어진 tree의 집합이다. 삽입0) 새로운 temp를 삽입하면 우선순위를 비교해 기존의 minHeap에서 가르키고 있는 min pointer 의 바로 lsb(왼쪽 형제)에 값을 둔다1) temp node의 우선순위가 더 높으면 min이 가르키고 있는 nodePointer를 temp로 옮긴다 2) 병합 과정을 전개(do while) - 최소 한번은 실행, 새로운 데이터와 병합 과정 진행.. 자료구조 프로그래밍 Lab05) 최소 좌향 트리 만들기(Leftist Min Tree, Heap) 자료구조 프로그래밍 Lab05) 최소 좌향 트리 만들기(Leftist Min Tree, Heap) 문제 최소 좌향 트리의 병합 과정은 다음과 같다. 해결 알고리즘 Main 함수.0. TreePointer를 저장할 Queue와 levelOrder로 출력할 Queue2와 Queue에 들어있는 각 Tree들의 size를 저장할 배열 TreeSize를 준비한다.1. 입력파일의 값을 하나씩 읽으면서 NodePointer로 만들어 Queue에 push 한다(이 때, TreeSize에 해당 rear로 1을 넣어준다).2. While 문(queue의 값이 하나가 될 때까지) 반복.3. NodePointer 두개를 pop 해서 minMeld를 통해 합친다.4. 합치면서 TreeSize의 front 인덱스로 접근해서 사이.. 자료구조 프로그래밍 Lab04) 그래프 모든 경로 찾기 C (두 vertex 사이) 자료구조 프로그래밍 Lab04) 그래프 모든 경로 찾기 C (두 vertex 사이) 문제 Graph와 Edge를 주어주고 특정 두 vertex를 지정하면 두 vertex 사이의 "모든 경로"를 탐색하여 출력합니다. 해결 알고리즘 알고리즘의 핵심은 dfs입니다. 0. 재귀함수로 구성합니다 void checkPath(int start, int end)1. 함수에서 들어오면 visit 배열을 통해 방문 true 값 주고, start 값을 stack에 push합니다.2. 만약 인자 start == end가 된다면 경로를 한 가지 발견한 것입니다.3. 이 때 stack에 들어온 경로 따라서 출력 후에 도착한 지점(end)를 pop한 후에 함수를 return합니다.4. 발견 못했을 시, 다음 경로를 탐색합니다 (조.. 자료구조 프로그래밍 Lab03) 최소힙(Min Heap) 만들기! 문제 최소힙 만들기힙이란 우선순위 큐라고도 불리며 말하는 것으로 다음과 같이 부모 노드의 값의 우선순위 자식 노드의 값의 우선순위보다 높은 상태를 말합니다. 최소힙이란 값이 적은 것이 우선순위가 높은 것으로Root Node에는 큐에서 가장 작은 값이 배정되어 있어야 합니다.위의 우선순위 큐에서도 알 수 있듯이 1이 가장 작은 값이기에 Root Node가 됩니다. 해결 알고리즘 Heap도 일종의 Queue이기에 구현하는 데 있어 고려해야 할 것은 삽입(push)과 삭제(pop), 두 가지 입니다.Push의 경우에는 Heap이라는 1차원 배열에다 값을 추가하는데 우선순위에 맞게 추가하면 됩니다. 123456789101112131415161718192021// heap 삽입함수void minHeap(int d.. 자료구조 프로그래밍_Lab02) 역대 최고가 주식 자료구조 프로그래밍_Lab02) 역대 최고가 주식 문제. 어느 기업의 주식가격을 날짜별로Day 1. 100 Day 2. 50 Day 3. 70 Day 4. 60 Day 5. 30 Day 6. 120 Day 7. 50 와 같이 제시한다.해당 주식 가격이 며칠 동안 최고가 였는지를 비교하며 기록하여 비교횟수와 함께 출력한다.단, 단순배열비교와 스택의 두 가지 방법을 사용하여 비교한다. 해결 알고리즘. 주어진 주식가격은 1차원 배열의 Stock에 저장하고각 요일별 최고가는 span에 저장한다. 알고리즘 단순 배열 비교 방법 0. span 기록 배열을 1로 초기화(최소 1일동안 최고가 일 수 있으므로)1. for 문을 통해 2번 째 날짜(인덱스 1) 부터 반복문처리2. count라는 변수를 주어진 날짜 -1 로.. 자료구조 프로그래밍_Lab01) 술 취한 바퀴벌레 문제 자료구조 프로그래밍 실습 1. 술취한 바퀴벌레 문제. 문제 내용은 다음과 같습니다. 문제 술취한 바퀴벌레는 M * N 의 이차원 배열을 헤매고 있습니다.전체 배열을 전부 1번 이상 씩 방문할 때까지 Random으로 8방향 중 한 방향으로 이동을 합니다.단 시작점은 [m/2][n/2] 에서 시작합니다. 해결 - 알고리즘 문제 해결의 알고리즘은 다음과 같습니다. 0. 배열 초기화 (0~m+1, 0~n+1)1. 방향 정리 (8방)2. while( 다 방문할 때 까지)을 통한 반복문3. 안에서 rand로 난수 받아서 다음방향 이동(단 , 0또는 m+1, 0또는 n+1 일때는 다시 난수받기)4. 돌면서 방문하는 곳은 0에서 1로 체크 0.배열 초기화는 사이즈 m+2 * n+2 의 배열을 할당합니다그리고 후에 방문.. 이전 1 2 다음
