대엉코딩

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

1. 풀이방법

- N개의 수중에 주어지는 M개의 수들이 각각 존재하는 지 확인해야합니다

- 선형탐색을 진행할 경우 O(N*M) 이므로 약 10,000,000,000 는 시간초과에 걸릴 것 같습니다.

- O(NlogN) 정렬 + O(M*logN) 이분탐색 으로 해결했습니다.

2. 주의사항

- 조건으로 인한 시간초과

3. 나의코드

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

int Narr[100000];
int N, M;
bool existnum(int target) {
	int ep = N - 1;
	int sp = 0;
	int mid;
	while (sp<=ep) {
		mid = (sp + ep) / 2;
		if (Narr[mid] == target) { return true; }
		else if (Narr[mid] < target) {
			sp = mid + 1;
		}
		else if (Narr[mid] > target) {
			ep = mid - 1;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Narr[i];
	}
	sort(Narr, Narr+N); //이분탐색을 위한 정렬
	cin >> M;
	int target;
	for (int i = 0; i < M; i++) {
		cin >> target;
		cout << existnum(target)<<"\n";
	}
	return 0;
}

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

1. 풀이방법

- 최대 깊이가 500입니다.

- 모든 경우의 수를 모두 구하면 매우 커짐을 알 수 있습니다.

- 점화식을 세우고, 0과 i==j 일때 (한변에서 양 끝은 선택권이 한개씩 뿐) 처리를 따로 해주시면 됩니다.

- 바텀업 방식으로 작성했습니다.

2. 주의사항

- 없음

3. 나의코드

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

int triangle[500][500];
int dp[500][500];
int n;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i + 1; j++) {
			cin >> triangle[i][j];
			dp[i][j] = -1;
		}
	}
	dp[0][0] = triangle[0][0];
	
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i + 1; j++) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][j] + triangle[i][j];
			}
			else if (j == i) {
				dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
			}
		}
	}
	int maxr = -1;
	for (int i = 0; i < n; i++) {
		maxr = max(dp[n - 1][i], maxr);
	}
	cout << maxr << "\n";
	return 0;
}

오늘은 적성시험을 보느라 많은 걸 하진 못했지만...^

요즘 문자열관련 문제를 좀 풀어보고 있는 중입니다..

c++ string 에서 push_back(char c) 즉 push_back은 쓸수 있지만 한글자만 넣을 때 사용가능

문자열을 붙일 경우 그냥 + 를 사용해서 뒤에 붙이시면 됩니다.

string to int --> stoi(string)

int to string --> to_string(int) 

사용

간단하게 정리했습니다

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

1. 풀이방법

- 비교적 간단한 구현 문제입니다.

- 1단계가 낚시왕의 이동, 2단계가 낚시, 3단계가 상어의 이동입니다.

- 1,2 단계는 매우 쉽고, 3단계에서 최대 상어의 마리수 M =10000이고, 한번에 이동할 수 있는 칸은 최대 1000칸 이므로

- 한칸씩 상어를 이동시킬 경우 10000000 에, 다른 부가적인 작업들이 들어가면 시간초과 가능성이 있다고 판단하여

- 문제의 사진을 잘 분석해 보면 한칸씩 이동시키는 것이 어떤 수가 되었을 때 정확히 같은방향, 같은 자리로 오는지를 

- 파악해보면, ( 2 * ((R or C)-1) ) 칸을 움직이면 같은방향을 가지면서 같은 자리로 이동합니다.

- 즉 최종으로 한칸씩 이동시킬 fixedmovecount= speed % ( 2 * ((R or C)-1) ) 만큼만 한칸 씩 이동시키면 됩니다.

2. 주의사항

- 모듈러연산을 활용한다 정도?

- 문제도 짧고 헷갈릴만한 단어도 딱히 없었습니다...

3. 나의코드

#include<bits/stdc++.h>
using namespace std;
int R, C,M;
struct shark {
	int speed, dir, ssize,num;
};
vector<shark> sea[102][102];
vector<pair<int, int>> sharkvec; // 상어들의 위치 저장
bool sharkdie[10001]; // 상어 살았는지 여부 조사
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 };
int sharksum;

