Algorithm/Simulation

[SW Expert Academy 13732번] 정사각형 판정 (C++)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 정사각형 판정 문제는 x의 최솟값/최댓값, y의 최솟값/최댓값을 찾아 해결할 수 있습니다. x, y의 최소/최댓값을 찾은 이후에는, 가로/세로 길이가 동일한지 확인하고, 정사각형의 내부가 막혀있는 격자로 채워져있는지 확인하면 됩니다. 아래는 전체 코드입니다. #include using namespace std; #define x first #define y second char board[30][30]; int main(){ ios::sync_with_stdio(0); cin.tie(0); int t, i = 1; cin >> t; while(t--){ in..

[백준 17779번] 게리맨더링 2 (C/C++)

https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 게리맨더링 문제는 기준점, d1, d2의 모든 경우의 수에 대해 각 선거구의 인구 수를 계산하여 문제를 해결할 수 있습니다. 알고리즘의 기본 틀은 아래와 같습니다. 각 기준점, d1, d2에 대해 2번부터 수행 경계선인 경우 board 배열에 5를 표시한다. 각 칸에 대해 3-1부터 수행 3-1. 경계선이고, 경계선의 왼쪽 부분인 경우, 오른쪽으로 이동하며 5를 저장한다. (단, 다른 경계선을 만난 경..

[백준 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에 넣어주면 시간 초과가 발생합니다. 따라서 각각의 나무를 모두 하나..