코딩하는 두꺼비

www.acmicpc.net/problem/2343

처음엔 정렬되지 않은 벡터를 이분탐색을 어떻게 진행하지 고민했었던 문제이다. 예전에 L사 코테를 봤을 때 나왔던 문제랑 매우 유사해서 꼭 풀어보고 싶었다!

다소 좀 생소한 이분 탐색 유형인 것 같아 고민을 좀 했었는데 반례 모음을 보고 풀 수 있었다.

이분 탐색을 진행할때 left와 right의 초기 값에도 신경을 써야된다는 것을 알 수 있었다.

참고한 반례모음: bingorithm.tistory.com/10

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

int n, m;
long long sum[100001];

int main() {
	int x;
	vector<int> v;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	int left = *max_element(v.begin(), v.end());
	int right = 10000 * n;

	while (left <= right) {
		int c = 1;
		int mid = (left + right) / 2;
		for (int i = 0; i < v.size(); i++) {
			sum[c] += v[i];
			if (sum[c] > mid) {
				sum[c] -= v[i];
				c++;
				sum[c] += v[i];
			}
		}
		if (c > m) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
		for (int i = 1; i <= m; i++) {
			sum[i] = 0;
		}
	}
	cout << left;
	return 0;
}

www.acmicpc.net/problem/2665

첨에 어떻게 접근할 지 고민하다가 방금 푼 문제였던 벽 부수고 이동하기의 코드를 활용해서 풀었다.

사실 최솟값이 필요없기 때문에 좀 비효율적으로 코드를 짠 것 같아서 좀 아쉽다..

다음에 풀 때는 그 전의 바꾼 방갯수를 비교해서 최신화하는 식을 짜봐야겠다..

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
using namespace std;

struct map {
    int x, y, w;
};

int n, ans = -1;
int a[51][51];
int dist[51][51][100];
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };

int bfs(int b) {
    queue<map> q;
    q.push({ 0, 0, 0 });
    dist[0][0][0] = 1;
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int w = q.front().w;
        q.pop();
        if (x == n - 1 && y == n - 1) {
            return dist[x][y][w];
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (dist[nx][ny][w]) continue;
            if (a[nx][ny] == 1) {
                dist[nx][ny][w] = dist[x][y][w] + 1;
                q.push({ nx, ny, w });
            }
            if (a[nx][ny] == 0 && w < b) {
                dist[nx][ny][w+1] = dist[x][y][w] + 1;
                q.push({ nx, ny, w+1 });
            }
        }
    }
    return -1;
}

int main() {
    int b = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &a[i][j]);
        }
    }
    while (1) {
        ans = bfs(b);
        if (ans >= 0) {
            printf("%d", b);
            break;
        }
        else {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k <= b; k++) {
                        dist[i][j][k] = 0;
                    }
                }
            }
        }
        b++;
    }
    return 0;
}

www.acmicpc.net/problem/2206

정말 고민을 많이 한 문제였는데.. 접근방식이 계속 틀린 것이 문제였다...

BFS에 다가 자신의 상태를 저장을 해주어야 하는데 그 생각을 못하고 시작점과 끝점에서 BFS를 두번돌려서 만나는 지점이 같으면 벽을 부수는 걸로 접근을 했었다.

답지를 보기 싫었는데 결국 보게 되서 좀 아쉬운 문제였고 아직 멀었구나 느꼈다..

참고 블로그: rebas.kr/658

이 블로그의 해답이 제일 깔끔하고 이해가 잘되었다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
using namespace std;

struct map {
    int x, y, w;
};

int n, m;
int a[1001][1001];
int dist[1001][1001][2];
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };

int bfs() {
    queue<map> q;
    q.push({ 0, 0, 0 });
    dist[0][0][0] = 1;
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int w = q.front().w;
        q.pop();
        if (x == n - 1 && y == m - 1) {
            return dist[x][y][w];
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (dist[nx][ny][w]) continue;
            if (a[nx][ny] == 0) {
                dist[nx][ny][w] = dist[x][y][w] + 1;
                q.push({ nx, ny, w });
            }
            if (a[nx][ny] == 1 && w == 0) {
                dist[nx][ny][1] = dist[x][y][w] + 1;
                q.push({ nx, ny, 1 });
            }
        }
    }
    return -1;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &a[i][j]);
        }
    }
    printf("%d", bfs());
    return 0;
}

www.acmicpc.net/problem/9663

백트래킹의 대표적인 문제이다.

처음엔 2차원배열로 풀려고 했는데 결국 실패해서 힌트를 보고 풀 수 있었다. 어차피 하나의 열과 하나의 행에 하나의 퀸만 놓을 수 있기 떄문에 1차원 배열로 풀 수 있는 문제였다.

대각선 처리가 좀 까다로웠는데 각 행의 차이와 열의 차이가 동일하지 않는 다는 것을 아는 것이 포인트였다.

참고: chanhuiseok.github.io/posts/baek-1/

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int N, ans;
int map[16];

