Algorithm & Problem Solving/브루트포스(Brute Force)
-
[백준 15683] 감시 (Python)Algorithm & Problem Solving/브루트포스(Brute Force) 2021. 2. 14. 19:37
www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 문제풀이 N, M, board : 입력값 cctv, cctv_n : CCTV 좌표 리스트, CCTV 개수 ans : 최소 사각지대 개수 check : 방문 여부 확인 재귀를 이용해 모든 CCTV를 4방향 돌리면서 감시 가능 영역을 만들어보는 브루트포스 방식으로 해결할 수 있다. 1. CCTV 좌표 및 개수 세주기 2. 재귀를 이용해 모든 CCTV의 감시 영역 탐색하기 - CCTV 종류에 따라서 방향 ..
-
[백준 2922] 즐거운 단어 (Python)Algorithm & Problem Solving/브루트포스(Brute Force) 2020. 12. 15. 13:53
www.acmicpc.net/problem/2922 2922번: 즐거운 단어 상근이는 자신이 다니는 학교에서 영어단어를 가장 많이 외우고 있다. 그 비법은 바로 조기교육이었다. 상근이는 젖병을 물기도 전에 영어 단어를 외웠다. 따라서, 지금은 자리에 앉으면 사전을 www.acmicpc.net 문제풀이 mo : 모음 ja : 자음 S : 입력값 go(s, idx, ch) : 재귀적으로 _에 문자를 놓는 함수, s : 문자열, idx : 인덱스, ch : _에 지금까지 사용한 단어 verify(s) : s가 문제의 조건(자음, 모음 연속 3개인지 아닌지, s에 L이 포함되어 있는지)에 위배하지 않는지 확인 _ 에 들어올 수 있는 글자는 모음, L이 아닌 자음, L 총 3가지 가능 => 3^10 이므로 브루트..
-
[백준 14889] 스타트와 링크 (Python)Algorithm & Problem Solving/브루트포스(Brute Force) 2020. 11. 29. 16:43
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 문제풀이 N, board : 입력값 check : 두 개의 팀을 나누기 위한 bool 순열 tmp : 순열의 마지막까지 도달했는지 확인하기 위한 check의 마지막 순열 ans : 결과값(두 팀의 능력치 차이의 최솟값) next_permutation(a) : 특정 순열의 다음 순열을 구하는 함수 단순히 bool 순열을 구하기만 하면 풀 수 있는 문제이다. python itertools의 permutation을 쓰면 시간이 좀 더 빠..
-
[백준 12100] 2048 (Easy) (Python)Algorithm & Problem Solving/브루트포스(Brute Force) 2020. 11. 24. 12:00
www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 풀이 N, board : 입력값 p: 행이나 열에서 블록이 이동하게 될 가장 끝의 위치 x: 이전 블록이 새로운 블록과 합쳐지는것을 표현 => 이전 블록을 저장하고 있는 변수 move_up(board) : 블록을 상단으로 이동 move_down(board) : 블록을 하단으로 이동 move_right(board) : 블록을 우측으로 이동 move_left(board) : 블록을..
-
[백준 15684] 사다리 조작 (Python)Algorithm & Problem Solving/브루트포스(Brute Force) 2020. 11. 24. 00:45
www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 문제풀이 N, M, H : 입력값(세로선의 개수, 가로선의 개수, 가로선을 놓을 수 있는 위치) board : 특정 지점 방문 여부 체크 ans : 가로선을 놓은 최소 개수(결과값) check() : i번 세로선이 i번으로 잘 도착하였는지 확인하는 함수 dfs(cnt, x, y) : 재귀적으로 가로선을 놓을 수 있는 곳에 다 놓는 함수, cnt - 현재까지 가로선을 놓은 개수, x - 행, y - 열 골드 5..