백준 7 문제 1. BOJ 14654 : 스테판 쿼리 - S5Implementation, Simulation 문제.주어진 기록대로 시뮬레이션을 돌려서 푸는 문제였다. 큐 같은걸로 시뮬레이션을 돌리는 문제.  2. BOJ 15084 : Treating Fractions Irrationally - S5Implementation, Math, Arithmetic 문제.나눗셈을 실제로 구현해서 돌리면서 0,9가 먼저 나오는지 아니면 주기성이 먼저 나오는지를 확인하는 문제였다.n 주기 최대 길이가 d일 것이므로... (n은 %d 값을 취하니깐 n 값은 0 ~ d-1 사이의 값이 된다.) 시간복잡도는 O(d)일 듯. 3. BOJ 14731 : 謎紛芥索紀 (Large) - S1Divide and Conquer, Mat..

백준 1 문제. 1. BOJ 14450 : Hoof, Paper, Scissors (Gold) - G3 DP 문제. DP 테이블을 dp[몇 번 손을 바뀌었는가][현재 낸 손 상태][몇 번째 소까지 상대 한 상태] 이런식으로 구상하고 테이블에 해당 상태에서 최대 이기는 횟수를 저장하도록 구성했다. 그렇게 DP 테이블을 구상하고 점화식을 세워보면 아래와 같은 경우들이 나온다. dp[k][i][j] = max( dp[k][i][j-1], dp[k-1][0][j-1], dp[k-1][1][j-1], dp[k-1][2][j-1] ) + (현재 낸 손이 j번째 소를 이길 수 있으면 1, 아니면 0) // 각각 대충 설명하자면, 손 상태를 안 바꿀 때, 손 상태를 바꿀 때 이렇게 생각할 수 있다. 까먹고 계속 안 올..

백준 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..