void dfs(int cnt) {
	int check = 0;
	if (cnt == N) {
		ans++;
		return;
	}
	for (int i = 0; i < N; i++) {
		map[cnt] = i;
		for (int j = 0; j < cnt; j++) {
			if (map[j] == map[cnt] || cnt - j == abs(map[cnt] - map[j])) {
				check = 1;
				break;
			}
		}
		if (check == 0) {
			dfs(cnt + 1);
		}
		else {
			check = 0;
		}
	}

}

int main() {
	cin >> N;
	dfs(0);
	cout << ans;
	return 0;
}

www.acmicpc.net/problem/17070

문제 자체는 DP로 분류되어 있었는데 dfs로 푸니까 간단하게 풀린 문제였다.

처음에 DP로 풀려고 하다가 시간을 많이 사용했는데 이런걸 생각하면 너무 분류에 집중해서 풀지 않아도 될 것 같다!

푸는 방법은 일단 파이프를 가로, 세로, 대각선 3가지 모드가 있다고 생각하고 각 모드에 맞게 모든 경우의 수를 진행해주었다. 크기가 최대 16*16이라 DFS가 터지지 않을 것 같았다.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int n, ans;
int map[17][17];

void dfs(int x, int y, int mode) {
	if (x == n && y == n) {
		ans++;
		return;
	}
	if (mode == 0 || mode == 2) {
		if (y + 1 <= n && map[x][y + 1] == 0) {
			dfs(x, y + 1, 0);
		}
	}
	if (mode == 1 || mode == 2) {
		if (x + 1 <= n && map[x + 1][y] == 0) {
			dfs(x + 1, y, 1);
		}
	}
	if (x + 1 <= n && y + 1 <= n && map[x + 1][y + 1] == 0 
		&& map[x][y+1] == 0 && map[x+1][y] == 0) {
		dfs(x + 1, y + 1, 2);
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}
	dfs(1, 2, 0);
	cout << ans;
	return 0;
}

www.acmicpc.net/problem/14716

그냥 전형적인 dfs/bfs문제였다. 섬 갯수 세는 문제와 매우 유사했다.

단, 4방향이 아닌 8방향을 고려하는 것만 조심하면 쉬운 문제였다.

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

queue<pair<int, int>> q;
int map[1000][250];
int ans, m, n;
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };

void bfs(int x, int y) {
	q.push({ x, y });
	map[x][y] = 0;
	while (!q.empty()) {
		int a = q.front().first;
		int b = q.front().second;
		q.pop();
		for (int i = 0; i < 8; i++) {
			if (a + dx[i] >= 0 && a + dx[i] < m && b + dy[i] >= 0 && b + dy[i] < n
				&& map[a + dx[i]][b + dy[i]] == 1) {
				map[a + dx[i]][b + dy[i]] = 0;
				q.push({ a + dx[i], b + dy[i] });
			}
		}
	}
	ans++;
	return;
}

int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1) {
				bfs(i, j);
			}
		}
	}
	cout << ans;
	return 0;
}

www.acmicpc.net/problem/13549

그냥 단순한 bfs 문제인줄 알았지만 간선이 0인 경우를 고려해야 해서 까다로운 문제였다..

결국 해결 하지 못해 힌트를 보고 말아서 좀 아쉬운 문제였다..

참고: www.acmicpc.net/board/view/38887#comment-69010

위에서 나오듯이 

1. 다익스트라 알고리즘을 사용하는 법

2. 0-1 BFS: 간선이 0(순간이동)을 넣을 떄 큐의 맨 앞에 넣는 법

3. * 2를 별도의 간선으로 생각하지 않고, +1이나 -1에 의한 좌표를 큐에 넣을 때 그 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법

위의 세가지 방법 중에 하나를 사용하는 되는 문제였고 난 덱을 사용해서 결국 2번 방법을 사용해 풀 수 있었다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

deque<pair<int, int>> dq;
int visit[100001];
int n, k;

void bfs(int x) {
	visit[x] = 1;
	dq.push_back({ x, 0 });
	while (!dq.empty()) {
		int y = dq.front().first;
		int z = dq.front().second;
		dq.pop_front();
		if (y == k) {
			cout << z;
			return;
		}
		if (2 * y <= 100000 && visit[2 * y] == 0) {
			visit[2 * y] = 1;
			dq.push_front({ 2 * y , z});
		}
		if (y - 1 >= 0 && visit[y - 1] == 0) {
			visit[y - 1] = 1;
			dq.push_back({ y - 1, z+1 });
		}
		if (y + 1 <= 100000 && visit[y + 1] == 0) {
			visit[y + 1] = 1;
			dq.push_back({ y + 1, z+1 });
		}
	}
}

int main() {
	cin >> n >> k;
	bfs(n);
	return 0;
}

www.acmicpc.net/problem/1707

처음엔 그냥 두 개의 벡터를 만들어서 나누는 식으로 구현을 하려 했지만 실패했고 결국 답을 볼 수 밖에 없었다.

