Approach 특정한 구간에 대한 정보를 묻고 있는 상황이므로 세그먼트 트리 자료구조를 활용할 수 있지 않을까라고 판단해주면 된다. 이때, 퀘스트가 총 21억개로 상당히 많은 것과 달리 처리한 퀘스트는 최대 2백만정도 밖에 존재하지 않는다. 따라서 처리한 퀘스트를 기준으로 좌표압축을 해주고, 특정 쿼리에 대한 해결한 퀘스트의 개수를 구해주는 방식으로 이 문제를 해결할 수 있다. 단, 이런 방식으로 처리하려면 입력값으로 들어오는 좌표들을 미리 한번에 받아두어야하므로 미리 정보를 다 저장해둔다. 처음에 접근한 방식은 해결한 퀘스트 번호만을 가지고 좌표 압축을 진행하였다. 다만 이 방식의 문제점은, request에서 퀘스트 번호가 주어졌을 때 무엇을 포함하고 포함하지 않을 것인지에 대한 기준이 모호하다. 만..

Approach 이 문제에 대해서 잘 고찰해보면, 어떤 기업이 선택되는 것은 이전 기업에 얼마만큼의 투자했는지에 의해서 결정된다. 따라서 이러한 측면에서 관계식을 통해 표현할 수 있으므로 DP라고 인식해야 한다. Let $dp[i][j]$ : the amount of maximum profit when we investing exactly $j$ until considering $i$'th element $dp[i][j] = \underset{k \in R, \forall k \in [0,j]}{max}(dp[i - 1][j - k] + b[i][k])$ 즉, i번째 기업까지를 고려해서 투자할 때, i - 1번째 까지의 투자 데이터를 가지고 있으면 된다. 그렇게 되면 투자 금액이 동일할 때, 최대의 이익..

Dynamic programming이란? 복잡한 문제를 여러 간단한 문제로 쪼개서 푸는 것 기본적으로 고등학교 때 학습하였던, 점화식을 활용하여 푸는 방법론이라고 이해해도 무방한다. 구현 방법 구현 방법은 크게 2가지가 있다. 반복분 장점 빠르고 메모리 측면에서 이득을 본다. DP 최적화 작용이 쉽다. (덱 DP, 세그 DP) 단점 테이블을 채우는 순서를 고려해야 한다. 순서가 복잡한 경우 사용하기 어렵다. (트리 DP, 비트 DP) 재귀 (Memoization을 사용) 장점 DP를 채우는 순서를 고려하지 않아도 되나, memoization을 사용하여 동일 반복 계산을 피한다. 순서가 복잡한 경우에도 처리하기 쉬움 (트리 DP, 비트 DP) 단점 반복문에 비해 느리고 메모리가 많이 든다. DP 최적화 작..

Approach 문제를 잘 보면 전체적으로 이전의 결과가 이후의 결과에 계속 영향을 주는 것을 알 수 있고 해당하는 경향성을 점화식을 통해 일반화해서 나타낼 수 있음을 쉽게 파악할 수 있다. 이 지점에서 DP문제를 떠올려 주면 된다. 다만, 이 문제에서 어느 블록을 이전에 썼는지를 파악해야 경우의 수를 더할 수 있으므로 각 타일의 종류마다 따로 DP를 할당해서 점화식을 세워주면 된다. 에를 들어 dp[i][1], dp[i][2], dp[i][3]을 각각 i번째 가로에 1 x 2, 2 x 1, 2 x 2 블럭을 사용했을 때의 경우의 수라고 하면 점화식을 다음과 같이 나타낼 수 있다. $$ dp[i][1] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]$$ $$dp[i][2]..

Approach 아래쪽으로 내려갈 때, 2가지 가능성이 존재한다. 대각선 왼쪽, 대각선 오른쪽 그런데 인덱스를 잘 생각해보면 자신이랑 같은 인덱스이거나 1개 더 작은 값이라는 것을 쉽게 파악할 수 있다. 이 점을 이용해보면, 점화식을 세울 수 있다. 추가적으로 자신보다 큰 index의 값은 필요가 없으므로 슬라이딩 윈도우 기법을 활용해서 Space complexity를 조금 더 낮출 수 있기는 하지만 생략.. dp[i][j]를 i번째 줄 j번째 index가 가지는 값의 최대값이라고 가정하자. 그러면 점화식은 다음과 같다. $$dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + v \mbox{ (단, i는 줄 넘버, j는 몇번 째 수)$$ Code #include #de..

Approach Let dp[i] : Continuous maximum sum considering i'th element If dp[i - 1] value is negative, dp[i] could be maximize by throwing previous continuous sum. On the oher hand, dp[i] could be maximized by along previous continuous sum. So, Recurrence relation could be represented by $$ dp[i] \begin{cases} v[i] & \mbox{(if dp[i - 1] is negative)} \\ v[i] + dp[i - 1] & \mbox{(if dp[i - 1] is po..

접근 방법 계속해서 이전 값들을 더해나가는 경향성 자체를 몇 번 시도하다보면 쉽게 파악할 수 있다. 또한 더하는 숫자들의 기준이 반복되는 것을 통해 점화식으로 이 문제를 쉽게 해결할 수 있음을 파악할 수 있다. 이전 포스트에서도 계속 언급한 것처럼 점화식 형태로 표현되는 것들은 일반적으로 DP를 활용해서 풀어줄 수 있다. 코드 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef long long ll; int main(void){ fastio; ll dp[101]; dp[1] = 1; dp[2] = 1; dp[3] = 1; dp[4] = 2; dp[5] = 2; dp..

접근 방법 일단, 어차피 카드 묶음이 1개씩 지워지는 상황이므로 무조건 큰 숫자가 나중에 묶이는 것이 유리하다. 그렇지 않으면 반복해서 묶이게 되어 숫자가 더 커지기 때문이다. 따라서, 숫자가 작은 것을 먼저 선택하기 위한 자료 구조가 필요하므로 우선순위 큐 자료구조를 활용해주면 된다. 코드 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; int n; cin >> n; priority_queue pq; for(int i = 0; i > temp; pq.push(temp); } int res..