Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처레이스 골드 2 📖 문제 이분탐색 + 그리디문제 이분탐색의 대상은 두 심판의 거리다.M명 배치할 수 있는 심판의 거리를 구해서 심판을 배치하고 그 중에서 가장 가까운 거리가 가장 긴 심판 배치를 출력한다. 그런데 가장 긴 심판 배치는 심판 거리계산하면서 자동으로 마지막에 계산된 것이 가장 긴 거리가 된다. (더 긴 거리를 탐색해보기 때문) 비슷한 문제로 예전에 풀었던 공유기 설치 문제랑 비슷하다. 나의 경우심판 배치 거리 탐색 - 이분탐색적절한 심판 배치 위치 탐색 - 이분탐색 3중 while문으로 풀어서 좀 보기 안좋을 수 있다.심판 위치 배치는 for문으로 해도 된다. 🔅 문제 풀이import java.io.*;import java.util.*;public class ..

🧫 문제 분석 ✔️ 출처카드 게임 플래티넘 5 📖 문제 이분탐색 + 유니온 파인드 (서로소 집합)문제 문제의 핵심은철수는 카드를 조작해서 낼 수 있고, 같은 수여러개를 낼 수 도 있음민수는 철수의 카드를 미리 알고 철수가 낸 카드 중 더 큰 수에서 가장 작은 수를 낸다. 문제에서 민수가 카드를 내지 못하는 경우가 없다고 가정하였으므로철수가 낸 카드보다 작거나 같은 카드만 남을 경우가 없다는 의미이다.즉, 철수보다 항상 더 큰 카드 k 개 만큼 내어 항상 승리한다 철수가 낸 카드에 맞게 민수는 자신의 카드에서 적절한 카드를 이분탐색으로 찾아서 낸다.찾은 카드가 철수가 낸 카드와 같다면 그 다음 카드를 가리킨다. 사용한 카드는 그 다음 카드의 대표 집합에 연결한다. 다음 카드의 대표 집합을 연결하는 ..

🧫 문제 분석 ✔️ 출처가장 긴 증가하는 부분 수열 5 플래티넘 5 📖 문제 LIS 시리즈중 마지막 문제기존 이분탐색 LIS에 역추적이 추가된 문제다. 실제 LIS를 구하려면 LIS를 기록해야한다.단순히 덮어씌운 값이 아닌 실제 증가하는 부분수열을 구해야하기에이전 값의 위치를 기록할 필요가 있다. 예제를 보면 10 20 10 30 20 50 이 입력되는데여기서 실제 LIS는 10 20 10 30 20 50이렇게 된다. 그럼 어떻게 추적을 해야하나 LIS 내에서 이분탐색을 하면서 새로운 값 추가가 아니면 기존 LIS 원소 내에 덮어씌운다. 때문에 LIS에 기록될 때 LIS에 기록된 위치에서 이전 위치의 값을 기록하는 것이다.단순히 -1~순차적으로 올릴 수 있지만 여기서는 prev만으로 바로 위치를 ..

🧫 문제 분석 ✔️ 출처중량제한 골드 3 📖 문제 최단 경로 + 최대신장(최소 신장의 반대라서 이렇게 붙였다) + 이분탐색 문제다.근데 본인은 최대 신장 트리로 안풀고, 현재 이분탐색 문제를 공부중이므로 이분탐색 + BFS 최단경로로 풀었다.  이분탐색으로 찾고자 하는 것은 두 섬 사이의 경로 이동 비용 최댓값이다. 가장 비용이 큰 값을 max로 잡고 1 ~ max 사이를 이분탐색하면서 mid값으로 BFS 탐색을 한다. BFS 탐색에서는 공장이 있는 섬A에서부터 탐색을 하되 mid 값 (중량)을 다리의 중량제한이 버틸 수 있다면 다음 다리로 탐색한다. 공장이 있는 섬 B에 도착하면 현재 mid 값의 중량은 버틴다는 의미이므로 true를 반환해 알린다.이분탐색에서는 BFS 결과가 true이면 mid 값..

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

🧫 문제 분석 ✔️ 출처가장 긴 증가하는 부분 수열 2 골드 2 📖 문제 가장 긴 증가하는 부분 수열 1에 이어 2문제는 DP로는 불가능하고이분탐색을 통한 대치, 추가를 하여 부분 수열을 만들어 가야한다.  많은 블로그들이 원리를 설명하고 있으므로 생략하고 내가 헷갈렸던 것만 정리한다.  범위 탐색에서 front 무분별하게 front  이문제는 이렇게 풀면 좋지 않다.  근데 이렇게 해서 풀긴했다... ㅋㅋ front 이유는 front == back일때도 탐색함으로써 정확한 탐색이 가능하기 때문이다.  front front = mid + 1;back = mid; 이런식으로 범위를 줄이는데 현재 mid 위치의 값 front는 mid + 1을 하는 이유가 뭘까 라는 의문점이 생겼다. LIS는 증가하는 부..

🧫 문제 분석 ✔️ 출처예산 실버 2 📖 문제 이진 탐색이다. 하지만 국가 예산이라는 제한이 걸려있다.때문에 무턱대고 이진탐색 범위를 0 ~ 10억 이렇게 설정하면 정말 쓴 맛을 느낄 수 있다.  필자는 저렇게해서 삽질을 엄청하고, 반례는 다 통과하는데 75퍼에서 자꾸 틀리는 문제가 발생했다. 생각해보면 탐색을 할 범위를 명확하게 알고 설정해야하는데 무턱대고 큰 값을 설정한 것이 화근이였고이진탐색을 할 줄만 알지 정확하게 이 알고리즘에 대해 이해하지 못함을 느꼈다. 따라서 이진탐색을 파볼 예정이다.  요청 예산중 최댓값을 max로 이진 탐색한다. mid값을 각 요청 예산에 연산하여 mid > 요청 예산[i] 면 요청 예산값을 합 변수에 더하고,크다면 mid값을 상한값으로 더한다.그리고 국가예산과 합을..

🧫 문제 분석  ✔️ 출처연구소 골드 4 📖 문제 완전탐색  + BFS 문제이다. ( + 백트래킹...?) 단순하게 0인 곳에서 1을 세우되 3개까지만 세우고 BFS로 탐색해보고 퍼진 바이러스 개수의 최솟값을 구한다. 1을 세우는 것은 모든 구역에 대해서 진행하면 된다.  1로 된 벽 개수를 세고바이러스 위치를 list에 담고안전한 구역을 zeroList에 담는다.  list는 bfs에서 빠르게 사용하기 위함이고,zeroList는 완전탐색을 빠르게 하기 위함이다. 전체 크기 - (벽의 개수 + 새롭게 세운 벽 3개 + 바이러스 개수의 최솟값) 이 안전구역의 최댓값이다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static..

🧫 문제 분석 ✔️ 출처나무 자르기 실버 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..