대엉코딩

www.acmicpc.net/problem/1715

1. 풀이방법

- 작은 순서대로 정렬하여 카드 묶음을 묶어나가면 된다.

- 주의할 점은 처음에만 정렬하고 앞쪽부터 연산 한다고 해결되는 것이 아니다

- 만약에 20 30 40 45 70 이 있을 떄 20+30=50이 되고 연산 순서를 그대로 하면 50 40 45 70 이 된다.

- 이러면 50+40이 먼저 계산 되므로 분명 오답을 가지고 올 것이다.

- 그럼으로 한번의 연산을 할 때마다 계산을 앞으로 해야할 배열들은 정렬되어 있어야 한다.

2. 주의사항

- 위의 로직을 처음에 그대로 vector와 sort로 구현하였다...물론 답은 맞겠지만 입력사이즈를 고려하면 시간초과가 뜬다.

  (매 단계마다 sort를 할 경우)

- 그래서 priority_queue 우선순위 큐를 이용하였다 <오름차순으로> 그러면 단계마다 합친 결과를 push 할 때 정렬 되

- 어 큐에 들어가므로 sort를 할 필요가 없다.

- 한번에 두개를 큐에서 꺼내고 그 합을 다시 넣어주므로 반복문은 N번이 아닌 N-1번만 돈다.

3. 나의코드

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

int N;
priority_queue<int, vector<int>, greater<int>> carddeck;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int card;
	for (int i = 0; i < N; i++) {
		cin >> card; carddeck.push(card);
	}
	int minsum = 0;
	int tmpcard1, tmpcard2;
	for (int i = 0; i < N-1; i++) {
		tmpcard1=carddeck.top();
		carddeck.pop();
		tmpcard2 = carddeck.top();
		carddeck.pop();
		minsum += (tmpcard1 + tmpcard2);
		tmpcard2 += tmpcard1;
		carddeck.push(tmpcard2);
	}
	cout << minsum;
	return 0;
}

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;
}

www.acmicpc.net/problem/10815

1. 풀이방법

- 일단 문제 input사이즈를 보면 크다 500,000

- 만약 두번의 for문을 돌려서 탐색을 할경우 최악의경우 250,000,000,000 인데, 

- c++기준 대략 1초에 1억번의 연산을 한다고 가정하여도, 시간제한 2초를 훨씬 넘기 때문에 

- 선형탐색을 사용해서는 안된다 ----->이진탐색(binary search)를 사용하자.

- 오름차순으로 sorting을 한 후 시작한다.

2.주의사항

- 전형적인 이진탐색문제로서 이론을 그대로 코드로 옮겨주면 되겠다.

- 조건을 살짝씩 빼먹을 경우 무한루프에 자주 빠지니 조건을 꼼꼼하게 체크 해주자....>!

3. 나의코드

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

int N, M;
int Narr[500001];
int Marr[500001];

void inputs() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Narr[i];
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> Marr[i];
	}
}
void bs(int start,int end,int searchnum) {
	int mid = (start + end) / 2;
	if (Narr[mid] == searchnum) { cout << 1 << " "; return; }
	if (mid >= end) { cout << 0 << " "; return; }
	if (Narr[mid] > searchnum) { bs(start, mid-1, searchnum); }
	if (Narr[mid] < searchnum) { bs(mid+1, end, searchnum); }
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	sort(Narr, Narr+N);
	for (int i = 0; i < M; i++) {
		bs(0, N - 1, Marr[i]);
	}
	return 0;
}

0. 알아보기전에....

 - 지금까지  insertion sort,  quick sort, merge sort, heap sort 등....

    에 대해서 알아보았습니다.

 - 이러한 sorting 알고리즘들은 모두 두 수의 대소비교(key value에 대한) 를 하여 sort를 하는 class 의 알고리즘입니다.

 - 두 수의 크기비교를 통해 정렬하는 알고리즘은 최적의(optimal) 알고리즘은 O(nlogn) 이라는 것도 확인 하였습니다.

1. radix sort (기수정렬)

 - 먼저 언급하자면 , 이 sorting 알고리즘은 O(n) 이라는 수행시간을 가집니다.

 - ?????? 최적은 O(nlogn) 이라는 것도 증명 하였는데 어떻게 O(n)에 수행하는 sorting 알고리즘이?!

 - 그 이유는  크기비교가 아닌 다른 연산을 사용하기 때문에 class가 다른 algorithm이기 때문입니다.

 - 즉 , 두 수간의 대소비교를 통한 어떠한 방법으로 정렬을 하는 것이 아니라는 뜻이죠

