문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 백트래킹 문제이다. 체스판에서 퀸이 공격할 수 있는 위치는 상하좌우와 대각선상의 모든 위치이다. 4x4 체스판의 (0,0) 위치에 퀸 하나를 두었을 때, 퀸이 공격 가능한 위치를 그림으로 나타내면 다음과 같다. 즉, nxn의 판에서 퀸 n개를 모두 서로 공격할 수 없는 위치에 놓으려면 각 퀸들이 상하좌우 대각선 중 어느 곳에도 위치해서는 안된다. 이 조건을 분해해보면, 1. 각 행에는 무조건 퀸이 존재..

문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 주어진 연산자들의 순열을 순차적으로 탐색하며 최솟값과 최댓값을 찾는다. 연산자들의 다음 순열을 찾아 나가므로, 연산자 배열을 string이 아닌 int 배열로 만든다. 숫자 n개가 주어질 때, 연산자의 총 개수는 n-1개이므로, 연산자 배열의 길이는 n-1이다. +를 0, -를 1, x를 2, %를 3으로 하여 연산자 배열에 저장한..

문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 주어진 두 단어의 알파벳을 숫자로 바꾸어 더했을 때의 최댓값을 구하는 문제이다. 만약, ABCDE와 FGH를 더할 때, 각 알파벳에 어떤 숫자가 오든지간에 ABCDE가 더 큰 숫자가 된다. 단어의 길이가 더 길다면, 더 높은 자릿수의 숫자이기 때문이다. 이런 경우, 같은 자릿수를 가지는 CDE와 FGH를 제외하고, 더 높은 자릿수인 A와 B에 큰 수 9와 8을 배치할 것이다. 그리..

문제 https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 풀이 백트래킹 방법으로 문제를 해결할 것이다. 백트래킹 방법은 가지를 탐색하다가 옳지 않으면 바로 다른 가지로 넘어간다. 이 문제에서는 첫번째 자리의 수부터 k+1번째 자리의 수까지 추가해나가며 탐색한다. 탐색 중에 j번째 자리에 넣을 수가 이전 수와의 부등호 조건에 맞지 않으면(ex- 부등호가

문제 https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 풀이 부등호가 k개 존재할 때, 부등호 앞 뒤로 숫자가 들어가게 되므로 숫자는 k+1개가 놓일 것이다. 어떤 부등호가 k개 쓰이든지 간에, k+1개의 숫자가 최대가 되려면 0부터 9까지의 정수 중 큰 k+1개의 정수만이 쓰여야 한다. 반대로, 최소가 되려면, 작은 k+1개의 정수만이 쓰여야 한다. ① 최댓값을 찾는 방법 가장 큰 수부터 시작하여 점점 작은 수를 탐색한다. 따라서 현재의 순열이 부등호의 조..

문제 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 풀이 사다리가 있는 위치라면 사다리를 타고 올라갈 위치가 존재하고, 뱀이 있는 위치라면 뱀을 타고 내려갈 위치가 존재한다. 사다리와 뱀이 있는 위치와, 이동할 위치를 해시맵으로 저장한다. ladder = new HashMap(); //사다리와 이동 위치 저장할 해시맵 snake = new HashMap(); //뱀과 이동 위치 저장할 해시맵 fo..