코딩테스트/백준
-
[Dev-Ping9] 백준 2580번 - 스도쿠 (Java) [DFS] [반례 포함]코딩테스트/백준 2021. 12. 23. 12:38
# 문제설명 완전 탐색을 진행하면서 스도쿠 규칙에 맞는 조건만 끝까지 탐색한다. [스도쿠 규칙] 1. 가로 2. 세로 3. 작은 사각형 # 접근 방법 0(빈칸)의 갯수를 탐색해야 할 노드의 갯수로 정의한다. 모든 노드를 dfs 방식으로 탐색하며, 조건에 맞지않을 경우 backtracking 한다. (마지막 노드에 도달한다면 그게 정답) # 주의사항 1. 답이 여러개일 경우에는 처음 발견된 답안을 출력한다. => 처음 발견된 답안을 출력하고 프로그램을 종료하여야 한다. # 코드구현 (반례 포함) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTok..
-
[Dev-Ping9] 백준 9663번 - N-Queen (Java) [DFS]코딩테스트/백준 2021. 12. 19. 15:03
# 문제 설명 퀸들은 같은 대각선과 같은 직선에 있으면 안된다. (조건) 경우의 수를 물으므로 완전탐색을 진행하여야 한다. 완전 탐색을 진행하면서 (조건) 에 부합하는지 검사 한 후, (조건)에 부합한다면 계속 진행하며 (조건)에 부합하지않으면 해당 Path로의 탐색은 중지한다. (BackTracking) # 코드 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ static boolean[] boardColVisited; static int[] queens; static boolean isPromising(int i, int currentNode){..
-
[Dev-Ping9] 백준 15649번 - N과 M (4) (Java) [DFS]코딩테스트/백준 2021. 12. 18. 17:32
# 문제 설명 N과 M 시리즈 마지막 문제이다. (3)번과 다르게 비내림차순이여야 한다. DFS를 처음 접근하시는분들께 좋은 연습문제시리즈인 것 같다. ** if 문의 or 절은 앞의 조건이 참일 시, 뒤의 조건을 검사하지않는다. (idx-1 이 OutOfArrayIndex Exception을 발생시키지 않음.) # 코드 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class test{ static boolean[] picked; static int[] space; static StringBuilder sb..
-
[Dev-Ping9] 백준 15649번 - N과 M (3) (Java) [DFS]코딩테스트/백준 2021. 12. 18. 17:24
# 문제설명 DFS 문제이다. N과 M (1)번 문제와 다르게 숫자를 중복으로 고를 수 있다. 노드의 방문처리유무를 표시하지 않아주면 된다. # 코드 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static boolean[] picked; static int[] space; static StringBuilder sb = new StringBuilder(); static void dfs(int idx, int nodeEnd,int limit){ if(idx == limit){ // pri..
-
[Dev-Ping9] 백준 15649번 - N과 M (2) (Java) [DFS]코딩테스트/백준 2021. 12. 18. 17:17
# 문제설명 N과 M(1) 과 같은 dfs 문제이다. (1)번 문제와는 다르게 오름차순을 만족해야 한다. 마찬가지로 노드들에 대한 탐색을 진행하면서 조건에 맞는 노드들만 탐색한다. ** if 문의 or 절은 앞의 조건이 참일 시, 뒤의 조건을 검사하지않는다. (idx-1 이 OutOfArrayIndex Exception을 발생시키지 않음.) # 코드구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static boolean[] picked; static int[] space; static S..
-
[Dev-Ping9] 백준 15649번 - N과 M (1) (Java)[DFS]코딩테스트/백준 2021. 12. 18. 17:09
# 문제설명 dfs 문제이다. 모든노드를 탐색하면서 조건에 도달할 시 출력해주면 된다. *StringBuilder 와 Sysout 의 성능차이는 어마어마하다. # 코드 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static boolean[] picked; static int[] space; static StringBuilder sb = new StringBuilder(); static void dfs(int idx, int nodeEnd,int limit){ if(idx == limi..
-
[Dev-Ping9] 백준 1436번 - 영화감독 숌 (Java)코딩테스트/백준 2021. 12. 18. 15:41
# 문제 설명 1666, ... , 5666, 6660, 6661 등의 변칙규칙으로 구현하기 귀찮게 정의되어 있기에, 이게 되나 하고 단순하게 짰다. 주어진 N의 크기도 작고, 시간제한도 2초(2억번 연산가능)로 넉넉한 편이기에 대충 통과 될거 같긴 했지만... 정말로 되네.... 이런거 공들여서 규칙찾기도 시간낭비 같아서 그냥 그대로 마무리했다. # 코드 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new..