Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처오르막 수 실버 1 📖 문제 깊이 별로 나누되 0~10까지 에 대해서 동적프로그래밍을 한다. 중요한 점수는 0으로 시작할 수 있다는 것이다.  현재 깊이의 각 수는 이전 깊이의 현재 수부터 9까지의 개수 합을 더하면 된다.   수 \ 깊이12301깊이 1의 0~9까지 : 10깊이 2의 0~9 까지 : 5511깊이 1의 1~9까지 : 9깊이 2의 1~9까지 : 4521깊이 1의 2~9까지 : 8깊이 2의 2~9까지 : 36 잘 모르겠다면 노드로 직접 그려보면 바로 알기 쉽다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws I..

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

🧫 문제 분석 ✔️ 출처영화감독 숌 실버 5 📖 문제 완전탐색 문제로6이 3개 이상 연속되어 들어가는 수를 말한다고 한다.즉 여러 수 중에 "666"이 포함되어 있으면 그 수는 종말의 수 라는 것이다. 문제의 이해를 잘 못했는데결국에는 사전 순서? 크기 순서대로 번호가 주어진다. 5666 -> 6660 -> 6661 -> ~ 6669 -> 7666 ... 이런식으로 가는 것이다. 나는 단순히 666부터 시작해서 intMax까지 완전탐색을 했다.현재 수를 문자열로 바꾸고 contains로 666이 포함되어있으면 count 하고count가 N과 같다면 count에 그 수를 저장하고 탐색을 종료한 뒤 count를 반환한다  🔅 문제 풀이import java.io.*;import java.util.*;pu..

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

🧫 문제 분석 ✔️ 출처36진수 골드 1 📖 문제  주어진 입력 중 Z로 k개 만큼 바꾸고 모두 더한 값이 최댓값이 되게 구하고, 그 값을 36진수로 변환하여 출력 정말정말 많은 시간을 썼고, 다른 블로그의 앞부분만 슬쩍봐서 큰 수를 어떻게 다루는지 참고하면서 풀었다. 결국에는 내가 생각한 아이디어와 로직이 맞았고, 큰 수를 다루는 BigInteger를 잘 안써서 떠오르지 못했던 것이다..   나의 경우 0~9 는 배열 각 인덱스 0~9에 1:1로 사용A~Z는 -'7'을 해주면 'A' - '7' = 10이 되므로배열을 35까지 만든 후 배열의 인덱스 0~9 A~Z까지 0~35로 사용하였다. 이 문제에서 중요한 것은Z로 바꾼 K개의 숫자가 무엇이냐다.맨 앞자리 수를 Z로 만든다고 무조건 최댓값이 나오는..

🧫 문제 분석 ✔️ 출처어린 왕자 실버 3 📖 문제 두 점 사이의 거리 공식을 이용하면 쉽게 풀리는 문제이다. 행성 경계의 좌표와 시작, 끝 지점의 좌표사이의 거리를 구하고그 거리가 행성 경계의 반지름 보다 짧다면 이는 그 행성 안에 시작점이나 끝 지점이 있다는 뜻이고이는 1번 진입/이탈을 해야한다는 의미이다.  중요한 점은 시작 점과 끝점 둘 다 한 행성 안에 있을 수 있다. 이때는 진입/이탈이 없다.따라서 시작 점이 행성 경계 안에 있는 경우 와 끝점이 행성 경계 안에 있는 경우만 따지면 된다.🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static class Planet { int x,y, r; ..

🧫 문제 분석 ✔️ 출처백준 17298번 오큰수 골드 4 📖 문제 오큰수는 현재 요소보다 크면서 가장 왼쪽에 있는 수이다.그렇다고 무작정 모두 비교하며 찾기에는 O(n^2)이 걸린다. 수열의 크기가 100만까지인 걸로 보아 1초안에는 절대로 불가능하다. 수열을 잘 생각해보자문제에서 [3, 5, 2, 7] 을 보면3은 바로 뒤 5가 있으므로 55 와 2는 7이 오큰수가 된다.  오른쪽 수가 크지 않다면 담아놓고담아놓은 수보다 큰 수가 나오면 이 수가 오큰수가 된다. 이렇게 사용할 수 있는 자료구조가 스택이다.  사실 단순한 스택문제이다.   🔅 문제 풀이import java.io.*;import java.util.*;public class Main { public static void main(..

🧫 문제 분석 ✔️ 출처RGB 거리 실버 1 📖 문제 DP 문제로현재 집 비용 + 이전 집에서 현재 집 열이 아닌 2 곳 중 가장 적은 비용을 가진다. 점화식을 세워보면 이렇다. dp[i][j] = Math.min(dp[i][j+1], dp[i][j+2]) + house[i][j];물론 한 행에 집은 3개이므로 현재 열을 제외한 다른 집 중에서 가장 적은 비용을 선택하므로% 연산이나 if문을 써서 현재 집 열을 피하면 된다.   🔅 문제 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = ..

🧫 문제 분석 ✔️ 출처잃어버린 괄호 실버 2 📖 문제 이 문제같은 경우첫번째 수를 저장한 뒤 +가 나오면 더해준다. 그런데 한 번이라도 -가 나오면 그 뒤에 아무리 많은 +가 나와도 처음 나온 - 때문에 이들은 전부 합한 후 -로 빼게 된다. 따라서 한 번이라도 - 가 나오면 저장 한 수에 계속해서 -로 빼주면 된다.  예를 들어 아래의 입력이 주어진다고 하자1+2-4-5+2+3처음 1 +2까지는 더하고 -가 나왔으므로 괄호를 쳐서 최솟값을 만들어야 하기에 - 뒤에 나오는 +로 더해지는 모든 수들을 빼주면 된다.(1 + 2) - 4 - 5 - 2 - 3 = -11(1+2)  -4 - (5 + 2 + 3) =   -11  🔅 문제 풀이import java.io.*;public class Main {..