Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처테트로미노 골드 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..

🧫 문제 분석✔️ 출처계단 오르기 실버 3 📖 문제 dp 문제로나올 수 있는 경우는 1.  2칸을 점프해서 도달2.  2칸 점프 + 한칸 앞으로 인 경우 뿐이다.  따라서  // 2칸 점프 도달 2칸 점프 후 한칸 앞으로 dp[i] = Math.max(dp[i-2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i]) 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStre..

🧫 문제 분석✔️ 출처1로 만들기 실버 3 📖 문제 3으로 나눴을 때 2로 나눴을 때 1을 뺐을 때   3가지 경우 중 더 작은 값을 찾으면 된다.  6을 예시로 보면6 / 3 의 최솟값 dp[6 / 3] + 1,6 / 2 의 최솟값 dp[6 / 2] + 1,6 - 1 의 최솟값 dp[6 - 1] + 1dp[2] = 1, dp[3] = 1, dp[5] = 3+1을 해주는 이유는 6에 대해 연산을 해주었기때문이다.  따라서 dp[6] = 2이다.   🔅 문제 풀이import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buff..

🧫 문제 분석 ✔️ 출처줄 세우기 골드 3 📖 문제 그래프를 사용해야할 것만 같은 예제입력..ㅋㅋㅋ 위상정렬에 대해서 공부하고 나서 풀었다. 학교에서 이산수학때 배웠는데 기억이 안나서 결국 다시 찾아봤다.  위상 정렬은 쉽게 말해 순서가 정해진 그래프를 순차적으로 처리하는 알고리즘이다. 어떻게 순서를 처리할 것인가 ?  바로 진입차수를 통해서 처리한다. 진입 차수가 0인 노드를 먼저 처리하며 해당 노드와 연결되어있던 노드들의 진입 차수를 1씩 뺀다. 진입 차수가 아니라면 우선순위에서 밀려난다고 생각하면 된다.  간단히 말해 그래프의 화살표를 따라 진행하되 진입 차수가 0인 노드를 처리하고 아니라면 넘긴다.   🔅 문제 풀이import java.io.*;import java.util.*;public ..

🧫 문제 분석 ✔️ 출처치킨배달 골드 5 📖 문제 // 치킨 거리 = 집과 가장 까가운 치킨집 사이의 거리// 집 기준, 집은 치킨거리를 가짐// 도시의 치킨 거리 = 모든 집의 치킨 거리의 합// 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|// 0 빈칸 , 1 집 , 2 치킨 집// 집의 개수  치킨 집 중 M개를 골라야하기에 백트래킹이 필요하다. 중요한 것은 전체 치킨 집 수 중 M개를 뽑는 방법이다.  처음에 그냥 i = 0 으로 모든 치킨집을 순회하면서 조합을 만들어갔기에 시간초과로 실패했다.중요한 것은 m개의 치킨집을 효율적으로 뽑아서 치킨거리를 계산하는 것이다. 치킨집을 뽑을때 이전에 뽑았던 가게는 이미 뽑혔기에 굳이 또 방문할 필요없다. ..

🧫 문제 분석 ✔️ 출처숨바꼭질 3 골드 5 📖 문제 bfs는 가중치가 같으면 항상 최단거리이다. x - 1, x + 1, x * 2 로 x가 k가 될 때까지 이동한다.n >= k 일 시 (x - 1) 로만 k로 갈 수 있기에  이를 고려한다. 정답 : n - kn과 k 는 0 ~ 100,000 사이이다. x - 1, x + 1, x * 2 인 노드를 bfs로 x(수빈)이가 k(동생)을 찾을때까지 반복하여 탐색한다.   🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static class Node { int cur, cost; public Node(int next, int cost) { ..

🧫 문제 분석 ✔️ 출처포도주 시식 실버 1 📖 문제 동적 프로그래밍 문제이다.  문제를 보면1. 선택한 잔은 모두 마시고 원위치2. 연속으로 3잔 마시기 불가능 i = 3 부터 시작 1. 현재 잔 + dp[i - 2]2. 현재 잔 + 이전 잔 + dp[i - 3]3. dp[i - 1]    // 이전까지의 최댓값을 가진다.  이 세가지 중 max값을 찾으면 된다.    1. 현재 잔 + dp[i - 2]2잔을 마시고 한 칸 뛰고 한 잔을 마신 경우이다.  1 2 3 번째 잔을 연속해서 마실 수 없으므로 dp[1]의 값 즉, 0과 1 번째 잔을 마신 최댓값 을 더한다.  2. 현재 잔 + 이전 잔 + dp[i - 3] 한 잔을 마시고 한 칸 뛰고 연속으로 2잔을 마신 경우이다.dp[0] 잔까지 마시고..

🧫 문제 분석 ✔️ 출처부분합 골드 4 📖 문제 누적합 문제를 한번도 안풀어봐서 기본 개념을 익히고 풀어봤다. 여기서는 투 포인터 알고리즘을 사용한다.  시작 포인터 : start끝 포인터 : end  처음 start 와 end를 첫번째 요소 위치에 둔다.end를 움직일때마다 해당 end에 값을 sum에 더하고 그 값이 목푯값 s 이상인지 확인한다. sum >= s 이면 end - start 와 기존 count 중 더 작은 값을 취한다.       🔅 문제 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedR..

🧫 문제 분석 ✔️ 출처Z 실버 1 📖 문제  문제에서 답을 줬다.  n-1 크기로 4등분 배열을 4 등분 하면서 구역을 4구역으로 나눈다.  (r,c) 의 위치가 어느 구역인지 판별후 해당 구역의 이전 구역들의 방문 수를 더하면서 n == 1 일때가지 진행한다.  내가 짠 코드는 문제에서 n-1 크기로 줄여가며 4등분하는 것을 활용해서 했더니 다른 사람들과 차이가 난다. 좀 복잡하게 풀었다.   🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static int[][] arr; static int r; static int c; static int count = 0; public static void main..