일지
-
JUNGOL...162일지 2021. 11. 17. 20:21
Intermediate_Coder/백트래킹-DFS/장기 문제 N×M장기판에 졸 한개와 말 한개가 놓여 있다. 말의 이동 방향이 다음과 같다고 할 때, 말이 최소의 이동횟수로 졸을 잡으려고 한다. 말이 졸을 잡기 위한 최소 이동 횟수를 구하는 프로그램을 작성해보자. 입력 형식 첫 줄은 장기판 행의 수(N)와 열의 수(M)를 받는다(1≤N, M≤100). 둘째 줄은 말이 있는 위치의 행(R), 열(C)의 수와 졸이 있는 위치의 행(S), 열(K)의 수를 입력받는다. 단, 장기판의 제일 왼쪽 위의 위치가 (1,1)이다. 각 행과 열은 R(1≤R≤N), C(1≤C≤M), S(1≤S≤N), K(1≤K≤M)이다. 출력 형식 말이 졸을 잡기 위한 최소 이동 횟수를 출력한다. 입력 예 9 9 3 5 2 8 출력 예 2..
-
JUNGOL...161일지 2021. 11. 16. 21:13
Intermediate_Coder/백트래킹-DFS/장기 문제 N×M장기판에 졸 한개와 말 한개가 놓여 있다. 말의 이동 방향이 다음과 같다고 할 때, 말이 최소의 이동횟수로 졸을 잡으려고 한다. 말이 졸을 잡기 위한 최소 이동 횟수를 구하는 프로그램을 작성해보자. 입력 형식 첫 줄은 장기판 행의 수(N)와 열의 수(M)를 받는다(1≤N, M≤100). 둘째 줄은 말이 있는 위치의 행(R), 열(C)의 수와 졸이 있는 위치의 행(S), 열(K)의 수를 입력받는다. 단, 장기판의 제일 왼쪽 위의 위치가 (1,1)이다. 각 행과 열은 R(1≤R≤N), C(1≤C≤M), S(1≤S≤N), K(1≤K≤M)이다. 출력 형식 말이 졸을 잡기 위한 최소 이동 횟수를 출력한다. 입력 예 9 9 3 5 2 8 출력 예 2..
-
알고리즘...84일지 2021. 11. 16. 20:40
KD 트리 개요 KD 트리는 이진 검색 트리를 확장한 것으로 k 개의 필드로 이루어진 키를 사용하며, 이진 검색 트리와 비슷하게 동작 하나 레벨 별로 분기 시 하나의 필드만을 사용한다는 점이 다르다. 위 그림에서 보는 것처럼 KD 트리는 같은 레벨의 노드는 동등한 위치의 필드를 사용하여 분기를 진행하며 k 개의 필드를 가지는 KD 트리에서 레벨 k에 도달한 경우 다시 0 번째 필드를 사용하여 분기를 진행한다. 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
JUNGOL...160일지 2021. 11. 15. 14:11
Intermediate_Coder/백트래킹-DFS/장기 문제 N×M장기판에 졸 한개와 말 한개가 놓여 있다. 말의 이동 방향이 다음과 같다고 할 때, 말이 최소의 이동횟수로 졸을 잡으려고 한다. 말이 졸을 잡기 위한 최소 이동 횟수를 구하는 프로그램을 작성해보자. 입력 형식 첫 줄은 장기판 행의 수(N)와 열의 수(M)를 받는다(1≤N, M≤100). 둘째 줄은 말이 있는 위치의 행(R), 열(C)의 수와 졸이 있는 위치의 행(S), 열(K)의 수를 입력받는다. 단, 장기판의 제일 왼쪽 위의 위치가 (1,1)이다. 각 행과 열은 R(1≤R≤N), C(1≤C≤M), S(1≤S≤N), K(1≤K≤M)이다. 출력 형식 말이 졸을 잡기 위한 최소 이동 횟수를 출력한다. 입력 예 9 9 3 5 2 8 출력 예 2..
-
알고리즘...83일지 2021. 11. 15. 14:00
다차원 검색 트리 데이터를 검색하기 위한 키가 여러 개로 이루어진 검색 트리를 말하며 다음과 같은 종류가 존재한다. KD 트리 이진 검색 트리를 확장한 것으로 검색에 두 키 중 하나의 키만 사용한다. KDB 트리 B 트리를 확장한 것으로 루트 노드에서 부터 전체 공간을 쪼개가면서 검색을 진행한다. R 트리 B 트리를 확장한 것으로 KDB 트리와 달리 키를 포함하는 최소 영역에만 노드가 존재한다. 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
알고리즘...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..