기록을

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE

연산자의 수가 가령 1,5,0,3

이렇게 주어지면 나는 새로운 벡터에 0을 1개, 1을 5개, 3을 3개 추가하고, 그 백터를 이용해서 순열을 돌렸다.

이 과정에서 중복도 발생하고, set을 사용해서 중복을 처리해주더라도 연산 시간이 소모되기 때문에 시간초과가 나는 것 같다.

따라서, 그냥 1,5,0,3 상태에서, 내가 무언가를 뽑으면 그 원소에 1을 더하거나 빼주고, 양수일 경우에만 뽑을 수 있게 하는 방식으로 DFS를 구현해야 통과할 수 있을 것 같다.

아래는 시간 초과를 받은 코드이다.

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

통 A가 비었을때, C에 존재할 수 있는 모든 물의 양의 경우를 출력해주면 된다.

물이 이동할 수 있는 방법은 6가지이다.

a->b, b->c ... 

초기에 각 통의 물의양은 0,0,C 이고, 6가지 모든 경우를 큐에 삽입해주고, a가 0인 순간에만 c의 물의 양을 기록해서 마지막에 출력해주면 된다.

보통 bfs문제를 풀이할 때는 큐에 삽입하는 순간에 방문처리를 해주는데, 이 문제에서는 그렇게 하면 상당히 귀찮아진다.

경우에 따라 bfs의 상단부에서 방문 검사를 해준 직후에 방문처리를 해줄수 있도록 하자.

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

2차원 배열을 문자열로 맵핑해서 해결한다.

1 2 3

4 5 6

7 8 0 

위와 같은 2차원 배열이라면 "123456780" 이러한 문자열이 되는 것이다.

0의 인덱스로부터 2차원 배열에서 0의 위치를 알아낼 수 있다.

한번의 시행에서, 빈칸의 위치를 옮길 수 있는 위치를 찾아준 다음에, 이전 시행에서 찾은 경우만큼만 bfs를 진행한다.

참고: http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220438835865

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

백준 16637번 괄호 추가하기라는 문제인데, 이 문제를 풀면서 했던 뻘짓을 기록해두려고 한다.

3+8*2 이런 문자열이 있다고 할 때, 결과값을 내도록 구현하려면 어떻게 해야할까?

그냥 str[0] ~ str끝까지 한 문자 한 문자 확인하려고 생각하는 순간 굉장히 피곤해진다.

324 + 232 이런 경우처럼, 한 자리수가 아닌 숫자가 존재할 수 있기 때문이다. 처음에 이렇게 접근했다가, 결과적으로 아래와 같은 뻘짓을 하게 되었다.

위와 같은 뻘짓을 하지 않으려면, 연산자와 피연산자를 분리해서 벡터(배열)에 저장하고 있으면 된다. 연산하기가 훨씬 수월하다.

이렇게 간단하게 계산할 수 있다.

정상적인 수식이라면, 연산자의 개수가 피연산자의 개수보다 하나 적을 것이므로, 깔끔하게 위와 같은 반복문을 만들어낼 수 있다.

https://www.welcomekakao.com/learn/courses/30/lessons/42891

k번 순회하도록 해서 정확도밖에 맞추지 못한 코드이다.

순회 방법을 줄일 아이디어가 필요하다.

처음에 든 생각은, 배열에서 0이 아닌것의 개수와, 배열의 최솟값을 곱하면 이만큼을 한 번에 먹는 것으로 처리할 수 있다는 것.

다른 생각은 정렬해서 k보다 작을동안 묶어서 빼준 이후에, 한 번에 먹을 수 있는 게 k보다 커지면 다시 순회하는 방법이 있을 것 같다.

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

4방향 dfs 탐색을 활용해서 y가 네개 이하인 경우에만 결과에 포함시키려고 했다.

이렇게 접근하면 자리에 앉아 있는 사람이 y파인지s파인지 말고는 개별적으로 구분할 수 없기 때문에 각자 결과로 나온 문자열을 구분하지 못한다.

가령 sysysys라는 문자열은 맞는 결과이지만, 행렬에서 어떤 위치의 성분을 가져다가 저걸 만들어냈느냐에 따라서 서로 다른 문자열일 수도 있고 같은 문자열일 수도 있다.

아래는 틀린 코드이다.

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

이 문제를 무작정 n^2으로 풀면 TLE를 받는다.

아래는 시간초과가 나는 코드이다.

한 대각선에 비숍은 하나밖에 존재할 수 없다는 것을 이용하면 복잡도를 2n-1 즉 n으로 떨어트릴 수 있을 것이다.

