PS/BOJ
BOJ 1759 암호 만들기 [Java]
BOJ 1759 암호 만들기 1. 문제 링크 https://www.acmicpc.net/problem/1759 2. 문제 해설 백트래킹 문제이다. 다만 조건이 조금 추가되었다. 어떤 조건이 있는지 살펴보자. 1. 암호는 L개의 알파벳 소문자로 구성된다. 2. 최소 한 개의 모음과 두 개의 자음으로 구성된다. 3. 알파벳이 사전 순으로 배열된다. 일단 solve 메서드가 받아야할 인자는 현재 암호의 길이(length), 살펴보고 있는 인덱스(idx), 모음의 수(vowel), 자음의 수(consonant)이다. solve 메서드가 1, 2번 조건을 만족할 때 탈출하여 문제의 조건을 만족시켜준다. 3번째 조건인 암호의 경우의 수가 사전 순으로 배열되게 하기 위해서 입력 받은 arr 배열을 미리 사전 순으로 ..
BOJ 15649 N과 M (1) [Java]
BOJ 15649 N과 M (1) 1. 문제 링크 https://www.acmicpc.net/problem/15649 2. 문제 해설 백트래킹을 할 때는 문제에서 주어진 조건을 잘 살펴야한다. 이 문제에서는 중복 없이 숫자 선택, 사전 순으로 수열 출력 이 2가지 조건만 만족하면 된다. 중복 체크를 하기 위해 vis 배열을 만들어주고, m개의 선택된 숫자를 담을 arr 배열을 만들어준다. 이제 백트래킹 과정을 행할 solve 메서드에 대해 알아보자. 매개 변수로 cnt를 받는데 cnt가 의미하는 바는 선택된 숫자의 갯수이다. 탈출 조건은 cnt가 의미하는 바를 생각하면 자연스레 도출된다. cnt == m 이 되면 solve 메서드를 탈출하고 arr 배열에 저장된 숫자들을 StringBuilder에 담는다..
BOJ 11403 경로 찾기 [Java]
BOJ 11403 경로 찾기 1. 문제 링크 https://www.acmicpc.net/problem/11403 2. 문제 해설 플로이드 알고리즘을 이용하면 쉽게 풀 수 있다. 정점의 최대 갯수가 100개이므로 최대 연산 수는 1000000으로 넉넉하게 통과한다. 입력으로 arr배열을 받고 1이 아니면 (Integer.MAX_VALUE - 1) / 2로 초기화해준다. Integer.MAX_VALUE로 초기화할 시 31번째 줄 코드에서 오버플로우가 발생할 수 있다는 점을 주의하자. 그 후 플로이드 과정을 거치고 arr[i][j] 값이 아직 (Integer.MAX_VALUE - 1) / 2 인 곳은 갈 수 있는 경로가 없다는 의미이다. 그러므로 그런 위치는 0, 아닌 곳은 1을 출력해주면 쉽게 해결할 수 있..
BOJ 15683 감시 [Java]
BOJ 15683 감시 1. 문제 링크 https://www.acmicpc.net/problem/15683 2. 문제 해설 백트래킹을 이용하여 cctv를 다 돌면서 cctv들의 방향에 따른 모든 조합의 경우를 다 보는 방식의 풀이를 생각했다. 방향을 어떻게 표현할 것인지가 문제였는데, 그냥 단순히 동쪽, 북쪽, 서쪽, 남쪽을 0, 1, 2, 3으로 대응시키기로 하였다. 우선 주어지는 입력에서 cctv의 위치와 타입을 저장하기위해 CCTV 클래스를 만들고 CCTV 배열을 만들어 cctv를 모두 담아주었다. 그리고 백트래킹을 이용하여 방향에 따른 모든 경우의 수를 다 살펴봐야하는데, cctv의 타입에 따라 방향의 갯수가 달라진다. cctv 타입에 대응되는 방향의 갯수를 담는 cctv_dir 배열을 만들어주었..
BOJ 1753 최단경로 [Java]
BOJ 1753 최단경로 1. 문제 링크 https://www.acmicpc.net/problem/1753 2. 문제 해설 다익스트라 알고리즘을 이용하는 기본 문제이다. 다익스트라 알고리즘 구현을 연습하기에 좋았다. 코드 구현에 대한 설명은 아래 다익스트라 알고리즘에 대해 써놓은 글을 참고해보자. [최단 거리 알고리즘 - 다익스트라 [Java]] 3. 코드 보기 import java.io.*; import java.util.*; public class Main { static class Node implements Comparable { int vertex; int distance; public Node(int vertex, int distance) { this.vertex = vertex; this.d..