Go Gradually - Repository

내 풀이 접근현재 인덱스까지 구할 수 있는 최대 수익을 계산하려면이전 인덱스에 담겨 있는 최대 수익과, 그 인덱스부터 지금까지의 1회 최대 수익을 알고 있어야 한다.이는 카데인 알고리즘과 굉장히 유사하다고 판단했다. 따라서 DP를 이용해 현재 인덱스까지 가장 최적의 이익을 찾도록 했다.class Solution { public int maxProfit(int k, int[] prices) { int[][] dp = new int[prices.length + 1][k+1]; int ret = 0; for(int kk = 1; kk이래도 통과는 한다.하지만, 조건이 빡빡하다면 통과하지 못했을 것이다.좀 더 효율적인 해이전에 구할 수 있는 최대 이익을, 0~i까지 전..

배낭(knapsack) 문제는 보통 제한된 용량의 컨테이너에 물건들의 부분집합을 넣되, 물건과 관련된 어떤 양을 세거나(카운트) 최적화하는 문제를 다룬다.거의 항상 각 물건은 양의 무게를 가지며, 우리가 선택한 물건들의 총 무게는 어떤 수로 주어지는 컨테이너의 용량을 초과해서는 안 된다. 배낭 유형 문제의 변형으로는 다음과 같은 것들이 있다.0/1 배낭 문제: 물건들의 부분집합을 골라 총 가치를 최대화하되, 총 무게가 컨테이너의 용량을 넘지 않도록 한다.가능한 총 무게 찾기: 컨테이너 용량을 넘지 않게 임의의 부분집합으로 만들 수 있는 모든 총 무게를 구한다.정확히 채우는 경우의 수 세기: 총 무게가 정확히 컨테이너 용량이 되도록 하는 물건의 순서열이 몇 개인지 센다(순서가 중요할 수도 있고 중요하지 않..

사실 '다이나믹'도 아니고, '프로그래밍'도 아닌 다이나믹 프로그래밍은 알고리즘 문제의 단골 요소이자 매우 효율적인 컴퓨터공학의 계산 효율화 방법이다.DP는 벨만-포드 알고리즘과 벨만 방정식, 강화학습의 토대를 마련한 미국의 응용수학자 리처드 E. 벨만이 발견했다. 이는 리액트의 렌더링 및 BFS, 캐싱, 비즈니스 로직 및 게임 엔진 최적화부터 심지어는 RL에까지 등장하고 있다. 이 DP에 대해, 지금부터 차근차근 알아보자.DP의 성질은 딱 두가지로 정리가 가능하다최적 부분구조중복 부분문제최적 부분구조최적 부분구조(Optimal Substructure)은 "경로에 관계없이" 다음 문제의 해답이 이전 부분문제의 최적화로 구해지는 구조를 의미한다.이를 다르게 표현하면, 뒷 문제의 정답을 구하는 과정이 앞 문..

모듈러 연산에서는 정수 그 자체로 계산하지 않고, 어떤 수를 m으로 나눈 나머지로 계산한다.이를 "모듈러 m을 취한다”라고 부른다. 예를 들어 m=23이라면, x=247 대신 x  mod  23=17을 사용한다.보통 m은 문제에서 주어지는 큰 소수(prime)이며, 가장 흔한 값은1000000007998 244 353=119⋅2^23+1이다.모듈러 산술은 내장 자료형의 범위를 넘는(오버플로) 큰 수를 다루지 않기 위해 사용되며, 다음 공식을 이용해 나머지를 취할 수 있다.Modular Exponentiation (모듈러 거듭제곱)거듭제곱 (Easy)https://cses.fi/problemset/task/1095 CSES - ExponentiationCSES - Exponentiation Time lim..

이와 같은 수학 문제는 코딩 테스트에는 잘 출제되지 않기 때문에 건너뛰는 사람들도 많지만,나는 시간복잡도 계산에 가장 강력한 인사이트를 부는 내용이 바로 이 수학 부분이라고 생각한다.그래서 이 수학 파트도 건너뛰지 않고 어느정도 설명을 진행하도록 하겠다.소인수분해 (Prime Factorization)양의 정수 a가 음이 아닌 정수 b의 약수(divisor) 또는 인수(factor)라고 불리는 것은, b가 a로 나누어떨어진다는 의미이다. 즉, 어떤 정수 k가 존재하여 b = ka가 되는 경우이다.정수 n > 1이 소수(prime)라는 것은 그 약수가 1과 n뿐일 때를 말한다.1보다 큰 정수 중 소수가 아닌 수는 합성수(composite)라고 한다. 모든 양의 정수는 유일한 소인수분해를 가진다. 즉, 소수..

아래 내용은 미국 정보 올림피아드인 USACO의 알고리즘 문제 학습 가이드인 usaco.guide를 참고하여 작성되었습니다 Introduction to Prefix SumsComputing range sum queries in constant time over a fixed 1D array.usaco.guide 시작 전에 이 문제를 풀어보고 오자.난이도: Very Easy Library Checker judge.yosupo.jp 길이가 N인 다음 값을 계산하기 원하는 1차원 정수 배열이 있다고 가정해보자.우리는 여기서 서로 다른 Q개의 쿼리를 (a,b)으로 보낼 것이다.그때의 (a, b)는아래 식을 만족한다.간단한 예시를 위해, N을 6으로 두고 문제를 풀어보자.인덱스 i123456arr[i]164253..

실제 contest중에는 풀지 못한, 난이도 높은 문제였다.Upsolving 을 진행하며, 정리한 내용을 공유하고자 한다.문제https://codeforces.com/contest/1905/problem/Dnn^2 으로는 절대 풀 수 없는 문제이다.핵심 아이디어1. 반드시 맨 앞 원소가, 맨 뒤로 간다.중요한 통찰을 얻을 수 있는 단서 중 하나는, a[0]이 맨 뒤로 간다는 것이다.이 사실을 응용해보자2. MEX값은, 범위가 넓어지면 넓어질수록 무조건 증가하는, 단조증가 형태를 띈다.단조증가 성질 또한, 무궁무진한 활용 가능성을 갖추고 있다.그리디한 접근 혹은, 파라매트릭 서치에도 응용이 가능하니, 기억하고 있도록 하자.3. 값이 순열로 주어진다.중요한 통찰을 얻을 수 있는 마지막 단서는, 값이 순열로 ..

기본적인 0-1 BFS 문제처럼 보인다.deque를 이용하면, push_front() 및 push_back() 을 이용해 열어야 하는 문의 갯수를 셀 수 있다.근데 단순 최단거리가 아니다.죄수 두명을 탈옥시켜야 한다.탈옥의 정의는, 현재 보여지는 지도 밖으로 죄수가 나간다는 의미이다.우리는 여기서, 지도 밖에 padding 을 한 줄 추가함으로서, 탈옥을 시킬 수 있다.단순히 bfs 하면?다음과 같이, 겹치는 지점을 제외해줘야 한다.근데 두개의 거리를, 중복 없이 어떻게 잴 수 있지?시나리오를 그려보며, 규칙성이 있는지 탐색해보면 반드시 어딘가에서 죄수 2명과 외부지점이 만날 수 있다.문제를 두번에 나눠서 풀면, 해를 구할 수 있지 않을까?다음과 같은 경우, 두 죄수 사이의 최단 거리는 5이고, 이 최단..

[2213] 트리의 독립집합문제를 천천히 읽어보자.독립집합이란, 모든 정점 쌍이 인접하지 않은 정점들의 집합이라고 한다. 간단하게 그림을 그려보면, 다음과 같은 예시를 들 수 있다.그리고 다음과 같은 애들은 독립집합이 아니다.여기서 문제는 한가지 새로운 정의를 내린다.독립집합의 크기란? 독립 집합 내 정점들의 가중치의 합정점의 가중치는 정수로 주어지고, 10000 이하로 제한되어 있다.우리의 목표는 독립집합을 이루는 경우의 수 중, 가장 큰 "집합 내 원소의 가중치의 합"을 구하는 것이다.문제에 그래프 형태가 트리 구조로 되어있다고 하는데, 여기에서 우리는 중요한 관찰을 할 수 있다.트리구조로 되어있다는 것은,정점 A가 어떤 독립 집합 S에 포함/제외되는 것이 재귀적으로 자기 자신에게 영향을 주는 "사이..

[1475] 방 번호어떠한 사람(기능) 이 필요한가?항상 설명이 너무 복잡하다면, 일단 문제를 단순화해서 보자. → 조건을 몇개 제거해보자.(6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다는 조건을 제외해보자.)만약, 122 라는 숫자를 만들어야 한다면, 플라스틱 세트는 2세트가 필요할 것이다(2를 2개를 수급하려면, 플라스틱 세트 2세트가 필요할 것이고, 3~9까지 각각 숫자 2개씩은 모두 버려질 것이다. 아깝네)만약, 9999라는 숫자를 만들어야 한다면, 플라스틱 세트는 4세트가 필요할 것이다.(9를 4개를 수급하려면, 플라스틱 세트는 4세트가 필요할 것이고, 9를 제외한 나머지 숫자들 각 4개들은 모두 버려질 것이다.)우리는 여기서, 다음과 같은 결과를 찾을 수 있다.가장 ..