Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처상자넣기 실버 2 📖 문제 LIS 문제DP, 이분탐색 둘다 풀 수 있다. 최장 증가 부분수열 풀이로 풀면된다. 하다가 찾은 반례 42 4 2 2정답 : 2오답 : 1 🔅 문제 풀이 [DP]import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(S..

🧫 문제 분석 ✔️ 출처합분해 골드 5 📖 문제 DP 연습셋 문제중 하나 0~N까지의 정수 K개를 더한 합이 N이 되는 경우의 수 구하기 0~N까지의 수(i) 를 1~K개를 뽑아서 더해 i가 되는 경우의 수를 구하는 식으로 구해봤더니 맞았다.i \ k123401111112342136103141020415153551621566172884 구한 결과점화식이 나왔다.DP[N][k] = (DP[N-1][k] + DP[N][k-1]) % 1000000000; 그리고 중요한 점은 문제에서 출력시 % 10억을 하라는 조건이 있으므로 잘 확인하자.🔅 문제 풀이import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOExcep..

🧫 문제 분석 ✔️ 출처타일 채우기 골드 4 📖 문제 홀 수 일때는 만들기가 불가능하다.크기가 3X2인 벽을 채우는 경우의 수부터 시작한다. 3가지가 있다. 현재 크기(i)의 개수 = i - 2번째 크기의 개수 * 3 (이는 이전 크기의 각 구조에 오른쪽으로 3가지 타일을 두는 경우의 수)또한 특수한 구조가 2가지씩 생긴다.i - 2번째 크기 * 3 에 특수한 구조 2가지에 대해서 왼쪽에 붙이는 경우의 수를 더한다. 쉽게 이해해본 결과i = 6 일때dp [4] * 3 + dp[2] * 2 + dp[0] * 2; dp[2] *2 dp[4]의 특수한 구조 2가지를 오른쪽에 두고 dp[2]의 구조들을 왼쪽에 채움 dp[0] * 2dp[6]의 특수한 구조 2가지를 오른쪽에 두고, dp[0]의 구조들을 ..

🧫 문제 분석✔️ 출처팰린드롬? 골드 4 📖 문제팰린드롬 문제인데 주어지는 S, E 구간이 100만개다.수열의 크기 N이 2000까지고 1최악의 경우 O(NM) 이되어 20억가지수를 계산해야한다. 그런데 투포인터로 하면 통과한다. 그리고 다른사람들의 알고리즘 시간을 보니 500~700ms 대를 보았다. 참 좋은 공부가 된 것 같다. S, E 구간을 이중 배열로 구별하여 DP로 이전의 구했던 구간을 다시 사용하여 현재 S,E 구간을 구하는 방식이다. 내가 이해한 바로는1. 팰린드롬 길이가 1일 때 : 자기 자신이므로 항상 팰린드롬이다. 따라서 dp[i][i] = true이다. 2. 팰린드롬 길이가 2일 때 : i, i+1이 같으면 팰린드롬이다. 따라서 seq[i] == seq[i+1] 이면 d..

🧫 문제 분석 ✔️ 출처LCS 2 골드 4 📖 문제 LCS 문제와 다른 점은 LCS를 출력해야한다는 것이다.단순히 순차적으로 탐색하면서LCS에서 길이가 1인 처음 만나는 문자LCS에서 길이가 2인 처음 만나는 문자이런식으로 풀면 안된다. 문자열이 같은 문자가 연속으로 주어지는 경우 잘못된 LCS를 구하게 되기 때문이다. AAACCCAACCA A A C C AA 1 1 1 1 1A 1 2 2 2 2 A 1 2 2 2 3C 1 2 3 3 3C 1 2 3 4 4C 1 2 3 4 4 이렇게 위에서부터 순차적으로 for문 탐색시 AAAC가 되버린다.답은 AACC 이다. 때문에 가장 마지막 위치에서 이전 대각위, 왼쪽, 위쪽을 탐색하여 같은 길이 값이면 그 곳으로 이동하고3곳이 다 다르다면 현재 자신이..

🧫 문제 분석✔️ 출처다각형의 면적 골드 5 📖 문제 신발끈 공식 이라는 특이한 다각형 면적 구하는 공식이 있다.문제에서 다각형을 이루는 순서대로 N개의 점 좌표가 주어진다하였으므로 그대로 신발끈 공식을 적용한다. 계산을 할때 long 형으로 받아야하는 점, 출력을 소수점 둘째 자리에서 반올림하여야하는 점을 고려하면된다.String.format을 사용해서 %.1f 를 사용하면 내부적으로 둘째자리까지 반올림해서 문자열을 만들어준다. 🔅 문제 풀이import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.StringTokenizer;public class Main { /..

🧫 문제 분석 ✔️ 출처마인크래프트 실버 2 📖 문제 완전탐색 문제로 땅 고르기를 하면된다. 주어진 땅 높이들의 최소, 최댓값을 구한 후최소~최대 높이까지 탐색을 해서 최단 시간이면서 가장 높은 높이를 구하면된다. 나는 잘못 푼게 있는데 맵 탐색중 2번 작업시 인벤토리내에 블록이 없으면 바로 불가능하다고 판단하고 멈췄는데 생각이 짧았다..현재 위치에서 인벤토리가 비어있더라도다른 위치에서 1번 작업을 통해 블록을 인벤에 저장하고 현재 위치에서 사용할 수 있는데이걸 생각못한게 정말 .. 눈물이난다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static int totalTime = Integer.MAX_VALUE; s..

🧫 문제 분석✔️ 출처N-Queen 골드 4 📖 문제 많은 깨달음을 준 문제다. 퀸의 특성상 상하좌우대각을 원하는 만큼 이동이 가능하기에 그에 따른 검증을 해야한다. 처음에는 이중 배열로 만들어서 각 퀸의 위치를 리스트에 저장하고 리스트를 순회하면서 검증하고 놨는데 시간복잡도가 너무 크게 나와서 O((N^2)^N) 힌트를 보고 풀었다. 퀸 특성상 n개의 체스판에서는 각 행에 하나씩 둬야 n개의 퀸을 둘 수 있다.때문에 퀸을 두고 다음 행을 탐색한 후 돌아온 다음 다시 퀸을 지울 필요없이 덮어씌우면된다. (백트래킹에서) 나의 잘못된 생각은검증시 0~n 행까지 전부 다 해서 쓸모없는 연산이 늘고, 잘못된 검증이 되어 값이 증가한 것이다. 말했듯이 n개의 퀸을 놓을려면 0행부터 순서대로 n행까지 하나..

🧫 문제 분석 ✔️ 출처치즈 골드 3 📖 문제 외부 공기를 기준으로 BFS 탐색하여 치즈와 맞닿으면 카운팅해준다.  그런데 다른 풀이를 보고 했는데 치즈가 가장자리 (0,0)에서 시작할 수도 있지 않나 싶은데0,0 부터 외부 공기 찾는 로직이 있어도 다 통과해서 치즈가 가장자리에는 위치하지 않나보다. 나는 치즈의 처음 만나는 지점과 마지막 지점을 구하고, 안쪽 방향을 제외한 3방향을 탐색해서 공기외부 좌표를 구한다음BFS 탐색을 하여 공기 접촉 탐색을 했다. 공기를 2번 이상 접촉하면그 지점을 공기로 만들면 된다.   7 71 1 1 0 0 0 01 0 1 1 0 0 01 0 1 0 1 0 00 1 0 1 0 1 00 0 1 0 1 0 00 0 0 1 0 0 00 0 0 0 0 0 0//answer ..

🧫 문제 분석 ✔️ 출처파티 골드 3 📖 문제 O(N^3) 인 플로이드 워샬은 사용불가능하고,다익스트라로 풀어야하는 문제다. 그런데 X→모든 정점은 구하겠는데 모든 정점→X를 편하게 구하는 법을 몰라서 각 정점에서 다익스트라 알고리즘을 돌려서 X까지의 값을 구하는 식으로 했다.  이 후 다른 사람의 풀이를 봤는데 정말 놀랍다.  단방향이지만 역방향으로 그래프를 만들어서// 기존 X -> AllAll -> X// 다른사람들의 풀이X -> All X 로 X에서 모든정점으로 가는 그래프를 만들고X로 오는 모든 정점으로 가는 역방향 그래프를 만드는 것이다. 좋은 것을 배웠다..  🔅 문제 풀이 [x→ all → x]import java.io.*;import java.util.*;public class Ma..