본문 바로가기

Problem Solving1214

[백준] 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.
[백준] 16236 아기 상어 - Implementation / Java • 문제 링크 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net • 풀이 과정 배열을 입력받을 때 상어의 위치와 거리의 초기값을 Shark 객체에 저장하고 bfs 탐색을 할 함수에 상어의 크기(2), 먹은 물고기 수 (0), 거리(0) 를 매개변수로 전달한다. bfs 탐색을 하되 문제에 제시된 조건을 적용하기 위해선 우선 순위 큐를 활용해야한다. 상어와의 거리, y축, x축 순으로 PriorityQueue 자료구조에 Comparator 오름차순으로 비교하여 우선 순위를 지정한다. 이러한 규칙을 전제로 상어.. 2022. 7. 2.
[백준] 14502 연구소 - Implementation / Java • 문제 링크 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net • 풀이 과정 연구소에 벽을 3개 세우는 모든 경우의 수를 재귀적으로 dfs 를 통해 구한다. 이렇게 벽을 세운 각각의 경우의 바이러스 확산을 bfs 를 통해 구현하고 이때 바이러스를 확산시킬 공간은 기존 lab 배열을 복사한 copy 배열을 생성해 구현한다. 바이러스가 확산된 copy 배열을 매개변수로 받아 해당 배열에 존재하는 0의 개수, 즉 안전 영역의 크기를 배열을 전체 탐색하여 구하고 이를 매번 maxCnt와 비교하여 최댓값으로써 갱신하여 정답을 출력한.. 2022. 7. 1.

티스토리툴바