2. Strategy 

 - 그럼 어떻게 할 것인가.......?

 - 선생님이 50명의 학생의 시험지를 점수별로 정렬을 시키고 싶은 상황이라고 해보자. (점수는: 0~99 <편의상>라 하자)

 - 일단, 0.1.2.3.....9 까지가 적혀있는 박스 10개를 준비하자.

 - 그리고 1의자리 수 를 기준으로 박스에 담자.

 - 그 후 0번 박스부터 9번 박스까지 들어있는 종이를  다시 하나의 뭉텅이로 합친 후

 -  이제 10의자리 수 를 기준으로 다시 0~9번 박스에 나누어 담자.

 - 모든 점수는 최대 2자리 수 이므로 2번의 이 작업을 수행 하면 sorting이 완료 된 상태이다.

 - 여기서 생각해보면 박스에 맞는 숫자를 담았을 뿐 두 수끼리의 비교하는 연산은 수행하지 않았다 !

 - 이렇게 할 수 있었던 이유는 무엇 일까? 자료에 대한 정보가 더 있었기 때문에 가능했다.

    (이 경우에는 점수 의 범위를 추가적으로 알고 있었다.)

 - **stable**

  : 이 알고리즘의 핵심 property 중 하나는 위에서(위의 상자부터) 순서대로(차례대로) 처리한다는 것

    이럴경우 stable하다고 이야기 한다.

    (즉, 같은 key값을 가진 input data가 여러개 있을 때 그 때 순서가 입력 순서와 같을 것을 보장한다는것)

     --각 단계를 수행 할 때 ! (각 단계는 stable 해야한다.)

3. Algorithm

 <list>이용

4. Analysis

 - distribute  --> Θ(n)  (숫자보고 통에넣고.....n번 수행)

 - combine  -->Θ(n) (list 내용을 하나로)

 - 이 작업을 몇번 수행 하느냐? 4자리수이면 4번....... 즉 자리수 (d) 만큼 (linear in n)

 - O(n)

** divide and conquer(분할 정복) 은 알고 들어가야한다. --> 퀵소트가 사용하는 기법

1.Quick-sort

 - random 한 속성을 가진 형태의 input을 정렬하는 데 성능이 매우 좋다.

 - pivot 이라는 하나의 element를 기준으로  L(less), E(equal), G(greater)로 나눈다 (분할)

 - 나눈후  L 과 G(E U G) 로 다시 recursive하게 sort를 수행한다.

2. Worst Case

 - 최악의 경우 pivot을 잡고 분류를 하는 과정에서 L,G를 나누는데 계속 한쪽으로 몰리는 경우 이다

 - 이럴경우 n-1번을 나누게 되고 (depth = n), 각 단계에서 약 n, n-1, n-2 ....... 1까지 진행되므로

 - running  time의 합은 n+(n-1)+ ... +1 이므로 최악의 경우 O(n^2) 이다.

3. Average Case

 - 평균분석의 경우 O(n*logn) 이다.

 - 최악의 경우는 느리지만 평균분석은 상당히 빠르다.

4. 알고리즘

-partion 별 

5. 특징

 - partion을 한번 하면 pivot은 자신의 위치를 찾는데 그 자리가 최종 출력 위치이다.

 - in-place 로 구현 가능 (추가적으로 사용하는 메모리가 tmp변수 하나 정도로 O(1) 정도

6. 구현

1. 삽입정렬(insertion sort) 란?

 - 각 단계 마다 하나의 원소를 그 앞의 원소들과 비교를 해서 자신의 자리를 찾아 가는 것이다.

 - 첫 번째 원소는 처음에는 혼자이므로 그 자체로 정렬된 상태이고 두번째 원소부터 비교를 하며 정렬을 한다

 - 첫번째 와 두번째 원소를 비교를 제대로 했다면 3번째 원소를 정렬 할때는 3번째 원소 앞쪽은 정렬이 되어있는 상태일 것 이다.

 - 그럼 세번째 원소가 이제 자신의 자리를 찾으러 갈 것이고 네번째 원소가 비교를 시작하려 할 때는 앞의 3개의 원소는 정렬된 상태

 - 그리고 비교를 해가면서 원소의 자리가 바뀔 수 있기 때문에 자신의 차례때 배정받은 위치가 최종출력의 위치는 아니다.

2. 최악의 경우 (worst case) 

 - 키 오름차순 정렬을 하고 싶다고 가정했을 때, 계속 키가 제일 작은 사람이 차례대로 들어오는 것이다.

   ( 즉, 입력이 역순으로 정렬되어 있을 때)   -->  Θ(n^2)

3. 평균의 경우 (Average Analysis)

 - 각 자리에 들어갈 확률은 모두 같다고 가정 (1/i+1) -->>내가 원소로 들어갔을 때 그자리도 포함 i+1

 - step i에서 평균 i/2의 연산

 - 평균 분석의 경우 대략 n^2/4 정도 이다. 

4.특징

 - input의 크기가 적을 때에 한정해서 매우 빠르다고 알려져있다.

 - 한번에 잘못된 위치를 하나만 수정할 수 있는 제한적인 조건 내에서는 최적의 알고리즘 이다.

5. 구현 (key값을 그냥 입력받은 int의 수라고 가정하고 , 그냥 vector<int>의 각 index에 해당하는 값을 통한 정렬을 구현)

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랑 더해서 넣으면 됩니다.

<필기>

<코드>