Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처영화감독 숌 실버 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 {..

✔️ 출처쉬운 계단 수 실버 1 📖 문제중복 연산이 많이 일어나고 반복적이다.  이참에 다시 학교에서 배운 DP의 적용 요건을 복습하겠다.  최적 부분구조(Optimal substructure)큰 문제의 최적 해에 하위 문제의 최적 해가 포함하위 문제들의 중복 (overlapping recursive calls)재귀적 해법으로 풀면 같은 하위 문제에 대한 호출이 심하게 중복 재귀적으로 깊이만큼 0~9까지 +1 -1을 하면서 생성하다보면 엄청난 중복이 생김이전의 깊이에서 얻은 갯수를 재활용할 수 있을 것 같음. DP를 적용해보자 우선 0과 9는 1가지 밖에 없다.0 → 19 → 8따라서 0 과 9는 따로 처리하고 1~8까지는 -1 +1 숫자가 계단 수이니 이전 깊이의 -1 +1 숫자의 개수를 더한다.  ..

🧫 문제 분석 ✔️ 출처가장 긴 증가하는 부분 수열 실버 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..