Study Log

점화식 초기 상태각 원소는 그 자체로 하나의 증가 부분 수열을 형성합니다.따라서 초기값:dp[i]=A[i](최소 합은 자기 자신)상태 전이인덱스 ii에서 가능한 이전 원소 jj를 탐색합니다:dp[i]=max⁡(dp[i], dp[j]+A[i]) (for all jdp[j]+A[i]: A[j]를 포함한 증가 부분 수열에 A[i]A[i]를 추가한 경우의 합.최종 결과모든 ii에 대해 dp[i]를 계산한 후:최대 합=max⁡(dp[0],dp[1],…,dp[n−1])  코드import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buff..

https://www.acmicpc.net/problem/2156문제 분석 과정이전에 두 잔을 연속으로 마셨다면 그 다음 잔은 마실 수 없습니다.최대 이전 3개의 값들까지만 기억하면 된다는 점을 이용해서 공간 최적화를 할 수 있습니다. 점화식dp[i−1]: 현재 잔 ii를 마시지 않고 이전 최적해를 그대로 가져오는 경우.dp[i−2]+array[i]: 이전 잔은 건너뛰고 현재 잔을 마시는 경우.dp[i−3]+array[i−1]+array[i]: 이전 잔과 현재 잔을 마시되, 두 칸 떨어진 잔은 건너뛰는 경우. dp[i]=max⁡(dp[i−1],dp[i−2]+array[i],dp[i−3]+array[i−1]+array[i])초기값 설정dp[0]=array[0]: 첫 번째 잔을 마시는 경우.dp[1]=arr..

https://www.acmicpc.net/problem/9465문제 접근 과정선택 가능한 경우의 수양옆 불가: 같은 열의 다른 행에 위치한 스티커를 선택할 수 없습니다.위아래 불가: 인접한 대각선 방향의 스티커도 선택할 수 없습니다.대각선 가능: 한 칸 떨어진 대각선 또는 두 칸 떨어진 대각선의 스티커는 선택 가능합니다.한 칸 떨어진 대각선: 현재 스티커와 같은 열의 반대편 스티커에서 이어지는 경우.두 칸 떨어진 대각선: 현재 스티커와 같은 열보다 2칸 앞에 있는 반대편 스티커에서 이어지는 경우.한 칸 대각선과 두 칸 대각선을 포함한 세 칸 이상의 대각선은 이미 점화식에서 표현 가능합니다. 점화식DP 배열 정의dp[0][j]: 첫 번째 행의 j번째 열 스티커를 선택했을 때 얻을 수 있는 최대 점수.dp..

https://www.acmicpc.net/problem/2193문제 접근 과정 이친수는 자리수를 기준으로 끝자리(0 또는 1)에 따라 앞의 숫자 조합이 결정됩니다.끝자리가 1인 경우:그 앞에는 반드시 0만 올 수 있습니다.끝자리가 0인 경우:그 앞에는 0과 1 모두 올 수 있습니다.  점화식DP 배열 정의:dp[length][0]: 길이가 length이고, 끝자리가 0인 이친수의 개수dp[length][1]: 길이가 length이고, 끝자리가 1인 이친수의 개수점화식:끝자리가 0인 경우:앞에 올 수 있는 숫자는 0과 1 모두 가능하므로: dp[length][0]=dp[length−1][0]+dp[length−1][1]끝자리가 1인 경우:앞에 올 수 있는 숫자는 0만 가능하므로: dp[length][1]..

https://www.acmicpc.net/problem/11057문제 접근 과정오르막 수의 개수를 계산할 때, 오름차순으로 계산하는 것이 아닌, 맨 끝자리 숫자를 고정했을 때의 관점에서 접근하는 것이 핵심입니다.끝자리 고정 관점오르막 수는 끝자리 숫자가 0부터 9 중 하나로 고정될 때, 앞의 숫자들이 어떤 값을 가질 수 있는지 계산하는 문제로 바꿀 수 있습니다.예를 들어, 길이가 2이고 끝자리 숫자가 1이라면 가능한 오르막 수는 다음과 같습니다:01, 11 (끝자리 1로 고정)길이가 3이고 끝자리 숫자가 1이라면 가능한 오르막 수는 다음과 같습니다:001, 011, 111 현재 자릿수에서 가능한 경우의 수현재 자릿수의 끝자리 숫자가 j로 고정된 경우, 이 숫자는 이전 자릿수에서 끝자리 숫자가 0부터 j..

https://www.acmicpc.net/problem/10844문제 접근 과정1자리 수는 모두 계단 수로 정의됩니다.1자리 수는 1부터 9까지 존재하며, 이는 모두 계단 수의 조건을 만족합니다. 따라서, 길이가 1인 경우 각각의 숫자(1~9)는 계단 수의 개수가 1개씩입니다.예외적으로, 문제에서 0으로 시작하는 수는 계단 수로 간주하지 않습니다.자릿수가 증가할 때, 숫자가 뒤에 추가된다고 가정합니다.숫자가 앞에 추가된다고 보는 것보다 뒤에 추가된다고 생각하는 편이 직관적입니다. 예를 들어, 길이가 3인 경우는 길이가 2인 계단 수의 뒤에 숫자를 추가하여 구성할 수 있습니다.예를 들어, 길이가 2인 계단 수 12에 숫자 3을 추가하면, 길이가 3인 계단 수 123이 됩니다.특수한 경우: 마지막 자리가 ..

https://leetcode.com/problems/network-delay-time/description/ 문제 문제 분석- 네트워크 중에서 모든 노드를 탐색하는 것이기 때문에 다익스트라로 검색 후, 가장 먼 거리에 떨어져있는 노드와의 거리를 반환하면 됩니다. (모든 노드를 탐지하는데 걸리는 총 시간이 아닙니다. 네트워크이기에 동시에 퍼져나간다는 가정 후, 가장 먼 노드까지 다 도달하는데 총 얼마나 걸리는가를 묻고 있는 것입니다.)- 초기 노드에서 출발 시 도착못하는 경우 -1를 반환하면 됩니다. 풀이#include #include #include #include using namespace std;class Solution {public: int networkDelayTime(vector>& ..

https://leetcode.com/problems/course-schedule/description/ 문제 문제 분석- 순환(cycle)이 있는지 탐색하는 문제입니다. 사이클이 존재하면 false를 반환하고, 존재하지 않으면 true를 반환하여야 합니다.- 현재 경로 중에서 중복되는 요소가 나온다면 false를 반환하면 됩니다. 이를 위해 set을 사용하였습니다.- traced의 경우 탐색이 끝나고 제거를 해주어야 [0,1], [0,2], [1,2]와 같이 cycle이 아닌 경우를 제대로 판별할 수 있습니다. 0 -> 1 -> 2 경로 탐색 후 제거하지 않는다면 1 -> 2 탐색할 때 2를 이미 탐색한 노드로 판별하여 false를 반환하게 될 것 입니다.- visited는 경로 탐색이 모두 끝난 요소..

https://leetcode.com/problems/reconstruct-itinerary/description/ 문제 문제 분석- 티켓들을 정렬 후 그래프로 구성한 뒤에 DFS 탐색을 하면 됩니다.- 현재 노드를 바로 결과에 추가하는 방식으로 하면 더 이상 갈 수 있는 경로가 없을 때, 올바른 경로가 구성되지 않게 됩니다.ex) tickets = [["JFK", "NRT"], ["JFK", "KUL"], ["NRT", "JFK"]] 의 경우 정렬 후 KUL이 먼저 나오게 되는데 JFK -> KUL로 가면 더 이상 갈 수 있는 경로가 없게 됩니다. 둘 다 가능한 경로라면 KUL이 먼저 나와야하지만, 경로가 가능한 경우에만 해당하기 때문에 가능하지 않은 경로라면 사전 순이 의미가 없게 됩니다.- 따라서 ..

https://leetcode.com/problems/subsets/description/ 문제 문제 분석- 조합을 만드는 문제이지만 result에 탐색하는 동안 나오는 부분집합들을 다 넣어주기만 하면 됩니다. 풀이class Solution {private: vector> result; void dfs(vector& nums, vector& current, int start){ result.push_back(current); for(int i = start; i > subsets(vector& nums) { vector current; dfs(nums, current, 0); return result; }};