Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처과자 나눠주기 실버 2 📖 문제 이 문제는 조카에게 최대한의 막대 과자 길이를 균등하게 나눠주는 것이 목표이다.  그러기 위해서는 적절한 과자길이를 찾아야하는데 여기서 이분탐색을 활용한다. 문제에서 알려줬듯이 과자를 하나로 합칠 순 없다.  예제 2번을 보면 왜 7인지 의문을 품을 수도 있다. 길이가 8이면 2 2 7 로 합치면 11이되는데 문제에서 여러 조각으로 나눠질 수 있지만 하나로 합칠 수 없다. 라고 나왔기에합치면 안된다. 이분탐색으로 적절한 길이를 찾고, 각 막대과자를 탐색한 길이로 나눈 개수가 조카M명을 넘는지 안넘는지 비교하면서 찾으면 된다.  나눠줄 수 없다면 0을 출력한다. 5 31 1 1 이런 경우 0이다.🔅 문제 풀이import java.io.*;impo..

🧫 문제 분석 ✔️ 출처좌표 압축 실버 2 📖 문제 이분탐색을 이용해서 주어진 좌표의 인덱스 위치를 빠르게 찾는 문제이다. 우선 문제를 이해하기 위해 좌표평면을 그린다. Xi > Xj 를 만족하는 '서로 다른' Xj의 개수가 Xi를 압축한 좌표이다. 예제 1번을 예로 정렬해보자 -10  -9     2    4(2개) 이제 첫 입력 좌표인 x1의 경우 2 > Xj의 개수를 찾으면 된다여기서 2보다 작은건 -10, -9이므로 2개즉, X1의 압축된 좌표는 2이다.  이 문제에서 중요한 점은 중복값 처리이다.  예제 2번에서 친절히 알려준다. 999 999 999 1000 1000 1000  사실상 좌표평면에서는 999 1000 이 두개이다.따라서 중복을 제거해야한다.  배열에 중복을 제거한 좌표들을 정..

🧫 문제 분석 ✔️ 출처나무 자르기 실버 2 📖 문제 이진 탐색 문제로나무를 잘랐을 때 적어도 M 미터의 나무를 집에 가져가기 위해 설정할 수 있는 높이의 최댓값을 구해야한다. 여기서 적어도 M미터의 의미는절단 높이가 최댓값을 가질때까지 찾되 적어도 M 미터 이상은 가져가야겠다는 의미이다. 예를 들어1~Int Max 의 절반으로 잘랐을 때 M미터를 넘겼다면 좀 더 그 위에를 잘랐을 때 M 미터 이상이면서 자르는 높이를 높여서 나무를 덜 자를 수 있는 경우가 있다.  푸는 방식 이진 탐색을 하되M 미터 이상이면 높이를 더 높여서 탐색해본다. 주의할 점자르는 높이 이하인 나무들은 무시해야한다.  반례 하나를 남기겠다.2 73 9정답 : 2오답 : 0 밑에 처럼 짜면 오답이 나온다. 이유를 생각해보자if ..

🧫 문제 분석✔️ 출처랜선 자르 실버 2 📖 문제 이진 탐색, 바이너리 서치 이진 탐색에 대해서 공부한 뒤에 풀 수 있었다. 힙, 트리 자료구조 배웠을 때 배웠었는데 막상 이런거에 적용할 수 있다는 거에서 당황.. 문제에서 중요한 점N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 그외에는단순히 이진 탐색을 하면 된다.중앙 값으로 각 랜선을 나눠서 나온 개수를 구한다.개수가 n보다 크거나 같으면 최댓값을 구하기 위해 랜선의 길이를 더 늘리고 탐색한다. 개수가 n보다 적다면 이는 랜선의 길이가 너무 길기 때문에 랜선의 길이를 줄이고 탐색한다.    🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static long[] la..

🧫 문제 분석 ✔️ 출처가장 긴 증가하는 부분 수열 실버 2 📖 문제 DP 문제로 현재 값이 이전 값보다 크다면 이전 값의 수열 개수와 현재 값의 수열 개수중 더 큰 값을 취하면 된다.  // j = i - 1 ~ 0까지if (arr[j]  문제의 예시로 현재 4번째 30이라고 하자 10 dp[4]는 처음 값은 0이므로 dp[3]의 값을 가진다. dp[3]은 1이다. (3번째 10은 이전에 증가하는 수열이 없고 10밖에 없음)그다음 2번째 20 dp[2] 는 2이므로 dp[4] = 2이고 이 연산이 끝나면 dp[4]에 30도 카운팅해주면 3이된다.   이 풀이에서 중요한 것은 수열의 크기가 1일 때는 수열의 길이도 1이라는 것이다.   🔅 문제 풀이import java.io.*;import java..

🧫 문제 분석 ✔️ 출처촌수계 실버 2 📖 문제 bfs는 가중치가 같으면 항상 최단거리이다.그래프는 연결되어있기에 어디에서 시작하든지 가중치가 같다면 거리는 같다. (양방향 한정)BFS는 재귀로 구현하지 못한다. 처음에는 진입 경로가 0인 최상위 부모를 찾아서 위에서부터 DFS 탐색으로 깊이를 측정하며 x와 y를 구했다.부모와의 관계를 문자열로 저장하고 각 각 비교하면서 촌수를 따졌는데 이렇게하면 너무 오래걸리고, 이상하게 중복이 생겼다. 푸는 방향이 잘못되었던 것이다. 이 문제에서 원하는건 그래프와 넓이 탐색에 대한 개념을 잘 이해하는지를 물어보는 문제였고 나는 제대로 이해하지 못했어서 이상하게 풀이를 시작한 것이다.  잘 기억하자.   🔅 문제 풀이import java.io.*;import ja..

🧫 문제 분석✔️ 출처스택 수열 실버 2 📖 문제 1~N까지의 숫자들이 오름차순으로 스택에 push될 수 있고,입력된 수열, 여기서는[4 3 6 8 7 5 2 1] 이라는 수열을 만들기 위해 스택이 해야하는 연산을 출력하는 문제이다.push : + pop : - 우선 먼저 수열의 맨 처음인 4를 놓기 위해서는 1~4까지 스택에 push 후 1번 pop한다. 그럼 스택에는 1 2 3 이 남게 된다. 그다음은 3이므로 pop 한 번 한다.다음 6이므로 5 6 을 push하고 pop 하여 6을 빼낸다. 즉 수열의 각 순서에 따른 수만큼 push하고 top의 수가 현재 순서의 수면 pop하고 아니라면 NO를 출력하고 중단한다.push는 현재 까지 넣은 수에 따라서 진행한다. 현재까지 넣은 수보다 큰 수가 오..