#include<iostream>
using namespace std;
int n, m[10][10];
int cnt = 0, Max = 0;
bool isused1[10], isused2[10];
void func(int k) {
	
	if (Max < k) Max = k;

	bool isExist1 = false , isExist2 = false;
	for (int i = 0; i < 10; i++) {
		if (!isused1[i]) {
			isExist1 = true;
			break;
		}
		if (!isused2[i]) {
			isExist2 = true;
			break;
		}
	}

	if (!isExist1 && !isExist2) return;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (m[i][j] == 1 && !isused1[i + j] &&
				!isused2[i - j + n - 1]) {
				//cnt++;
				isused1[i + j] = true;
				isused2[i - j + n - 1] = true;
				func(k + 1);
				isused1[i + j] = false;
				isused2[i - j + n - 1] = false;
			}
		}
	}
	return;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> m[i][j];
	
	func(0);
	cout << Max << '\n';
}

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

C개의 수를 입력받아서 길이 L의 수열을 출력하면 된다.

입력은 소문자로만 들어오고, 정렬되어서 들어오지 않는다.

출력되는 수열은 오름차순 정렬 상태여야 하기 때문에 입력을 받은 이후에 정렬이 필요하다. 그리고 사전순의 상태를 유지하기 위해서 st라는 변수를 두어서 이전에 사용된 문자의 인덱스를 관리한다.

문자의 길이가 0이 되면 이 전에 사용한 문자의 인덱스가 존재하지 않기 때문에 0으로 처리해준다.

문자를 중복해서 사용할 수 없기 때문에 특정 인덱스의 문자가 사용중인지 여부를 판단하는 배열이 필요하다.

출력되는 문자열의 문자 사이사이에 공백이 당연히 포함된다고 생각해서 공백까지 출력해서 맞왜틀을 반복했다.

출력 형식을 잘 확인하도록 하자.

#include<iostream>
#include<algorithm>
using namespace std;
int L, C, st;
char n[15], arr[15];
bool isused[15];
bool Check() {
	int cntM = 0, cntJ = 0;
	for (int i = 0; i < L; i++) {
		if (arr[i] == 'a' or arr[i] == 'e' or
			arr[i] == 'i' or arr[i] == 'o' or arr[i] == 'u')
			cntM++;
		else
			cntJ++;
	}
	if (cntM >= 1 && cntJ >= 2) //모음1, 자음2개가 있어야 true
		return true;
	else
		return false;
}
void func(int k) {
	if (k == L) {
		if (Check()) {
			for (int i = 0; i < L; i++)
				cout << arr[i];
			cout << '\n';
		}
		return;
	}
	if (k == 0) st = 0;
	for (int i = st; i < C; i++) {
		if (!isused[i]) {
			arr[k] = n[i];
			isused[i] = true;
			st = i;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	cin >> L >> C;
	for (int i = 0; i < C; i++)
		cin >> n[i];
	sort(n, n + C);
	
	func(0);
	return 0;
}

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

퀸이 올라올 수 없는 곳의 위치를 체스판 한 칸 한 칸으로 관리하려고 했다.

그래서 2차원 배열을 활용했는데

초반의 생각은 이러했다.

가령 1,0에 퀸을 놓으면 1,0이 포함된 행과 열 그리고 두 개의 대각선에 퀸을 놀 수 없다.

이때 1,2는 둘 수 없는 위치이다. 그런데 2, 2는 둘 수 있는 위치이고, 2,2에 퀸을 두고 또 2,2를 둠으로써 둘 수 없는 위치를 잡고 나서 재귀를 빠져나올 때, 2,2의 행과 열 그리고 두 대각선의 bool 값을 모두 변경해버리면 1,1가 막고 있었던 것이 풀리게 되어서 제대로 된 연산이 되지 않는다.

따라서 좌표 하나하나를 관리할 게 아니라, 열과 행 그리고 대각선들로 사용중 여부를 관리하는 배열을 잡아야 한다.

#include<iostream>
using namespace std;
int N, m[15][15];
bool isused[15][15];
int cnt = 0;
void usage(int i, int j, bool ctr) {
	isused[i][j] = ctr;
	if (ctr) {
		printf("퀸위치: %d %d'\n", i, j);
	}
	for (int k = 0; k < N; k++) {
		isused[i][k] = ctr;
		isused[k][j] = ctr;
	}
	for (int l = 0; l < N; l++) {
		for (int m = 0; m < N; m++) {
			if (l + m == i + j) isused[l][m] = ctr;
			if (l - m == i - j) isused[l][m] = ctr;
		}
	}
}
void func(int k) {
	if (k == N+1 ) {
		cnt++;
		
		return;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!isused[i][j]) {
				usage(i, j, true);
				printf("%d %d에 퀸추가\n", i, j);
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						cout << isused[i][j] << ' '; 
					}cout << '\n';
				}
				cout << '\n'<<'\n';
				func(k + 1);

				//isused[i][j] = false;
				usage(i, j, false);
				printf("%d %d에 퀸제거\n", i, j);
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						cout << isused[i][j] << ' ';
					}cout << '\n';
				}
				cout << '\n' << '\n';
			}
		}
	}
}
int main(void) {
	cin >> N;
	func(1);
	cout << cnt << '\n';
	return 0;
}