본문 바로가기

브루트포스 알고리즘22

[백준] 17779번 - 게리맨더링 2 [Java] https://www.acmicpc.net/problem/17779 1.  아이디어 경계선을 표시하고 각 선거구의 영역에 대해 경계선에 닿기 전까지 탐색하는 방식을 활용했다.2. 문제풀이 먼저 기준점의 좌표와 d1, d2의 길이 모든 경우에 대해 탐색하는 브루트포스 알고리즘으로 접근했고 이를 위해 4중 for문으로 모든 케이스르 탐색했다. 기준점의 좌표와 d1, d2를 결정하면 해당 정보로 그림의 파란 경계선에 숫자 5를 넣은 방문 체크 배열을 만들었고 이를 활용해 탐색 경계를 구분했다. 탐색은 1번 영역은 정방향 순회, 2번 영역은 90도 돌린 정방향 순회, 4번 영역은 180도 돌린 정방향 순회, 3번 영역은 270도 돌린 정방향 순회로 탐색을 했고 탐색 과정에서 경계를 만나면 해당 안쪽 for문은 .. 2025. 2. 21.
[SWEA] 2001번 - 파리 퇴치 [Java] https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq 1.  아이디어 N의 크기가 작아서 배열의 각 점에서 파리채를 전부 내리쳐보는 브루트포스 알고리즘으로 해결이 가능하고 누적합 배열을 활용해도 해결이 가능하다.2. 문제풀이 브루트포스는 배열의 해당 점이 파리채의 왼쪽 위가 위치한다고 가정하고 4중 for문을 활용했다. 누적합 배열은 2차원 누적합으로 1행 1열부터 r행 c열까지 두 점을 대각점으로 하는 직사각형의 넓이가 저장되게 했다.3. 코드 import java.io.*;import java.util.*;public class Solution { public static void .. 2025. 2. 13.
[백준] 1018번 - 체스판 다시 칠하기 [Java] https://www.acmicpc.net/problem/1018 1.  아이디어 보드의 각 점을 8 x 8 체스판의 맨 왼쪽 맨 위 칸으로 하는 점이라고 가정하고 브루트포스 알고리즘을 적용해서 해결했다.2. 문제풀이 보드에서 만들 수 있는 모든 체스판을 탐색했으며 검은색과 흰색이 번갈아 나오는 것은 행과 열 인덱스의 합이 짝수인지 홀수인지로 판단할 수 있었다. 각 점에 대해 색칠해야하는 개수를 구한 후 이들 중 가장 최솟값을 찾아 출력했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader b.. 2025. 2. 13.
[백준] 7568번 - 덩치 [Java] https://www.acmicpc.net/problem/7568 1.  아이디어 2중 for문으로 각 사람에 대해 모든 사람과의 덩치를 비교하는 방식으로 해결했다.2. 문제풀이 N이 최대 50이어서 O(N^2)인 2중 for문의 브루트포스 알고리즘으로 접근했다. 각 사람의 키와 몸무게를 통해 다른 모든 사람과 비교해서 등수를 구하는 과정을 모든 사람에 대해 반복했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReade.. 2025. 2. 12.
[백준] 9627번 - 문장 [Java] https://www.acmicpc.net/problem/9627 1.  아이디어 Map 자료구조와 StringBuilder로 숫자에 해당하는 글자를 구하는 방식으로 해결했다.2. 문제풀이 1부터 9와 10의 배수들의 글자를 미리 Map에 static 블록을 활용해서 저장했다. 이후 getStr 메서드에서 이미 저장된 숫자면 바로 반환하고 아니면 100 이상일 때 100의 자리까지 계산하고 십의 자리 수가 2보다 크면 십의 자리와 일의 자리 글자의 조합으로, 20보다 작으면 바로 Map에서 꺼내는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final Map map = new HashMa.. 2025. 2. 12.
[백준] 16463번 - 13일의 금요일 [Java] https://www.acmicpc.net/problem/16463 1.  아이디어 13일이 금요일이려면 해당 달의 1일이 일요일이어야 한다.2. 문제풀이 윤년과 윤년이 아닌 년의 각 달의 날짜를 저장한 배열을 사용했고 윤년 여부에 따라 사용할 배열을 먼저 선택했다. 현재 요일은 week 변수에 저장했고 2019년 1월 1일이 화요일인데 일요일을 0, 토요일을 6으로 0 ~ 6까지 번호를 부여해서 현재 요일인 화요일(2)로 초기화했다. 이후 각 년의 각 월에 대해 1일이 일요일이면 개수를 세주고 해당 월의 날짜 수만큼 더한 후 7로 나누어주었다. 이렇게 하면 week는 각 년, 각 월의 1일의 요일이 계속 담기게 된다.3. 코드 import java.io.*;public class Main { /.. 2025. 2. 12.
[백준] 14500번 - 테트로미노 [Java] https://www.acmicpc.net/problem/14500 1.  아이디어 모든 테트로미노의 모양을 미리 구한 후 각각에 대해 종이에 순회하며 계산하는 방식으로 구현했다.2. 문제풀이 init 메서드로 모든 테트로미노의 모양을 2차원 배열로 구해서 List에 담았다. init은 5가지 기본 모양을 2차원 배열로 만든 후 90도, 180도, 270도 회전 메서드와 좌우반전 메서드를 작성해서 이 기본 모양을 회전 및 반전시켜 모든 테트로미노의 모양을 구했다. 테트로미노의 경우의 수- 하늘색 테트로미노는 기본 모양, 90도 회전, 총 2가지- 노란색 테트로미노는 기본 모양, 총 1가지- 주황색 테트로미노는 기본 모양, 90도 회전, 180도 회전, 270도 회전, 반전 모양, 반전+90도 회전, 반전.. 2025. 2. 10.
[백준] 17142번 - 연구소 3 [Java] https://www.acmicpc.net/problem/17142 1.  아이디어 이전 연구소 문제에서 이제 바이러스가 비활성 상태로 존재하고 활성 시킬 일부 바이러스를 선택했을 때로 바뀐 문제이다. 비활성 상태로 존재하는 바이러스도 맵에 바이러스로 존재하는 것을 고려해서 BFS 종료 조건을 변경하면 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 17141번 - 연구소 2 [Java])2. 문제풀이 초기 비활성 바이러스의 수를 virusCnt로 센 후 BFS 알고리즘을 적용했다. 종료 조건은 동일하지만 BFS에서 최단거리가 갱신될 때마다 수행하는 방식으로 구현했고 활성 바이러스가 퍼질 때 비활성 바이러스가 존재하는 칸으로 퍼지면 Queue에는 넣지만 바이러스의 수를 세지는 않는 방식으.. 2025. 2. 4.
[백준] 17141번 - 연구소 2 [Java] https://www.acmicpc.net/problem/17141 1.  아이디어 이전 연구소 문제에서 이제 바이러스를 놓을 수 있는 칸 중 바이러스를 M개 놓고 모든 위치에 바이러스를 퍼트릴 수 있는 최소 시간을 구하는 문제로 조합을 통해 바이러스를 퍼트릴 위치를 정한 후 최단거리 BFS를 통해 바이러스가 모두 퍼졌으면 최단거리를 반환하는 방식으로 해결했다.([코딩테스트 준비/백준] - [백준] 14502번 - 연구소 [Java])2. 문제풀이 빈칸 없이 바이러스가 퍼졌는지 알기 위해 벽의 개수를 wallCnt로 저장하고 바이러스를 놓을 수 있는 칸을 리스트로 저장했다. 이후 리스트에 대한 조합을 구해서 최단거리 BFS를 수행 후 이를 현재까지 구한 최단 시간과 비교 갱신하는 방식으로 구현했다. 최단.. 2025. 2. 4.
[백준] 14502번 - 연구소 [Java] https://www.acmicpc.net/problem/14502 1.  아이디어 주어진 빈 칸 중 세 개를 뽑아 벽으로 만들고 시뮬레이션을 돌린 후 다시 빈 칸으로 만드는 과정을 반복하면 해결할 수 있다. 벽을 정확히 3개를 세우면 돼서 3중 for문을 활용했고 시뮬레이션은 BFS 알고리즘을 활용했다.2. 문제풀이 입력에서 빈칸과 바이러스의 위치는 각각 리스트에 저장 후 3중 for문으로 빈칸 리스트에서 3개를 뽑아 벽으로 바꾼 후 바이러스의 위치를 통해 BFS 알고리즘을 적용했다. 이후 벽을 빈 칸으로 바꿔주면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Node { int.. 2025. 2. 4.
[백준] 5619번 - 세 번째 [Java] https://www.acmicpc.net/problem/5619 1.  아이디어 두 수를 붙여서 만든 수들 중 세 번째로 작은 수를 구하는 문제로 수어진 수열을 크기 순으로 정렬했을 때 5번째 이상으로 큰 수를 사용해서 세 번째로 작은 수를 만들 수 없음을 이용했다.2. 문제풀이 주어진 수열의 길이가 3일 경우 3가지 수의 조합들 중 정답이 있고, 주어진 수열의 길이가 4 이상일 경우 주어진 수열을 정렬했을 때 가장 작은 4가지 수들의 조합 중 정답이 있다. 해당 조합들을 우선순위 큐에 넣은 후 세 번째 수를 뽑아내는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(Strin.. 2025. 2. 4.
[백준] 1497번 - 기타콘서트 [Java] https://www.acmicpc.net/problem/1497 1.  아이디어 기타의 개수가 최대 10개라서 부분집합을 통한 완전탐색으로 해결했다.2. 문제풀이 N개의 기타로 만들 수 있는 모든 부분집합을 구한 후 해당 부분집합에서 연주할 수 있는 곡의 수가 모든 기타로 연주할 수 있는 곡의 수와 일치하는지 계속 비교하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static int N; private static int M; private static char[][] status; private static boolean[] visited; private static int.. 2025. 2. 4.

티스토리툴바