문제 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 9 * 9의 네모안에서 값이 0인 지점들을 스도쿠 규칙에 따라 올바른 숫자로 채우는 문제입니다. 스도쿠 규칙은 다음 3가지를 충족하면 됩니다. 가로 9칸의 숫자가 모두 달라야합니다. 세로 9칸의 숫자가 모두 달라야합니다. 3 * 3의 작은 네모안에 있는 9칸의 숫자가 모두 달라야합니다. 다음의 순서로 풀이합니다. 0 값을 갖고 있는 지점들을 List에 저장합니다. dfs를 통해 list..

문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 유명한 N-Queen 문제를 풀면 된다. 예전에 대학교 알고리즘 수업 때 c++로 백트래킹을 써서 풀어 본적이 있었는데 이번에 자바로 다시 한번 풀어보았다. 제가 푼 방식은 다음과 같습니다. 1) 세로로 인덱스 0부터 n - 1까지 퀸을 하나씩 배치할 것입니다. 2) dfs를 사용하여 세로 -> 가로 순으로 0 ~ n - 1까지 해당 지점에 퀸을 놓을 수 있는지 확인합니다. 3) isPos() 메서드를..

문제 https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 풀이 간단하게 dfs로 풀었습니다. 여기서 중요한 부분은 구슬들을 리스트에 넣고 중간에 있는 구슬을 삭제해야 되는 부분이 있는데 자바의 list.remove()와 list.insert()는 O(n)이 걸리는 연산이기 때문에 시간초과가 날 수 있으므로 주의해서 사용해야 합니다. 이 문제에서는 n 값이 최대 10이므로 시간초과가 발생하지 않을 것이라고 생각하고 사용하여 풀었습니다. 코드 i..

문제 https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 풀이 움직임의 최소값을 찾는 문제이므로 bfs를 사용해서 풀이했습니다. 제가 사용한 풀이 방법은 1) 두 동전의 위치를 찾아서 pair에 저장해둔다 2) bfs를 사용하여 큐에 값을 넣어주고 4가지 방향으로 움직일 때 조건에 맞으면 새로운 좌표를 큐에 넣습니다. 이 때 방문 했는지 여부를 확인하기 위해 4차원 배열 visited를 사용하여 두 동전의 위치를 체크합니다. 3) 움직인 좌표가 ..

문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 이 문제는 5가지의 도형중에서 분홍색 도형은 따로 해결해주고 나머지 4가지 도형은 dfs로 풀면 됩니다. 1) 나머지 도형 2차원 배열을 이중 for문으로 돌면서 각 점마다 dfs를 진행합니다. dfs는 첫번째 점 좌표를 넘겨주고 방문체크를 하면서 총 4개의 점을 방문 했을 때 합을 구해 최대값을 갱신해주면 됩니다. 2) 분홍색 도형 이 문제가 골드 5인 이유가 이 분홍색 도형을 따로 ..

문제 https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수 www.acmicpc.net 풀이 dfs를 사용하여 풀 수 있는 문제입니다. 연산자를 사용할 때 마다 카운트 해주면서 결과 값을 갱신하고 계산이 완료 되면 최대값과 최소값을 갱신하면 됩니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ja..

문제 https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 풀이 수열의 정의에 대해서 정확히 알고 있어야 헷깔리지 않습니다. 처음에 풀 때 연속된 순서로 존재하는 값들을 부분 수열이라고 생각했는데 잘못 생각했네요.. ex) 1, 2, 3, 4 -> (1, 2, 3), (2, 3, 4), (1, 2) 이런 것들만 되는 줄 알았는데 조합이라고 생각하면 될거 같습니다. 따라서, dfs를 ..