Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처여행 가자 골드 4 📖 문제 서로소 집합 또는 BFS-DFS 알고리즘 둘중 하나로 풀 수 있는 문제다. 주어진 섬들을 여행 시작점을 출발로 탐색해서여행 계획 섬들을 전부 방문했는지만 따지면된다.  서로소 집합의 경우 여행 계획 섬들의 부모가 모두 같으면 여행 가능하다. 🔅 문제 풀이 [BFS]import java.io.*;import java.util.*;public class Main { static boolean[] visited; static boolean[][] graph; // 방문한 곳을 여행 계획에서 체크하면 된다. // 여행계획 섬을 방문하지 않았다면 이는 불가능한 것 public static void main(String[] args..

🧫 문제 분석✔️ 출처리모컨 골드 5 📖 문제 부서진 버튼을 제외한 버튼들을 가지고 BackTracking으로 완전탐색해서 이동하려는 채널 길이와 가장 가까운 수를 찾는다. 이동하려는 채널 길이 - 1 ~ 이동하려는 채널 길이 +1 까지의 수를 찾는데 그 이유는 998  이문제 15% 와 32%에서 계속 틀렸었다. 15% 실패처음 백트래킹 메서드를 호출할때 매개변수로 깊이를 0, 숫자를 0으로 줘서 n = 1 이고0버튼이 부숴졌다고 했을 때 매개변수로 시작 숫자를 0으로 줘서 버튼이 부숴졌음에도 불구하고 if문에 걸려 바로 최솟값으로 반환되버렸다.  32% 실패단순 Math.abs(n - 탐색으로 찾은 수) Math.abs(n - 탐색으로 찾은 수), len = 현재 num의 길이 이런식으로 구하고탐..

🧫 문제 분석 ✔️ 출처뱀과 사다리 게임 골드 5 📖 문제 주사위를 굴려서 1~6까지 숫자를 현재 위치에 더하면서 BFS 탐색을 하면 된다. (최단 경로) 1차원 배열을 게임 판이라 생각하고 100칸을 만든다. x번 도착하면 y번 칸 이동 , u번 도착하면 v번 칸 이동 이므로왼쪽 입력을 인덱스로 사용, 오른쪽 입력을 값으로 사용한다.  BFS 탐색을 하면서 주사위를 굴려 이동할때 이동한 위치가map에서 값이 있다면 그 값으로 이동한다.  물론 방문 체크를 해줘야한다. 이 경우 특별한 이동방법이 없으므로 1차원 배열로 체크해주면 된다.  특별한 이동 방법을 쓰는 문제 포스팅 보러가기 백준 1600번 : 말이 되고픈 원숭이 자바 백준 2206번 : 벽 부수고 이동하기 자바  🔅 문제 풀이import ..

🧫 문제 분석✔️ 출처모음사전 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..

🧫 문제 분석✔️ 출처백준 2206번 벽 부수고 이동하기 골드 3 📖 문제 그래프 BFS 탐색 문제이다.여러가지 방법으로 탐색, 최단 거리로벽을 부순 경우와 부수지 않은 경우 방문을 체크해줘야한다.  그외에는 단순한 넓이 우선 탐색을 해주면 된다.  조심할 것은 시작지점도 거리에 포함  비슷한 문제 백준 1600번 : 말이 되고픈 원숭이 자바   🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static int[][] graph; static boolean[][][] visited; static int[] dx = {0, 0, 1, -1}; static int[] dy = {1, -1, 0, 0}; publ..

🧫 문제 분석 ✔️ 출처말이 되고픈 원숭이 골드 3 📖 문제 상하좌우, 체스의 나이트 이동방식을 BFS 방식으로 푸는 문제이다. 이 문제에서 핵심은 말 움직임은 k번만 가능하다이때 중요한 것은 0~k번 말 움직임의 경우를 각각 따져서 가장 빠르게 오른쪽 끝으로 도달한 경우를 찾는 것이다. 말 움직임을 0번도 안쓰고 상하좌우로만 목표점에 도달한 경우말 움직임을 1번 쓰고 상하좌우로만 목표점에 도달한 경우 ...말 움직임을 k번 쓰고 상하좌우로만 목표점에 도달한 경우  이때 각 말 움직임 횟수마다 방문 체크를 해줘야한다.  말 움직임 구현상하좌우로 먼저 탐색을 하고그 방향으로 1번 더 간 다음 상하일 경우 좌우를 탐색좌우일 경우 상하를 탐색한다.  코드와 그림을 보면 이해하기 쉽다.    이와 비슷한 ..

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

🧫 문제 분석 ✔️ 출처신기한 소수 골드 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..

🧫 문제 분석 ✔️ 출처촌수계 실버 2 📖 문제 bfs는 가중치가 같으면 항상 최단거리이다.그래프는 연결되어있기에 어디에서 시작하든지 가중치가 같다면 거리는 같다. (양방향 한정)BFS는 재귀로 구현하지 못한다. 처음에는 진입 경로가 0인 최상위 부모를 찾아서 위에서부터 DFS 탐색으로 깊이를 측정하며 x와 y를 구했다.부모와의 관계를 문자열로 저장하고 각 각 비교하면서 촌수를 따졌는데 이렇게하면 너무 오래걸리고, 이상하게 중복이 생겼다. 푸는 방향이 잘못되었던 것이다. 이 문제에서 원하는건 그래프와 넓이 탐색에 대한 개념을 잘 이해하는지를 물어보는 문제였고 나는 제대로 이해하지 못했어서 이상하게 풀이를 시작한 것이다.  잘 기억하자.   🔅 문제 풀이import java.io.*;import ja..