Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처엘리베이터 플래티넘 5 📖 문제 최단경로 + BFS + 역추적 문제 이문제를 풀면서 메모리초과가 진짜 자꾸 나서 정말 힘들었다. 여러번의 테스트 끝에 알아낸 것은컬렉션에서for (int i : list)향상된 for문(for-each)는 내부적으로 Iterator 객체를 생성해서 순회한다.때문에 수많은 엘리베이터를 갖는 리스트를 foreach로 접근했으니메모리초과될 수밖에 없었다. 많은 양의 요소를 담는 컬렉션 객체는 되도록이면 for-each문을 사용하지 말아야겠다. 그리고 거리는 dist배열로 따로 빼자.괜히 큐에 같이넣어서 메모리초과뜬다. 🔅 문제 풀이 [다익스트라]import java.io.*;import java.util.*;public class Main { ..

🧫 문제 분석✔️ 출처부대 복귀 level 3📖 문제 최단경로인데 길이가 1이라해서 그냥 BFS로 풀었다.  몰랐던 사실인데 n이 10만이고, roads에서 모든 노드를 주지 않으므로, 메모리 낭비라고 생각해서 HashMap을 사용하는것이 좋아보인다고 생각해서 사용했다.  목적지 (destination)부터 끝노드까지 (탐색이 종료될때까지 ) 돌게 하되방문한 곳이 source[i] 면 거리값을 저장한다.   물론 다익스트라 알고리즘을 쓰는게 맞는것 같다. 내 로직보다 속도는 약 5배 정도 더 빠르다. 문제에서 최단 경로 라고 주어졌는데 비용이 1이라는 말에 BFS로 밀고 가려해서 저렇게 짠 것이다.   참고 HashMap은 해시 충돌을 대비한 내부 구조 (엔트리 배열, 체이닝 등)로 인해 메모리 오버..

🧫 문제 분석✔️ 출처미로 탈출 level 2📖 문제 단순 BFS이며,레버를 당기고 난 후 출구로 나갈 수 있으며레버를 당기지 않아도 출구 지역은 지나다닐 수 있고모든 지점은 여러 번 지나갈 수 있다.  나는 출발점을 찾고 거기서 부터 BFS로 L를 탐색한다음현재 위치에서 다음 위치가 레버이면서 아직 레버를 안당겼다면여태까지 방문한 기록을 없애고, 큐를 초기화 시킨 다음 레버를 당기고(레버 위치를 큐에 담고), 레버 위치에 방문했다고 표시한다. 그리고 레버 위치에서부터 시작하게끔 현재 위치에서 탐색을 중지시킨다.(break)레버 위치에서부터 다시 BFS 탐색을 해서 E인 탈출구를 찾는다. 🔅 문제 풀이import java.util.*;class Solution { // 1. 레버로 이동 ..

🧫 문제 분석✔️ 출처배달 level 2📖 문제  거리 값이 존재하는 그래프 문제이 문제를 통해 다익스트라, 플로이드 워샬 등거리 값이 존재하는 그래프의 탐색이 얼마나 부족한지 깨달았다. 해당 문제를 BFS, 플로이드 워샬, 다익스트라로 풀어보았다. 그리고 거리가 있는 그래프에 대한 간단한 정리를 할 예정이다.  🔅 문제 풀이 - BFSimport java.util.*;class Solution { // N개의 마을, K : 갈 수 있는 거리 // BFS 탐색으로 K - 각 마을까지의 비용 >= 0 인 곳을 방문 int[] visited; public int solution(int N, int[][] road, int K) { int[][] graph = n..

🧫 문제 분석✔️ 출처소수 찾기 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📖 문제 BFS 문제로 다른점은 한방향으로 쭉 가야한다는 것과D라는 장애물이나 가장자리 즉, 배열의 범위를 넘어서는 곳을 만나면 멈춘다는 것이다.  장애물을 만나거나, 가장자리 (배열 범위)를 넘어선 곳을 만날때 멈춘 자리가 G(목표지점) 인지 확인하면 되는 단순한 문제이다. 🔅 문제 풀이import java.util.Queue;import java.util.LinkedList;class Solution { boolean[][][] visited; int[] dx = {0, 0, 1, -1}; int[] dy = {1, -1, 0, 0}; int answer = 0; class Token { int y; ..

🧫 문제 분석✔️ 출처광물 캐기 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[]..

🧫 문제 분석✔️ 출처프로그래머스 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..