대엉코딩

www.acmicpc.net/problem/10825

1. 풀이방법

- algorithm 라이브러리 내에 정의되어있는 sort를 사용하였습니다.

- 이를 사용한다는 가정하에 cmp함수를 원하는 대로 작성할 수 있는지를 물어보는 문제인 것 같습니다.

- 조건 그대로 작성해주시면 됩니다.

- 코드의 길이를 줄일 수 있지만 저는 보통 아래의 코드의 형식을 벗어나게 작성하지는 않습니다.

- 이 문제처럼 이것만을 물어보기 위한 경우가 아닌 경우 보통 이렇게까지 분류조건이 많이 달리지는 않는데 그랬을 때

  코드 한 두줄 정도 더 길지만 저 같은 경우 의미 파악이 그게 더 분명히 되서 실수할 가능성도 줄고 해서 그대로 작성

  하는 편입니다.

2. 주의사항

- 증가순, 감소순 정확히 구별

3. 나의코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

int N;
struct studentscore {
	int kor; int eng; int mat;
	string name;
};
vector<studentscore> studentarr;

bool cmp(studentscore s1, studentscore s2) {
	if (s1.kor > s2.kor) { return true; }
	else if(s1.kor==s2.kor){
		if (s1.eng < s2.eng) return true;
		else if (s1.eng == s2.eng) {
			if (s1.mat > s2.mat) return true;
			else if (s1.mat == s2.mat) {
				if (s1.name< s2.name) return true;
				return false;
			}
			else return false;
		}
		else return false;
	}
	else return false;
}

void inputs() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		studentscore tmps;
		cin >> tmps.name >> tmps.kor >> tmps.eng >> tmps.mat;
		studentarr.push_back(tmps);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	sort(studentarr.begin(), studentarr.end(), cmp);
	for (int i = 0; i < studentarr.size(); i++) {
		cout << studentarr[i].name << "\n";
	}
	return 0;
}

1. 기본 개념

 - 만약 순서대로 정렬된 두개의 배열 이 있다고 생각해보자.

 - 이 두 배열을 합쳐서 정렬된 배열을 얻고자 할때는 첫번째 elemet끼리의 비교만을 반복하면 된다.

    (둘 중 하나의 배열이 끝날때 까지만)  ---> 즉 가장 많이 비교할때는 (지그재그) n-1, 적게는 n/2 이다.

//지금 까지 설명한 것이 병합(merge) 과정이다.

2. mergesort의 대표적인 특징 

 - divide and conquer 전략을 이용하는 대표적인 알고리즘이다.

 - 원소들 끼리 대소를 비교해서 정렬하는 알고리즘 중에서는 최적의 알고리즘 이다.(O(nlogn))

3. MergeSort Strategy

 - 입력받은 배열을 divide 한 후 merge 한다. 

 - (merge를 하는 과정에서의 아이디어는 1에서 설명한 내용과 같다.)

 - 모두 merge를 하면 sort가 완료된 상태이다.

 - divide를 완료한 상태에서 sort를 진행하면서 Merge 하면서 올라오므로 merge가 완료 됬다면 sorted 된 상태이다.

4. Algorithm : Mergesort

5. Analysis

 위의 의사 코드를 확인 하고 분석해보면 이러한 점화식이 나온다.

 W(n) =O(1)+O(1)+W(n/2)+W(n/2)+Wmerge(n)

 (by MasterTheorem)

 =====>>> Θ(nlogn)

6. 구현

결과화면

https://www.acmicpc.net/problem/1932

- 삼각형의 위에서 부터 길을 만들어 각 수 를 더하였을 때 가장 큰 값이 되도록 하는 길을 쫓아가서

- 그 값을 출력하는 문제입니다.

- vector 두개를 이용하여 들어오는 값과 vector 0과 들어오는 값을 비교하여 vector 1에 저장하고

- 그다음 들어오는 값들은 vector 1과 들어오는 값들을 비교하고 더해 vector 0에 저장하는 작업을 반복한 후

- 물론 작업이 끝난 배열은 초기화를 해야 합니다 (그 다음 줄에서 넣어야하므로)

- 마지막에 n의 값에 따라서 vector 0 또는 vector 1 을 내림차순 으로 정렬 한후 index 0의 값을 출력하였습니다.

- 값을 더하고 저장하고 더하고 저장하고 를 반복하는 작업이라고 생각 하시면 될거 같습니다.

- 그리고 각 입력의 처음과 마지막은 비교를 할 필요없이 바로 0번쨰 index그리고 마지막 index랑 더해서 넣으면 됩니다.

<필기>

<코드>

https://www.acmicpc.net/problem/10610

- 일단 정수론을 저도 잘하지 않았지만 아주 기본인 3의배수 이려면 각자리 숫자의 합이 3의 배수여야 한다는 것.

- 그리고 출력 부분에 있어서 그리디 를 통해서 큰수부터 내림 차순으로 출력하면 된다는 것

- 그리고 입력은 매우 큰 숫자일 수 있으므로 문자열을 이용해야 한다는 것 

(정수 형을 나타내는 기본 자료형으로는 입력을 받을 수 없다.)

<필기>

<코드>

https://www.acmicpc.net/problem/2217

-문제를 읽어보고 예시를 한번 그려보았더니 로프가 버틸 수 있는 중량의 

-입력 값이 어떻게 주어지냐에 따라서 들 수 있는 최대 무게가 많이 달라질 수 있는 문제였습니다.

-몇개의 로프를 선택 하던 간에 그 로프들로 들 수 있는 중량의 최대 무게는

- (로프 중 가장적은 무게를 들수 있는 중량) * (로프의 개수) 입니다.

-로프  n개 선택 한다고 치면 큰 무게를 들 수 있는 로프를 두고 적은 무게를 들 수 있는 로프를 선택할 이유 가 없으므로

-큰것들 부터 n개를 선택 해 가면서 반복문을 1회 돌면서 그 값들을 비교하면 되는 문제 였습니다.

- 내림차순으로 정렬 후 앞에서 부터 로프의 개수를 하나씩 늘려가며 최대값만 저장 후 출력하였습니다.

<필기>

<코드>

https://www.acmicpc.net/problem/1181

정렬에 관련된 문제입니다.

sorting을 하면서 조건을 조금씩만 걸어서 주면 되는 문제이구요

compare 을 선언해서 sort를 하는데 조건으로 사용하였고

같은 문자가 있는경우 생략해서 출력해야 하는데 이는 입력을 받을때나 또는 따로 비교를 해서 제거를 하려 하면

비교를 하는데 있어서 따로 시간을 또 사용해야 할 것 같아서

출력을 할때 비교하여 생략하는 방식으로 구현하였습니다.

https://www.acmicpc.net/problem/1427

간단한 정렬문제!

https://www.acmicpc.net/problem/16212

기본적인 정렬을 할줄 아는지 물어보기 위한 문제 인듯 싶네요

c++에서 정렬은 

sort(arr.begin(),arr.end()) 이렇게 하고

내림차순, 오름 차순이냐에 따라 greater<int> () 를 파라미터로 추가 해주느냐 마느냐 결정하시면 될 듯 합니다.