대엉코딩

오늘은 완전탐색 문제를 풀다가 사용한 c++의 next_permutation 입니다.

사실 알고리즘 동아리를 할 때, 한번 설명을 들은 적이 있어 알고는 있었는데 대부분의 문제풀이 때 그냥 DFS 완탐 으로 모든 경우의 수를 구해서 문제를 풀어왔었는데요.

오랫만에 문제를 풀어서 그럴수도 있겠지만, 익숙치 않은 IDE 에서 짜다보니 코드가 길어질수록 미세한 실수도 많이 나오고 다른 디버깅 환경에서 그 실수를 찾아내기가 생각보다 오래걸려서 next_permutation도 제대로 알아보고 익숙해져볼 생각입니다.

1. 조건

- next_permutation은 정렬을 조건으로 합니다.

- 물론, 원하는 출력에 따라 조건을 변경해서 출력하면 됩니다.

- 기본적인 5개의 후보로 부터 모든 가능한 5개 사이즈의 조합을 구하는 경우,

   이 후보들은 모두 오름차순 정렬이 되어 있어야 합니다. ( ex - 1 2 3 4 5 )

1-1. 

 - 특수한 상황이지만 기존 배열(벡터)의 상태가 { 7, 5, 1, 2, 3 }일 경우,

   7과 5는 앞에 고정된 상태로 1,2,3 만 변경됩니다.

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	vector<int> arr_1{ 1,5,5,7 };

	do {
		for (int i = 0; i < arr_1.size(); i++) {
			cout << arr_1[i] << " ";
		}
		cout << "\n";
	} while (next_permutation(arr_1.begin(), arr_1.end()));
	cout << "\n";

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

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/1946

1. 첫 번째는 입력은 순위 입니다(점수가 아님)  --조심 !

2. 전 첫번째 제출한 코드는 시간초과가 되었습니다. 당연한 것이 최악의경우를 생각해보면

   입력을 고려해 보았을 떄 10000000000 이는 약 1억번 연산이 1초라고 계산해보면

   당연히 시간초과가 나올 수 밖에 없겠죠.

3. 그래서 우선 서류점수로 오름차순 정렬을 한후

   반복문을 돌리는데 이때는 전체를 다 탐색할 필요가 없이 본인보다 서류점수 우선순위가 높은 사람들

    (즉 본인보다 낮은 index)

   의 면접점수만 확인 하면 되기 때문에 입력이 커질경우 연산 횟수를 대폭 줄일 수 있습니다.

** 그리고 저 같은 경우 vector를 사용하였는데 시간적 측면에서 더 단축 하고 싶다면

    그냥 max값을 define 하여 그만큼의 배열을 잡아 버리는 것이 시간적 측면에서는 더 이득인 것 같더라구요 !

<시간초과 코드>

<맞춘 코드>

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

회의실 배정에 관한 문제이다.

그리디 알고리즘 에 해당하는 문제이다

(기준은 끝나는 시간!) 빨리 끝내고 다른 회의를 최대한 넣어야 하기 때문이다. 이는 조금만 생각해도 알수 있었다.

하지만 처음짠 코드에서 채점 87%정도에서 틀렸습니다 ! 를 많이 보았는데

내가 고려하지 않은 반례가 테스트케이스에 있다는 것이였는데... 찾는데 꽤 오래걸렸다.

그것은 바로 끝나는 시간만을 기준으로 정렬을 했기 때문 이였다.

예를 들면 시작/끝이 3/3 3/3 1/3 같은 경우 회의 3개를 진행할 수 있는 것인데

조건에서 파악하여 앞에 두개 3/3 3/3은 카운트 할 수 있었으나

3/3을 해버리면 currenttime을 3으로 바꾸어 버리기 때문에 1/3이 카운트 되지 않는다.

즉 끝나는 시간이 같다면 시작시간이 먼저인것을 앞에 두게 정렬을 하여야 한다.

<필기>

<코드>

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

그리디 알고리즘 기본문제 인 것 같다.

대기시간이 최소로 되게끔( 대기시간의 총합)

어쩌면 형평성 측면에서는 잘못되었다고도 할 수 있겠다..... 오직 효율성 만을.....

문제자체는 간단하고 쉽습니다.

오름차순 정렬을 시킨후 이전까지 걸렸던 시간과 그 사람이 걸리는 시간을 합을 더해서 

총 결과(합) 에 더해주고 그 자신이 걸리는 시간이 들어있던 배열에 그 자신을 포함한 걸린 시간을 넣어주면 되겠습니다.

<필기>

<코드>

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

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

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

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

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

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

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