기록을

C++ 기준

1. 배열의 크기를 벗어나서 index에 접근하는 경우

2. 전역 변수들의 메모리 크기 총합이 메모리 제한을 초과하는 경우

3. 지역 변수들을 메모리 크기 총합이 스택 메모리 제한을 초과하는 경우

4. 재귀 호출이 너무 깊어지는 경우

5. 0으로 나누는 경우

6. main 함수가 0이 아닌 다른 값을 반환하는 경우

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

다리의 상태와 트럭의 상태를 나타내야 한다.

다리의 경우, 지금 버티고 있는 무게가 몇인지 그리고 현재 다리 위에 몇 개의 트럭이 올라와 있는지를 항상 유지해야 한다.

트럭의 경우에는, 각 트럭 별로 트럭의 무게, 그리고 다리 위에 있는지 여부, 그리고 다리 위에 존재한 시간(혹은 거리)을 유지해야 한다.

따라서 위와 같은 조건을 나타내기 위해서 구조체를 사용했다.

무한 루프를 만들고, 마지막 차가 다리를 탈출하는 순간을 루프 탈출 조건으로 잡았다.

#include<iostream>
using namespace std;
struct Bridge { 
	int wei = 0; //다리에 가해진 무게
	int cnt = 0; //다리위 차의 개수
};
struct Car {
	int wei = 0; //차의 무게
	int time = 0;//차의 이동 시간(거리)
	bool onBri = false; //차가 다리위에 있는지 여부
};
Car car[2000];
Bridge brg;
int n, len, lim; //차의 개수, 다리의 길이, 하중 제한
int main(void) {
	cin >> n >> len >> lim;
	for (int i = 0; i < n; i++)
		cin >> car[i].wei;
	brg.cnt = 0;
	brg.wei = 0;
	int idx = 0, Time = 0; //다리위에 올라가는 차의 인덱스, 전체 시간
	bool endFlag = false;
	while (1) {
	
		//다리 위의 차들 이동(시간 증가)
		for (int i = 0; i < n; i++) {
			if (car[i].onBri) {
				car[i].time++;
				//printf("%d번 차 움직인 거리: %d\n", i, car[i].time);
				if (car[i].time >= len) {
					if (i == n - 1) {
						//다리를 벗어나는 차가 마지막 차라면
						endFlag = true;
						Time++;
						break;
					}
					//이 차가 다리를 다 건너면
					brg.cnt--;
					brg.wei = brg.wei - car[i].wei;
					car[i].onBri = false;
				}
			}
		}

		if (endFlag) break;

		if (lim - brg.wei >= car[idx].wei && brg.cnt < len) {
			//가능한 무게이면서 다리위에 공간이 남았으면
			car[idx].onBri = true;
			brg.wei = brg.wei + car[idx].wei;
			idx++;
			brg.cnt++;
		}
		Time++;
	}
	cout << Time << '\n';
	return 0;
}

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

1차원에서 최단거리를 구하는 문제이고, 가중치가 없기 때문에 bfs를 활용해주면 된다.

움직임 배열을 입력받는 U와 D로 정해주고, 시작점을 큐에 넣은 이후에, 하나씩 pop 해서 확인해주면 된다.

#include<iostream>
#include<queue>
using namespace std;
int n, src, des, Up, Down;
int dis[1000001]; //1 indexed
int Move[2];
queue<int> q;
void bfs(int start) {
	q.push(start);
	dis[start]++;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < 2; i++) {
			int nf = cur + Move[i];
			if (nf < 1 || nf > n || dis[nf] >= 0) continue;
			q.push(nf);
			dis[nf] = dis[cur] + 1;
		}
	}
}
int main(void) {
	
	cin >> n >> src >> des >> Up >> Down;
	for (int i = 1; i <= n; i++)
		dis[i] = -1;
	Move[0] = Up;
	Move[1] = Down * -1;
	bfs(src);
	if (dis[des] == -1) cout << "use the stairs\n";
	else
		cout << dis[des] << '\n';
	return 0;
}

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

먼저 주사위의 동, 서, 남, 북, 위, 아래를 배열 인덱스의 0~5까지로 대응시킨다.

명령을 하나씩 받아서, 먼저 이동할 수 있는지 판단한다. 동쪽이면 동쪽으로 벗어날 것이고, 남쪽이면 남쪽으로 벗어날 것이고 이런 식으로 확인할 수 있다.

지도를 벗어나지 않는다면, 명령에 맞춰서 주사위를 회전해주면 된다. 회전 방향에 따라 주사위의 상태를 갱신해주고, 주사위의 위치를 변경해준다.

