분류 전체보기
-
JUNGOL...125일지 2021. 8. 30. 16:30
Intermediate_Coder/자료구조/불쾌한 날(Bad Hair Day) 문제 농부 시현이의 N(1≤N≤80,000)마리의 소들은 "bad hair day"를 맞이하였다. 각 소들이 자신들의 촌스런 머리 모양을 부끄러워 하자, 시현이는 소들이 다른 소들의 머리 모양을 얼마나 알 수 있는지를 알고자 했다. i번째 소들은 키가 hi(1≤hi≤1,000,000,000) 이며, 동쪽(오른쪽)을 바라보고 서있다. 따라서, i번째 소는 자신의 앞 ( i+1, i+2,...)의 소들의 머리 모양만 볼 수 있으며, 앞에 자신의 키보다 작은 소들만 볼 수 있다. 다음 예제를 고려해보자: ()의 숫자는 키를 나타낸다. 1번 소는 2,3,4번소의 머리 모양을 볼 수 있다. 2번 소는 어떤 소의 머리 모양도 볼 수 없..
-
알고리즘...43일지 2021. 8. 30. 15:57
AVL 트리 구현 준비 이진 검색 트리를 기반으로 AVL 트리를 구현하기 위해 필요한 정보를 추가한다. AVLTree.h #pragma once #include "../Common.h" /// /// AVL 트리에 사용할 노드 /// struct AVLNode { AVLNode() : data{ 0 }, bf{ 0 }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} AVLNode(int data) : data{ data }, bf{ 0 }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} void Clear() { data = 0; parent = nullptr; left = nullptr; righ..
-
알고리즘...42일지 2021. 8. 29. 12:31
AVL 트리의 회전 레드 블랙 트리의 회전의 경우 자식 노드를 신경 써서 옮겨줘야 했으나 AVL 트리의 회전은 균형이 무너진 경우 진행하게 되므로 자식 노드가 존재하지 않는 상황에 진행된다. 이때, BF가 무너진 노드를 x, x의 자식을 c, c의 자식을 c²라 하면 회전이 필요한 경우는 다음과 같이 구분된다. c가 x의 왼쪽 자식이고, c²가 c의 왼쪽 자식인 경우(LL) x를 오른쪽 회전 c가 x의 오른쪽 자식이고, c²가 c의 오른쪽 자식인 경우(RR) x를 왼쪽 회전 c가 x의 왼쪽 자식이고, c²가 c의 오른쪽 자식인 경우(LR) c를 오른쪽 회전 후 x를 왼쪽 회전 c가 x의 오른쪽 자식이고, c²가 c의 왼쪽 자식인 경우(RL) c를 왼쪽 회전 후 x를 오른쪽 회전 ※ AVL 트리의 회전 명..
-
JUNGOL...124일지 2021. 8. 29. 01:27
Intermediate_Coder/분할정복/제곱수 출력 문제 X를 Y번 곱한 값을 찾는 프로그램을 작성하라. 결과가 클 수 있기 때문에 결과 값은 20091024로 나눈 나머지를 출력하라. 입력 형식 입력의 첫 번째 줄에는 X와 Y가 입력된다. X와 Y는 모두 0 이상 231-1 이하의 정수이다. 출력 형식 X를 Y번 곱한 값을 20091024로 나눈 나머지를 출력하라. 단, 0를 0번 곱한것은 편의상 1로 정한다. 입력 예 2 10 출력 예 1024 PrintSquare.h #include class PrintSquare : public Base { private: long long SquareModuler(long long x, long long pow); }; PrintSquare.cpp void ..
-
JUNGOL...123일지 2021. 8. 28. 15:42
Intermediate_Coder/분할정복/제곱수 출력 문제 X를 Y번 곱한 값을 찾는 프로그램을 작성하라. 결과가 클 수 있기 때문에 결과 값은 20091024로 나눈 나머지를 출력하라. 입력 형식 입력의 첫 번째 줄에는 X와 Y가 입력된다. X와 Y는 모두 0 이상 231-1 이하의 정수이다. 출력 형식 X를 Y번 곱한 값을 20091024로 나눈 나머지를 출력하라. 단, 0를 0번 곱한것은 편의상 1로 정한다. 입력 예 2 10 출력 예 1024 PrintSquare.h #include class PrintSquare : public Base { private: long long PrintSquareModuler(long long x, long long pow); }; PrintSquare.cpp ..
-
알고리즘...41일지 2021. 8. 28. 02:54
AVL 트리 기본 개념 이진 검색 트리의 삽입 알고리즘에 따라 삽입을 진행하면 삽입된 노드의 조상 노드들은 균형이 깨지게 된다. 불균형 상태는 각 노드가 가진 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이를 비교하여 높이의 차이가 1보다 커지게 된 경우를 말하며 이때 비교 결과 값을 Balance Factor(이후 BF)라고 한다. 위와 같이 각 노드가 가진 BF의 값이 [-1, 1]의 범위로 존재하는 경우엔 트리의 균형이 잘 잡힌 상태로 본다. 이 상태에서 15를 삽입하고 BF를 확인하면 14의 BF를 보면 -2가 되게 되며 이 경우 문제가 발생한 것으로 판정하게 된다. 더보기 참고문헌 Wikipedia.AVL tree yoongrammer.(2021.04.20).[자료구조] AVL 트리(Tree)
-
JUNGOL...122일지 2021. 8. 27. 14:05
Intermediate_Coder/분할정복/제곱수 출력 문제 X를 Y번 곱한 값을 찾는 프로그램을 작성하라. 결과가 클 수 있기 때문에 결과 값은 20091024로 나눈 나머지를 출력하라. 입력 형식 입력의 첫 번째 줄에는 X와 Y가 입력된다. X와 Y는 모두 0 이상 231-1 이하의 정수이다. 출력 형식 X를 Y번 곱한 값을 20091024로 나눈 나머지를 출력하라. 단, 0를 0번 곱한것은 편의상 1로 정한다. 입력 예 2 10 출력 예 1024 PrintSquare.h #include class PrintSquare : public Base { private: long long PrintSquareModuler(long long x, long long pow, long long result = 1..
-
알고리즘...40일지 2021. 8. 26. 18:45
레드 블랙 트리 삭제 메서드 구현 RedBlackTree.h #pragma once #include "../Common.h" enum class NodeColor { Red, Black }; /// /// 레드 블랙 트리에 사용할 노드 /// struct RedBlackNode { RedBlackNode() : data{ 0 }, color{ NodeColor::Red }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} RedBlackNode(int data) : data{ data }, color{ NodeColor::Red }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} void Clear(..