void inputs() {
	cin >> R >> C>>M;
	int r, c, s, d, z;
	for (int i = 0; i < M; i++) {
		cin >> r >> c >> s >> d >> z;
		sharkvec.push_back({ r,c });
		sea[r][c].push_back({ s,d - 1,z,i });
	}
}
void getshark(int f) {
	for (int i = 1; i <= R; i++) {
		if (!sea[i][f].empty()) {
			sharksum += sea[i][f][0].ssize; //잡음
			sharkdie[sea[i][f][0].num] = true;
			sea[i][f].pop_back();
			return;
		}
	}
	return;
}

void moveshark() {
	vector<shark> tmpsea[102][102];
	for (int i = 0; i < M; i++) {
		if (sharkdie[i]) continue; //죽었으면 보지않음

		int x = sharkvec[i].first; int y = sharkvec[i].second;
		int tmps, tmpd, tmpz;
			tmps = sea[x][y][0].speed;
			tmpz = sea[x][y][0].ssize; //크기
			tmpd = sea[x][y][0].dir;


		int fixexmovecount;
		if (tmpd <= 1) { // 세로이동
			fixexmovecount = tmps%(2*(R - 1));
			for (int a = 0; a < fixexmovecount; a++) {
				if (x == R) { tmpd = 0; }
				if (x == 1) { tmpd = 1; }
				x += dx[tmpd];
			}
		}
		else { //가로이동
			fixexmovecount = tmps%(2*(C - 1));
			for (int a = 0; a < fixexmovecount; a++) {
				if (y == C) { tmpd = 3; }
				if (y == 1) { tmpd = 2; }
				y += dy[tmpd];
			}
		}
		sharkvec[i].first = x; sharkvec[i].second = y;
		if(tmpsea[x][y].empty()) tmpsea[x][y].push_back({ tmps,tmpd,tmpz,i }); //아무도 없으면 그냥 삽입
		else { //다른 상어가 있으면 큰놈이 작은놈을 잡아먹는다
			if (tmpsea[x][y][0].ssize < tmpz) {
				sharkdie[tmpsea[x][y][0].num] = true; // 기존에 있던놈 잡아먹힘
				tmpsea[x][y].pop_back();
				tmpsea[x][y].push_back({ tmps,tmpd,tmpz,i });
			}
			else { //넣으려던놈이 잡아먹힘
				sharkdie[i] = true;
			}
		}
	}
	for (int t = 1; t <= R; t++) {
		for (int k = 1; k <= C; k++) {
			sea[t][k] = tmpsea[t][k];
		}
	}
	return;
}
/*void watchshark() {
	cout << "\n";
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (sea[i][j].empty()) cout << 0 << " ";
			else cout << sea[i][j][0].num+1 << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}*/
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	for (int fm = 1; fm <= C; fm++) { // 낚시꾼의 위치 (1초당)
		getshark(fm);
		moveshark();
	}
	cout << sharksum;


	return 0;
}

www.acmicpc.net/problem/17822

1. 풀이방법

- 구현문제입니다.

- circular의 특성만 체크 해서 0이 될경우 M으로 바꿔주고 M+1이 될경우 1로 바꿔주는 것에 신경써주고,

- 문제에서 구현하라는 대로 하시면 됩니다.

- bfs를 통해서 인접한 수 들을 모두 지워주었습니다.

2. 주의사항

- 평균에 대한 특별한 언급이 없어서( 나머지는 버린다던가...) 

- 그냥 double형으로 선언하여 평균을 구해주었더니 맞았습니다.

3. 나의코드

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

int N, M, T; // 반지름, 원판당 수, T번 회전시킨다.
int circle[51][51]; // 몇번째 원/ 몇번째 수
bool visited[51][51]; //bfs를 위한 
queue<pair<int, int>> tmpq;
int xi, di, ki;
int xdk[51][3];
bool checkexist = false;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
double tmpsum, tmpn;
bool neighbor = false;

