분류 전체보기
-
B 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 11. 11. 19:58
B 트리 이진 검색 트리를 기반으로 노드에 Balance Factor(이후 BF)를 추가하여 BF의 상태에 따라 트리의 균형을 유지한다. B 트리 개요 검색 트리가 방대하면 검색 트리를 메모리에 모두 올려두고 사용할 수 없게 되어 검색 트리가 디스크에 있는 상태에서 작업을 해야 한다. 이런 경우에 CPU 작업 효율성보다 디스크 접근 횟수가 효율을 좌우하게 된다. B 트리는 디스크 환경에서 사용하기 적합한 외부 다진 검색 트리로 B 트리의 한 노드에는 최대 k개까지의 키가 크기 순으로 저장되어 있다. ※ 검색 트리가 디스크에 있는 상태로 사용되면 이를 외부 검색 트리라고 한다. B 트리에 k개의 키가 존재하는 경우 k + 1 개의 자식을 가지게 된다. 이때, 주어진 키를 key 0 ~ key k - 1로 ..
-
JUNGOL/Intermediate_Coder/백트래킹-DFS/2217 : DNA 조합코딩 테스트/JUNGOL 2021. 11. 11. 09:54
Intermediate_Coder/백트래킹-DFS/DNA 조합 문제 도훈이는 학교에서 배운 유전자 실험을 이용해서 자신만의 실험을 계획하고 있다 (프로그램을 작성해주는 복제인간을 만드는 것이 목표라고 한다). 도훈이가 갖고 있는 DNA 조각은 n(2 TACAGATTA TACA+ACA -> TACA TAC+TACA -> TACA ATAC+TACA -> ATACA TACA+ACAT -> TACAT 입력 형식 첫 줄에 n이 입력되고, 두 번째 줄부터 n개의 줄에 걸쳐 각 DNA 조각이 입력된다. DNA조각의 길이는 1 ~ 7 이다. 출력 형식 첫 번째 줄에 n개의 DNA를 모두 조합해서 하나의 DNA 순열로 만들었을 때 최소 길이를 출력한다. 입력 예 4 | 3 GATTA | ABC TAGG | BCD ATC..
-
알고리즘...82일지 2021. 11. 10. 09:16
B 트리 삭제 메서드, 병합 처리 병합 처리를 구현한 부분 중 leaf 노드와 키를 처리하는 부분에서 키를 노드에서 빼는 과정으로 인해 버그가 발생하여 해당 값을 빼는 게 아니니 최소 값인 keyRoot를 이용하는 것으로 수정했다. BTree void BTree::ClearUnderflow(BTreeNode* node) { // 노드가 루트인 경우 if (node == _root) { if (node->size == 0) { _nodeManager.Push(node); _root = nullptr; } } else { bool isDone{ false }; BTreeNode* parent{ node->parent }; BTreeNodeKey* lsKey{ nullptr }; BTreeNodeKey* rs..
-
JUNGOL...159일지 2021. 11. 10. 07:26
Intermediate_Coder/백트래킹-DFS/DNA 조합 문제 도훈이는 학교에서 배운 유전자 실험을 이용해서 자신만의 실험을 계획하고 있다 (프로그램을 작성해주는 복제인간을 만드는 것이 목표라고 한다). 도훈이가 갖고 있는 DNA 조각은 n(2 TACAGATTA TACA+ACA -> TACA TAC+TACA -> TACA ATAC+TACA -> ATACA TACA+ACAT -> TACAT 입력 형식 첫 줄에 n이 입력되고, 두 번째 줄부터 n개의 줄에 걸쳐 각 DNA 조각이 입력된다. DNA조각의 길이는 1 ~ 7 이다. 출력 형식 첫 번째 줄에 n개의 DNA를 모두 조합해서 하나의 DNA 순열로 만들었을 때 최소 길이를 출력한다. 입력 예 4 | 3 GATTA | ABC TAGG | BCD ATC..
-
알고리즘...81일지 2021. 11. 9. 20:16
B 트리 삭제 메서드 구현 시작 기존 삭제 메서드에서 문제가 있었던 부분을 수정했다. BTree::GetProperNodeToDelete BTreeNode* BTree::GetProperNodeToDelete(int data) { BTreeNode* node{ _root }; BTreeNode* leafNode{ nullptr }; while (node != nullptr) { if (node->IsContainsData(data)) { BTreeNodeKey* key{ node->GetKey(data) }; leafNode = node; while (key->right != nullptr) { leafNode = key->right; key = leafNode->GetSmallestKey(); } br..
-
JUNGOL...158일지 2021. 11. 9. 08:20
Intermediate_Coder/백트래킹-DFS/DNA 조합 문제 도훈이는 학교에서 배운 유전자 실험을 이용해서 자신만의 실험을 계획하고 있다 (프로그램을 작성해주는 복제인간을 만드는 것이 목표라고 한다). 도훈이가 갖고 있는 DNA 조각은 n(2 TACAGATTA TACA+ACA -> TACA TAC+TACA -> TACA ATAC+TACA -> ATACA TACA+ACAT -> TACAT 입력 형식 첫 줄에 n이 입력되고, 두 번째 줄부터 n개의 줄에 걸쳐 각 DNA 조각이 입력된다. DNA조각의 길이는 1 ~ 7 이다. 출력 형식 첫 번째 줄에 n개의 DNA를 모두 조합해서 하나의 DNA 순열로 만들었을 때 최소 길이를 출력한다. 입력 예 4 | 3 GATTA | ABC TAGG | BCD ATC..
-
JUNGOL/Intermediate_Coder/백트래킹-DFS/1409 : 벽장문의 이동코딩 테스트/JUNGOL 2021. 11. 5. 17:57
Intermediate_Coder/백트래킹-DFS/벽장문의 이동 문제 n개의 같은 크기의 벽장들이 일렬로 붙어져 있고 벽장의 문은 n-2개만이 있다. 한 벽장 앞에 있는 문은 이웃 벽장 앞에 문이 없다면(즉, 벽장이 열려있다면) 그 벽장 앞으로 움직일 수 있다. 그림은 7개의 벽장의 예이다. 그림에서 2번 벽장과 5번 벽장이 열려있고, 나머지 벽장은 닫혀 있다. 벽장 문은 좌우 어느 쪽이든 그 이웃 벽장이 열려 있다면 그 쪽으로 한 칸씩 이동할 수 있다. 그림에서 주어진 상태에서는 1번 벽장을 닫고 있는 벽장문을 오른쪽으로 한 칸 이동함으로써 1번 벽장을 사용할 수 있다. 이때 2번 벽장은 닫혀져 사용할 수 없다. 역시 5번 벽장이 열려 있으므로 4번 벽장 또는 6번 벽장 앞의 벽장문을 5번 벽장 앞으로..
-
유니티 화면 비율 고정 처리...18일지 2021. 11. 3. 20:30
빌드 후 테스트 분석 완료한 코드를 실제 빌드하여 실행해본 결과는 다음과 같았다. 유니티 화면 비율 고정 처리 버그 이 버그를 수정후 내 깃허브에 올려야겠다. 먼저, 의심되는 점은 좌, 우 조정 시에는 위와 같은 버그가 발생하지만 상, 하 조정 시에는 버그가 발생하지 않고 적절하게 처리가 되었다는 점이다. 현재 처리 과정을 보면 위치를 나타내는 left와 top에 대해서 현재 정확한 위치를 나타내는 대신 right나 bottom에서 크기를 빼서 계산하고 있는데 이게 문제가 될 수 있을 것 같다. 이것을 정확한 윈도우의 위치를 받아온 뒤 그 값에서 보정된 크기를 더해 right와 bottom을 구하는 방식으로 수정해 봐야겠다. 그리고 아마 최대화 처리에 대해서는 max와 min 사이즈를 정해두고 clamp..