분류 전체보기
-
JUNGOL...121일지 2021. 8. 25. 16:08
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 ..
-
알고리즘...39일지 2021. 8. 25. 14:57
레드 블랙 트리 삽입 메서드 구현 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(..
-
JUNGOL...120일지 2021. 8. 24. 21:40
Intermediate_Coder/분할정복/색종이 만들기2(4진트리) 문제 재우는 분할정복을 공부중이다. 그래서 1335:색종이 만들기 문제를 풀었다. 좀 더 공부하고 싶은 재우는 다음과 같은 문제를 생각해 보았다. 한 변의 길이가 2의 제곱수인 정사각형에 주어질 때, 주어진 정사각형에 포함된 숫자가 모두 0이면 0, 주어진 정사각형에 포함된 숫자가 모두 1이면 1 로 나타낸다. 그렇지 않고 주어진 정사각형에 포함된 숫자가 0, 1이 함께 있다면 대문자 X로 그 영역을 나타내고 해당 영역을 4등분하여 재귀적으로 호출하여 같은 규칙을 적용한다. 4등분한 영역의 호출 순서는 좌상, 우상, 좌하, 우하 이다. 예를 들면 아래와 같은 정보가 주어지면 8 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1..
-
알고리즘...38일지 2021. 8. 24. 21:29
레드 블랙 트리 삽입 메서드 구현 진행 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 Cle..
-
JUNGOL...119일지 2021. 8. 23. 19:09
Intermediate_Coder/분할정복/색종이 만들기(영역구분) 문제 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지..
-
JUNGOL...118일지 2021. 8. 19. 16:20
Intermediate_Coder/분할정복/Tutorial: STL Sort 4(심화) 문제 STL(Standard Template Library-표준 템플릿 라이브러리)는 알고리즘(Algorithm), 컨테이너(container), 함수객체(functions), 반복자(iterator)로 구성된 C++을 위한 라이브러리(Library) 이다. STL에는 많은 유용한 내용들이 있지만 여기서는 헤더에 포함된 sort함수를 집중하여 다루어 본다. [ std::sort ] 0. 함수 원형은 두 가지 포맷이 있다. (1) void sort (RandomAccessIterator first, RandomAccessIterator last); sort(구간의 시작 포인터, 구간의 끝 포인터); // last는 마..
-
알고리즘...37일지 2021. 8. 19. 16:04
레드 블랙 트리를 재정렬해야 하는 경우 자식 노드를 x, 부모 노드를 p, 형제 노드를 s, 형제의 왼쪽 자식을 l, 형제의 오른쪽 자식을 r이라고 할 때 다음과 같은 경우들이 존재한다. p가 레드, s는 블랙인 경우 Case 1-1 Case 1-2 Case 1-3 p가 블랙 Case 2-1 Case 2-2 Case 2-3 Case 2-4 ※ Case 1-2와 Case 2-2 그리고 Case 1-3과 Case 2-3은 p의 색상이 처리 방법에 영향을 미치지 않으므로 통합한다. 각각의 경우에 처리하는 방법은 다음과 같다. Case 1-1 p와 s의 색상을 맞바꾼다. Case *-2 p를 중심으로 왼쪽으로 회전시키고, p와 s의 색상을 바꾼 다음 r의 색상을 레드에서 블랙으로 바꾼다. Case *-3 s를 ..
-
JUNGOL...117일지 2021. 8. 18. 14:21
Intermediate_Coder/분할정복/Tutorial: STL Sort 4(심화) 문제 STL(Standard Template Library-표준 템플릿 라이브러리)는 알고리즘(Algorithm), 컨테이너(container), 함수객체(functions), 반복자(iterator)로 구성된 C++을 위한 라이브러리(Library) 이다. STL에는 많은 유용한 내용들이 있지만 여기서는 헤더에 포함된 sort함수를 집중하여 다루어 본다. [ std::sort ] 0. 함수 원형은 두 가지 포맷이 있다. (1) void sort (RandomAccessIterator first, RandomAccessIterator last); sort(구간의 시작 포인터, 구간의 끝 포인터); // last는 마..