//번호가 xi의 배수인 원판을 di방향(0-시계,1-반시계) ki칸 만큼 회전
void inputs() {
	cin >> N >> M >> T;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> circle[i][j];
		}
	}
	for (int i = 1; i <= T; i++) {
		cin >> xdk[i][0] >> xdk[i][1] >> xdk[i][2];
	}
}
bool boundcheck(int x) {
	return (x >= 1 && x <= N); //원의 범위
}
void rotate(int r) {
	for (int k = 0; k < xdk[r][2]; k++) {
		for (int i = 1; i <= N; i++) {
			if (i % xdk[r][0] != 0) continue; // xi의 배수인 원판만 회전

			int tmpnum;
			if (xdk[r][1] == 0) { // 시계방향
				tmpnum = circle[i][M];
				for (int j = M; j >= 2; j--) {
					circle[i][j] = circle[i][j - 1];
				}
				circle[i][1] = tmpnum;
			}
			else { //반시계방향
				tmpnum = circle[i][1];
				for (int j = 1; j < M; j++) {
					circle[i][j] = circle[i][j + 1];
				}
				circle[i][M] = tmpnum;
			}
		}
	}
}
void initvisit() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			visited[i][j] = false;
		}
	}
}
void bfs(int x, int y) {
	visited[x][y] = true;
	tmpq.push({x,y});
	while (!tmpq.empty()) {
		int qsize = tmpq.size();
		while (qsize--) {
			int nextx = tmpq.front().first;
			int nexty = tmpq.front().second;
			tmpq.pop();
			for (int i = 0; i < 4; i++) {
				int tx = nextx + dx[i]; int ty = nexty + dy[i];
				if (ty == 0) ty = M; //circular
				if (ty == M + 1) ty = 1;
				
				if (boundcheck(tx) && !visited[tx][ty] && circle[tx][ty] == circle[x][y]) {
					tmpq.push({ tx,ty });
					visited[tx][ty] = true;
					neighbor = true;
					circle[tx][ty] = 0; //지우기
					checkexist = true;
				}
			}
		}
	}
	if (neighbor == true) {
		circle[x][y] = 0; 
	} //하나라도 존재하면 여기도 지우기 (시작점)
}
void getsum() {
	tmpsum = 0; tmpn = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (circle[i][j] != 0) {
				tmpsum += circle[i][j];
				tmpn++;
			}
		}
	}
}
/*void watchcircle() {
	cout << "\n";
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cout << circle[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}*/
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs(); //원판 셋팅
	for(int a=1;a<=T;a++) {
		rotate(a); //회전
		getsum(); // 전체 존재의 수와 그들의 합
		if (tmpn == 0) { cout << 0; return 0; }
		initvisit();
		checkexist = false; // 인접하면서 같은 수가 하나라도 존재하는지 체크
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				neighbor = false; //이웃이 하나라도 있으면 삭제되고 아니면 지워지지 않음
				if (circle[i][j] != 0 && visited[i][j] == false) {
					bfs(i, j);
				} // 인접
			}
		}
		if (checkexist == false) { //인접한 수가 존재하지 않을 때
			double avg = tmpsum / tmpn;
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= M; j++) {
					if (circle[i][j] == 0) continue;

					if (circle[i][j] > avg) {
						circle[i][j]--; continue;
					}
					else if (circle[i][j] < avg) {
						circle[i][j]++; continue;
					}
				}
			}
		}
	}
	int resultsum = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			resultsum += circle[i][j];
		}
	}
	cout << resultsum;
	return 0;
}

www.acmicpc.net/problem/17825

1. 풀이방법

- 쉽다고 생각하면서 , 시작해서 개고생하며 어렵게 끝낸 문제입니다.....

- 첫번째 문제점, 30 노드가 중복되는 것을 체크하지 못한점.

- 30 노드에 도착하면 방향을 바꾸도록 설정했다가 다른 30 (끝 쪽에 가까운) 거기에 말들이 도착헀을때도 방향을 바꾸는 현상 발생.

