분류 전체보기
-
알고리즘...56일지 2021. 9. 24. 17:20
B 트리 개요 검색 트리가 방대하면 검색 트리를 메모리에 모두 올려두고 사용할 수 없게 되어 검색 트리가 디스크에 있는 상태에서 작업을 해야 한다. 이런 경우에 CPU 작업 효율성보다 디스크 접근 횟수가 효율을 좌우하게 된다. B 트리는 디스크 환경에서 사용하기 적합한 외부 다진 검색 트리로 B 트리의 한 노드에는 최대 k개까지의 키가 크기 순으로 저장되어 있다. ※ 검색 트리가 디스크에 있는 상태로 사용되면 이를 외부 검색 트리라고 한다. B 트리에 k개의 키가 존재하는 경우 k + 1 개의 자식을 가지게 된다. 이때, 주어진 키를 key 0 ~ key k - 1로 나타내고 자식 서브 트리를 각각 T 0 ~ T k 로 나타내면 다음의 관계가 성립한다. T 0 의 모든 노드의 값 < key 0 < T 1..
-
JUNGOL...142일지 2021. 9. 23. 15:44
Intermediate_Coder/백트래킹-DFS/해밀턴 순환회로 문제 태현이는 방학기간 동안 택배 알바를 해서 최고급 노트북을 장만하려고 한다. 오늘 배달해야 하는 장소를 한 번씩만 방문해서 물건을 모두 배달하고 다시 회사로 돌아와야 한다. 배달하는 장소에만 도착할 수 있다면 물건은 모두 배달할 수 있으므로 물건의 개수나 크기등은 고려하지 않아도 된다. 그런데 문제는 방문하는 순서를 어떻게 정할지가 고민이다. 어떤 장소에서 다른 장소로 이동하는 데에는 비용이 발생하는데 만약 방문하는 순서를 잘못 정하게 되면 알바비로 받은 돈을 모두 이동비용으로 사용하고 눈물을 흘릴지도 모른다. 태현이가 물건을 모두 배달하고 회사로 돌아오기 위한 최소의 비용을 계산하는 프로그램을 작성해 주자. 입력 형식 첫 줄은 배달해..
-
이진 검색 트리 출력 함수 구현프로그래밍 기초/알고리즘 2021. 9. 21. 13:55
이진 검색 트리 출력 이진 검색 트리를 화면에 출력하는 함수를 구현한다. 노드 출력 알고리즘 노드를 동일한 간격으로 출력하기 위해 다음의 제약 사항이 존재해야 한다. 모든 노드는 동일한 크기를 갖는다. 최대 깊이의 노드 간의 간격은 노드의 크기와 같다. 최대 깊이에 빈 노드가 없다고 가정하여 최대 크기를 구한다. 구한 최대 크기를 모든 깊이에 사용하여 출력한다. 깊이가 n 일 때, 노드의 개수 및 공백의 개수는 다음과 같다. 노드의 수 2ⁿ - ¹ 개 공백의 수 n + 1 개 따라서 최대 깊이에서 출력에 필요한 크기는 다음의 식을 만족한다. 출력에 필요한 크기 = (공백의 수 + 노드의 수) * 노드의 크기 ※ 깊이에 따라 노드의 수가 달라지므로 공백의 크기는 출력에 필요한 크기 - (노드의 수 * 노드..
-
JUNGOL...141일지 2021. 9. 20. 18:37
Intermediate_Coder/백트래킹-DFS/해밀턴 순환회로 문제 태현이는 방학기간 동안 택배 알바를 해서 최고급 노트북을 장만하려고 한다. 오늘 배달해야 하는 장소를 한 번씩만 방문해서 물건을 모두 배달하고 다시 회사로 돌아와야 한다. 배달하는 장소에만 도착할 수 있다면 물건은 모두 배달할 수 있으므로 물건의 개수나 크기등은 고려하지 않아도 된다. 그런데 문제는 방문하는 순서를 어떻게 정할지가 고민이다. 어떤 장소에서 다른 장소로 이동하는 데에는 비용이 발생하는데 만약 방문하는 순서를 잘못 정하게 되면 알바비로 받은 돈을 모두 이동비용으로 사용하고 눈물을 흘릴지도 모른다. 태현이가 물건을 모두 배달하고 회사로 돌아오기 위한 최소의 비용을 계산하는 프로그램을 작성해 주자. 입력 형식 첫 줄은 배달해..
-
AVL 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 9. 20. 17:45
AVL 트리 이진 검색 트리를 기반으로 노드에 Balance Factor(이후 BF)를 추가하여 BF의 상태에 따라 트리의 균형을 유지한다. ※ AVL 트리는 노드의 수가 n일 때 최대 깊이가 Ο(logn)이 되게 된다. AVL 트리의 개념 기본적으로 삽입과 삭제는 이진 검색 트리의 알고리즘을 그대로 따르며 이후 BF에 따라 보정하는 작업을 진행하여 트리의 균형을 유지한다. BF는 노드의 왼쪽 서브 트리의 깊이와 오른쪽 서브 트리의 깊이의 차이이다. 정상 상태일 때 BF의 범위는 [-1, 1]이 되게 되며 노드의 삽입 혹은 삭제를 통해 이 범위를 넘게 되면 균형이 무너진 것으로 판단한다. AVL 트리의 회전 알고리즘 BF가 무너진 노드를 x, x의 자식을 c, c의 자식을 c²라 하면 회전이 필요한 경우..
-
유니티 화면 비율 고정 처리...5일지 2021. 9. 20. 13:12
WinAPI 마우스 처리 함수 마우스의 상태를 가져오는 함수들을 찾아보면 다음과 같은 종류가 존재한다. GetCursor 커서의 핸들을 반환한다. GetCursorInfo 커서의 CursorInfo(커서 핸들, 커서 좌표) 구조체를 반환한다. GetCursorPos 커서의 좌표를 반환한다. GetIconInfo 주어진 커서 혹은 아이콘의 이미지를 반환한다. LoadCursorA 변수 중 hInstance를 null로 하고 원하는 커서 모양의 번호를 입력하면 미리 정의된 커서의 핸들을 반환한다. 이상의 함수에서 얻을 수 있는 정보 중 그나마 처리할 만한 건 GetCursor로 현재 커서를 가져온 뒤 LoadCursorA로 Resize와 관련된 커서의 핸들을 가져와 비교하여 현재 화면 크기 변경이 진행되고 ..
-
JUNGOL/Intermediate_Coder/백트래킹-DFS/1889 : N Queen코딩 테스트/JUNGOL 2021. 9. 19. 23:12
Intermediate_Coder/백트래킹-DFS/N Queen 문제 체스에서 queen의 가로, 세로, 대각선 방향으로 어느 곳이나 한 번에 움직일 수 있다. 즉 다음과 같은 체스판에서 queen이 X라고 표시된 위치에 있을 때, 그 다음 queen이 움직여 갈수 있는 부분은 어둡게 칠해진 부분 중의 하나이다. N X N 크기의 정방형 체스판이 주어졌다. 우리는 거기에 N개의 queen을 배치하려고 하는데, 모든 queen들은 서로 잡아먹을 수 없어야 한다. 그렇다면 queen들을 어떻게 배치해야만 할까? 가능한 모든 경우의 개수를 출력한다. 입력 형식 queen의 수 N(1≤N≤13)을 입력 받는다. 출력 형식 N X N의 체스판에서 N개의 queen들이 서로 잡아먹지 않는 위치로 놓을 수 있는 방법..
-
유니티 화면 비율 고정 처리...4일지 2021. 9. 19. 22:59
WinAPI에서 드래그 종료를 체크할 방법에 대한 고민 드래그 종료를 감지하는 게 유니티에는 당연하게 존재하지 않으며 이것을 체크하기 위해 WinAPI를 사용해야 했다. 먼저 떠올린 건 콜백 이벤트. WinAPI에는 다양한 이벤트가 존재하고 해당 이벤트를 전달받은 뒤 수행할 내용을 따로 작성할 수 있기 때문에 해당 내용을 찾아봤다. c++ - WinAPI. Check if window resizing has been finished - Stack Overflow WinAPI. Check if window resizing has been finished I've got C++ application (used for share application's window via network). I need to ..