kthng

boj 1520 : 내리막 길 https://www.acmicpc.net/problem/1520 메모이제이션을 적용한 재귀함수로 문제를 해결할 수 있다. 1. f(1,1) = 12. f(i,j) = f(i,j - 1) + f(i, j + 1) + f(i - 1,j) + f(i + 1,j) 만약 세준이가 평지도 이동하였다면 재귀에 loop가 생겨 이 방법으로는 불가능하다.세준이가 내리막길로만 이동하기 때문에 가능하다.

boj 1935 : 후위표기식2 https://www.acmicpc.net/problem/1935 자료구조시간에 단골로 나올 법한 문제이다. 1. 피연산자가 나오면 stack에 push,2. 연산자가 나오면 stack의 위에 2개를 연산한 후 push 위의 과정을 반복한다. ABC*+DE/- 와 같은 후위표기식을 우선 저장해놓고, 아스키코드 배열에 정수값을 입력받은 후 stack에서는 value만으로 모든 연산을 진행하였다.

boj 1978 : 소수 찾기 https://www.acmicpc.net/problem/1978 에라토스테레스의 체를 이용하여 1000 이하의 자연수 중의 소수를 구하고,주어진 수들 중 소수의 갯수를 센다. for i = 2 ; i * i

boj 1003 : 피보나치 함수 https://www.acmicpc.net/problem/1003 introduction to dynamic programming이라는 책이 있다면 앞부분에 수록될만한 문제이다. 1. fibonacci[n][0] : fibonacci(n)이 0을 호출하는 횟수2. fibonacci[n][1] : fibonacci(n)이 1을 호출하는 횟수 위와같이 두면, 3. fibonacci[n][0] = fibonacci[n-1][0] + fibonacci[n-2][0]4. fibonacci[n][1] = fibonacci[n-1][1] + fibonacci[n-2][1]

boj 1874 : 스택 수열 https://www.acmicpc.net/problem/1874 스택수열은 큐와 스택으로 해결된다.1. Ai : i번째 문자2. queue : 1~N까지 순서대로 담켜있다.3. stack : stack의 top은 0.- 여기까지가 전처리. 1. Ai가 queue의 front보다 같거나 작을 때까지 queue를 pop하고 stack에 push.;2. Ai가 stack의 top과 같으면 pop.3. i++ 1,2,3의 과정을 반복하면 답을 구할 수 있다. 올바르지 않은 수열은 어떻게 구할 수 있을까?stack의 top보다 Ai가 작다면 만들어질 수 없는 스택수열이다. stack의 top보다 Ai가 작으면 stack의 pop 과정이 이루어진 후에 Ai를 pop할 수 있는데, 이..

boj 9935 : EKSPLOZIJA(문자열 폭발) https://www.acmicpc.net/problem/9935 시간초과를 저격한 문제.1. 폭파문자가 있으면 폭파문자를 제거한다.2. 폭파문자가 없을 때까지 1의 과정을 반복한다 위의 방법으로 하면 시간초과.다른방법을 생각해보아야 한다. stack을 통해 구현하면 보다 편하다.1. stack에 문자열을 담아간다.2. stack의 윗부분이 bomb와 일치하면 bomb부분을 제거한다. 위의 방법으로 해결하면 문제가 풀린다.stack의 윗부분이 bomb와 일치하는지 확인하는 과정도 bomb size의 만큼의 시간복잡도가 필요한데, 이 부분은 character 말고 int도 함께 stack에 쌓아주는 방법으로 접근하면 보다 빠르게 풀 수 있다. stack..

boj 2624 : 동전 바꿔주기 https://www.acmicpc.net/problem/2624 이 문제 또한 전형적인 DP문제이다.나에게는 조금 생소했던... 하지만 이것저것 검색해보니 이문제 또한 전형적인 DP문제라는 것을 알 수 있었다. 이 문제가 만약 동전의 갯수가 주어지지 않았다면 바로 DP로 접근해서 풀었겠지만, 동전의 갯수가 주어져 있으면 DP로 접근하면 해결할 수 없을 것만 같다.시간복잡도가 엄청 높기 때문이다. (약 T*k*n) 그렇다면 그냥 시간초과 나는게 아닌가? 일단은 풀린다. 방법은 i번째의 동전으로 table을 채워가는 것. 초기 세팅은 0원의 경우의 수를 1로 두고 table을 채운다. 1. a[cost][i] i 번째 동전까지의 cost의 경우의 수2. Pi, ni : i..

boj 1149 : RGB거리 https://www.acmicpc.net/problem/1149 DP로 해결한다. 1. dp[i][j] : i번째의 집을 j로 칠했을 때 1~i번째 집까지의 최소비용2. dp[i + 1][j] = min{ dp[i][k] } + cost[i + 1][j]; ( j != k )

boj 9657 : 돌 게임 3 https://www.acmicpc.net/problem/9657 재미있는 문제다.어려워보이지만 굉장히 간단한 코드를 작성할 수 있다. 위의 표를보면, 돌의 갯수가 2개일 때는 cy가 이긴다.7번째와 9번째도 cy가 이긴다.공통점은 a[i - 4] , a[i - 3], a[i - 1]이 모두 sk가 이길 경우 a[i] 는 cy가 이긴다는 것.왜그럴까?cy가 이긴다는 것은 후수가 이긴다는 얘기다. 마찬가지로 sk가 이기는 경우는 선수가 이긴다는 것이다.i 개일 때 sk가 이기려면, sk가 후수를 내주었을 때, 즉 i - 4, i -3, i - 1 셋중 하나가 후수가 무조건 이기는 경우가 있어야만 가능하다. 8의 경우를 보면 8 - 4 = 4 : sk, 8 - 3 = 5: s..

boj 11052 : 붕어빵 판매하기 https://www.acmicpc.net/problem/11052 DP로 해결할 수 있는 문제이다.1. dp[i] : i개를 판매할 때 최대의 가격2. a[i] : i개 세트의 가격위와 같이 두면, 3. dp[i] = max{ dp[i - k] + a[k] } ( k = 1 ~ i - 1 ) 위와같이 점화식을 구성하여 해결한다.