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

Problem : https://www.acmicpc.net/problem/16986 16986번: 인싸들의 가위바위보 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되 www.acmicpc.net Approach 순열을 이용한 완전탐색과 구현이 필요한 문제였다. 먼저 문제에서 주의할 점을 짚고 가자. 입력으로 주어지는 경희와 민호의 패는 라운드 별 패가 아니다. 경희와 민호가 참여하는 게임에서 내는 패의 순서일 뿐이다. 지우가 질 경우에도 사용한 적이 없는 패를 내야한다. (서로 다른 패로 이기는 경우만을 찾는 것이 아니다.) 문제 풀이의 주요 로직은 다음과 같다..

→2021.06.24

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) 로 가는 ..

→2021.06.21

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 배열을 두어 해당 연산자가..

→2021.06.18

Algorithm/Baekjoon Online Judge

[Java] 백준 16988 (Baaaaaaaaaduk2 (Easy)) Gold 3

Problem : https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net Approach BruteForce 완전탐색과 BFS의 개념을 같이 사용한 문제였다. 일단 문제 풀이의 주요 로직은 다음과 같다. 먼저 BFS를 이용하여 상대편 돌을 Grouping한다. 그리고 그룹핑한 결과를 groups에 저장한다. 그리고 Backtracking을 사용하여 돌을 2개 놓는 모든 경우를 만든다. 그 상태에서 상대 돌을 ..

→2021.06.15

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 에 도착하는지를 검사한다. 모든 경우의 수에 대하여 위 과정을 수행한다. 생각하기..

→2021.06.14

Algorithm/Baekjoon Online Judge

[Java] 백준 9944 (NxM 보드 완주하기) Gold 3

Problem : https://www.acmicpc.net/problem/9944 9944번: NxM 보드 완주하기 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 www.acmicpc.net Approach BruteForce완전탐색 + 구현으로 문제를 풀이하였다. 문제풀이에 앞서 해당 문제는 입력의 끝이 정해져 있지 않다. 해당 내용에 관한 부분은 아래 포스팅을 참고하면 좋을 것이다. https://gre-eny.tistory.com/307 [Java] EOF(End Of File) 처리하기 EOF(End Of File) EOF(End Of File) 은..

→2021.06.13

Algorithm/Baekjoon Online Judge

[Java] 백준 17088 (등차수열 변환) Gold 4

Problem : https://www.acmicpc.net/problem/17088 17088번: 등차수열 변환 크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1] www.acmicpc.net Approach 등차수열의 공차 개념을 이용한 BruteForce(완전탐색)로 문제를 풀이하였다. 수열의 각 요소들에 -1, +1연산을 최대 1번 수행할 수 있다고 한다. 주의할 점은 0번 수행해도 된다는 것이다. 수열에서 연속된 두 요소의 차를 공차 라고 한다. 직전 숫..

→2021.06.12

Algorithm/Baekjoon Online Judge

[Java] 백준 16938 (캠프 준비) Gold 4

Problem : https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net Approach 조합(Combination)을 이용한 BruteForce(완전탐색)문제이다. 입력의 크기가 최대 15로 비교적 작으므로 가능한 풀이이다. 캠프에 사용할 문제를 고르는 전체 방법의 수는 nC2 + nC3 + ... + nCn이다. 이렇게 나온 결과 조합의 숫자들을 검증해주면 된다. 배열 요소의 총합, 최댓값, 최솟값은 Stream을 사용하여 간결한 코드로 구할 수 있다. Code import java.io.*; import java.util.Arrays; import java...

→2021.06.11

Algorithm/Baekjoon Online Judge

[Java] 백준 15683 (감시) Gold 5

Problem : https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net Approach BruteForce(완전탐색) + 구현 문제이다. 1 ~ 5번 연산을 구현해야 하고, 연산에 필요한 CCTV가 감시하고 있는 영역을 구현해야 한다. 먼저 1 ~ 5번 연산에 필요한 공통적인 부분을 구현해야 한다. (fiilLeft(), fillRight(), fillUp(), fillDown()) 위 4개 메소드는 현재 위치 (x, y)에서 XXX 방향..

→2021.06.11

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를 곱한 수가 배열에서 아직 사용이 되지 ..

→2021.06.10

티스토리툴바