대엉코딩

오늘은 완전탐색 문제를 풀다가 사용한 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/16235

1. 풀이방법

- 단순한 구현 문제입니다.

- 문제는 간단하고 이해도 어렵지 않지만, 시간제한이 0.3초 인 점을 감안하여야 합니다.

- 문제에서의 단계대로 차례차례 진행해줍니다.

2. 주의사항

- 전 처음에 시간제한 및 어린나이부터 진행되어야 한다는 문제를 보고 우선순위 큐를 생각해서 접근하였는데,

- 정답은 잘 뽑아내는 것 같으나, 시간초과가 계속 되어 결국 자료형을 vector로 바꿔서 봄에만 정렬을 하여 사용하였습니다.

- vector를 사용하자니, 죽은 나무를 뽑아내는 것이 문제였는데, vector는 index로 쉽게 접근이 가능하나 원하는 위치의데이터를 맘대로 뽑기는 어렵습니다.

- 그래서 양분이 부족해지는 지점이 딱 왔을 때, 그 이차원벡터배열의 맨뒤부터 양분/2를 더해주면서 pop_back() 해주었습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int n, m, K;
int ground[11][11]; // 양분의 양
vector<int> treeageset[11][11]; //나이 기준 정렬
int s2d2[11][11];
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
int tmpv[1001];
int presize[11][11]; 

void inputs() {
	cin >> n >> m >> K;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ground[i][j] = 5;
			cin >> s2d2[i][j];
		}
	}
	int x, y, z;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		treeageset[x][y].push_back(z);
	}
}
bool boundcheck(int x, int y) {
	return (x >= 1 && x <= n && y >= 1 && y <= n);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	for (int i = 0; i < K; i++) { //1년

		//봄
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (treeageset[j][k].empty()) continue;
				int tmpground = ground[j][k];
				ground[j][k] = 0;
				sort(treeageset[j][k].begin(), treeageset[j][k].end());
				int vsize = treeageset[j][k].size();
				for (int a = 0; a < vsize; a++) {
					if (tmpground >= treeageset[j][k][a]) {
						tmpground -= treeageset[j][k][a];
						treeageset[j][k][a]++;
					}
					else {
						for (int b = vsize - 1; b >= a; b--) {
							ground[j][k] += treeageset[j][k][b] / 2;
							treeageset[j][k].pop_back();
						}
						break;
					}
				}
				ground[j][k] += tmpground; //남은 양분+죽은나무의 양분
			}
		}


	//새로 추가되는 나무들은 번식시키지 않기 위해서
	for (int j = 1; j <= n; j++) { 
		for (int k = 1; k <= n; k++) {
			presize[j][k] = treeageset[j][k].size();
		}
	}
	//가을 번식
	for (int j = 1; j <= n; j++) {
		for (int k = 1; k <= n; k++) {
			for (int a = 0; a < presize[j][k]; a++) {
				if (treeageset[j][k][a] % 5 == 0) {
					for (int b = 0; b < 8; b++) {
						int nextx = j + dx[b];
						int nexty = k + dy[b];
						if (boundcheck(nextx, nexty)) {
							treeageset[nextx][nexty].push_back(1);
						}
					}
				}
			}
			ground[j][k] += s2d2[j][k]; //양분 보급
		}
	}
}
	int resultsum = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			resultsum += treeageset[i][j].size();
		}
	}
	cout << resultsum;
	return 0;
}

www.acmicpc.net/problem/17140

1. 풀이방법

- 구현 문제이고, 일단 문제를 이해를 잘해야합니다....

- 읽으면서도 이게 무슨말이지 싶고, 예시로 주어진 것들을 써보고 규칙을 정확히 이해해야 합니다.

- 읽으면서도 처음에는 숫자가 먼저 쭉 들어가고 등장횟수가 새로 배열에 들어가는 줄 알았으나 예시가 이상해서 보니

- (수, 등장횟수, 수, 등장횟수, 수 등장횟수...) 이런 순입니다

- 정렬순서를 구현했고 이차원배열로 max 범위로 잡아놓고 현재의 행의 수, 열의 수 를 관리하는 변수 두개를 두어

- 관리 하였습니다. 특별히 어려운 사항은 없었던 것 같습니다.

2. 주의사항

- 가끔 예제를 돌리다가 걸리는 사항인데, 저는 보통 n이면 0~n-1만큼을 사용합니다.

- 즉 문제에서 [r][c]를 원하면 저의 배열에서는 [r-1][c-1]의 값인거죠~!

- 여담이였고, 이 문제는 그냥 문제 자체만 잘 이해하면 되는 것 같습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int r, c, k;
int ground[101][101];
int hang = 3; //현재 행의 수
int yull = 3; //현재 열의 수
struct xx {
	int xnum;
	int totalcount;
};


