문제풀이 (2) 썸네일형 리스트형 스택 문제 풀이2(16909, 카드 구매하기3)[Stack PS] 스택 가장 큰 특징 : LIFO 마지막에 넣은 게 가장 먼저 나온다 문제를 풀이하면서 가장 중요한 건 스택을 어떤 용도로 사용하고. 어떤 경우에 push를 하고, 어떤 경우에 pop을 해야 할까? 를 생각해야 된다. 문제풀이 11052 - 카드 구매하기 (실버1) : https://www.acmicpc.net/problem/11052 풀이 : N개의 카드를 구매하기 위해 지불할 수 있는 금액의 최댓값을 구하는 문제. 전형적인 dp(다이나믹 프로그래밍) 문제이며, N의 범위가 10^3으로 시간복잡도가 O(N^2)일 때 10^6으로 제한시간 내에 충분히 가능하다. 가장 쉬운 방법으로는 가능한 모든 경우의 수를 구하여 값 중 최댓값을 구하는 것이다. 하지만 같은 카드를 구매하는 경우에서 굳이 적은 비용을 낼 .. 스택 중간난이도 문제 풀이(Stack PS) 스택 가장 큰 특징 : LIFO 마지막에 넣은 게 가장 먼저 나온다 문제를 풀이하면서 가장 중요한 건 스택을 어떤 용도로 사용하고. 어떤 경우에 push를 하고, 어떤 경우에 pop을 해야 할까? 를 생각해야 된다. 문제풀이 9935 문자열 폭팔 : https://www.acmicpc.net/problem/9935 가장 쉽게 생각하는 방법 : 배열에 문자를 저장해서 폭발이 없을 때까지 포문 돌리기 O(N*N), N = 백만이므로 불가능 stack 사용 -> 문자열이 폭파하였을 때, 폭파 가능한 이전 문자열을 O(1)만에 찾을 수 있다. (서로 다른 문자 이므로 가능, 중복이 될 경우 첫 번째 문자인지 마지막 문자인지 구별이 안됨에 따라서 스택 알고리즘 적용이 어렵다.) 폭파 대상을 저장하는 stack 1.. 이전 1 다음
