본문 바로가기

브루트포스

 (9)
백준 21277 짠돌이 호석 (파이썬) https://www.acmicpc.net/problem/21277 21277번: 짠돌이 호석 DIY(Do It Yourself)는 호석이가 제일 좋아하는 컨텐츠이다. 이번 DIY는 동네 친구 하늘이랑 각자 직소 퍼즐을 하나씩 맞춰보기로 했다. 두 개의 퍼즐은 각자 N1 행 M1 열과 N2 행 M2 열의 격자 형태 www.acmicpc.net 풀이 구현 문제이다. 그러나 회전한다는 점을 생각하는게 까다로웠다. 그러나 풀이 자체는 그리 어려운 편이 아니다. 아래의 글을 참고하여 풀었다. https://ongveloper.tistory.com/526 백준 21277 짠돌이 호석 Kotlin (완전탐색) 문제 출처 : https://www.acmicpc.net/problem/21277 21277번: 짠돌이 호..
백준 16988 Baaaaaaaaaduk2 (Easy) (파이썬) https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net 문제를 풀지 못하여 다른 블로그의 글을 참고하였으나...가독성이 떨어지고 불필요한 코드가 있어 고생했다. 나같은 사람들이 없기를 바라면서 글을 정리한다. 풀이 이 문제는 BFS와 조합탐색을 이용해서 해결하는 문제이다. 문제를 해결하는 방법은 다음과 같다. 상대측 돌의 그룹을 찾고 만약 상대측 돌의 그룹에 인접해 있는 빈 칸이 2개 이하이면 해당 그룹과 인..
백준 20164 홀수홀릭호석 (JAVA) 문제 https://www.acmicpc.net/problem/20164 20164번: 홀수 홀릭 호석 호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 www.acmicpc.net 코드 package com.company; import java.util.Scanner; public class Main { static String N; static int max = Integer.MIN_VALUE; static int min = Integer.MAX_VALUE; static int temp = 0; public static void main(String[] args) {..
백준 2615 오목 (JAVA) 문제 https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { private static int[] dr = {-1, 0, 1, 1, 1, 0, -1, -1}; private static int[] dc = {1..
[백준] 2630 색종이 만들기(JAVA) https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 필자는 문제를 처음보고 분할 정복과 재귀를 이용하면 쉽게 풀릴것 같다는 생각을 하였다. 이번에는 두개의 코드를 포스팅 할것이다. 우선 첫번째 코드는 내가 짠 코드이고 두번째는 다른 사람들이 짠 코드이다. 첫번째 코드는 우선 처음 메소드에 들어가면 해당사이즈 만큼의 색종이가 하나의 색으로 되어있는지 확인하고 만약 여기서 하나의 색으로만 되어있으면 그자리에서 바로 함수..
[백준] 14500 테트로노미노 (JAVA) 풀이 이 문제를 처음 접근할떄는 어떠한 규칙이 있는지 확인 하였다. 그러나 문득 어느 한점에서 DFS처럼 갈수있는 공간을 하나씩 만들다보면 테트로노미노를 대칭 혹은 회전시킨 도형이 나온다는것을 알아차리고 DFS로 하였다. 물론 이러면서 중복이 발생하는 경우도 있었지만 신경쓰지 않고 진행하였다. 그리고 마지막으로 ㅗ모양을 따로 처리를 해주어야 한다. 또한 중간에 Math.max함수를 사용할수 있음에도 사용하지 않은 이유는 풀이시간이 차이가 나기때문이다. 처음 통과하였을떄는 Math.max를 하였는 결과값이고 두번째는 삼항연산자로 하였는것이다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRead..
[백준] 14502 연구소 (JAVA) 풀이 위의 문제는 BFS와 DFS를 적당히 조합하여 푸는 문제이다. 문제를 푸는 순서는 다음과 같다. 문제에서 벽을 3개를 세워 안전구역의 최대값을 구하라고 하였다. 우리는 벽을 세우고 바이러스를 퍼트리는 일을 한번에 할수 없으니 벽을 먼저 세우고 만약 세운 벽의 개수가 3개이면 바이러스를 퍼트리는 식으로 하였다. 벽을 세우는 과정은 브루트 포스로 처음부터 끝까지 모든 경우의 수를 확인 하였고 바이러스를 퍼트리는 과정은 퍼트리기전 바이러스의 위치를 큐에 전부 넣고 큐에 있는 바이러스 위치를 토대로 하나씩 뽑아 가면서 퍼트릴수있다면 퍼트리고 큐에 추가하는 방식으로 진행하였다. 코드 import java.io.BufferedReader; import java.io.IOException; import java..
[백준] 14888 연산자 끼워넣기 (JAVA) https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 이 문제는 저번과 마찬가지로 백트래킹에 대해 알고있다면 어떠하게 풀지 감이 오는 문제였다. 나는 처음 이문제를 접하였을때 매경우 최적의 경우를 찾아내는 방법이 있는줄 알고 고민하였으나 브루트 포스라는 카테고리를 보고 그냥 전부 돌리기로 생각했다. 여기서 변수는 숫자의 개수를 나타내는 N, 최대값 MAX 최소값 MIN, 숫자들을 담을 ar..
[백준] 1182 부분수열의 합 (JAVA) 풀이 살짝 변칙적인 백트랙킹 인듯하다. 이문제에서는 for문이 필요하지 않다. 이해는 코드를 보면 갈것이다. 백트랙킹 문제를 더 풀어봐야 할것 같다. package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { static int N; static int S; static int count=0; static int Sum; static int[] Num; public static void main(String[] args) throws IOException { BufferedRea..

티스토리툴바