Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처단어 변환 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..

🧫 문제 분석 ✔️ 출처인구 이동 골드4 📖 문제 랜덤 문제를 돌리다가 나왔다. 그래프 탐색 냄새가 솔솔 난다. BFS를 사용하면 될것 같다.  1. 한 나라의 좌우 상하로 인접한 다른 나라와의 인구차를 M명이라 했을 때 L 해야한다.2. 조건을 만족한 나라들과는 연합을 하여 국경선을 하루 연다. 3. 인구가 이동하며 각 나라의 인구수는 (연합 인구수 / 연합한 나라 개수) 가 되며 소수점은 버린다. 4. 이동후 연합 해지 및 모든 국경선을 닫는다.5. 인구 이동이 없을때까지 반복한다.6. 인구 이동이 며칠동안 발생했는지가 문제이다.  내가 생각한 방법1. 우선 연합가능한 나라들을 찾고, 그 나라에 연합 번호를 매기며 각 인구수를 더해놓는다. 2. 연합은 1개 이상 생길 수 있다. 3. 만약 1번 연..

🧫 문제 분석✔️ 출처프로그래머스 PCCP 기출문제 2번 / 석유 시추📖 문제 핵심그래프 bfs or dfs을 사용하여 각 석유 덩어리에 개수를 따로 저장하고 번호를 매긴다. 각 열이 어떤 번호를 가졌는지 저장한다음 반복문으로 각 열을 돌아서 가진 번호에 대한 석유 덩어리 개수들을 뽑아서 최대값을 찾는다.🔅 문제 풀이row = 깊이col = 1 2 3 4 .. 등 시추할 위치 열import java.util.*;class Solution { private static int[][] graph; private static int[] upDown = {0, 0, 1, -1}; private static int[] leftRight = {1, -1, 0, 0}; public int ..

🧫 문제 분석✔️ 출처게임 맵 최단거리 level 2📖 문제dfs/bfs 문제이다. bfs로 풀면 좋을것 같아서 bfs로 방향을 잡았다.방문한 좌표에 대해 check를 해주고, 갈 수 있는 곳을 check해주는 것이 핵심이다.처음에 visited를 q에서 뽑고나서 true로 해주어서 무한 루프에 빠졌었는데중복 좌표값이 Queue 에 추가되서 그런거였다.1 23 4그래프가 이렇게 있고Queue에 2,3 순으로 들어가 있다고 하자.2가 나와서 4를 추가한다.3이 나와서 4를 추가한다. 이를 해결하기 위해서 while문 밖에서 시작지점에 true를 미리 넣어주고가능한 좌표일때 방문 표시를 즉시 해줌으로써 해결하였다. 🔅 문제 풀이import java.util.*;class Solution { sta..

백준 2667번 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 풀이 미로 찾기와 매우 유사한 문제이다. 다른점은 단지라는 그래프의 개수와 각 단지의 집들 즉, 각 그래프의 노드들의 개수를 오름차순으로 출력하는 문제이다. 그저 그래프를 찾아내서 얼마만큼의 노드들이 연결되어 있는지만 확인하기에 BFS, DFS 둘다 사용이 가능하다. 여기서는 BFS를 사용하였다. import java.io.*; import java.util.*; public class Main { static int[][] graph; st..

백준 2606번 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 문제 풀이 그래프에서 1번 컴퓨터(노드)를 시작점으로 연결되어있는 컴퓨터들은 모두 바이러스에 감염된 것이기에 BFS , DFS 둘다 사용하여 풀 수 있다. 이번에는 DFS를 사용하여 풀었다. 재귀호출 , Stack 두 가지 경우를 둘다 사용해보았다. import java.io.*; import java.util.*; public class Main { static int[][] graph; static boolean[] visited; static i..