문제문제 링크 풀이두 가지 풀이 방식을 소개해 보겠습니다.첫 번째 풀이는 흔히 생각할 수 있는 완전탐색으로 O(N²)의 풀이이고,두 번째 풀이는 단조 스택을 이용한 효율적인 풀이입니다.풀이 1현재(i)원소를 기준으로 남은 원소들(j)를 탐색하며 모두 비교한다.완전 탐색을 사용한 풀이이므로 아이디어는 생략하겠습니다.알고리즘 설명순서는 다음과 같습니다.모든 주식들이 떨어지지 않는다고 가정하에 ans 배열을 최대 날짜들로 초기화한다.price의 각 원소들을 비교하며 떨어진 날이 있을 경우에만 ans값을 업데이트한다. 구현 코드[python]def solution(price): ans = [len(price) - i - 1 for i in range(len(price))] for i in range(..

1. 문제 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 2. 풀이 아이디어 완전 탐색으로 로프의 모든 조합을 비교하면 부분집합의 개수를 구하는 문제와 같아진다. 이런 경우 2ⁿ의 가지수가 생긴다. 최대 N이 10⁵이므로 완전 탐색을 이용할 경우 무조건 시간 초과가 발생한다. DP를 사용하여 memoization한다고 해도 O(N²)의 시간 복잡도를 가지므로 제한 시간내에 통과할 수 없다. 따라서 더 빠른 풀이를 생각해야 한다. 그러..