백준 24 문제. 1. BOJ 31503 : DP (Large) - P5 O(NlogN) LIS 문제. 문제를 해석해보면 결국 특정 위치의 원소가 꼭 들어갈 때의 LIS의 길이 구하기 문제가 된다. i 번째 원소를 포함한 LIS의 길이는 (i 번째 원소가 마지막 원소인 LIS의 길이) + (i 번째 원소가 제일 처음에 들어있는 LIS의 길이) - 1 이 되는데, 여기서 배열의 원소들에 -1를 곱하고 역으로 뒤집으면 "N번째 원소부터 볼 때 i 번째 원소가 제일 마지막 원소인 LIS의 길이" = "i 번째 원소가 제일 처음에 들어있는 LIS의 길이"가 된다. 따라서, O(NlogN) LIS로 먼저 " i 번째 원소가 마지막 원소인 LIS의 길이"를 모든 i 번째 원소에 대해서 미리 계산하고, 배열에 모두 ..

백준 18문제. 1. BOJ 13511 : 트리와 쿼리 2 - P3 LCA, Sparse Table 문제. 일단 아무 노드를 루트로 두어 LCA Table + 루트로부터 해당 노드까지 가는데의 비용을 O(NlogN)으로 다 계산한다. 그리고 이제 각 쿼리에서의 u,v에 대한 LCA를 lca라고 한다면... 1번 쿼리는 루트에서의 u까지의 비용 + v까지의 비용 - 2 * lca까지의 비용 이렇게 계산하면 된다. 2번 쿼리는 만약에 k가 u에서 lca까지의 거리보다 크다면 역으로 v에서부터 lca까지 가는 도중에 (u에서 v까지 거치는 노드 개수) - k 번째 노드를 아니면 u에서 lca까지의 k번째 노드를 LCA Table로 O(logN)에 구하면 된다. 총 시간복잡도는 O((N+Q)logN). 하필 이..

지난번에 Dijkstra 알고리즘에 대해서 제가 이해한 방식대로 설명해봤었는데, 이번에는 Mo's 알고리즘을 제가 이해한대로 한 번 설명해보고자 합니다. 물론, 지난번과 같이 이건 제가 이해한대로 설명한 것이기 때문에 정확한 설명이 아닐 수 있습니다. 그래도 Mo's 알고리즘이 무엇인지를 이해하는데에는 도움이 되지 않을까 해서 글을 올려봅니다. 그 전에 Mo's 알고리즘이 무엇인지와 어떤 문제들을 해결할 수 있는지에 대해서 설명해보겠습니다. Mo's 알고리즘은 무엇인가? 후술하겠지만 Mo's 알고리즘은 Sqrt-Decomposition(평방분할)의 아이디어를 차용해서 특이한 구간 쿼리들을 계산하는 테크닉 입니다. 구간 쿼리라면 Segment Tree를 주로 떠올리실텐데, 이 알고리즘의 시간복잡도는 Seg..

백준 13 문제. 1. BOJ 31430 : A+B - 투 스텝 - B1 A + B가 최대 2*10^18까지 가능하다. 그런데 'a' = 0, 'b' = 1, ... 이렇게 매핑하면 26진법으로 표현이 되면서도 26^13 이 2*10^18보다 더 크므로 26진법 인코딩을 해주면 된다. 이후에 다음 프로그램 에서는 26진법 표현을 받고 이를 다시 10진법으로 변환하면 된다. 처음으로 푼 투 스텝 문제라서 리뷰해보았다. 투 스텝 문제를 이해하고 입문하기 매우 좋은 문제라 생각한다. 2. BOJ 15651 : N과 M (3) - S3 Backtracking 문제다. 그냥 N^M 가지의 경우의 수를 전부 돌려보면 된다. 다른 N과 M 문제들과 비슷한 문제였다. 3. BOJ 5347 : LCM - S5 Numbe..

백준 19 문제. 1. BOJ 11502 : 세 개의 소수 문제 - S4 Number Theory(Primality Test) + Bruteforcing 문제. 1000 이하의 모든 소수를 찾는 건 그냥 O(N^2)로도 찾을 수 있다. 1000 이하의 소수는 대략 200 개 미만일 것이라 생각해서 세 수를 찾는 건 O(N^3)로 모든 조합을 찾아보았다. 앞에 소수 찾는 걸 Sieve로 좀 더 빠르게 찾을 수는 있는데... 귀찮아서 구현을 안 했다. 2. BOJ 11332 : 시간 초과 - S3 Implementation + Case-working 문제. 시간복잡도를 나타내는 문자열에 따라서 로직을 전부 다르게 구현해야 한다. O(N^2), O(N^3), O(2^N), O(N!)은 오버플로우가 나타날 가능..

백준 16~17문제. 1. BOJ 23760 : 까다로운 아이들과 선물 상자 - P5 (업다운 랜덤디펜스 성공! Solved - 18:01) Segment Tree + Binary Search 문제. 쿼리 순서대로 K 번째로 큰 수를 Segment Tree에 쿼리를 날려서 찾고 이를 업데이트 해주는 문제였다. 쿼리는 Binary Search를 응용하면 된다. 처음에 쿼리 순서를 마음대로 바꿔도 되는가 싶어서 예제가 이해 안 되었는데, 나중에보니 순서가 고정이라서 쉽게 풀었던 문제. 2. BOJ 23757 : 아이들과 선물 상자 - S2 Priority Queue 문제. 위의 BOJ 23760을 푼 김에 같이 풀어본 문제였는데, K=1이 고정인 문제여서 PQ로 풀 수 있었다. PQ 공부하기 좋은 문제라 생..