- 두번째 문제점, 방문체크를 할때 여러개 있는 노드들을 고려하지 않은 것.

- 문제를 보면, 두개이상 존재하는 노드들이 있다 (16, 22,28,30.....)

- 결국 현재 말들의 위치만을 비교함으로써 겹쳐지는지 아닌지 알 수 가 없다.

- 결국 코드를 싹 지우고, 다시 짜면서 해결한 방법은

- 각각 고유의 번호를 가지는 노드들로 같은 모양의 그래프를 만들어 준 후, 문제에서의 노드들은 점수들로서

- 매칭을 시켜주었습니다. 그러면 첫, 두 번째 문제점들이 모두 해결됩니다.

- 그림을 보시면 아이디어를 이해하시기 편할 겁니다.

- 전체적인 문제해결은 dfs를 이용한 완전탐색 입니다.

2. 주의사항

- 일단 코드를 작성하기 전, 문제를 항상 정확히 파악하고 시작하고자 노력하지만

- 이 문제처럼, 처음 시작할 때 발생하는 문제를 예상하지 못하고 시작하면 굉장히 어려워 지고 꼬입니다....

- 역시, 주의사항은...... 문제를 꼼꼼히 잘 분석하자......

3. 나의코드

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

// 시작노드 0, 도착점 노드 21
int route[4][33];
int score[33]; // 점수계산을 위한 노드
int maxresult;
int inputnum[10];
pair<int, int> ob[4]; //4개의말 (현재위치, 타고있는 방향)

