본문 바로가기

Problem Solving1486

[백준] 10819 차이를 최대로 - Backtracking / Java • 문제 링크 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net • 풀이 과정 방문 여부를 확인하는 재귀 호출 함수로 입력받은 배열의 중복을 허용하지 않은 모든 순열을 구한다. 순열에 문제에 제시된 (arr[0] - arr[1]) + (arr[1] - arr[2]) + ... + (arr[n - 2] - arr[n - 1]) 의 연산을 수행하는데 이는 배열의 현재 인덱스와 다음 인덱스를 뺀 값을 sum 변수에 연속해서 더하며 식의 최댓값을 구하는 순서를 찾기 위해, 뺄셈의 값은 절대값으로 계산한다. 각각의 순열에서 구해진 연산.. 2022. 7. 8.
[백준] 6603 로또- Backtracking / Java • 문제 링크 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net • 풀이 과정 while 문에서 입력의 한 라인을 StringTokenizer 로 받되, 첫 토큰이 0이 아닐 시에만 탐색을 수행한다. 첫 토큰이 곧 문제상 k값이며 int 배열 arr 와 boolean 배열 visit 의 크기를 k 로 생성하고 원소를 저장한다. 해당 배열을 재귀 함수의 깊이가 6일 때까지 호출하여 탐색하며, 인덱스의 방문 여부를 확인하는 방식으로 구한 각각의 순열을 StringBuilder 에 적절히 줄바꿈하여 하나의.. 2022. 7. 7.
[백준] 9663 N-Queen - Backtracking / Java • 문제 링크 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net • 풀이 과정 탐색을 할 체스판을 1차원 배열로 정의하고 퀸의 위치의 열을 배열의 인덱스 값, 행을 배열의 원소의 값으로 간주하여 접근한다. 예를 들어 n = 4 이고 배열의 값이 [2, 0, 1, 3] 일 경우 체스판의 퀸의 위치는 아래와 같다. 기본적으로 퀸은 자신의 위치 기준 가로, 세로, 대각선을 모두 차지한다. 각각의 퀸을 놓을 수 있는 자리를 탐색할 때 depth 는 행을 의미하며 재귀적으로 0 ~ n 까지의 해당 열의 모든 행을 검사한다. 각 행이 다.. 2022. 7. 6.
[백준] 2529 부등호 - Backtracking / Java • 문제 링크 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net • 풀이 과정 방문 여부를 확인할 boolean 배열을 활용하는 재귀 함수로 모든 순열을 확인하되, 입력으로 주어진 부등호에 맞는 다음 수를 선택하는 함수로 검사하여 다음 수를 결정한다. 이전 인덱스의 수와 현재의 수가 부등호 조건에 맞을 경우에 String 변수에 더하는 방식이며 String 변수의 길이가 비교할 수의 크기와 같을 때 해당 분기 탐색이 완료되었으므로 List 에 더한다. 자연스럽게 모든 순열 중 최대값은 List 의 마지막 인덱.. 2022. 7. 5.
[백준] 1182 부분수열의 합 - Backtracking / Java • 문제 링크 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net • 풀이 과정 수열의 부분 집합을 구하는 여러가지 방법 중 비트 마스크를 활용하여 풀이하였다. 원소가 n개인 순열의 부분 집합의 수는 2의 n승 이며 이를 비트 연산자로 나타내면 1 2022. 7. 4.
[백준] 14888 연산자 끼워넣기 - Backtracking / Java • 문제 링크 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net • 풀이 과정 크기가 n인 number 배열을 생성해 연산할 수를 입력받아 저장하고, 연산자는 크기가 4인 operator 배열에 연산자의 개수를 입력받아 저장하여 해당 배열의 인덱스가 각각의 연산자를 의미하도록 한다. (+ : 0, - : 1, * : 2, / : 3) operator 배열에 존재하는 연산자를 사용하는 모든 연산의 경우의 수를 재귀 함수를 통해 구하고 연산자를 사용할 때마다 해.. 2022. 7. 3.

티스토리툴바