kthng

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