컴퓨터 공학 기초/알고리즘 (브루트포스)
-
백준 15683 (감시)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 20. 18:47
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감�� www.acmicpc.net 해당 문제는 각 CCTV 당 최대 4개의 경우의 수를 가질 수 있다. 따라서 map을 탐색하며 CCTV 가 존재할 경우 해당 CCTV가 감시할 수 있는 모든 경우의 수를 탐색하면 되는 문제이다. 재귀의 흐름을 보면 다음과 같다. 위와 같이 탐색 된 CCTV의 종류 별로 나올 수 있는 모든 경우의 수를 탐색하며 탐색되는 영역을 visit 배열에 체크하며 재귀를 수행하면 문제를 해결할 ..
-
백준 14503 (로봇 청소기)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 20. 14:27
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 해당 문제는 재귀를 이용하여 지문의 조건에 맞게 풀었다. 지문의 조건을 요약하면 다음과 같다 1. 청소기의 현재 방향을 기준으로 왼쪽이 청소를 하지 않은 영역이라면 해당 영역을 청소하고 청소기의 방향전환 2. 만약 청소기의 왼쪽 영역이 청소가 되어 있거나 벽이라면 청소기의 방향을 왼쪽으로 돌린 뒤 다시 1 부터 수행 3. 만약 청소기를 계속 왼쪽 방향으로 돌려 4방위를 모두 탐색했을 때 모든 방..
-
백준 14891 (톱니바퀴)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 16. 21:47
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 � www.acmicpc.net 풀이 해당 문제는 재귀를 사용하여 회전시킬 톱니바퀴의 위치와 -1 or + 1 위치에 해당하는 톱니바퀴의 마주보는 면을 비교하며 회전시킬지 말지 선택하여 풀면 되는 문제이다. 주의 사항 예를들어 하나의 톱니바퀴가 회전하고 인접한 위치의 다른 톱니바퀴가 회전해야 한다면 다른 위치의 톱니바퀴를 기준으로 또 다른 톱니바퀴가 회전하는 경우의 수 까지 구해야 한다. 즉 3 번이 회전하고 그에 따라..
-
백준 14499 (주사위 굴리기)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 16. 17:03
https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 풀이 해당 문제 풀이의 핵심은 주사위의 회전 (동, 서, 북, 남 방향으로 회전) 을 구현하는 것과 회전하기전 주사위의 위치를 이동시켜 이동시킨 위치가 주어진 N * M 좌표 안에 존재하는지 체크하는 부분이다. 1. 주사위 회전구현 주사위의 각 면에 해당하는 크기 6개의 배열이 필요하며, 이동했을때 각 면이 어떻게 이동했는지 알수있..
-
백준 3190 (뱀)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 16. 14:30
https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. www.acmicpc.net 풀이 해당 문제는 완전탐색 문제로 재귀함수를 이용하여 풀이할 수 있다. 조건을 살펴보면 다음과 같다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 ..
-
백준 14888 (연산자 끼워넣기)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 16. 12:03
https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 풀이 해당 문제는 DFS로 모든 경우의 수를 탐색하면서 MAX, MIN 값을 구하면 되는 문제이다. 1. 숫자 배열과, 연산자 기호를 넣을 배열을 동시에 운용하며 문제를 풀이 2. 재귀함수를 통해 level이 N값과 같아지면 return 3. 각 재귀시 for 루프는 연산자의 개수만큼 수행한다. and visit 배열을 사용하여 각 연산..
-
백준 14501 (퇴사)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 15. 19:42
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 DFS 재귀함수를 사용하여 풀면 되는 간단한 문제이다. 조건을 정리하면 다음과 같다 1. N이 주어지며 N + 1 일째 되는날 퇴사를 한다. 따라서 일을 수행할 수 있는 날은 N일 까지이다 2. 상담시 당일을 포함하여 날짜를 계산 EX ) 1일에 상담을 실시하며 1일에 수행하는 상담 소요일이 2일 일경우 1, 2 일 이렇게 총 2틀이 소요 됨 따라서 다음 상담은 3일에 가능하다. 따라서 당일 + 상담 소요일을 하면 다음 상담 가능 날짜가 구해진다. 이때 주의를 해야하는 부분이 마지막 날 일 경우이다 만약 N == 7 일 경우 7..
-
백준 14500 (테트로미노)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 15. 19:05
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 풀이 DFS를 사용하여 풀이하면 되는 문제이다. 1. 최대 입력값은 500이기 때문에 배열의 크기는 500으로 할당 2. ㅗ 도형을 제외한 나머지 도형은 위, 아래, 우측, 좌측 으로 이동하며 DFS를 돌리면 도형이 나온다. EX ) 우측, 우측, 우측, 우측 -> " ---- " 과 같이 예제에서 주어지는 도형 중 " ㅗ " 자 도형을 제외한 모든 경우의 수는 위, 아래, 왼쪽, 오른쪽 방향으..