백트랙킹

    [Java] 백준 16985 (Maaaaaaaaaze) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16985 (Maaaaaaaaaze) Gold 3

    Problem : https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net Approach BruteForce(완전탐색) 순열 + BFS + 구현 개념이 사용된 문제였다. 문제 풀이에 사용된 주요 로직은 다음과 같다. 주어진 판들의 순서를 순열로 구하여 쌓는다. 쌓인 판들을 0도, 90도, 180도, 270도를 돌려서 나오는 모든 경우를 찾는다. 2번 과정에서 찾아진 각 경우에 대해 (0, 0, 0) ~ (4, 4, 4) 로 가는 ..

    [Java] 백준 16638 (괄호 추가하기 2) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16638 (괄호 추가하기 2) Gold 1

    Problem : https://www.acmicpc.net/problem/16638 16638번: 괄호 추가하기 2 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계 www.acmicpc.net Approach Backtracking 기법과 중위표기 -> 후위표기 를 위한 Priority, Stack 등을 사용해야 했던 문제이다. 중첩된 괄호는 사용할 수 없고, 괄호 안에는 하나의 연산자만 존재할 수 있다는 점을 활용하면, 연산자를 기준으로 괄호를 씌울 것인지 말 것인지를 결정하면 된다는 걸 알 수 있다. 따라서 brackets 배열을 두어 해당 연산자가..

    [Java] 백준 15684 (사다리 조작) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 15684 (사다리 조작) Gold 4

    Problem : https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net Approach 백트랙킹 Backtracking을 활용하여 BruteForce 완전탐색으로 풀이하였다. 가로선을 놓을 수 있는 개수는 0, 1, 2, 3개 이다. 이를 이용하여 문제를 푸는 주요 로직은 다음과 같다. 가로선을 놓을 수 있는 개수만큼 가로선을 놓아본다. 이 때, A 번째 사다리가 A 에 도착하는지를 검사한다. 모든 경우의 수에 대하여 위 과정을 수행한다. 생각하기..

    [Java] 백준 16936 (나3곱2) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16936 (나3곱2) Gold 5

    Problem : https://www.acmicpc.net/problem/16936 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net Approach Backtracking으로 BruteForce(완전탐색)를 수행하는 문제이다. 만들 수 있는 모든 경우의 수를 탐색하기 위해 백트랙킹 기법을 사용하였다. 모든 숫자를 시작 숫자로 시도해 보아야 한다. 3으로 나누어 떨어지면, 3으로 나눈 수가 배열에서 아직 사용이 되지 않았는지 검사하고 재귀 호출한다. 2를 곱한 수가 배열에서 아직 사용이 되지 ..

    [Java] 백준 16198 (두 동전) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16198 (두 동전) Gold 4

    Problem : https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net Approach 백트랙킹(Backtracking)을 이용한 완전탐색(BruteForce)문제 이다. BFS로도 풀이가 가능할 것 같다. 먼저 두개 동전의 위치를 찾는다. (입력으로 map을 구성하면서 찾을 수 있다.) 그리고 다음 작업을 반복한다. 두 동전을 상하좌우 방향으로 굴려본다. 굴렸을 때 3가지 상황이 발생한다. 두 동전이 모두 떨어지면 더 이상 굴려보지 않는다. (돌..

    [Java] 벡준 1248 (맞춰봐) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 벡준 1248 (맞춰봐) Gold 3

    Problem : https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문 www.acmicpc.net Approach Backtracking을 이용하여 완전탐색(BruteForce)를 수행하는 문제이다. 이 문제에서 주의할 점을 좀 적어보겠다. 중복된 수로 수열을 만들 수 있다. 숫자 0 과 문자 '0'은 다르다. 수열을 완전히 만들고 검사하는 것이 아니라, 만드는 과정에서 검사가 이루어져야 한다. 먼저 주어진 문자열로 i ~ j까지의 합의 상태를 나타낸 s[i][j..

    [Java] 백준 17136 (색종이 붙이기) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 17136 (색종이 붙이기) Gold 2

    Problem : https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net Approach BruteForce + DFS + Backtracking 문제이다. DP로도 풀 수 있을까 고민했지만, 색종이의 개수 제한도 있고 개수를 어떻게 세야할 지 감이 안와서 다른 방법을 생각했다. 색종이를 붙일 수 있는 모든 곳에 대해서 색종이 사이즈가 5, 4, 3, 2, 1인 색종이를 붙일 수 있는지 각각 검사한다. 현재 사용한 색종이의 개수가 최솟값보다 ..

티스토리툴바