bruteforce
-
brute force알고리즘 2020. 3. 26. 21:39
Brute Force 브루트 포스 - 개념 : brute "난폭한, 무식한"이라는 뜻이고, brute-force는 "무식한 힘, 폭력" 이라 해석할 수 있다. 영어 뜻처럼 단순무식한 알고리즘 방식이다. 완전 탐색 알고리즘(Exhaustive Search) 이라고도 한다. 가능한 모든 경우의 수를 탐색하면서 문제를 해결하는 방법이다. - 사용 : 선형 구조에서는 순차 탐색, 비선형 구조에서는 깊이우선탐색(dfs), 너비우선탐색(bfs)가 있다. - 장&단점 장점 : 만들기가 쉽고, 다른 알고리즘을 구현하기 전 기본이 되어 주는 알고리즘이다. 단점 : 시간면에서 비효율적이다. - 무식한 방법이지만, 공간과 시간이 충분하다면 당연히 정확도 100%를 보장한다. - 예시문제로 백준 15683 & 15684 같은..
-
[백준] 15684 사다리 조작문제 풀이 2020. 3. 26. 21:15
15684 사다리조작 문제사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.사다리 게임은 각각의 세로선마..
-
[백준] 15683번 감시문제 풀이 2020. 3. 26. 20:08
15683 감시 문제스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.1번2번3번4번5번1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.CCTV는 회전시킬 수 있는데,..