본문 바로가기

백트래킹14

[백준] 2468번 안전 영역 JAVA (자바) 풀이 문제 2468 (dfs, 백트래킹)지역의 높이 정보를 파악지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정각 지역의 높이 정보 = N크기의 2차원 배열 형태배열의 각 원소 = 높이 침수 정도를 어떤 높이로 설정해야 안전한 영역이 최대가 되는지 계산해라 예) N=5 → 5 x 5 배열 6826232346673327253689527 높이가 4 이하인 지점 물에 잠겼다 = 회색6826232346673327253689527 →  안전한 영역 = 물에 잠기지 않는 지점 상, 하, 좌, 우로 인접하며 그 크기가 최대인 영역→  안전한 영역 = 5개 높이가 6이하인 지점이 잠긴다면 안전.. 2024. 1. 22.
[백준] 1182번 부분수열의 합 JAVA (자바) 풀이 문제 1182번  :  N개의 정수로 이루어진 수열    크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하기  [입력] :  첫 줄에 정수 개수 N, 정수 S (1 ≤ N ≤ 20, |S| ≤ 1,000,000)     둘째 줄에 N개의 수열이 공백으로 구분[출력] : 합이 S가 되는 부분수열 개수 출력 [과정] - [공통] 공집합일 경우를 생각해야 하므로 S = 0 이라면 -1 하고 시작한다  - 재귀적 백트래킹반복문을 쓰지 않아서 좀 더 직관적으로 코드를 간결하게 볼 수 있다dfs(next,sum);         dfs(next,sum+arr[start]); 예) [3, 7, 2] / S=9        backtrack(0, 0)              ├.. 2023. 11. 27.
[백준] 15649번 N과 M(1) JAVA (자바) 풀이 문제 15649번 (백트래킹) :  자연수 N과 M이 주어졌을 때,     1부터 N까지 자연수 중에서 중복 없이 M개를 골라서 수열을 모두 구하는 프로그램        (예) N = 3, M = 1 인 경우    1~3까지의 수 중에서 1개만 골라서 만들 수 있는 수열을 모두 만든다    1 / 2 / 3 이렇게 만든 수열을 한줄에 하나씩 출력한다  [입력] :  첫 줄에 자연수 N, M (1 ≤ M ≤ N ≤ 8)[출력] : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력 (중복 수열 X)   수열의 원소는 공백으로 구분해서 출력  : 수열은 사전 순으로 증가하는 순서로 출력  [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 문제 조건) 숫자 중복금지 → 완전 탐색이 아닌.. 2023. 11. 13.
[백준] 14888번 연산자 끼워넣기 JAVA (자바) 풀이 문제 14888번 : N개의 수열 (A1, ... , AN) 주어진다 수 사이에 끼워넣을 수 있는 N-1개의 연산자 (+ 덧셈, - 뺄셈, × 곱셈, ÷ 나눗셈) 주어진다 숫자 순서 바꿀 수 X, 연산자 순서 바꿀 수 O : 우선순위 무시하고 앞에서부터 계산 나눗셈은 몫만 구하고, 음수를 양수로 나눌 때에는 숫자끼리만 나누고 몫에 -만 붙여준다 (=음수처리) : 결과식 최대인 것과 최소인 것을 구해라 [입력] : 첫 줄에 수열 개수 N : 둘째 줄 N개의 수열 : 연산자 개수 ( +, -, ×, ÷ 순서 ) [출력] : 식 최댓값 첫째줄에, 식 최솟값 둘째줄에 출력 [알고리즘] 모든 경우를 분석해야 하는구나 = 완전 탐색 = 브루트 포스 연산자의 조합을 이용해야 한다 = 순열 순열을 쉽게 구하기 위해서는.. 2023. 10. 29.

티스토리툴바