Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처여행경로 level 3📖 문제 모든 경로를 탐색해서 사전순으로 앞서는지 확인하는 문제 간과한 것은 같은 경로가 여러개 있을 수 있다는 것이다. ICN -> SFO, ICN -> SFO 이렇게 같은 경로가 여러개로 입력될 경우가 있다. 문제에서 따로 중복에 대한 내용이 없으면 항상 중복 케이스가 있다고 생각하는게 좋다. 그렇다면 어떻게 문자열로 된 그래프에서 방문처리를 할까 나의 경우 (현재 공항 + 다음 공항의 idx )를 key값으로 사용하여Set에서 방문처리를 하였다. 이부분만 빼면 딱히 어려운 문제는 아니다. 🔅 문제 풀이import java.util.*;class Solution { static Map> graph; static int n; // 총 방..

🧫 문제 분석✔️ 출처주사위 고르기 level 3📖 문제 많은 공부가 된 문제다.. 문제 풀이 방법까지는 잘 도출했는데 정작 최대 5개를 뽑았을때주사위의 눈의 합을 구하는 법에서 막혔다. 문제는 너무 많은 생각이라고 생각한다. 나오는 모든 합에 대하여 카운트를 해주려다가 이건 또 너무 복잡하고머리가 잘 안돌아갔다. 이번에 알게된 것 N개의 조합의 모든 합 구하기dfs로 짜는 것 까진 했는데 정작 어떻게 더해야할지 감이 안잡혔다. 근데 그냥 하나하나씩 주사위를 건드리면 됐다.1번 주사위의 i번째 + 2번 주사위의 i번째.. 이런식으로 잘 기억해두자.. 이분 탐색최대 개수를 구할때는 size() 까지 해줘해한다는 것 처음에 탐색 범위를 0 ~size()-1 까지로 했는데12번 테스트 케이스가 계속..

🧫 문제 분석 ✔️ 출처내리막 길 골드 3 📖 문제 나의 가장 약한 부분인 DP 연습 기간을 잡아 DP문제를 풀어보려한다. DFS + DP로 풀었다.중복 탐색 방지를 위해 static으로 방문처리 배열을 만들어서 처리했다.약간 백트래킹 느낌으로 BFS + 우선순위 큐 풀이도 있다고 한다.생각해보면 탐색은 점점 높이가 낮은 곳으로 이동하므로 높이가 낮은 순으로 큐에 넣으면중복없이 풀어낼 수 있다는 것이다. 탐색 조건에 뭔가 우선순위를 매길 수 있다면 우선순위 큐를 떠올려 보자 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static int N, M; static int[][] dp; static int[][] ..

🧫 문제 분석 ✔️ 출처사회망 서비스 (SNS) 골드 3 📖 문제 DP 문제트리를 이용한 DP 문제는 처음이라 좀 어려웠다 처음에는 엣지가 많은 노드 순으로 연결 해제 여부를 따지며 선정하면 되지않나 싶었는데불가능한 케이스가 있어서 바꿨다. 현재 노드를 얼리 아답터로 선정할지 안할지에 대해서 탐색하면된다.DFS+DP 식으로 풀어서 별로일 수 있다. 또한 입력을 받을 때 주의해야한다.방향성을 가지면 안되며 양방향으로 트리를 만들어야한다.그 이유는 단방향시 루트를 가지는 트리가 되는데 이러면 방향에 따라 값이 달라진다. 51 52 12 32 4이런 입력이 들어오면 1을 루트로 설정시2를 탐색할 수 없다. 때문에 양방향으로 설정해야한다. 루트를 1 기준으로 입력이 들어온다는 생각때문에이런 실수를 했다...

🧫 문제 분석 ✔️ 출처텀 프로젝트 골드 3 📖 문제 그래프 탐색을 하되 Stack + Set 조합으로 풀었다. 근데 DFS로 푸는게 정석인가보다. test case142 1 2 3answer : 2wrong : 무한루프 DFS로 다시 풀었을때 시간 초과가 났던 문제의 코드 private static void dfs(int current) { visited[current] = true; int next = students[current]; if (!visited[next]) { dfs(next); } else { if (finished[next]) return; // 이미 팀 구성을 한 학생이면 더이상 탐..

🧫 문제 분석✔️ 출처단어 변환 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📖 문제 정말 어려워했던 문제이다.결국에는 풀었다.  A : 1E : 2I : 3O : 4U : 5로 바꾸고  이에 맞춰서 완전탐색을 해서 매개변수로 넘어온 word 와 equals로 비교한 후 같다면 깊이 탐색을 멈추고 count를 반환한다. 🔅 문제 풀이class Solution { int count = 0; boolean flag = false; StringBuilder sb = new StringBuilder(); public int solution(String word) { dfs(trans(word), 0); return count; } private void dfs(Stri..

🧫 문제 분석 ✔️ 출처적록색약 골드 5 📖 문제 BFS 혹은 DFS 그래프 탐색 문제이다.나는 BFS를 좋아해서 BFS로 풀었다.  적록색약은 적록색(R) 과 초록색(G)의 차이를 거의 못느낀다.따라서 둘중 하나로 통일하면 된다.   나는 문제를 잘못 이해해서적록색과 초록색의 상화좌우로 인접해 있는 부분만 차이를 못느끼는 줄 알고 문제의 난이도를 더 높여서 풀다가 자꾸 틀리고 이상해서 문제를 다시봤더니 초록색과 적록색 차이가 없다고 보는게 맞았다...(이때문에 시간을 많이 소요함) 이 풀이법도 밑에 올리겠다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static boolean[][] visited; static i..

🧫 문제 분석 ✔️ 출처암호 만들기 골드 5 📖 문제  조건최소 한개의 모음 && 두 개 이상의 자음 알파벳이 사전 순서대로 정렬   ex) ba 불가능, ab 가능  알파벳을 배열에 담고 오름차순 정렬한 다음 길이를 주고 각 자리수에 맞게 완전탐색을 해본다. 처음(0일때) a일 경우 a를 방문했다고 하고 나머지 c i t s w 에 대해서 또 DFS를 한다. 중요한 것은 이전 사전 순이기에 이전 알파벳보다 현재 알파벳이 커야한다.(순서로 따지자면 뒷 번호여야 한다.)따라서 이전 알파벳에 대한 인덱스를 매개변수로 넘긴다.   그리고 모음의 만들어야하는 암호의 길이 L - 모음의 개수 = 자음의 개수이다.    🔅 문제 풀이import java.io.BufferedReader;import java.i..