void inputs() {
	cin >> r >> c >> k;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> ground[i][j];
		}
	}
}
bool compare(xx t1, xx t2) {
	if (t1.totalcount < t2.totalcount) return true;
	if (t1.totalcount == t2.totalcount) {
		if (t1.xnum < t2.xnum) return true;
		else return false;
	}
	else return false;
}

void Rcal() {
	int maxyull = 0;
	vector<int> tmpcount; //각 행의 수를 저장해두었다가 max-tmpcount[i] 만큼 0으로채우려고
	for (int i = 0; i < hang; i++) { //모든 행에 대하여
		int tmpyull = yull;
		vector<xx> xarr;
		for (int j = 0; j < tmpyull; j++) {
			if (ground[i][j] == 0) continue;
			bool c = false;
			for (int k = 0; k < xarr.size(); k++) { // 이미 있는지 확인
				if (ground[i][j] == xarr[k].xnum) {
					xarr[k].totalcount++; c = true; break;
				}
			}
			if (c == false) { //위에서 안걸러 졌으면
				xarr.push_back({ ground[i][j],1 });
			}
		}
		sort(xarr.begin(), xarr.end(), compare); //정렬
		tmpyull = xarr.size() * 2; // 새로운 열의 사이즈가 됨
		for (int j = 0; j < tmpyull; j++) {
			ground[i][j] = xarr[j / 2].xnum;
			ground[i][j + 1] = xarr[j / 2].totalcount;
			j++;
		}
		tmpcount.push_back(tmpyull);
		if (tmpyull > maxyull) { maxyull = tmpyull; }
	}
	 yull = maxyull;
	 for (int i = 0; i < tmpcount.size(); i++) { //나머지 부분 0으로 채우기
		 for (int j = yull - 1; j >= 0; j--) {
			 if (tmpcount[i] - 1 < j) {
				 ground[i][j] = 0;
			 }
			 else break;
		 }
	 }
}
void Ccal() {
	int maxhang = 0;
	vector<int> tmpcount;
	for (int i = 0; i < yull; i++) {
		int tmphang = hang;
		vector<xx> xarr;
		for (int j = 0; j < tmphang; j++) {
			if (ground[j][i] == 0) continue;
			bool c = false;
			for (int k = 0; k < xarr.size(); k++) {
				if (ground[j][i] == xarr[k].xnum) {
					xarr[k].totalcount++; c = true; break;
				}
			}
			if (c == false) {
				xarr.push_back({ ground[j][i],1 });
			}
		}
		sort(xarr.begin(), xarr.end(), compare); //정렬
		tmphang = xarr.size() * 2;
		for (int j = 0; j < tmphang; j++) {
			ground[j][i] = xarr[j / 2].xnum;
			ground[j + 1][i] = xarr[j / 2].totalcount;
			j++;
		}
		tmpcount.push_back(tmphang);
		if (tmphang > maxhang) { maxhang = tmphang; }
	}
	hang = maxhang;
	for (int i = 0; i < tmpcount.size(); i++) {
		for (int j = hang - 1; j >= 0; j--) {
			if (tmpcount[i] - 1 < j) {
				ground[j][i] = 0;
			}
			else break;
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int second = 0;
	inputs();
	while (1) {
		if (ground[r-1][c-1] == k) { cout << second << "\n"; return 0; }
		if (second > 100) { cout << -1 << "\n"; return 0; }
		if (hang >= yull) {
			Rcal();
		}
		else {
			Ccal();
		}
		second++;
	}
	return 0;
}

www.acmicpc.net/problem/1254

1. 풀이방법

- 일단 처음 문제를 읽고 든 생각은 제일 길어봤자 문자열의 길이 *2 정도 이겠구나 였습니다.

   (뒤에서부터 차례대로 추가하면 되니까)

- 입력은 string으로 받아 편의를 위해 저는 vector<char>에 옮겨 담았습니다.

- 그리고 이제 하나씩 추가를 하고 이게 펠린드롬이 맞는지를 확인하였습니다.

- 반복문만 활용하면 잘 풀 수 있는 문제였습니다.

2. 주의사항

- 없음. 

3. 나의코드

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

string s;
vector<char> carr;
vector<char> tmpc;
int resultlen;

bool isitpelen() {
	for (int i = 0; i < tmpc.size() / 2; i++) {
		if (tmpc[i] != tmpc[tmpc.size() - 1 - i]) return false;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> s;
	for (int i = 0; i < s.length(); i++) carr.push_back(s[i]);

	resultlen = s.length();
	tmpc = carr;
	if (isitpelen()){
		cout << resultlen << "\n"; return 0;
	}
	for (int i = 0; i < s.length(); i++) {
		tmpc = carr;
		for (int j = i; j >= 0; j--) {
			tmpc.push_back(s[j]);
			if (isitpelen()) {
				cout << resultlen + i + 1 << "\n"; return 0;
			}
		}
	}
	return 0;
}

www.acmicpc.net/problem/1406

1. 풀이방법

- 커서가 여러칸씩 뛰는 명령어는 없으므로 상대적으로 간단하였습니다.

- 저는 커서의 앞쪽은 VECTOR 커서의 뒤쪽은 STACK 을 이용하였습니다.

- 방법은 여러가지가 있을 것 같습니다 편하신대로...

- 커서를 왼쪽으로 옮길 때 커서의 뒤쪽이 되는 한 문자는 STACK에 푸쉬하고

- 커서를 오른쪽으로 옮길 때는 STACK에서 POP해 와서 다시 VECTOR에 넣는 식으로 하였습니다.

- 아마 시작할 떄의 커서의 위치가 맨 뒤쪽이라서 이러한 생각을 자연스럽게 하게된 것 같습니다.

2. 주의사항

3. 나의코드

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


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s;
	vector<char> tmpc;
	stack<char> tmps;
	int cursor;
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		tmpc.emplace_back(s[i]);
	}
	cursor = s.length();
	int n;
	cin >> n;
	while (n--) {
		char c;
		cin >> c;
		if (c == 'L') {
			if (cursor == 0) continue;
			else { //커서 뒤쪽은 스택으로 옮겨 놓음
				tmps.push(tmpc[cursor - 1]); tmpc.pop_back(); cursor--;
			}
		}
		else if (c == 'D') {
			if (tmps.empty()) continue;
			else {
				tmpc.emplace_back(tmps.top()); tmps.pop();
				cursor++;
			}
		}
		else if (c == 'B') {
			if (cursor == 0) continue;
			else {
				tmpc.pop_back();
				cursor--;
			}
		}
		else {
			char c;
			cin >> c;
			tmpc.emplace_back(c);
			cursor++;
		}
	}

	//출력부
	for (int i = 0; i < tmpc.size(); i++) {
		cout << tmpc[i];
	}
	while (!tmps.empty()) {
		cout << tmps.top();
		tmps.pop();
	}


	return 0;
}

* 벡터(Vector) 란 ?

- 배열의 확장 느낌으로서 시퀀스 컨테이너의 대표적인 자료구조이다.

-  동적배열과 유사하다

- 자료들(data)가 구조적으로 인접한 위치에 있기 때문에 접근이 쉽고 메모리를 효율적으로 관리가능하다

- 배열과 같이 index를 통한 요소(data) 접근이 가능하다 .(매우 편리, 접근이 용이)

- 만약 맨뒤에 삽입이 아닌 맨 앞이나 중간, 임의의 위치 등에 삽입을 하려고 하는 경우 다른 요소들도

  재조정을 해야 하기 때문에 느리다 (비 효율적)

- 임의의 위치에 삽입, 삭제 등이 많이 일어나는 경우 벡터보다는 리스트를 활용하는것이 효과적이다.

* 벡터 ADT

- at( x ) (index가 x인 위치의 자료형 리턴)

- set(int x, object o) (index x의 위치에 o라는 객체 assign)

- insert(int i, object o) (index i의 위체서 o라는 객체 삽입)

- erase(int i) (index i에 있는 객체 삭제)

- size() (vector 의 사이즈 리턴)

- empty() (비어있는지 확인 -bool)

- push_back(object o) (vector 맨 끝에 삽입)

* ADT 시간복잡도 분석

- at(i),  set(i,0)   ----> O(1) ( vector는 index로 접근 가능 하므로 at, set은 모두 직접 접근하여 O(1) 타임에 가능하다.

- insert(i,o)  ----> O(n) (임의의위치 i에 자료를 삽입하는 경우 원래의 i위치 부터 끝까지 있던 자료들을 모두 한칸씩 뒤로 밀린다.)

-erase(i)  ----> O(n) (역시 비슷한 느낌입니다 ---앞으로 땡겨줘야함 )

* 벡터 활용의 예

- 정렬된 객체들의 집합들을 관리 해야할 때

* 벡터의 구현

<잘못된 부분이 있을 수 있습니다>

<알려주시면 수정 하겠습니다>

기본 크기를 64(index) 로 하고 만약 입력을 받다가 이크기를 넘어가게 되면

배열의 크기를 두배로 늘리고 기존의 자료구조들을 모두 옮기는 식으로 구현하였습니다.

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

- 0이 들어 올 경우 이전의 받았던 숫자를 하나 지운다.

- 문제 자체에

#정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.#

- 이러한 조건이 있어서 따로 예외처리를 할 필요도 없었다.

- 스택을 써도 좋고 저는 그냥 벡터로 했습니다.