분류 전체보기

[백준 4991번] 로봇 청소기 (C/C++)

https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 로봇 청소기 문제는 BFS, 백트래킹과 메모이제이션을 이용하여 해결할 수 있습니다. 로봇 청소기 문제는 같은 칸을 여러 번 방문할 수 있으므로, 백트래킹을 이용하여 로봇이 인접한 칸으로 이동하는 모든 경우의 수를 계산하면 시간 초과가 발생할 수 있습니다. ((cur.x, cur.y)에서 인접한 (nx.x, nx.y)으로 이동하면, (nx.x, nx.y)에서 다시 (cur.x, cur.y)로 이동할 수 있으..

[백준 17144번] 미세먼지 안녕! (C/C++)

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 미세먼지 안녕!문제는 t번 미세먼지를 확산시키고, 공기청정기를 작동시켜 해결할 수 있습니다. ⚠️ 다만, 미세먼지의 확산이 모든 칸에서 동시에 발생하기 때문에, 확산시키는 것과, 확산된 양을 더해주는 것을 구분하여 진행해주어야 합니다. 또한, 공기청정기가 작동할 때, 그림에 나온 방향으로 진행하면서 한 칸씩 이동시키는 것이 아니라, 공기청정기부터 시작하여 한 칸씩 당겨주어야 합니다. 아래는 전체..

[백준 17143번] 낚시왕 (C/C+)

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 낚시왕 문제는 2차원 배열의 각 칸에서 가장 큰 상어에 대한 정보만 유지하면 해결할 수 있습니다. 단, 상어를 이동시킬 때 한 칸씩 이동시키면 시간초과가 발생할 수 있습니다. 따라서 일단 상어의 속도만큼 이동시킨 뒤, 격자판의 경계를 넘는다면 격자판의 경계로 이동시키고 방향을 바꿔주어야 합니다. 아래는 전체 코드입니다. #include using namespace std; ty..

[백준 17140번] 이차원 배열과 연산 (C/C++)

https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 이차원 배열과 연산 문제는 빈도수 배열을 이용하여 해결할 수 있습니다. 또한 문제에서 입력이 100보다 작거나 같은 자연수가 주어지며, 행 또는 열의 크기가 100을 넘지 않기 때문에 100을 초과하는 숫자가 나올 수 없습니다. 따라서 빈도수 배열의 크기는 100 또는 101로 하면 됩니다. 알고리즘의 기본 틀은 아래와 같습니다. (단, board는 2차원 배열, freq는 빈도수 배..

[백준 16236번] 아기 상어 (C/C++)

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 아기 상어는 BFS를 이용하여 해결할 수 있으며 잡아먹을 물고기가 없을 때까지 반복해주면 됩니다. ⚠️단, 상어의 이동 전 위치를 0으로 바꾸어주어야 해당 위치도 이후 반복에서 이동할 수 있습니다. 아래는 전체 코드입니다. #include using namespace std; typedef struct{int x, y;}pos; // 좌표에 대한 구조체 typedef struct{pos p..

[백준 16235번] 나무 재테크 (C/C++)

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 나무 재태크 문제는 임의의 위치 요소의 제거 그리고 제일 앞에 원소를 추가하는 연산이 빈번하므로 List를 사용하는 것이 좋습니다. 또한 번식 할 때, 나이가 1인 나무가 생기므로, 새로 생기는 나무를 리스트의 Front에 넣어주면 어린 나무부터 양분을 먹도록 할 수 있습니다. 하지만 나무가 번식할 때마다 List에 넣어주면 시간 초과가 발생합니다. 따라서 각각의 나무를 모두 하나..

[백준 16234번] 인구 이동 (C/C++)

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 인구 이동 문제는 BFS를 이용하여 해결했습니다. 각 좌표를 시작점으로 BFS를 수행하여, 인구 차이가 L명 이상, R명 이하인 연합을 찾고, 각 연합에 대해 인구 이동을 시킨 뒤, 다시 BFS를 수행합니다. BFS를 수행하고 나서 더이상 연합이 존재하지 않는다면, 종료하면 됩니다. 전체 코드는 아래와 같습니다. #include using namespace std; #define x..

[백준 17281번] ⚾ (C/C++)

https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 야구 게임 문제는 큐와 백트래킹을 이용하여 문제를 풀 수 있습니다. 백트래킹을 이용하여 타순의 모든 경우의 수를 구하고, 각 타순에 대한 게임 결과를 계산하면 됩니다. 알고리즘의 기본 틀은 아래와 같습니다. 타순의 각 경우의 수에 대해 게임을 진행한다. (단, 1번 타자를 제외한 permutation을 구한다.) 타순의 4번 타자에 1번 선수를 넣는다. 게임을 시작한다. 3-1) 이닝을 시작한다. (단..