브루트포스 알고리즘

[Python] 백준 14888번 : 연산자 끼워넣기

문제 14888번: 연산자 끼워넣기 [ 문제 조건 ] 입력 N : 수의 개수 A1 ~ An : 수들 sum(N-1) : 합이 N-1인 4개의 정수, 연산자 4개의 각각 개수가 주어짐 (+,-,×,÷) 순으로 출력 만들 수 있는 식의 최대 & 최소 값 출력 -10억 ≤ 결과값 ≤ 10억 [ 해결순서 ] 백트래킹 유형은 dfs를 주로 사용하는 것 같아 dfs로 풀어보려고 했다. 모든 경우의 수를 전부 구해 최대 최소를 비교하는 문제여서 어쨌든 모두 비교해서 구해야한다. 처음 먼저 plus가 1이니까 dfs가 걸려 깊이우선탐색 후 나머지 연산까지 깊이우선탐색 해 값을 갱신 깊이우선탐색 plus 연산은 끝났고, 나머지 연산 중 multiply 값이 1이므로 해당 연산 기준으로 재귀적으로 dfs 진행 후 최대, ..

[Python] 백준 9663 : N-Queen

문제 https://www.acmicpc.net/problem/9663 [ 문제 조건 ] 1 ≤ N < 15 출력 : 서로 공격할 수 없게 놓는 경우의 수 백트래킹 문제 → 개념을 알고 있어야 함 [ 해결순서 ] 체스판에 퀸을 놓기위한 조건은 퀸의 가로, 세로, 대각선에 위치한 곳에 두면 안된다. 백 트래킹 문제에선 퀸을 놓을 때 직전의 열에 두지 않는다고 한다. ( 중복제거를 위해 ) 하나의 행에 하나의 퀸만 놓을 수 있다. 그렇다면 N * N개의 경우의 수가 존재 할 텐데 이 중에서 서로 공격하지 않게 놓는 경우의 수를 구해야한다. nqeen()은 퀸을 오른쪽 행으로 하나씩 옮기면서 경우의 수를 확인하고 check()로 행은 비교할 필요가 없고 (3번참고) 같은 열인지, 대각선상에 있는지 비교한다. ..

[Python] 백준 2468번 - 안전 영역

문제 https://www.acmicpc.net/problem/2468 [ 문제 조건 ] 문제에서 예시를 들어 설명할 때 모든 경우를 다 조사해 보면 이라고 설명되어 있다. 즉, 모든 경우의 수를 조사해야 됨 (이라고 나는 이해했다.) 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력 [ 해결순서 ] 배열을 입력할 때 N 이상인 값들만 방문여부를 True 값으로 바꾸고 깊이우선탐색을 진행한다. 깊이우선탐색을 진행하고 끝날때 안전영역 값(count)을 늘린다. 또 깊이우선탐색을 반복해야하는데 현재 count 값이 1차에서 3번째 줄처럼 할려고 했으나, ..