코딩테스트
-
[Dev-Ping9] 백준 14889번 - 스타트와 링크 (Java)코딩테스트/백준 2021. 12. 30. 00:38
[1차 시도] ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 메모리가 터져나간다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 공부를 좀 더해야겠다....😢 [2차 시도] # 문제설명 일단 문제 설명에 따라 nCn/2 의 경우를 탐색해야한다. 탐색한 후, 각 경우에서 또 (n/2)! 만큼 탐색하면 되는 것 같다. 그러나 나는 A팀에 1번이 포함됬을 경우, [1][] , [][1] 을 모두 지워버리는 식으로 A팀에 포함된 모두를 아래와 같이 지워버리고 B팀의 점수를 집계했다. 그 결과 2308ms -> 1212ms 라는 좋지 않은 수행시간 점수를 받아버렸다... # 구현코드 1차 코드 (메모리 303,956KB / 시간 2308ms) - nCr 마구잡이로 짜보고, 2차원배열도 clone()을 통해 복사가 되는지 확인해보았다. (된다...!!!..
-
[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..