이후에 조건에 맞게 출력을 해주면 된다.

#include<iostream>
using namespace std;
int dice[6];
int Row, Col, srcR, srcC, cnt, m[20][20];
void Move(int dir) {
	int temp;
	if (dir == 1) { //동쪽으로 굴릴 때
		if (srcC + 1>= Col) return;
		//주사위 회전, 좌표 이동
		//남2 북3 그대로
		temp = dice[0];
		dice[0] = dice[4];
		dice[4] = dice[1];
		dice[1] = dice[5];
		dice[5] = temp;
		srcC++;
	}
	else if (dir == 2) { //서
		if (srcC - 1 < 0) return;
		temp = dice[1];
		dice[1] = dice[4];
		dice[4] = dice[0];
		dice[0] = dice[5];
		dice[5] = temp;
		srcC--;
	}
	else if (dir == 3) { //북
		if (srcR - 1 < 0) return;
		temp = dice[3];
		dice[3] = dice[4];
		dice[4] = dice[2];
		dice[2] = dice[5];
		dice[5] = temp;
		srcR--;
	}
	else { //남
		if (srcR + 1 >= Row) return;
		temp = dice[2];
		dice[2] = dice[4];
		dice[4] = dice[3];
		dice[3] = dice[5];
		dice[5] = temp;
		srcR++;
	}
	if (m[srcR][srcC] == 0) {
		m[srcR][srcC] = dice[5];
	}
	else {
		dice[5] = m[srcR][srcC];
		m[srcR][srcC] = 0;
	}
	cout << dice[4] << '\n';
}
int main(void) {
	
	cin >> Row >> Col >> srcR >> srcC >> cnt;
	for (int i = 0; i < Row; i++) {
		for (int j = 0; j < Col; j++) {
			cin >> m[i][j];
		}
	}
	while (cnt--) {
		int op;
		cin >> op;
		Move(op);
	}
	return 0;
}

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

arr[0]에 공이 있다고 정해둔다.

arr에 1,2,3을 초기에 순서대로 담아두고, 값이 컵의 번호라고 생각하고 들어오는 숫자의 인덱스를 구해서 두 인덱스에 해당하는 arr값을 스왑해준다.

#include<iostream>
using namespace std;
int m, arr[3] = { 1,2,3 };
int main(void) {
	cin >> m;

	while (m--) {
		int num1, num2, idx1, idx2;
		cin >> num1 >> num2;
		for (int i = 0; i < 3; i++) {
			if (arr[i] == num1) idx1 = i;
			if (arr[i] == num2) idx2 = i;
		}
	
		int temp = 0;
		temp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = temp;
	}
	cout << arr[0] << '\n';

	return 0;
}

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

dfs와 bfs를 모두 활용한다.

dfs를 통해서 섬의 개수를 파악하고, 섬마다 index를 할당해준다.

이후에는 섬으로부터 바다로 탐색을 수행하고, 이때 bfs를 활용한다.

거리를 측정하기 시작한 섬에 대한 정보를 idx 배열에 저장해준다.

즉 i행 j열이 바다라고 한다면, 섬이 아니기 때문에 index가 할당되어있지 않은데, 

어느 섬으로부터 측정한 거리라는 것을 idx 배열에 명시해준다.

이를 통해서 다른섬이 만났을 때, 그 지점까지의 거리가 만들 수 있는 다리의 최소 거리인지 판단해준다.

#include<iostream>
#include<queue>
using namespace std;
int m[100][100], n, dis[100][100], idx[100][100];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int Min = -2;

queue <pair<int, int> > q;
void init() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			dis[i][j] = -1;
	while (!q.empty()) q.pop();
}
void minCal(int val) { //최소 거리인지 판단
	if (Min == -2) { //최솟값이 갱신된 적이 없다면
		Min = val;
		return;
	}
	else {
		if (Min > val) Min = val;
		else
			return;
	}
}
bool boundCheck(int r, int c) {
	return r < 0 || c < 0 || r >= n || c >= n;
}
void dfs(int row, int col, int landCnt) {
	dis[row][col]++;
	idx[row][col] = landCnt; //섬의 index 지정
	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];
		if (boundCheck(nr, nc) || m[nr][nc] == 0 || dis[nr][nc] >= 0) continue;
		dfs(nr, nc, landCnt);
	}
}
void bfs(pair<int, int> start) {
	q.push(start);
	dis[start.first][start.second]++;

	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			if (boundCheck(nr, nc) || dis[nr][nc] >= 0) continue;
			if (m[nr][nc] == 1) {
				//섬을 만났을 때
				if (idx[nr][nc] == idx[cur.first][cur.second]) continue;
				else {
					//출발한 섬과 다른 섬을 만났을 때
					minCal(dis[cur.first][cur.second]);
					init();
					return;
				}
			}
			q.push({ nr, nc });
			dis[nr][nc] = dis[cur.first][cur.second] + 1;
			idx[nr][nc] = idx[cur.first][cur.second];
			//어느 섬에서 측정한 거리라는 것을 명시
		}
	}
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> m[i][j];
	init();
	
	int landCnt = 0; // 섬 번호
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dis[i][j] < 0 && m[i][j] == 1) {
				landCnt++;
				dfs(i, j, landCnt);
			}
		}
	}
	init(); //방문처리 배열 초기화

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dis[i][j] < 0 && m[i][j] == 1) {
				bfs({ i, j });
			}
		}
	}
	cout << Min << '\n';
	return 0;
}
//섬과 섬을 잇는 가장 짧은 다리
//1에서 시작해서 0으로 퍼져나가게
//퍼져나가기 시작한 점이 어느 섬인지 확인하면서 비교

