전체 글
-
백준 16235 나무 재테크Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 18. 17:22
https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net - 단순 구현 문제이다. 특이점으로는 for loop이 여러개가 중첩된다. 따라서, 집중해서 잘 코드를 구현하는게 중요하다. 또한, 하나의 1x1 구역에 여러 개의 나무가 심어질 수 있다는 것에 유의한다. 이걸 C로는 어떻게 구현을 하는지는 모르겠지만, C++에는 vector라는 무기가 있기 때문에 2차원 vector 배열을 선언해서 각 영역에 존재하는 나무의 나이를 push 해 ..
-
백준 16234 인구 이동Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 18. 15:45
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net - 그래프 탐색을 활용하는 구현 문제이다. - 시간 복잡도는 알 수가 없다.. 언제까지 인구 이동이 일어날 지를 모르기 때문 - 가장 먼저, 모든 영역에 대해 BFS를 진행한다. 단 이미 다른 연합에 속한 영역은 진행하지 않는다. BFS를 진행할 때 마다 연합의 번호를 초깃값 1부터 1씩 늘려주면서 연합의 번호를 표시를 한다. 이는 나중에 인구 이동을 하기 위함이다. - 그 후, 모..
-
백준 15686 치킨 배달Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 18. 12:02
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net - 브루트포스 백트래킹 문제이다. - 치킨집 최대 13개 중 M개를 고르는 경우의 수 중 최대값은 13C6이며, 해당 경우에 각 집마다 치킨집과의 거리를 구해야 하므로 시간복잡도 값은 13C6∗2∗50∗13=2230800 정도가 나온다. - a벡터에 치킨집 m개의 좌표를 push 해 가면서 m개를 채우는 모든 경우의 수가 될 때 마다 치킨거리를 구하는 식으로 구현을 한다. 초..
-
백준 15685 드래곤커브Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 17. 19:19
https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net - 시간복잡도는 신경 쓸 필요 없는 문제이다. g가 최대 10일때, 2^10 + 2^9 .. 정도의 계산량밖에 되지 않기 때문 - 규칙을 찾아내면 된다. 스택2개와 큐 1개를 사용했는데, 더 간단한 방법이 있지 않을까 생각한다. - x,y좌표는 계속해서 최신화하면서, 어느 방향으로 전진해야 하는 지를 구한다. 예를 들어 0과 1을 사용하여 전진을 했다면, 다음 세대에서 ..
-
백준 15694 사다리 조작Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 17. 17:51
https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net - 문제를 꼼꼼히 잘 읽어봐야 한다. 300C3의 경우의 수가 나온다. - 사다리는 최대 3개를 둘 수 있다. 또한, 사다리를 가로로 연달아서 둘 수 없다. - visited[i][j]는, i번 세로선에서 i+1 세로선으로 이동할 때 사용된 가로선이 j라는 뜻이다. 즉, i에서 i+1로 이어질 때, 가로선 j가 사용 된 것이다. - 매번 가로선을 놓을 때 마다, test를 진행한다. 시간 초과를..
-
백준 15683 감시Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 17. 12:05
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net - 역시나 브루트포스, 백트래킹 문제이다. 구현 난이도 자체는 어렵지 않다. - 감시카메라의 좌표를 벡터에 담고, 해당 카메라가 가질 수 있는 모든 경우의 수에 대해 조사를 한다. 감시가 되는 구역을 선택할 때 (1) 해당 구역이 벽이면 감시구역 조사를 중단한다. (2) 해당 구역이 0이면 감시구역(-1)임을 표시한다. (3) 해당 구역이 감시카메라이거나 이미 감시된 구역인 경우 con..
-
백준 14891 톱니바퀴Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 16. 20:42
- 무난한 구현문제이다. (백준 골드5) - 8개의 톱니 * 4개의 톱니바퀴 * 최대 100의 회전 수를 해서 시간복잡도는 신경쓰지 않아도 된다. - 한 번의 회전이 일어날 때 마다, 각 톱니바퀴들이 어느 방향으로 회전 할 지를 조사하여 일괄적으로 변화시키도록 구현한다. - 처음 톱니의 상태를 입력을 받을 때, string 타입의 vector로 받는다. 그 후, 회전시킬 톱니바퀴와 방향을 입력받는다. 톱니바퀴를 기준으로 왼쪽에(혹은 오른쪽에) 있는 톱니들로 이동하면서 회전 여부 및 어느 방향으로 회전을 할 지를 vector d에 담아서 처리한다. #include #include #include using namespace std; int main() { int n = 4; vector a(n); // 8..
-
백준 14890 경사로Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 16. 14:04
- 단순(하지만 시간이 많이 걸리는) 구현 문제이다. 시간복잡도는 O(n^2)이다. - 각 행과 각 열에 대해 test를 거쳐서, 경사로를 놓아 지나갈 수 있는 길을 몇 개나 만들 수 있는지를 체크하면 된다. 따라서, check하는 함수를 따로 두고 vector를 넘겨서 체크하도록 하였다. 만약 이렇게 하지 않는다면 4중 for문이 되어 코드의 가독성이 많이 떨어지게 된다. - 조건에 따라 분기를 해 준다. 1. 인접한 두 개의 칸을 비교해서 높이가 다른 경우 1) 두 칸의 높이 차가 1을 초과하는 경우 -> false 2) 두 칸의 차이가 1인 경우 (1) 이전 칸이 다음 칸보다 작은 경우 => 이전 칸(i-1)에서 l 길이 만큼의 블록들을 체크 해 간다. => i-1칸과 높이가 다르다면 false /..