본문 바로가기

Problem Solving1218

[백준] 16924 십자가 찾기 - Brute Force / Java • 문제 링크 16924번: 십자가 찾기 십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크 www.acmicpc.net • 풀이 과정 문제에 대한 접근 방식은 * 로 만들 수 있는 십자가를 찾는 것이 아닌, 갖가지 크기의 십자가만이 주어졌을 때 예제 입력의 상태로 만들 수 있는 지를 찾는 것이다. 따라서 십자가를 적용할 수 있는 시작점을 map 배열의 n - 1 * m - 1 의 범위내에서 찾고 해당 시작점에서 4 방향을 모두 탐색 가능할 시, 십자가를 적용할 수 있는 경우이므로 탐색한 모든 좌표를 boolean 배열에 방문 표시한다. 십자가의 개수를 나타내.. 2022. 8. 3.
[백준] 2580 스도쿠 - Backtracking / Java • 문제 링크 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net • 풀이 과정 입력받은 스도쿠 판의 값 중 비어있는 칸의 좌표를 제네릭이 Node 클래스인 List 객체 list 에 저장한다. 재귀 호출 함수 recur 에서 비어있는 좌표의 y, x 값을 list 에서 꺼내어 해당 값이 속한 가로, 세로축을 모두 탐색하고 3 * 3 정사각형을 탐색할 시작점의 좌표를 ny, nx 라 하였을 때 ny = y / 3 * 3, nx = x / 3 * 3 을 통하여 시작점을 구할 수 있다. 예시로 y, x 값이 2, 5.. 2022. 8. 2.
[백준] 16943 숫자 재배치 - Backtracking / Java • 문제 링크 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net • 풀이 과정 입력받은 문자열 a를 순열으로써 charAt() 으로 인덱스를 탐색하고, boolean 배열을 활용한 백트래킹으로 구한다. 이때 문제에 주어진 조건 상 구해진 순열이 0 으로 시작하면 안되고 b 보다 작거나 같아야 하므로 순열의 하나의 경우의 수를 c 이고 탐색을 수행할 반복문의 인덱스를 i 라고 할 때, 현재 문자열 a 에서 탐색한 숫자가 0 이거나 (a.charAt(i) - '0' == 0), 구해진 순열이 .. 2022. 8. 1.
[백준] 16922 로마 숫자 만들기 - Backtracking / Java • 문제 링크 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net • 풀이 과정 4개의 수 중에서 n개의 순열을 찾되, 서로 다른 수를 찾아야 하는 문제의 조건을 고려하여야 한다. 예를 들어 n = 6 일 때, I I I I I L = 1 + 1+ 1+ 1+ 1 + 50 = 55, V X X X X X = 5 + 10 + 10 + 10 + 10 + 10 = 55 과 같이 합이 중복인 값이 존재한다. 따라서 1 ≤ N ≤ 20 조건에 의해 합의 최대 값은 50 * 20 = 1000, 인덱스의 범위를 벗어나지 않기 위해 크기가 1001 인 boolean 배열을 생성하여 중복을 검사한다. 백트래킹을 활용하여 순열의 .. 2022. 7. 31.
[백준] 1744 수 묶기 - Greedy / Java • 문제 링크 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net • 풀이 과정 수열의 합의 최대 값을 만들기 위해선 양수와 음수가 곱해져서 더 큰 음수를 만들지 않고, 음수와 음수끼리 곱하여 양수로 만들거나 0 와 음수를 곱하여 음수를 제거하여야 한다. 양수의 경우 내림차순으로 정렬하여 큰 순서대로 두 수를 곱하거나, 연산을 하는 두 수 중 1이 존재 할 시 두 수를 곱하는 대신 더한다. 따라서 양수는 양수끼리 연산하고, 음수는 0을 포함한 음수끼리 연산하여야 하므로 서로 다른 List 객체 pn (posit.. 2022. 7. 30.
[백준] 12904 A와 B - Greedy / Java • 문제 링크 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net • 풀이 과정 A 에서 B 로 변환하는 과정에서 재귀 호출 함수로 풀이 시 두 가지 연산의 모든 경우의 수를 모두 고려하므로 시간 초과가 발생한다. 따라서 B 에서 A 로 변환하여 B 의 끝자리의 문자에 따라 한 가지 경우의 수만 고려하는 방식으로 접근한다. A 문자열을 s, B 문자열을 StringBuilder 객체 t 에 입력받고 연산에 의해 두 문자열의 길이가 같을 때까지 while 문을 수행한다. t 문자.. 2022. 7. 29.

티스토리툴바