들어가기에 앞서
Naver 코테가 당장 코앞이어서 그 당시 같이 알고리즘 스터디를 준비하던 사람과 문제를 준비하고 2시간 안에 문제를 푸는 연습을 했다. 그렇게 어려운 문제로 준비하지는 않았고, BFS, DFS, DP, 시뮬레이션 유형의 문제를 준비했다....
하지만 Naver는 호락호락하지 않았다!!!! 미친 완전 다른 문제가 나왔다 ㅠㅠ
자료구조를 조금 더 열심히 공부할 필요가 있어 보인다...
이분탐색, 분할정복, 그리디... 등
백준 1012 - 유기농 배추
간단한 탐색 문제이다.
방문확인용 배열을 만들고, 밭에서 배추를 찾는다. 이때 찾은 배추를 방문한 적이 없다면 해당 배추를 시작점으로 BFS를 탐색한다. BFS를 탐색하면서 방문한 배추들은 방문확인용 배열에 체크한다.
BFS가 한번 끝나면 지렁이가 하나 필요하니까 카운트를 해준다.
다시 밭에서 배추를 탐색한다. 마찬가지로 배추가 방문한 적이 없는 경우에만 BFS를 시작해야한다!!
코드는 아래와 같다
#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;
int T;
int M, N;
int K;
int baechoo[50][50] = { 0, };
int bc_copy[50][50] = { 0, };
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
queue<pair<int, int>> q;
int answer = 0;
/*
배추 가로 : M / 배추 세로 : N / 배추 개수 : K
*/
bool check(int x, int y) {
if (x > -1 && x < N && y > -1 && y < M)
return true;
return false;
}
void bfs(int x, int y) {
q = queue<pair<int, int>>();
q.push(make_pair(x, y));
bc_copy[x][y] = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (check(nx, ny) && baechoo[nx][ny] == 1 && bc_copy[nx][ny] == 0) {
bc_copy[nx][ny] = 1;
q.push(make_pair(nx, ny));
}
}
}
}
void search() {
memset(bc_copy, 0, sizeof(bc_copy));
answer = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (baechoo[i][j] == 1 && bc_copy[i][j] == 0) {
answer += 1;
bfs(i, j);
}
}
}
}
int main() {
cin >> T;
for (int testcase = 0; testcase < T; testcase++) {
memset(baechoo, 0, sizeof(baechoo));
cin >> M >> N >> K;
int x, y;
for (int i = 0; i < K; i++) {
cin >> y >> x;
baechoo[x][y] = 1;
}
search();
cout << answer << '\n';
}
}11724 - 연결 요소의 개수
유기농 배추와 유사한 문제다
방문확인용 배열을 만들고 1번 정점부터 탐색한다. 정점을 방문한 적이 없다면 해당 정점을 시작점으로 BFS를 돌린다. 방문한 정점들은 방문확인용 배열에 체크한다.
BFS가 끝나면 마찬가지로 하나의 연결 요소가 있는 것이므로 카운팅한다.
다시 정점 탐색을 이어간다. 이때 역시 정점이 방문한적이 없는 경우에만 해당 정점을 시작으로 BFS를 돌려야한다.
코드는 아래와 같다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> graph[1000];
int N, M;
bool visit[1000] = { false, };
queue<int> q;
void bfs(int n) {
q = queue<int>();
q.push(n);
visit[n] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int i = 0; i < graph[node].size(); i++) {
int next_node = graph[node][i];
if (!visit[next_node]) {
q.push(next_node);
visit[next_node] = true;
}
}
}
}
int main() {
cin >> N >> M;
int x, y;
for (int i = 0; i < M; i++) {
cin >> x >> y;
graph[x - 1].push_back(y - 1);
graph[y - 1].push_back(x - 1);
}
int cnt = 0;
for (int i = 0; i < N; i++) {
if (!visit[i]) {
cnt++;
bfs(i);
}
}
cout << cnt << '\n';
}백준 14502 - 연구소
간단한 구현 문제이다.
따라서 로직만 아이디어대로 흘러간다면 문제가 없다.
- 빈 칸에 벽을 세 개 세우는 조합을 모두 구한다.
- 조합마다 벽을 실제로 세우고 바이러스를 퍼뜨린 뒤, 안전 영역을 센다.
- 모든 조합을 다 해보고 가장 큰 안전 영역이 존재할 때의 안전 영역 값을 출력한다.
코드는 아래와 같다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M;
int map[8][8] = { 0, };
int copy_map[8][8] = { 0, };
vector<pair<int, int>> virus;
vector<pair<int, int>> space;
vector<int> comb;
queue<pair<int, int>> q;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
int answer = -1;
/*
벽을 3개 꼭 세워라 먼저 벽을 세우고 바이러스가 존재하는 칸으로부터 바이러스를 퍼뜨린다.
바이러스가 퍼질 수 없는 곳을 안전 영역이라고 하는데, 안전 영역 크기의 최댓값을 구해라
*/
bool check(int x, int y) {
if (x > -1 && x < N && y > -1 && y < M) {
if (copy_map[x][y] == 0)
return true;
}
return false;
}
void bfs() {
for (int i = 0; i < virus.size(); i++) {
q.push(virus[i]);
}
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (check(nx, ny)) {
copy_map[nx][ny] = 2;
q.push(make_pair(nx, ny));
}
}
}
}
void spread_virus() {
copy(&map[0][0], &map[0][0] + 64, ©_map[0][0]);
for (int i = 0; i < comb.size(); i++) {
int index = comb[i];
int x = space[index].first;
int y = space[index].second;
copy_map[x][y] = 1;
}
bfs();
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (copy_map[i][j] == 0) {
cnt++;
}
}
}
answer = max(answer, cnt);
}
void create_wall(int depth, int start) {
if (depth == 3) {
spread_virus();
}
else {
for (int i = start; i < space.size(); i++) {
comb.push_back(i);
create_wall(depth + 1, i + 1);
comb.pop_back();
}
}
}
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
if (map[i][j] == 2) {
virus.push_back(make_pair(i, j));
}
else if (map[i][j] == 0) {
space.push_back(make_pair(i, j));
}
}
}
create_wall(0, 0);
cout << answer << '\n';
}백준 1932 - 정수 삼각형
일일히 탐색하기에는 시간초과가 날 것이라는 것을 삼각형 사이즈만 보면 알 수 있다.
따라서 DP를 사용해 풀이한다!!
아마 그림만으로도 풀이가 쉽게 이해가 될 것이라고 생각한다.
코드는 아래와 같다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int tree[500][500] = { 0, };
int dp[500][500] = { 0, };
int main() {
cin >> n;
int input;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i + 1; j++) {
cin >> input;
tree[i][j] = input;
}
}
dp[0][0] = tree[0][0];
if (n == 1) {
cout << tree[0][0];
}
else {
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] + tree[i][j];
}
else if (j == i) {
dp[i][j] = dp[i - 1][j - 1] + tree[i][j];
}
else {
dp[i][j] = max(dp[i - 1][j - 1] + tree[i][j], dp[i - 1][j] + tree[i][j]);
}
}
}
int answer = -1;
for (int i = 0; i < n; i++) {
answer = max(answer, dp[n - 1][i]);
}
cout << answer << '\n';
}
}소감
Naver 코테가 쉽게 나왔다... 심지어 3문제...
구현으로는 다 풀었다.. 그 대신 O(n^2) 급으로 풀이했기 때문에 부분 점수가 존재하지 않는 이상 다 틀렸을 것 같다 ㅠㅠ
그래도 느낀 점이라면 현재 8주차까지의 알고리즘을 풀이했는데, 이렇게 일주일동안 느긋하게 푸는 것도 중요하지만 가끔은 2시간 또는 3시간씩 시간을 정해놓고 알고리즘을 푸는 연습을 하는게 좋은 것 같다.
그런 압박감 속에서는 알고리즘을 떠올리기도 힘들고,, 실수가 났을 때 당황하지 않고 침착하게 풀어나가는 연습을 하기 좋은 것 같다.
이번 연습 때는 2시간 안에 네 문제를 전부 풀어서 좀 자만했었는데 자만하지말고~ 최선을 다해야겠다.
아참, 마지막으로는 시간이 n^2이 걸리더라도 당장 자료구조가 떠오르지 않는다면 일단 문제를 풀어라! 그러고 나서 나중에 알고리즘을 수정하면 된다고 생각한다.
