Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처AC 골드 5 📖 문제 문자열, 구조 문제이다.덱이 생각이 안나서 그냥 투 포인터로 풀었다..ㅎㅎㅎㅎ 문제에서 핵심은 문자열 파싱 : [1,2,3,4] 이런 식으로 입력이 주어지기에 이를 적절하게 파싱한다.R : 배열 순서 뒤집기D : 첫번째 요소 삭제빈 배열에 D를 사용할 경우 에러 발생 [1,2] 에서 DD 를 하면 [] 을 출력한다. error가 아니다.   문자열 파싱은 subString으로 앞 뒤의  ' [ ' , ' ] ' 를 짤라내고split으로 정규표현식을 사용하여 [^0-9]로 숫자가 아닌 모든 것을 기준으로 짤라 문자열 배열을 만들었고이를 int 배열에 파싱하여 저장하였다.  두 개의 포인터를 사용하여 풀었다. 자세한건 코드를 참고해주면 좋을 것 같다.  🔅 ..

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

🧫 문제 분석✔️ 출처계단 오르기 실버 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] 잔까지 마시고..