Algorithm/구현(Brute force, Back tracking, etc.)
-
백준 21608 상어 초등학교Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 25. 13:59
https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net - 빡구현 문제이다. 시간복잡도는 N^2명의 학생이 N^2개의 칸을 순회하면서 자신이 앉을 위치를 찾아나가므로 총 O(N^4)이다. - 일단 student_order배열에 앉을 순서대로 학생들의 번호를 넣고, 학생들을 배치하기 시작한다. 이 과정에서 모든 칸을 순회하면서, 어느 칸에서 좋아하는 학생이 인접 칸에 가장 많이 있는지를 탐색한다. 이 과정에서 벡터에 후보 칸을 모두 담는데, ..
-
백준 20057 마법사 상어와 토네이도Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 24. 11:48
https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net - 빡구현 문제이다. 시간복잡도는 모든 칸을 순회하면서 각 칸에서 모래를 이동시키므로(상수연산) O(N^2)이다. - 필자는 먼저, 각 칸의 다음 이동 방향을 dir배열에 구현했다. 그 후, 이 방향을 기반으로 하여 토네이도가 이동한 후 흩날리는 모래들을 구해서 각 칸에 넣어주는 식으로 구현을 했다. - 방향을 구하는 과정은 1. 먼저, 해당 칸의 방향 최신화 2...
-
백준 20056 마법사 상어와 파이어볼Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 22. 13:29
https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net - 시뮬레이션 + 구현 문제이다. 시간복잡도는 k번 이동 * 각 이동마다 m개의 파이어볼이 이동하므로 O(km)이다. - 필자는 모든 정보를 vector 하나로 해결했다. vector에 들어가는 요소들은 순서대로 질량, 속력, 방향, 이동 여부이다. - 가장 먼저, 파이어볼의 정보를 받아 push_back한다. 이 후, 총 k번의 이동을 진행한다. 1. 파이..
-
백준 20055 컨베이어 벨트 위의 로봇Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 17. 15:44
https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net - 시간복잡도는, 칸과 로봇을 옮기는 작업 O(N) + 내구도가 로봇이 올려질때마다 반드시 깎이므로 O(2NA)해서 O(2NA)이다. - 칸의 개수와 로봇의 개수를 배열에 담고, while문 조건으로 매 단계마다 내구도가 0인 칸의 개수가 k 이상인지를 확인한다. 가장 먼저 로봇과 벨트를 한 칸씩 이동시키고, 로봇이 내리는 칸에 도달했으면 로봇을 내려준다. 이동 과정에서 첫 ..
-
백준 19237 어른 상어Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 16. 18:42
https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net - 맵의 크기는 최대 N^2이고, 총 t초동안 이동가능하므로 O(t * N^2)이므로 시간초과는 나지 않는다. - 가장 먼저, 상어들이 이동하기 위한 좌표를 한 번에 구한다. 한 번에 이동까지 하도록 구현을 하면, 로직이 굉장히 복잡해 질 것이다.(상어들이 한 번에 이동을 하는 것을 가정하기 때문에, 한 마리씩 이동시키는 것은 거의 불가능할 것이다.) ..
-
백준 17822 원판 돌리기Algorithm/구현(Brute force, Back tracking, etc.) 2021. 12. 1. 16:28
https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net - 브루트포스 + 빡구현 문제이다. - 시간복잡도는 N개의 행에 대해서 rotation을 돌리는 데에 M^2 = O(NM^2) + 모든 칸에 대해서 인접 칸을 살펴야 하므로 O(NM) = O(NM^2)이다. 따라서, 주어진 시간 내에 통과가 가능하다. - 처음 문제를 읽었을 때 어떻게 틀을 잡아야 하는지 망설여질 수 있는데, 삼성 기출이 늘 2차원 배열에서 시작하는 것을 기반으로 ..
-
백준 17779 게리맨더링2Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 30. 19:51
https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net - 브루트포스 + 빡구현 문제이다. - 시간복잡도는, 최악의 경우 거의 O(N^6)까지도 도달할 수 있다. 하지만 N의 최대값이 20이므로 1억 이하이기 때문에 해당 알고리즘으로 통과가 가능하다. - 시작점 x,y와 모든 d1, d2에 대한 경우의 수들을 선택해서 계산을 해야 한다. 4중 for문으로 4가지 변수값을 선택했다면, area 배열에 구역을 입력 해 주면 된다. 일단 1. 5번 경계점들을 넣..
-
백준 17142 연구소3Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 26. 12:40
https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net - 브루트포스 백트래킹 + BFS 문제이다. - 시간 복잡도는 BFS에 O(N^2) + 백트래킹은 10Cn의 최대값이므로, 값이 10! 이하이기에 시간초과는 나지 않는다. - 먼저, map에 정보를 입력받는다. 이 때, virus의 좌표 정보는 virus 벡터에 따로 저장한다. 그 후, m개의 바이러스를 선택한다. 선택을 하는 과정은 백트래킹을 통해 진행하며, 전역변수 selected_virus에 해당 좌..