1. 큐와 간선 그래프 등을 포함해 모든 것을 테스트 케이스마다 초기화 해주기

2. 연결 그래프가 아닐 수도 있다는 것

이 두가지가 중요한 문제였다고 생각한다.

결국 푼 방법은 0, 1, 2 세가지의 종류로 정점들을 나눴고 이를 활용해서 풀 수 있었다.

참고: hugssy.tistory.com/231

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

bool c = true;
int k, v, e;
queue<int> q;
vector<int> edges[20001];
int visit[20001];

void bfs(int x) {
	q.push(x);
	visit[x] = 1;
	while (!q.empty()) {
		int y = q.front();
		q.pop();
		for (int i = 0; i < edges[y].size(); i++) {
			int z = edges[y][i];
			if (visit[z] != 0 && visit[y] == visit[z]) {
				c = false;
				return;
			}
			if (visit[z] > 0) {
				continue;
			}
			q.push(z);
			visit[z] = visit[y] % 2 + 1;
		}
	}
}

int main() {
	int a, b;
	cin >> k;
	while (k--) {
		cin >> v >> e;
		for (int i = 0; i < e; i++) {
			cin >> a >> b;
			edges[a].push_back(b);
			edges[b].push_back(a);
		}
		for (int i = 1; i <= v; i++) {
			if (visit[i] == 0) {
				bfs(i);
			}
			if (!c) {
				cout << "NO" << "\n";
				break;
			}
		}
		if (c) {
			cout << "YES" << "\n";
		}
		while (!q.empty()) {
			q.pop();
		}
		for (int i = 1; i <= v; i++) {
			visit[i] = 0;
			edges[i].clear();
		}
		c = true;
	}
	return 0;
}

www.acmicpc.net/problem/1759

처음엔 그냥 next_permutation을 사용하고 l개 만큼 만 출력하는 식으로 해결하려 했지만 메모리 초과가 나서 시간이 꽤 걸렸던 문제이다.

메모리 초과의 문제는 정확힌 모르겠지만 string의 메모리가 제대로 해제가 되지 않았거나 벡터에 중복값들이 들어가서 그랬던 것 같다.

계속 시행착오를 겪다가 그냥 정렬을 해놓고 0과 1로 이루어진 임시 벡터를 사용해 조합을 한다면 어차피 정렬은 되있기에 자음과 모음의 개수만 체크해주면 되는 문제였다.

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

vector<string> s;

int main() {
	int l, c, check1 = 0, check2 = 0;
	string a = "";
	cin >> l >> c;
	vector<char> v(c);
	vector<int> temp;
	for (int i = 0; i < c; i++) {
		cin >> v[i];
	}
	for (int i = 0; i < c; i++) {
		if (i < l) {
			temp.push_back(0);
		}
		else {
			temp.push_back(1);
		}
	}
	sort(v.begin(), v.end());
	do {
		a = "";
		check1 = 0, check2 = 0;
		for (int i = 0; i < c; i++) {
			if (temp[i] == 0) {
				a += v[i];
			}
		}
		for (int i = 0; i < a.size(); i++) {
			if (a[i] == 'a' || a[i] == 'e' || a[i] == 'i' 
				|| a[i] == 'o' || a[i] == 'u') {
				check1++;
			}
			else {
				check2++;
			}
		}
		if (check1 >= 1 && check2 >= 2) {
			s.push_back(a);
		}
	} while (next_permutation(temp.begin(), temp.end()));

	for (int i = 0; i < s.size(); i++) {
		cout << s[i] << "\n";
	}

	return 0;
}

www.acmicpc.net/problem/1916

그냥 단순한 다익스트라 알고리즘을 사용한 문제였다.

최근 본 코테에서 다익스트라가 나왔는데도 불구하고 생각이 안나 못풀었던 걸 생각하면ㅠㅠ 미리 왜 공부를 안했나 후회가 되는 문제였다.

참고 블로그: alswnsdl.tistory.com/13

이 블로그를 통해 우선순위를 이용한 다익스트라 알고리즘을 공부하였고 문제에 적용할 수 있었다.

#define _CRT_SECURE_NO_WARNINGS
#define INF 1e9
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
	int V, E, start, end;
	int a, b, c;
	cin >> V >> E;
	vector<pair<int, int>> arr[1001];
	int dist[1001];

	for (int i = 0; i < E; i++) {
		cin >> a >> b >> c;
		arr[a].push_back({ b,c });
	}
	cin >> start >> end;
	fill(dist, dist + V + 1, INF);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

	pq.push({ 0, start});
	dist[start] = 0;

	while (!pq.empty()) {
		int cost = pq.top().first;
		int here = pq.top().second;
		pq.pop();

		for (int i = 0; i < arr[here].size(); i++) {
			int next = arr[here][i].first;
			int ncost = arr[here][i].second;

			if (dist[next] > dist[here] + ncost) {
				dist[next] = dist[here] + ncost;
				pq.push({ dist[next], next });
			}
		}
	}
	cout << dist[end];
	return 0;
}