백트래킹

[백준] 16943. 숫자 재배치 (Java)

문제 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net 알고리즘 브루트포스 알고리즘, 백트래킹 풀이 A, B의 크기가 최대 109 이므로 숫자의 개수는 최대 10개이다. 10개의 숫자를 나열하는 경우의 수는 10! = 약 360만개이므로 모든 경우의 수를 탐색해 답을 구한다. A에 포함된 각 숫자의 개수를 크기 10의 1차원 배열에 담는다. 예를 들어 remain[3] = 2 라면 A에 3이 2개 포함되어있다는 의미이다. 숫자 선택 dfs 를 진행하며 i번째 수의 남은 개수가 1 이상이라면..

[백준] 4574. 스도미노쿠 (Java)

문제 4574번: 스도미노쿠 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 www.acmicpc.net 알고리즘 브루트포스, 구현, 백트래킹 풀이 문제 설명에 오해의 소지가 있는 것 같다. 우선 36개의 도미노 타일은 종류 별로 모두 한 번씩 사용해야한다. (1 + 2) ~ (8 + 9) 까지의 개수가 36개이다. 또 문제에 "도미노 타일은 회전 시킬 수 있다." 고 주어져있는데 입력으로 주어지는 이미 채워진 도미노 쌍은 고정된 것으로 회전하지 않는다. 따라서 각 그리드에 대해 인접한 그리드의 값도 같이 정해주는 스도쿠 문제인 셈이다. 도미노..

[백준] 2580. 스도쿠 (Java)

문제 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 알고리즘 브루트포스, 백트래킹 풀이 빈 칸에 1부터 9까지 모든 수를 넣어보며 가능한 경우 다음 빈 칸으로 넘어가는 식으로 모든 빈 칸을 채웠을 때 결과를 출력한다. 1. 각 빈 칸의 좌표를 리스트에 저장한다. 2. 0번째 빈 칸부터 1~9까지 유효한 수를 찾는다. 3. 유효하다면 빈 칸을 그 수로 채우고, 다음 빈 칸으로 넘어간다. 4. 리스트의 마지막 빈 칸까지 채웠다면 결과를 출력한다. 유효성 확인 (y, x) 좌표에 num을 삽입할 수 있는지 확인한..

[백준] 16197. 두 동전 (Java)

문제 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 알고리즘 깊이우선탐색(DFS), 백트래킹 풀이 깊이우선탐색을 통해 상하좌우 네 방향으로 동전을 이동시키며 모든 경우를 탐색해 최소 횟수를 찾는다. 아이디어는 다음과 같다. 1. 동전의 위치를 보드 배열에 'o' 로 표시하는게 아니라 (y1,x1) (y2,x2) 좌표로 관리한다. 보드 배열을 수정하지 않음으로써 구현을 편하게 할 수 있다. 2. [N+2][M+2] 크기의 배열을 선언하여 테두리는 초기화된 0 그대로 두고, 그 안쪽 [N][M] 크기만 입력으로..

[백준] 1248. Guess (Java)

문제 1248번: Guess Given a sequence of integers, a1, a2, …, an, we define its sign matrix S such that, for 1 ≤ i ≤ j ≤ n, Sij="+" if ai + … + aj > 0; Sij="−" if ai + … + aj < 0; and Sij="0" otherwise. For example, if (a1, a2, a3, a4)=( −1, 5, −4, 2), then www.acmicpc.net 알고리즘 완전탐색, 백트래킹 풀이 한 자리에 -10 ~ 10 까지 21개의 수가 올 수 있고, n이 최대 10이므로 만들 수 있는 경우의 수는 최대 21^10 으로 굉장히 커진다. 하지만 matrix의 (i, i) 칸을 통해 i 자..

[백준] 16922. 로마 숫자 만들기 (Java)

문제 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 알고리즘 깊이우선탐색(dfs), 백트래킹 풀이 한 자리 당 (1, 5, 10, 50)으로 4가지의 선택지가 있다. 따라서 N이 20일 때 경우의 수는 420 = 240 = 2104 = 약 1034 = 1012 로 시간초과가 난다. 하지만 겹치는 수가 굉장히 많기 때문에 백트래킹을 이용하여 시간을 단축할 수 있다. 이를 위해 boolean형 배열 visited[N + 1][1001] 을 사용한다. visited[i][num]은 i번 숫자를 더했을 때 합이 num이 나온 경우가 있는지를 저장한 것이다. 동일한 횟수에 동일한 합이 나온적이 있다면 앞으로 나올 ..

[프로그래머스] N-Queen (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 브루트포스, 백트래킹 풀이 모든 칸에 퀸을 놓아보면서, 조건을 만족하는 경우를 센다. 각 행에 어떤 열에 퀸이 배치되어있는지 저장할 cols 배열을 만들고 setQueen(row)를 호출한다. 각 행에 퀸 놓기 row번째 줄에 퀸을 놓는 setQueen(int row) 함수의 동작은 다음과 같다. 1. row - 1 번째 행까지 놓아진 퀸들이 조건을 만족하지 않는다면(!avail()) 더 이상 진행하지 않고 반환 2. row가 n보다 크다면 모든 행에 퀸을 놓았고 조건을 만족하는 것이므로 ans..

[백준] 18290. NM과 K (1) (Java)

문제 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 알고리즘 브루트포스, 백트래킹 풀이 원소가 최대 100개, K가 최대 4이고 100C4 = 3,921,225 이므로 브루트포스로 문제를 해결한다. 각 칸이 더할 수 있는 칸인지 저장하기 위해 board와 동일한 크기의 boolean형 배열을 만들고, dfs(int count, int sum, int y, int x) 를 호출한다. count는 더한 수의 개수, sum은 합, y는 현재 열의 인덱스, x는 현재 행의 인덱스이다. count가 K가 되..

[SWEA] 2112. 보호 필름 (Java)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 구현, 완전탐색, 백트래킹 풀이 각 행은 약품 투입을 하지 않거나, A 약품을 투입하거나 B 약품을 투입하는 3가지 선택지가 있다. 경우의 수는 보호 필름의 두께(행의 수)는 최대 13이므로 3^13 = 약 160만 개이므로, 모든 경우의 수에 대해 완전 탐색하면서 유망하지 않은 경우는 가지 않는 백트래킹을 통해 시간을 단축한다. 유망하지 않은 경우는 현재 약품 투입 횟수가 지금까지 구한 약품 투입 횟수의 최솟값보다 크거나 같은 경우이다. 또 합격 기준이 K이면 연속된 K 줄에 같은 약품을 투입하면 무조건 검사에 통과할 수 있기 때문에 약품 투입 횟..

[백준] 16986. 인싸들의 가위바위보 (Java)

문제 16986번: 인싸들의 가위바위보 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되 www.acmicpc.net 알고리즘 구현, 브루트포스, 백트래킹 풀이 문제가 복잡해보이지만 잘 읽어보면 어렵지 않다. 승패를 알 수 있는 테이블이 주어지고, 경희와 민호가 낼 20개의 손동작이 주어진다. 지우가 모든 손동작을 다르게 내어 우승한다는 말은 지우가 N번의 손동작을 중복되지 않게 낸다는 말이므로 중복이 없는 순열을 의미한다. 따라서 중복이 없는 순열로 지우가 낼 손동작을 구했다면 셋 중 한명이 우승할 때까지 승부를 진행하고 우승자가 지우라면 1을 출력 후 프로그램을..