문제문제 링크 풀이두 가지 풀이 방식을 소개해 보겠습니다.첫 번째 풀이는 흔히 생각할 수 있는 완전탐색으로 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. monotone stackmonotone stack은 stack의 한 종류로 "단조로운 스택"이란 뜻이다. 우리말로 해석하자면 단순하게 증가하거나 감소하기만 하는 stack이다. 즉, 오름차순 또는 내림차순의 형태만 가지는 stack을 말한다.2. 활용데이터를 다루거나 알고리즘 문제를 푸는 과정에서 stack을 사용할 때 오름차순 또는 내림차순으로 stack을 유지해야하는 경우가 생긴다.

1. 문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 스택을 활용한 전형적인 괄호의 유효성을 검사하는 문제이다. 2. 풀이 문자열을 탐색하면서 stack이 비어있으면 추가한다. stack이 차있는 경우 stack.top와 문자를 비교하여 짝이 맞으면 stack.top을 제거하고 짝이 맞지 않으면 현재 문자를 stack에 추가한다. 3. 코드 #include #include #include using names..

1. 문제 https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net A와 B를 입력받고 같은 문자끼리 짝을 짓는 문제이다. 이때 아치형 곡선을 그어 서로의 곡선이 겹치지 않게 만든다 2. 풀이 아치형 곡선을 그어 서로의 곡선이 겹치지 않게 만든다는 말은 다음과 같이 바꿔 해석할 수 있다. 홀수 번째 입력받은 A를 ' ( '로, 짝수 번째 입력받은 A를 ' ) '로 치환하여 괄호쌍을 짝짓는 문제로도 볼 수 있다. 마찬가지로 B도 홀수 번째 입력받은 B를 ' [ '로..

깔끔하게 구현한 최종 코드는 맨 아래에 정리해 두었다. 1. 문제 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 괄호쌍의 유효성을 검사하는 문제이다. 2. 풀이 문자열을 탐색하며 열린 괄호( ' ( ' 또는 ' [ ' )가 닫힌 괄호( ' ) ' 또는 ' ] ' )와 만날 때마다 짝을 지어서 준다. 이 과정에서 자료구조의 스택(stack)을 활용하면 효율적으로 풀 수 있다. 방법 열린 괄호( ' ( ' 또는 ' [ ' )..