Go Gradually - Repository

비슷한 문제를 풀어본 적이 있다.https://www.acmicpc.net/problem/11066 이 문제와 다른 것은 뭘까?파일 합치기는 반드시 바로 옆칸 1개와 합치기 때문에, 순차대로 순회하기가 쉽다.이 문제는 연속된 k칸끼리 합쳐야 하기 때문에, 추가적인 처리가 필요하다.n%(k-1)==1 이 아니면 -1을 반환해야 한다.연속된 k칸끼리의 합치는 방법을 생각해야 한다.파일 합치기의 경우DP[i][j] = DP[i][k] + DP[k+1][j] + psum[j] - psum[i-1]이 문제는?연속된 k칸을 합쳐야 한다. 점화식 자체가 달라지는건가?dp[i][p] + dp[p][q] + ...k가 커지면 for문의 깊이도 그만큼 커진다.k가 2인 경우를 제외하고,내부가 len % (k-1) == 1..

내 풀이 접근설명이 복잡하지만, 읽어보면 결국 가장 작은 수 안에 target 문자들 전부 포함시키는 최소 단어 수를 구하는 문제이다.이는 최단거리 문제와 유사하다.BFSDP조건에서 추가로 최적화할 부분이 없나 탐색해보자.target.length 16^50너무 크다.가장 부족한 단어부터 그리디하게 탐색하는 것이 최적해를 보장하나? -> Xtarget.length 중복조합 수식 (64 15)이것도 너무 크다.그래프를 target에서 시작하면 어떨까?깊이 16선택지 50가지가 맞나? 8가지여도 안되는데...(2^32)결국 중요한건 남은 문자열 정보이다. 이를 활용해보자.이를 2^15로 표현하면?32768그래서 이걸 어떻게 활용하느냐...여기서 차도가 없어 풀이를 봤습니다.정해백트래킹이었습니다~핵심 아이디어 ..

이번 문제는 다음 자료구조를 완성하라는 문제였다. 이런 유형의 문제는 릿코드만의 독특한 알고리즘 문제로, 라이브코테에서 만날 법한 문제였다. 가장 먼저 든 생각은 "중간을 찾는 자료구조"를 만드는 것이었다.두개의 스택을 이용해 큐를 만드는 것처럼,두 개의 우선순위 큐를 이용해 중간값을 유지하는 MedianFinder 클래스를 구현했다.class MedianFinder { PriorityQueue high = new PriorityQueue(); PriorityQueue low = new PriorityQueue(Collections.reverseOrder()); int count = 0; public MedianFinder() { } public void addNum(in..

내 풀이 접근현재 인덱스까지 구할 수 있는 최대 수익을 계산하려면이전 인덱스에 담겨 있는 최대 수익과, 그 인덱스부터 지금까지의 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. 값이 순열로 주어진다.중요한 통찰을 얻을 수 있는 마지막 단서는, 값이 순열로 ..