Algorithm
-
백준 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 /..
-
백준 14889 스타트와 링크Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 15. 18:24
https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net - 난이도가 어렵진 않았지만, 디테일에 신경써야 하는 문제였다. - 역시나 브루트포스 백트래킹 문제이다. 1번부터 최대 20번 선수까지 주어질 때, 각 선수가 A팀에 선택이 되던지, B팀에 선택이 되던지 두 가지의 경우의 수이고, 재귀의 깊이는 20을 넘지 못한다.(한 팀에 과반수의 인원이 들어가는 경우 바로 종결되기 때문.) 따라서, 2^20 이하의 연산량이 되므로 재귀적으로 구현이 가능하다. - 각 팀의 구성원은 ..
-
백준 14888 연산자 끼워넣기Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 15. 17:31
- N개의 수열과 N-1개의 연산자가 주어질 때, 가능한 모든 연산 결과의 최소값과 최대값을 구하는 문제이다. - 브루트 포스 문제이고, N의 범위가 2 이상 11 이하인 것으로 보아, 재귀 백트래킹으로 풀 수 있는 문제임을 알 수 있다. (약 4^11 = 2^22) - 백트래킹을 평소 열심히 연습해왔다면 쉽게 풀 수 있는 문제이다. 종결 조건은 cnt 매개변수가 n과 같아질 때, 즉 모든 피연산자를 사용 했을 때 최대 / 최소값을 최신화하면 된다. #include #include using namespace std; int n; int executed[11]; int num_plus, num_minus, num_multiply, num_divide; int min_answer = 1000000000; ..
-
백준 14503 로봇 청소기Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 15. 16:28
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net - N x M 크기의 장소가 주어진다. 테스트 케이스 마음이라 시간복잡도는 구할 수 없다고 생각.. - 벽인지 바닥인지 여부를 나타내는 place array, 그리고 청소가 된 지 여부를 체크하는 cleaned array를 두었다. - 방향은 x, y 각각 배열을 두어서, 북 : 0, 동 : 1, 남 : 2, 서 : 3 각 값을 index로 사용하도록 하였다. 즉, 현재 x,y에 해당 인덱스의 ..
-
백준 1260 DFS와 BFSAlgorithm/그래프 2021. 11. 13. 12:18
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net - 그래프 알고리즘을 처음 입문할 때 좋은 문제이다. - DFS의 경우, 재귀적으로 구현하는 경우 O(V^2)의 시간복잡도가 나온다. BFS의 경우, 인접 행렬을 사용할 것이므로 O(V^2)의 시간복잡도가 나온다. - 주의해야 할 점은, 무방향 그래프이므로 처음 인접 행렬을 구성할 때 양방향으로 등록을 해 주어야 한다는 것, 또 하나의 노드에서 여러 개의 간선..