JUNGOL
-
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..
-
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는 마..
-
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는 마..
-
JUNGOL...116일지 2021. 8. 17. 17:45
Intermediate_Coder/분할정복/Tutorial: STL Sort 3 문제 지난 시간에 sort()를 이용하여 배열을 오름차순과 내림차순으로 정렬하는 방법을 배웠다. 오늘은 구조체를 이용하여 직접 만든 자료형으로 선언된 배열을 원하는 기준에 따라 정렬하는 방법을 배워보자. 우선 설명에 들어가기 전에, 구조체로 선언된 배열을 정렬한다는게 무슨 말인지 생각해 보자. 예를 들어, 5명의 학생들의 이름과 점수를 입력 받아서, 점수가 낮은 순서부터 높은 순서대로 출력하는 프로그램을 작성한다고 생각해보자. 제일 간단한 방법은 역시 우리가 써오던 sort()함수를 사용하여 정렬하는 것이다. 아래 코드를 보자. (참고로 아래 코드는 컴파일되지 않는다.) - 컴파일되지 않는 코드 - #include ///와 ..
-
JUNGOL...115일지 2021. 8. 15. 18:10
Intermediate_Coder/분항정복/Tutorial: Operator Overloading(연산자 오버로딩) 문제 다음 단계인 구조체 정렬로 넘어가기 전에, C++ 문법 중 다소 난해해서 생략했던 부분 하나를 소개하고 넘어가려고 한다. 아래 코드를 따라 치고 실행시켜보자. 여러분들이 혹여나 당황할까 해서 미리 말하는데, 아래 코드는 컴파일되지 않는게 정상이다. /// 에러가 나는 코드 /// #include using namespace std; struct Student { char name[20]; int age; double height; }; int main() { Student s1 = {"멋쟁이" , 17 , 178.5}; Student s2 = {"이쁜이" , 18 , 165.9}; i..
-
JUNGOL...114일지 2021. 8. 12. 12:55
Intermediate_Coder/분할정복/Tutorial: STL Sort 2 문제 이전 시간에는 배열을 오름차순으로 정렬하는 함수인 sort()에 대하여 알아보았다. 이번 시간에는 내림차순으로 정렬하는 방법을 배워 보자. 방법 1. reverse() 함수 사용. #include #include using namespace std; int main() { int i; int arr[8] = {1,9,9,4,1,1,0,8}; sort(arr+0,arr+8); reverse(arr+0,arr+8); for(i = 0 ; i < 8 ; i++) printf("%d ", arr[i]); return 0; } 실행결과 9 9 8 4 1 1 1 0 reverse() 함수는 "뒤집다" 라는 뜻에 맞게, 배열의 앞뒤..
-
JUNGOL...113일지 2021. 8. 11. 14:30
Intermediate_Coder/분할정복/Tutorial : 합병(병합)정렬(Merge Sort) 문제 [합병(병합)정렬 (Merge Sort)] 머지소트는 폰 노이만(John von Neumann)이 1945년 개발한 알고리즘이다. 원소들간의 비교을 통하여 정렬하는 비교기반정렬 알고리즘이다. 원소들 중에 같은 값이 있는 경우 정렬후에도 이들의 순서가 유지되는 안정 정렬에 속한다. N개의 데이터를 정렬할 때, 시간복잡도는 O(N * logN)이 보장된다. 정렬의 각 과정은 분할 -> 정복 -> 결합과정으로 이루어진다. [합병정렬(오름차순) 알고리즘 프로세스] 정렬할 배열을 A[], 구간의 시작 인덱스(배열번호)를 low, 끝 인덱스를 high 라고 하자. 1. low >= high 라면 현재 ..