void inputs() {
	for (int i = 0; i < 10; i++) {
		cin >> inputnum[i];
	}
}
void setscore() {
	for (int i = 1; i <= 20; i++) {
		score[i] = 2 * i;
	}
	score[22] = 13; score[23] = 16; score[24] = 19;
	score[25] = 25; score[30] = 26; score[29] = 27;
	score[28] = 28; score[26] = 22; score[27] = 24;
	score[31] = 30; score[32] = 35; score[21] = 0;
}
void makegraph() {
	for (int i = 0; i < 21; i++) {
		route[0][i] = i + 1;
	}
	route[0][21] = 21;
	route[1][5] = 22; route[1][22] = 23; route[1][23] = 24;
	route[1][24] = 25; route[1][25] = 31; route[1][31] = 32;
	route[1][32] = 20; route[1][20] = 21; route[1][21] = 21;
	route[2][10] = 26; route[2][26] = 27; route[2][27] = 25;
	route[2][25] = 31; route[2][31] = 32; route[2][32] = 20;
	route[2][20] = 21; route[2][21] = 21;
	route[3][15] = 28; route[3][28] = 29; route[3][29] = 30;
	route[3][30] = 25; route[3][25] = 31; route[3][31] = 32;
	route[3][32] = 20; route[3][20] = 21; route[3][21] = 21;
}
bool existcheck(int s,int index) {
	if (s == 21) return false;
	for (int i = 0; i < 4; i++) {
		if (i == index) continue;
		if (ob[i].first == 21) continue;
		if (ob[i].first == s) return true;
	}
	return false;
}
void makecase(int cnt,int resultsum) {
	if (cnt == 10) {
		maxresult = max(resultsum, maxresult);
		return;
	}
	int thisnum = inputnum[cnt];
	for (int i = 0; i < 4; i++) {
		if (ob[i].first == 21) continue; //이미 도착점에 있는 말
		int prevnum = ob[i].first;
		int prevdir = ob[i].second;
		for (int j = 0; j < thisnum; j++) {
			ob[i].first = route[prevdir][ob[i].first];
		}
		if (ob[i].first == 5) ob[i].second = 1;
		if (ob[i].first == 10) ob[i].second = 2;
		if (ob[i].first == 15) ob[i].second = 3;

		if (!existcheck(ob[i].first,i)) {
			makecase(cnt + 1, resultsum + score[ob[i].first]);
		}
		ob[i].first = prevnum;
		ob[i].second = prevdir;

	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	setscore();
	makegraph();
	makecase(0,0);
	cout << maxresult;
	return 0;
}

www.acmicpc.net/problem/17837

1. 풀이방법

- 구현문제입니다.

- 문제의 조건대로 출력해주면 됩니다.

- 자료형을 잘 생각해서 문제풀이 시작에 들어가면 됩니다.

2. 주의사항

- 아무리봐도 맞는데, 마지막 테케가 원하는 대로 안나오고 -1이 나왔습니다.

- 문제를 잘 읽어보니 종료조건을 TURN 이 증가 될때마다가 아닌, 한마리의 말을 이동시킬 때 마다 종료조건을 검사해야 합니다. 

-왜냐하면, 높이가 4이상이 되는 순간 (게임이 진행되는 도중) 바로 게임이 종료되기 때문입니다.

3. 나의 코드

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

int N, K;

int ground[14][14];
vector<pair<int,int>> chess[14][14]; //쌓이는 말들을 표시하기 위에 맨앞=맨아래 (번호, 이동방향)
vector<pair<int, int>> horse; //그말은 아니지만;;ㅎ

int dx[4] = { 0,0,-1,1 }; //1234
int dy[4] = { 1,-1,0,0 };

void inputs() {
	cin >> N >> K;
	for (int i = 0; i <= N + 1; i++) { //테두리는 파란색 취급
		ground[0][i] = 2;
		ground[i][0] = 2;
		ground[N + 1][i] = 2;
		ground[i][N + 1] = 2;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> ground[i][j];
		}
	}
	horse.push_back({ -1,-1 }); //index 맞추기 용

	int x, y, z;
	for (int i = 1; i <= K; i++) {
		cin >> x >> y >> z;
		chess[x][y].push_back({ i, z-1 });
		horse.push_back({ x,y }); //말의 위치 표시
	}
}
bool checkexit() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (chess[i][j].size() >= 4) return true;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	int turncount = 0;
	while (1) {

		turncount++;
		//1번말부터 이동
		for (int i = 1; i <= K; i++) {
			int tx = horse[i].first; int ty = horse[i].second; // 그 말의 위치
			for (int j = 0; j < chess[tx][ty].size(); j++) {
				if (chess[tx][ty][j].first == i) { //쌓여있는 말의 위치를 알았다.

					int tmpdir = chess[tx][ty][j].second; //이동방향
					int nextx = tx + dx[tmpdir]; int nexty = ty + dy[tmpdir];


					if (ground[nextx][nexty] == 0) { //흰색
						int erasecount = 0;
						for (int k = j; k < chess[tx][ty].size(); k++) {
							chess[nextx][nexty].push_back(chess[tx][ty][k]);
							horse[chess[tx][ty][k].first] = { nextx,nexty }; //말의 위치가 바뀐걸 알려줘야 한다.
							erasecount++;
						}
						while (erasecount--) { //이동헀으니 제거
							chess[tx][ty].pop_back(); 
						}
						break;
					}

					else if (ground[nextx][nexty] == 1) { //빨간
						int erasecount = 0;
						for (int k = chess[tx][ty].size() - 1; k >= j; k--) {
							chess[nextx][nexty].push_back(chess[tx][ty][k]);
							horse[chess[tx][ty][k].first] = { nextx,nexty };
							erasecount++;
						}
						while (erasecount--) {
							chess[tx][ty].pop_back();
						}
						break;
					}
					else { //파란
						//이동방향 반대로

						if (tmpdir == 0) tmpdir = 1;
						else if (tmpdir == 1) tmpdir = 0;
						else if (tmpdir == 2) tmpdir = 3;
						else tmpdir = 2;

						chess[tx][ty][j].second = tmpdir;

						if (ground[tx + dx[tmpdir]][ty + dy[tmpdir]] == 2) { //반대도 파란색
							break;
						}
						else {
							j--;
						}// 한번 더 반복
					}
				}
			}
			//순간 이므로 !
			if (checkexit()) { cout << turncount; return 0; }
		}
		if (turncount > 1000) { cout << -1; return 0; }
	}
}