Meluu_의 코딩 공부 일지

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

🧫 문제 분석 ✔️ 출처고층건물 골드 4 📖 문제 핵심사실상 수학문제라고 봐도 과언이 아니라 생각한다.기울기의 증감을 따져서 비교하면 되는데  빌딩중 하나를 기준으로 생각해보자. 좌측 부분은 기울기가 증가 하는 형태이고우측 부분은  기울기가 감소하는 형태이다.  대략 이렇게 볼 수 있다.  뒷건물에 대해서는 기울기 최솟값을 저장하고 최솟값보다 기울기가 크다면 그 빌딩은 볼 수 없는 빌딩이다. 앞 건물에 대해서는기울기 최대값을 저장하고최댓값보다 기울기가 작다면 그 빌딩은 볼 수 없는 빌딩이다.  문제에서 A-B 빌딩 선분이 다른 빌딩을 지나거나 접하지 않아야한다 했으므로 기울기가 같으면 그 빌딩은 볼 수 없다.  🔅 문제 풀이import java.io.*;import java.util.StringTo..

🧫 문제 분석 ✔️ 출처감소하는 수 골드 5 📖 문제  핵심감소하는 수는 완전탐색 + 백트래킹 문제이다. 먼저 문제를 보면 321, 950 같은 수는 감소한다. 즉 각 앞 자리수보다 뒷 자리수가 더 작아야한다. ex)321이면 3보다 작은 수가 와야하고 여기서는 2 가 왔다2보다 작은수 1이 왔다. 수를 생각해보면 0~9 까지 있고 나올 수 있는  감소하는 수 최대 값은9 8 7 6 5 4 3 2 1 0 이다. (98억7654만..)즉 10자리수까지만 탐색하면 된다는 의미이다.  문제에서 주어지는 N번째 수가 무엇인지를 출력하면 된다.예제 1번을 예시로 보자 0~9까지는 각 수에 대한 각 번호이다. 0 은 0번째 , 1은 1번째그리고 10 은 10번째이고 11부터 19까지는 감소하는 수가 아닌 같거나..

🧫 문제 분석 ✔️ 출처암호 만들기 골드 5 📖 문제  조건최소 한개의 모음 && 두 개 이상의 자음 알파벳이 사전 순서대로 정렬   ex) ba 불가능, ab 가능  알파벳을 배열에 담고 오름차순 정렬한 다음 길이를 주고 각 자리수에 맞게 완전탐색을 해본다. 처음(0일때) a일 경우 a를 방문했다고 하고 나머지 c i t s w 에 대해서 또 DFS를 한다. 중요한 것은 이전 사전 순이기에 이전 알파벳보다 현재 알파벳이 커야한다.(순서로 따지자면 뒷 번호여야 한다.)따라서 이전 알파벳에 대한 인덱스를 매개변수로 넘긴다.   그리고 모음의 만들어야하는 암호의 길이 L - 모음의 개수 = 자음의 개수이다.    🔅 문제 풀이import java.io.BufferedReader;import java.i..