Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처극장 좌석 실버 1📖 문제 피보나치 수열 문제vip 영역일때는 이전 값을 이어받는다 현재 좌석을 기준으로 현재 좌석을 고정한 경우의 수 + 현재 좌석이 왼쪽 좌석과 교환했을 때 경우의 수를 구하면 된다.1 2 3 4 이고 현재 4라면1 2 3 | 4 로 4를 고정하고 1 2 3까지 의 경우의 수 dp[3]+1 2 | 4 3 으로 3과 교환하고 1 2 까지의 경우의 수 dp[2] 를 더한다 즉 점화식은if (isVip[i] || isVip[i-1]) : dp[i] = dp[i-1]else : dp[i] = dp[i-1] + dp[i-2] vip 좌석은 따로 기록해놓고피보나치 수열을 연산할때현재 좌석 혹은 이전 좌석이 vip 좌석이면 dp[..

🧫 문제 분석 ✔️ 출처암호코드 골드 5 📖 문제 DP 문제 연습셋DFS + DP (메모이제이션)으로 풀었는데 좀 더럽게 풀었다.DP[암호의 각 인덱스][알파벳 인덱스] 이렇게 2중 배열로 생각해서 풀었다. 그런데 알파벳은 고려대상이 아니다. 다른 사람 풀이를 보고 이해한 것도 정리한다. 0에 대한 모든 경우의 수를 처리했는데 그럴필요가 없었다... 그리고 DFS로 풀때 idx 즉, 인덱스만 신경쓰면 충분히 풀이가 가능했다. 나는 굳이 알파벳 수치 값을 파라미터로 넘겼는데 그럴 필요없이 현재 선택한 수가 알파벳 변환이 가능한지 여부로 따지고 가능하다면 다음 인덱스로 넘어가는 식으로 하면된다. 비슷한 문제 포스팅https://progis.tistory.com/85🔅 문제 풀이 [내 풀이 To..

🧫 문제 분석 ✔️ 출처상자넣기 실버 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곳이 다 다르다면 현재 자신이..

🧫 문제 분석 ✔️ 출처파이프 옮기기 1 골드 5 📖 문제 BFS로 89%에서 시간초과 떠서 별짓을 다 하다가 질문게시판에 map[n][n] == 1일때 예외처리를 하면 된다 해서 했는데 통과했다. DP로 풀 생각은 들었는데 방향을 DP로 어떻게 표현할지 모르겠어서 무작정 BFS로 일단 풀었다.  방향 정하는 방식을 좀 이상하게했다.  DP로 하는 법을 이해해 보고 그림으로 그려봤다 dp로 현재 들어오는 방향에 대해서 다 구하면 된다 . 🔅 문제 풀이import java.io.*;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Main { static int[] dy =..

🧫 문제 분석 ✔️ 출처LCS 골드 5 📖 문제 최장 공통 부분 수열로 알고리즘 시간에 배웠었다. 근데 배운거랑 직접 구현해본거랑 차이가 심한 것을 느꼈다. 이 문제를 못푸니 배낭문제도 못푼다. LCS에 대한 이해가 있었다면 배낭 문제를 쉽게 풀 수 있을 것이다.  현재 비교하는 두 문자가 같다면 이전 최장 공통 부분 수열 길이에 + 1을 하여 LCS를 갱신한다. 두 문자열의 길이를 각각 n과 m이라 할 때,DP 테이블 dp는 인덱스 i∈[0,n]  j∈[0,m] 범위를 기반으로 구성된다. i-1, j-1까지 진행 했을때 LCS 길이 + 현재 공통 문자가 나왔으므로 길이가 1 증가때문에 dp[i-1][j-1] + 1이 된다.  같지 않다면 dp[i-1][j], dp[i][j-1] 중 큰 값을 유지한다..

🧫 문제 분석 ✔️ 출처오르막 수 실버 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..