//dfs로 섬 개수 파악하고 번호 매김
//섬이면서 방문 안 한 곳 bfs -> 주변이 바다인 곳 방문(거리측정)
//가다가 섬이면서 내 섬이 아닌 곳을 만나면 중지 -> 길이 최소 비교

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

흑과 백으로 칸을 구분한다.

1을 흑 0을 백이라고 하면

1 0 1 0

0 1 0 1

1 0 1 0

0 1 0 1

이런식으로 체스판이 이루어져있다고 생각하고 흑은 흑대로 먼저 처리하고, 백은 백대로 먼저 처리하는 것이다.

개인적으로 굉장히 해내기 어려운 발상이라고 생각한다.

#include<iostream>
using namespace std;
int n, m[10][10];
int cnt = 0, Bmax = 0, Wmax = 0;
bool isused1[20], isused2[20];
void Black(int row, int col, int cnt) {
	if (col >= n) {
		row++;
		if (row % 2 == 0) col = 0;
		else
			col = 1;
	}
	if (Bmax < cnt) Bmax = cnt;
	if (row >= n) return;
	
	if (m[row][col] == 1 && !isused1[row + col]
		&& !isused2[row - col + n - 1]) {
		isused1[row + col] = true;
		isused2[row - col + n - 1] = true;
		Black(row, col + 2, cnt + 1); //(r,c)가 가능한 지점일 때
		isused1[row + col] = false;
		isused2[row - col + n - 1] = false;
	}
	Black(row, col + 2, cnt);
}
void White(int row, int col, int cnt) {
	if (col >= n) {
		row++;
		if (row % 2 == 0) col = 1;
		else
			col = 0;
	}
	if (Wmax < cnt) Wmax = cnt;
	if (row >= n) return;

	if (m[row][col] == 1 && !isused1[row + col]
		&& !isused2[row - col + n - 1]) {
		isused1[row + col] = true;
		isused2[row - col + n - 1] = true;
		White(row, col + 2, cnt + 1); //(r,c)가 가능한 지점일 때
		isused1[row + col] = false;
		isused2[row - col + n - 1] = false;
	}
	White(row, col + 2, cnt);
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> m[i][j];
	

	Black(0, 0, 0);
	for (int i = 0; i < 2 * n - 1; i++) {
		isused1[i] = false;
		isused2[i] = false;
	}
	White(0, 1, 0);
	cout << Wmax + Bmax << '\n';
}

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

사용했던 숫자를 여러 번 사용할 수 있다.

따라서 숫자 사용 여부를 관리하는 배열이 필요하지 않다.

수열을 벡터에 쌓고, 원하는 길이만큼 쌓이면 set에 넣고 벡터를 비워주는 것을 반복한다.

set에는 중복되는 원소가 들어갈 수 없다는 것을 활용했다.

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int m, n, num[8], arr[8], Start;
set<vector<int> > st;
void func(int k) {
	if (k == m) {
		vector<int> v;
		for (int i = 0; i < m; i++)
			v.push_back(arr[i]);
		st.insert(v);
		v.clear();
		return;
	}
	if (k == 0) Start = 0;
	for (int i = Start; i < n; i++) {
		arr[k] = num[i];
		Start = i;
		func(k + 1);
	}

}
int main(void) {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	sort(num, num + n);
	func(0);
	set<vector<int> >::iterator itr;
	for (itr = st.begin(); itr != st.end(); itr++) {
		vector<int> tmp = *itr;
		for (int i = 0; i < tmp.size(); i++)
			cout << tmp[i] << ' ';
		cout << '\n';
	}
	return 0;
}