그레고리로그

사용한 언어 C++ 사용한 알고리즘 Merge sort #include using namespace std; struct Student{ string name; int kra; int eng; int math; }; void MergeSort(Student studentList[], int start, int end); void Merge(Student studentList[], int start, int mid, int end); char CompareName(string l_name, string r_name); Student sorted[100000]; int main(){ ios_base::sync_with_stdio(false); //이거 없으면 176ms, 있으면 84ms int student..

코드 전문 Merge sort 복습을 위해 Merge sort로 구현했다. #include using namespace std; #define MAXSIZE 100000 struct Point{ int x; int y; }; void MergeSorting(Point* list, int start, int end); void Merge(Point* list, int start, int mid, int end); Point sorted[MAXSIZE]; int main(){ ios_base::sync_with_stdio(false); int pointCnt; cin >> pointCnt; Point* list = new Point[pointCnt]; // 좌표 입력 for(int i=0;i> list[i]..

● 가능한 정렬 알고리즘과 불가능한 알고리즘 백준 2751번은 그냥 아무 정렬을 사용하면 시간초과가 나올 수 있다. 2750번의 경우 같은 정렬이라도 입력값의 개수가 N(1 ≤ N ≤ 1,000)이다. 그러나 2751번은 입력값의 개수가 N(1 ≤ N ≤ 1,000,000)이다. 즉, 2750의 경우 최악의 시간복잡도가 O(n^2)이어도 괜찮다. 그러나 2751은 최악의 경우가 O(n^2)이라면 정말 오래걸리기 때문에 시간초과가 될 것이다. 따라서 최악의 경우가 O(nlogn)인 정렬알고리즘을 사용해야한다. - 불가능한 정렬 : 버블정렬 (Bubble sort), 삽입정렬(Insertion sort) , 퀵 정렬(Quick sort) - 가능한 정렬 : 합병정렬 (Merge sort), 힙 정렬(Heap..

8393 #include using namespace std; int main(){ int a; int total = 0; cin >> a; for(int i=1;i

1924 조건문으로 해도 상관없었지만 문자열 배열을 통해 구현하고 싶었다. 문자열 배열 생성하는 방법을 몇가지 정리해 보자. 1. std::array 표준 라이브러리 소속 vector는 헤더 파일을 include 해야한다. std 네임스페이스 안에 들어있다. std::array str_arr = {"a", "b", "c", "d"}; 2. string arr[] string 클래스가 string 헤더파일 안에 있다. 헤더파일을 include 해야한다. std 네임스페이스 안에 들어있다. #include std::string str_arr[4] = {"a", "b", "c", "d"}; 3. char arr[][] char str_arr[4][20] = {"a", "b", "c", "d"}; 4. std:..

10952 #include using namespace std; int main(){ int a,b; while(1){ cin >> a >> b; if( a != 0 && b != 0) cout caseNum; for(int i=0;i> a >> comma >> b; cout caseNum; for(int i=0;i> a >> b; cout

10951 10951의 이슈는 test case를 얼마나 입력을 받을지 모른다는 것이다. 이런 경우 EOF를 감지해서 프로그램을 종료시켜야 한다. EOF는 End of File의 약자로, 파일의 끝을 의미한다. 개행문자나 공백문자처럼 EOF도 하나의 문자로, 맥의 경우 control + d 를 누르면 EOF를 입력할 수 있다. EOF는 c++에서 몇가지로 표현되는데 상수 -1로도 표현되고, EOF라고 써도 표현 된다. 10951에서는 몇개의 test case를 입력받은 후에 종료해야하는지 미리 정하지 않으므로 EOF가 입력되기 전까지 [test case 입력받기 > 값 계산 후 출력하기]를 반복해야한다. 입력받은 문자가 EOF인지 확인하는 방법에는 몇가지가 있다. 1. cin.eof() : cin을 통해..

2558 #include using namespace std; int main(){ int a,b; cin >> a; cin >> b; cout > caseNum; for(int i=0;i> a >> b; cout