들어가기에 앞서
벌써 알고리즘 스터디가 4주차에 들어섰다!!
이렇게 꾸준히 잘 이어나갈 줄은 잘 몰랐는데, 잘 진행되서 기쁘다.
멤버도 한명 추가되었다. 예전에 나랑 같이 학부생 인턴을 하시던 분인데 취직 전 코테 준비도 할겸 같이 공부하기로 되었다. 이 분 덕분에 이슈로 깃을 관리하면서 알고리즘 풀이를 올리는 방법을 배웠다!!
백준 2156
이 전에 비슷한 문제를 풀어본 적이 있어서, 쉽게 풀었던 것 같다. 사실 그림에서는 i번째까지 그려져 있지만 쥬스가 3개 있을 때를 생각하면 규칙을 바로 떠올릴 수 있다. 쥬스가 세 개 있을 때, 세 번째 쥬스까지 탐색을 한다면 가장 많이 마실 수 있는 경우는 아래의 세 가지 경우 중 하나이다.
1) 첫 번째까지 먹을 수 있는 최대 쥬스 량 + 세 번째 쥬스 량
2) 0 번째까지 먹을 수 있는 최대 쥬스 량(0) + 두 번째, 세 번째 쥬스 량
3) 세 번째 쥬스를 먹지 않는 경우, 두 번째 쥬스까지 먹을 수 있는 최대 쥬스 량
따라서 이 규칙을 i번째에도 적용시키면, 아래와 같다.
1) i-3번째까지 최대로 마실 수 있는 쥬스 량 + i-1번째 쥬스 량 + i번째 쥬스 량
2) i-2까지 최대로 마실 수 있는 쥬스 량 + i번째 쥬스 량
3) i를 마시지 않고 i-1번째까지 최대로 마실 수 있는 쥬스 량
DP 배열을 만들고,dp[i]에는 i까지 마실 수 있는 최대 량을 저장하고 있으면 된다.
최종 출력에서 dp[n]의 값을 구하면 끝난다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int dp[10000] = { 0, };
int juice[10000] = { 0, };
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> juice[i];
if (i == 0) {
dp[i] = juice[i];
}
else if (i == 1) {
dp[i] = juice[i - 1] + juice[i];
}
else if (i == 2) {
dp[i] = max(juice[i - 1] + juice[i], dp[i-2] + juice[i]);
dp[i] = max(dp[i - 1], dp[i]);
}
else {
dp[i] = max(dp[i - 3] + juice[i - 1] + juice[i], dp[i - 2] + juice[i]);
dp[i] = max(dp[i - 1], dp[i]);
}
}
if (n == 1 || n == 2)
cout << dp[n - 1] << '\n';
else
cout << dp[n - 1] << '\n';
}백준 6118
너무 너무 간단한 문제이다.
아이디어만 제시하면, 먼저 그래프를 만든다. 그래프를 만드는 방법에는 다양한 방식이 있을 수 있는데, 나의 경우 이전 문제들에서 많이 시도했던 방식으로 특정 정점이 어떤 정점들과 연결되어있는지 정보를 가지도록 만들었다.
이후에 BFS를 돌리고, visit 배열에는 각 칸에 몇 번만에 도달했는지 정보를 저장했다. 방식은 위 그림과 같다.
최종적으로 마지막에 기록된 depth와 같은 칸들이 몇 개인지 찾고, 그 중 가장 번호가 작은 정점을 출력하면 된다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <memory.h>
using namespace std;
int N, M;
vector<int> v[20000];
queue<pair<int, int>> q;
int visit[20000];
int dist = 0;
void BFS() {
memset(visit, -1, sizeof(visit));
q.push(make_pair(0, 0));
visit[0] = 0;
while (!q.empty()) {
int node = q.front().first;
int depth = q.front().second;
dist = max(depth, dist);
q.pop();
for (int i = 0; i < v[node].size(); i++) {
int next = v[node][i];
if (visit[next] == -1) {
q.push(make_pair(next, depth + 1));
visit[next] = depth + 1;
}
}
}
}
int main() {
int A, B;
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> A >> B;
v[A - 1].push_back(B - 1);
v[B - 1].push_back(A - 1);
}
BFS();
int cnt = 0;
int number = 10000;
for (int i = 0; i < N; i++) {
if (visit[i] == dist) {
cnt++;
number = min(i, number);
}
}
cout << number + 1 << " " << dist << " " << cnt << '\n';
}백준 8972
정말 복잡한 구현 문제였다. 조건은 간단하다.
- 종수를 옮긴다, 움직임 카운트를 +1한다. 아두이노를 만나더라도 움직임은 +1해야한다.
- 미친 아두이노를 종수와 가까운 쪽으로 움직인다.
- 이동시킨 아두이노들이 겹치는지 확인한다. 겹치는 아두이노들을 폭파된 것으로 간주하기 때문에 더 이상 추적할 필요가 없다.
- 이 과정을 반복한다.
미친 아두이노를 관리하는 방법은 다음과 같다.
- 처음에 미친 아두이노의 좌표들을 crazy_aduino 벡터에 저장한다.
- 미친 아두이노들을 각각 종수와 가까워지는 쪽으로 이동시키고 이동시킨 좌표들을 temp 벡터에 저장한다. 그리고 겹치는 아두이노들이 있는지 확인해야하므로, visit배열과 같은 방문 확인용 배열을 0으로 초기화해둔 상태에서 아두이노가 특정 칸으로 이동하면 해당 칸을 +1 한다.
- crazy_aduino를 초기화한다.
- 현재 temp 배열에는 이동한 아두이노들의 좌표들이 저장되어있다. 하나씩 꺼내서 visit 배열에서 해당 좌표의 값이 1이면 crazy_aduino에 담는다. 1 이상이라면 해당 칸으로 이동한 아두이노가 두 개 이상이라는 얘기이므로, 해당 아두이노는 폭파되었기 때문에 더 이상 추적하지 않는다. 따라서 crazy_aduino에 담지 않는다.
코드는 아래와 같다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <cstdlib>
using namespace std;
int R, C;
char board[100][100];
char direction[100];
int dx[9] = { 1, 1, 1, 0, 0, 0, -1, -1, -1 };
int dy[9] = { -1, 0, 1, -1, 0, 1, -1, 0, 1 };
pair<int, int> me;
vector<pair<int, int>> crazy_aduino;
int move_num = 0;
bool check(int x, int y) {
if (x < R && x >= 0 && y < C && y >= 0)
return true;
return false;
}
bool move_crazy_aduino() {
vector<pair<int, int>> temp;
int visit[100][100] = { 0, };
int x = me.first;
int y = me.second;
for (auto it : crazy_aduino) {
int min_dist = 200;
pair<int, int> next;
int cx = it.first;
int cy = it.second;
int nx, ny;
for (int k = 0; k < 9; k++) {
nx = cx + dx[k];
ny = cy + dy[k];
if (check(nx, ny)) {
if (abs(x - nx) + abs(y - ny) < min_dist) {
min_dist = abs(x - nx) + abs(y - ny);
next = make_pair(nx, ny);
}
}
}
temp.push_back(next);
visit[next.first][next.second] += 1;
}
crazy_aduino.clear();
memset(board, '.', sizeof(board));
board[x][y] = 'I';
for (int i = 0; i < temp.size(); i++) {
if (board[temp[i].first][temp[i].second] == 'I') {
return true;
}
else if (visit[temp[i].first][temp[i].second] == 1) {
crazy_aduino.push_back(temp[i]);
board[temp[i].first][temp[i].second] = 'R';
}
}
return false;
}
bool game_start(int cnt) {
for (int i = 0; i < cnt; i++) {
int idx = direction[i] - '0';
int nx = me.first + dx[idx - 1];
int ny = me.second + dy[idx - 1];
if (!check(nx, ny))
continue;
if (board[nx][ny] != 'R') {
board[me.first][me.second] = '.';
me = make_pair(nx, ny);
board[nx][ny] = 'I';
move_num++;
if (move_crazy_aduino()) {
return true;
}
}
else {
// 준수가 아두이노랑 만난 경우, 종료
// 진짜 킹받네... 움직여서 만나도 +1을 해줘야 되네;;
move_num++;
return true;
}
}
return false;
}
int main() {
cin >> R >> C;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> board[i][j];
if (board[i][j] == 'I')
me = make_pair(i, j);
if (board[i][j] == 'R')
crazy_aduino.push_back(make_pair(i, j));
}
}
int cnt = 0;
while (cin >> direction[cnt]) {
cnt++;
}
if (!game_start(cnt)) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cout << board[i][j];
}
cout << '\n';
}
}
else {
cout << "kraj " << move_num << '\n';
}
}백준 3257
제일 어려운 문제가 아니었나 싶다. 규칙을 찾는데만 한 세월이 걸렸다....
사실 설명하는 것도 굉장히 어렵다. 내 설명을 다들 잘 이해했으면 좋겠다.
시행착오 끝에 떠울릴 수 있는 규칙은 아래의 그림과 같은 것이었다.
그리고 비슷한 문제를 2차원 배열로 해결한 적이 있어서, x, y로 이루어진 2차원 배열을 쓰면 된다고 생각했다.
그러고 나서 나는 조그마한 입력 예제를 만들고 해당 입력 예제를 알맞게 풀이하려고 노력했다.
그러면 위의 그림과 같이 배열을 채울 수 있다.
그리고 나는 배열을 다 채우면 (0, 0)에서 DFS로 경로 탐색을 하면 답을 출력할 수 있다고 생각하였으나, 안되는 경우가 발생했다.
그러다가 해당 칸에 1이 올 수 없다는 것을 깨닫는다. 왜냐하면 이전 과정이 존재하지 않기 때문이다. 그리고 해당 칸에 온 숫자가 무엇인지에 따라 이전 칸이 어딘지를 찾을 수 있기 때문에, 배열을 다 만들고 마지막 칸에서 (0, 0)까지 역으로 탐색을 해야한다는 것을 발견했다.
그렇게 되면 마지막칸에 1이 오든 2가 오든 상관없이 답을 출력할 수 있다!!!
근데 사실 이 알고리즘 분류가 DP로 되어있는데 왜 DP인지 모르겠다. 그리고 뭔가 풀면서도 계속 찜찜했던 건 뭔가 규칙이 확실치 않아서 내가 제대로 풀고 있는지 계속 긴가민가했던 문제이다.
첫 번째 그림에서 떠올린 규칙을 계속 보고있으면 아 뭔가 답에 도달할듯 말듯 간질간질 거리는 그 느낌만 오고 풀지를 못해서 너무 짜증났던 것 같다... 같이 스터디하는 팀원들도 많이 힘들어했다고,,,
#include <iostream>
#include <vector>
#include <memory.h>
#include <string>
using namespace std;
string cy;
string gs;
string str;
int dp[151][151];
vector<int> answer;
void reverseSearch(int x, int y) {
int cx = x;
int cy = y;
while (cx > 0 || cy > 0) {
if (dp[cx][cy] == 2) {
answer.push_back(2);
cy--;
}
else if (dp[cx][cy] == 1) {
answer.push_back(1);
cx--;
}
}
}
int main() {
cin >> cy;
cin >> gs;
cin >> str;
int x = cy.size();
int y = gs.size();
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
for (int i = 0; i <= x; i++) {
for (int j = 0; j <= y; j++) {
if (i == 0 && j == 0)
continue;
else if (i >0 && dp[i-1][j] != -1 && cy[i - 1] == str[i + j - 1])
dp[i][j] = 1;
else if (j > 0 && dp[i][j - 1] != -1 && gs[j - 1] == str[i + j - 1])
dp[i][j] = 2;
}
}
reverseSearch(x, y);
for (int i = answer.size() - 1; i >= 0; i--) {
cout << answer[i];
}
cout << '\n';
}소감
으으으음... 조금씩 늘고 있는 것 같기도 하고? 잘 모르겠다. 하 왜 이렇게 코테에는 재능이 없는지... 좀 진짜 잘하고 싶은데 참 마음처럼 되지를 않는 것 같다!!! 진작진작 좀 해둘걸~~
