pinevienna blog

알파벳을 숫자로 암호화한 뒤, 다시 알파벳으로 복호화 할 때 발생할 수 있는 모든 경우의 수를 구하는 문제 암호는 두 가지 중 하나이다. 1. 한 자릿수 암호 : 1(A) ~ 9(I) 2. 두 자릿수 암호 : 10(J) ~ 26(Z) 점화식을 세워보자 case1 : 한 자리만 복호화 하는 경우 dp[N] = dp[N] + dp[N-1] case2 : 두 자리를 복호화 하는 경우 dp[N] = dp[N] + dp[N-2] 단, 맨 앞 문자는 두 자리로 해석할 수 없으며 && 두 자리 중 앞자리가 0이라면 해석할 수 없다. 이를 해결하기 위해 입력받은 문자열 앞에 0을 붙여줬고, if문의 조건을 아래와 같이 정해줬다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20..

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제 타일 채우기 아우 지겨워~ 하고 풀었다가 멍청한 나한테 질렸다.. 모든 예외들을 잘 고려해줘야 한다. 1. N이 홀수일 때 해보면 알겠지만 3x1, 3x3, 3x5 ··· N이 홀수일 땐 채울 수 없다. 2. 3x2 3x2의 경우엔 이렇게 세 가지 모양으로 채울 수 있다. 각각을 A, B, C라 칭하겠음! 3. 3x4 1번에 A, B, C + 2번에 A, B, C를 조합하여 채우는 형태로 생각할 수 있다 이러면 3x3=9, 총 9개의 형태로 채울 수 있다!! 하지만 답은 9가 아니다. 3x4부터 예외가 발생한다... 단순히 A, B, C를 조합해서는 만들 수 없는 모양으로, 3x4부터 이런 형태가 등장한다. 이런 경우를 '..

AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 문제 함수와, 배열에 들어있는 수의 개수, 배열이 주어졌을 때 결과를 구하면 된다! RDD 4 [1,2,3,4] 이렇게 입력되면 [2,1]을 출력한다 문제 자체는 쉽다!! 근데 시간초과를 조심해야 한다 R이 순서를 뒤집는 함수라고 했는데, 진짜 뒤집으려 하면 끝도 없음 내가 또 그 끝도 없는걸 한 번 했었지..^^! 덱의 장점을 살려서, R을 홀수번 수행하면 역방향으로 출력하게..

큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 큐의 크기 N, 뽑아내려고 하는 수의 개수 M 뽑아내려고 하는 수의 위치가 순서대로 주어졌을 때 2번, 3번 연산의 최솟값을 출력하는 문제 덱을 이용하면 쉽다! 양방향으로 뺐다 넣었다.. 최솟값을 출력하라고 했으니 뽑아내려고 하는 수의 위치가 덱의 앞쪽이면 front의 원소를 뒤로 보내는게 빠르고,..

프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 쉬운 문제지만 비효율적으로 풀면 실행 시간만 반나절이다 priority_queue를 사용하여 풀 수 있음 priority_queue는 큐 안의 원소를 내림차순으로 정렬하기 때문에 입력받은 값과 priority_queue의 top을 비교하면 됨 입력받은 문서의 중요도를 저장할 queue는 pair로 선언하여 first에는 중요도를 second에는 몇 번째 입력값인지 저장해준다 queue.front().first ..