https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 접근 방식 이중 for문을 통해 답을 구해보려 했지만, n =stack.top()) stack.pop()하는 식으로 관리된다. vector[i]>=stack.top()이라면 stack.top()은 vector[i]보다 크지도 않고, vector[i]보다 오른쪽에 있지도 않으므로 오큰수가 될 수 없다. n-1부터 0까지 탐색하는 i에 대해 stack을 관리하며 ans[i]를 채워주고 stack에 vector[..

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 접근 방식 냅색(knapsack) 알고리즘을 이용하여 접근했다. 일반적인 알고리즘에서의 w(무게)를 메모리, v(가치)를 비용으로 대응했다. 하지만 이렇게 냅색 알고리즘을 이용하게 되면 배열의 크기가 100*10,000,000이 훨씬 넘어가게 되므로 제한 조건을 어기게 된다. 풀이 방법 배열의 크기가 문제가 되므로 배열의 크기를 줄일 방법을 생각했다. 위에서 생각했던 방법은 dp[i][j] : i번째까지..

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 접근 방식 처음엔 괄호가 옳바르게 쓰였는지 확인하는 문제처럼 접근했다. 하지만 괄호 문제와는 다르게 폭발 문자열이 괄호처럼 한쌍으로 이루어진게 아니었기 때문에 괄호처럼 푸는 것은 어려울 것이라 생각하고 다른 방법을 생각해보았다. 그 다음으로 생각해본건 stack에 한 글자씩 넣으며 문자열이 있는지 검사하는 방법을 생각했다. 하지만 완전 탐색을 하게 되면 시간 복잡도가 O(n^2)이 ..