Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처사다리 조작 골드 3 📖 문제 i번째 사다리로 시작해서 i번째 사다리로 끝나도록 가로선을 최소한으로 추가하는 문제다. 가로선은 최대 3개까지 추가할 수 있고불가능하거나 3개를 넘어가면 -1로 반환한다. 1. 현 상태 사다리 시뮬레이션 구현2. 가로선을 추가시 인접한 사다리의 가로선과 맞닿는지 확인 그리고 처음에 풀이시 2200ms가 나왔다.그저 낮은 깊이부터 탐색하면 되는데 굳이 처음부터 3까지 탐색해서 시간이 이렇게 나왔다. 깊이 1일떄 조합깊이 2일때 조합깊이 3일때 조합 순으로 탐색하면 깊이가 낮을때 먼저 답 발견시 빠르게 끝날 수 있다. 🔅 문제 풀이import java.io.*;import java.util.*;import java.util.jar.JarEn..

🧫 문제 분석 ✔️ 출처감시 골드 3 📖 문제 완전탐색 + 구현 + 백트래킹 문제 핵심CCTV 감시 모든 경우의 수 탐색 (이미 감시한 곳은 넘어가고, CCTV를 넘어설 수 있음)CCTV 방향에 대한 탐색을 구현하는 방법 풀며서 실수한게항상 그렇듯, 변수 새로 생성하고 이전 변수를 안고쳐서변수에 값을 -1 빼서 사용한다 해놓고 정작 리턴하는 곳에서는 -1을 안해서 틀림. 로직을 짜고 좀 더 세심히 머리로 시뮬레이션을 그리며 코드를 점검해볼 필요가 있다.🔅 문제 풀이import java.io.*;import java.util.*;public class Main { // 15683번 감시 static int[] dr = {-1, 0, 1, 0}; static int[] dc = {0..

🧫 문제 분석✔️ 출처N-Queen 골드 4 📖 문제 많은 깨달음을 준 문제다. 퀸의 특성상 상하좌우대각을 원하는 만큼 이동이 가능하기에 그에 따른 검증을 해야한다. 처음에는 이중 배열로 만들어서 각 퀸의 위치를 리스트에 저장하고 리스트를 순회하면서 검증하고 놨는데 시간복잡도가 너무 크게 나와서 O((N^2)^N) 힌트를 보고 풀었다. 퀸 특성상 n개의 체스판에서는 각 행에 하나씩 둬야 n개의 퀸을 둘 수 있다.때문에 퀸을 두고 다음 행을 탐색한 후 돌아온 다음 다시 퀸을 지울 필요없이 덮어씌우면된다. (백트래킹에서) 나의 잘못된 생각은검증시 0~n 행까지 전부 다 해서 쓸모없는 연산이 늘고, 잘못된 검증이 되어 값이 증가한 것이다. 말했듯이 n개의 퀸을 놓을려면 0행부터 순서대로 n행까지 하나..

🧫 문제 분석 ✔️ 출처N과 M (9) 실버 2 📖 문제 N과 M 9번째 시리즈N개의 자연수 중 M개를 고른 수열이면서 그 수열이 중복되면 안된다.  입력받은 N개의 자연수를 우선 오름차순으로 정렬한 후 백트래킹 탐색을 한다. 수열을 문자열로 만들고 Set에 중복 체크를 한 다음 없다면Queue에 넣어서 저장 탐색이 끝나면 Queue를 다 꺼내서 출력하면 된다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static Set set = new HashSet(); // 수열 중복 체크 static StringBuilder sb = new StringBuilder(); // 수열 만들기용 static List list..

🧫 문제 분석✔️ 출처단어 변환 level 3📖 문제 begin 알파벳 중 하나를 words 단어중 하나의 알파벳으로 바꿀 수 있다.순서는 상관없고, 변경을 최소한으로 해서 target을 만들면 된다.   백트래킹하면서 words를 탐색한다.  words 각 단어의 알파벳을 begin의 각 알파벳과 비교해서 2개이상 다르면 바꾸지 않고 넘어가도록 한다.  만약 알파벳이 1개만 다르다면 그 단어를 begin으로 하고백트래킹 탐색을 한다. 🔅 문제 풀이class Solution { // 완전탐색 // 백트래킹 boolean[] visited; int min = Integer.MAX_VALUE; public int solution(String begin, Str..

🧫 문제 분석✔️ 출처소수 찾기 level 2📖 문제 numbers의 각 자릿수를 조합하여 숫자를 만들고 그 수가 소수인지 카운트  소수 판별 + 완전탐색 문제 핵심0으로 시작하지 않음2는 소수짝수는 소수가 아님조합된 수 중복 체크🔅 문제 풀이class Solution { boolean[] visited; boolean[] check = new boolean[10000000]; int answer = 0; public int solution(String numbers) { char[] num = numbers.toCharArray(); visited = new boolean[num.length]; dfs(..

🧫 문제 분석✔️ 출처피로도 level 2📖 문제 현재 피로도 k >= 최소 필요 피로도 인 조건을 따져서 백트래킹 완전탐색을 하면 된다. (최소 필요 피로도 >= 소모 피로도) 문제에서 던전 개수가 8 이하이기에 완전탐색을 해도 시간복잡도가 괜찮을 거 같다는 생각이 들었다.  🔅 문제 풀이import java.util.Arrays;class Solution { // 현재 피로도 (k), [최소 필요 피로도, 소모 피로도] // 최필피 >= 소피 boolean[] visited; int max = 0; public int solution(int k, int[][] dungeons) { visited = new boolean[dungeons..

🧫 문제 분석✔️ 출처광물 캐기 level 2📖 문제 백트래킹 문제로 곡괭이의 내구도 :  5한 번 선택한 곡괭이는 터질때까지 사용광물은 주어진 순서대로 채광 종료 조건은 모든 곡괭이 내구도 0 이거나 모든 광물을 채광했을 경우 이다.이때 최소 필요도를 구하는 것이 이 문제의 답이다.  곡괭이 하나 선택하고, 최대 5개 캐고 하면서 백트래킹 하면 된다. 🔅 문제 풀이class Solution { // 0 : 다이아, 1 : 철 , 2: 돌 int[][] fatigue = {{1, 1, 1}, {5, 1, 1}, {25, 5, 1}}; int minFatigue = Integer.MAX_VALUE; public int solution(int[] picks, String[]..

🧫 문제 분석 ✔️ 출처신기한 소수 골드 5 📖 문제  (첫번째 수 + 두번째 수) 가 소수면 첫번째 수 * 10 + 두번째 수 를 파라미터로 넘겨 재귀로 호출한다.  백트래킹으로 풀어주면 된다. 소수 판별은 제곱근을 이용한 방법을 사용했다.  판별할 수의 제곱근을 구해서2~제곱근까지의 수로 나눠떨어지면 소수가 아니다. 자세히 말하자면 n = p*q 라 했을 때 (n > 0) p >=√n 일때p로 나누면 그 몫은 q이며q 이다.한쪽이 √N이상이고, 한쪽이 √N이하인 수의 곱이다.  4를 생각해보자p x q √N = 2      p            q1 x 4  1  ≤ √N,  4  ≥ √N 2 x 22  ≤ √N,  2  ≥ √N4 x 14  ≥ √N,  1 ≤  √N1은 소수가 아니지만 여기..

🧫 문제 분석 ✔️ 출처테트로미노 골드 4 📖 문제 완전탐색 + 백트래킹 문제다.  5가지중 가운데 볼록한 모양을 제외하곤상하좌우로 탐색하며 탐색한 깊이가 4이면 테트로미노가 만들어진다. 이때 각 수를 max와 비교한다.  가운데 볼록한 모양(키보드 방향키 모양) 은 현 위치에서 상하좌우 4개중 3개를 뽑아서 처리한다.  예를 들어 dx, dy 0, 1, 2 번째 인덱스를 탐색하라고 "012 " 문자열을 만들어서 저장해놓는다는 것이다. 현재 위치에서 dx, dy 만큼 더한 인덱스에 접근하면 ㅓ 모양이 나온다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static int[] dx = {0, 0, 1, -1}; stat..