너무 뻔한 이야기 일 수도 있지만, 올해 들어서 이해했기에 글로 남겨봅니다. PS를 꾸준히 풀다가 보면, 히스토그램이라는 문제를 한 번쯤은 들어봤을 수 있습니다. 플레 5 기준으로 사실상 제일 많이 풀린 문제이기도 하고 종만북, 바킹독 문제 모음집 등에서도 볼 수 있는 만큼 매우 유명한 문제이며 풀이도 여러 방법이 있습니다.  분할 정복, 세그먼트 트리 등등의 여러 방법도 있지만 그래도 제일 유명한 풀이는 스택 풀이입니다. Monotone Stack 테크닉을 통해서 스택에 필요한 정보들만 남겨서 푸는 방법인데, 이렇게 풀면 O(N)으로 풀 수 있다고 알려져 있습니다. 그런데, 저는 이 문제를 풀면서 왜 이게 O(N)인지가 궁금했습니다. 일단 제 구현 상에서 핵심 아이디어 코드만 따서 보면 이렇게 됩니다...

백준 4 문제. 1. BOJ 1256 : 사전 - G2DP + Combinatorics 문제. 가능한 모든 문자열의 개수는 N+M C M 이 된다. 그러면 현재까지 i개의 a와 j개의 z를 사용했다면 가능한 나머지 문자열들의 개수는 N+M-i-j C M-j가 된다. 이를 활용한다면 현재 자리에 a를 박았을 때 가능한 나머지 문자열들의 개수가 K 미만이라면 z를 꼭 사용하도록 구현해서 풀면 된다. 따라서, 모든 이항 계수를 DP 테이블로써 미리 계산을 해두고 현재까지 i개의 a와 j개의 z를 사용한 상태에서 a를 하나 더 박을 시 즉, N+M-i-j-1 C M-j가 K 미만이라면 z를 사용, 아니라면 a를 사용해서 정답을 채워 나가면 된다. 이렇게 말로만 표현하니깐 뭔가 애매한듯... 그래도 G2 DP를 ..

백준 5문제. 1. BOJ 31713 : Double Up - S4 Math + Ad hoc + Hash map 문제. a가 홀수라면, 2^k * a 형태로 나타낼 수 있는 모든 수들끼리는 같은 수로 만들 수가 있다.이를 활용해서 모든 수를 2로 나눌 수 있을 만큼 나눈다음 같은 수들끼리 묶어보면 가장 많이 등장하는 수의 최대 등장 횟수를 알 수 있다. 2. BOJ 3644 : 그래프 매칭 - G3DP 문제. n = 3, 4, 5, 6일 때의 경우의 수를 보니 C_n = C_n-1 + C_n-2로 피보나치 점화식 형태로 표현됨을 파악했다.그래서 그대로 대입해보니 정답이 나왔다;;; 나중에 알아보니 이렇게 초항이 0,1이 아닌 수에서 피보나치 점화식 형태로 표현되는 수열을 뤼카 수열이라고 한다 하더라. 문..

백준 4 문제. 1. BOJ 20052 : 괄호 문자열 ? - P4 Prefix Sum + Segment Tree 문제. '('를 +1, ')'를 -1로 치환해서 푸는 문제인데, 옳은 문자열이라면 저렇게 치환했을 때의 총합은 0이어야 한다. 또한, 중간에 누적합의 결과가 음수가 나온다면 ')'의 개수가 더 많아지는 경우가 생기므로 옳은 문자열이 될 수 없다. 따라서, Prefix Sum을 미리 구하고 이에 대해서 Segment Tree를 생성하면 Min query로 중간 누적합 결과가 음수가 나오는지 판별도 쉽게 가능하다. Prefix Sum을 이미 구했으니 총합이 0이 되는지의 여부도 쉽게 파악이 가능하다. 오랜만에 풀어본 세그 문제. 2. BOJ 26093 : 고양이 목에 리본 달기 - G3 DP 문..

백준 6 문제. 1. BOJ 22251 : 빌런 호석 - G5 Implementation + Bruteforcing 문제. 두 숫자간에 7개의 표시등 중에서 몇 개나 차이가 나는지를 미리 계산을 해둔다. 이후에 1 ~ N까지 숫자에 대해서 X와 표시등의 차이가 1개 이상 P개 이하인 숫자들을 모두 찾아보면 된다. 표시등 개수의 차이는 각각 자리 별로 비교를 해보면 되니, 총 시간복잡도는 O(NK)가 된다. 2. BOJ 16876 : 재미있는 숫자 게임 - G2 Game Theory + DP 문제. M번째 턴이 끝난 순간에 결과가 0~N이라면 cubelover, N+1 ~ 9999 이면 koosaga가 이긴게 된다. 그렇다면 M번째 턴이 짝수면 cubelover, 홀수면 koosaga의 턴일텐데, cube..

백준 3 문제. 1. BOJ 16953 : A → B - S2 BFS 문제. 각 숫자를 노드로 치환해서 BFS로 풀어줄 수 있다. 숨바꼭질 시리즈와 비슷한 문제. 다만, 숫자 범위가 매우 커질 수 있으므로 map은 필수인 것 같다. 다른 방법으로는 그냥 그리디로 B에서 A로 줄여나가는 방법도 있다 한다. (아마 2의 배수면 2로 계속 나눠주고, 끝이 1이면 1 빼고 10으로 나눠주고를 반복하는게 아닐까...?) 2. BOJ 31738 : 매우 어려운 문제 - ? Math 문제. N이 M이상이면 N!은 N * (N-1) * ... * M * ... 이렇게 계산이 되니 M의 배수가 된다. 따라서, N >= M이면 답은 항상 0이 된다. N < M이면 그냥 실제 팩토리얼을 계산하면 된다. (M의 범위가 10^..