문제문제 링크 풀이두 가지 풀이 방식을 소개해 보겠습니다.첫 번째 풀이는 흔히 생각할 수 있는 완전탐색으로 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. 스택의 의미와 특징스택이란?마지막으로 들어온 원소가 제일 먼저 나가는 자료구조더 이해하기 쉽게 풀어보면 한쪽 입구만 뚫린 터널이라고 생각할 수 있다. 이 구조는 데이터들이 한쪽으로만 들어갔다가 나오며 무언가 쌓는 모양을 생각할 수 있다. 이러한 형태 때문에 "쌓다"라는 의미에서 스택(stack)으로 불린다. 스택의 특징LIFO(Last In First Out)의 구조를 가진다.원소의 추가/제거/확인이 모두 O(1)이다.최상단의 원소에만..

1. 문제 https://www.acmicpc.net/problem/28323 28323번: 불안정한 수열 $N$개의 자연수가 좌우 일렬로 놓여 있다. 왼쪽에서 $i$ ($1 \le i \le N$)번째에 놓여 있는 자연수는 $A_i$다. 여러분은 이 중 몇 개의 자연수를 원하는 만큼 고를 수 있다. 단, 아무 자연수도 고르지 않 www.acmicpc.net 2023년 정보올림피아드 초등부 1번 문제이다. 2. 풀이 문제에서 정의한 불안정안 수열이란 이웃한 두 숫자의 합이 모두 홀수인 수열을 말한다. 자연수의 배열이 주어졌을 때 최대 몇개의 숫자로 불안정한 수열을 만들 수 있는지 구하는 문제이다. 불안정한(이웃한 두 수의 합이 모두 홀수인) 수열을 만들려면 수열을 탐색하며 이웃한 두 수의 합이 짝수가 되..

1. 괄호쌍의 유효성 괄호쌍의 유효성이란 열린괄호' ( '와 닫힌 괄호' ) '가 서로 순서와 짝이 맞게 이루어져있는지 판단해주는 방법이다. 일반적으로 괄호쌍을 다룰 때에 소괄호' ( '가 주로 판단대상이지만 중괄호' { '나 대괄호' [ '로 확장하여 판단하기도 한다. 괄호쌍이 유효한 경우 ( ) ( ( ) ) ( [ ] ) 괄호쌍이 유효하지 않은 경우 ) ( { ( } ) { } ) 2. stack을 이용한 괄호쌍 유효성 검사하기 알고리즘 그러면 어떻게 이를 판단할 수 있을까? 위에서 괄호쌍이 유요하지 않은 경우는 괄호의 짝이나 순서 또는 개수가 맞지 않는다는 것을 확인할 수 있다. 데이터가 입력되었을 때 현재까지 입력된 상태를 유지하고 제일 마지막에 입력된 값과 비교해야 함을 느낄 수 있다. 따라서..

https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net #define F first #define S second #include #include using namespace std; stack sta; int main(void) { cin.tie(0); ios_base::sync_with_stdio(NULL); long long int max, s, h; int n; while (1) { ci..

1. 재귀 함수란? 한자로 풀어서 해석하면 다시 "재(再)" 돌아올 "귀(歸)", 말 그대로 다시 돌아오다 라는 뜻이다. 프로그래밍의 관점에서 재귀란 "함수 자신을 다시 호출하다"라는 의미이다. 2. 재귀함수의 쓰임 재귀함수는 기본적으로 현재의 condition을 유지한 상태로 전의 작업과 비슷한 행동을 할 때 매우 유용한 알고리즘이다. 이러한 재귀함수의 특성때문에 stack, 분할정복 등의 많은 문제에서 활용되곤 한다. 다음은 재귀함수로 간단하게 구현할 수 있는 문제이다. https://wondrous-developer.tistory.com/1 [백준 17609] 회문 (C++) 처음 고민했던 사고과정과 이후 정답풀이를 같이 정리해 놓았다. 1. 문제 https://www.acmicpc.net/prob..

1. monotone stackmonotone stack은 stack의 한 종류로 "단조로운 스택"이란 뜻이다. 우리말로 해석하자면 단순하게 증가하거나 감소하기만 하는 stack이다. 즉, 오름차순 또는 내림차순의 형태만 가지는 stack을 말한다.2. 활용데이터를 다루거나 알고리즘 문제를 푸는 과정에서 stack을 사용할 때 오름차순 또는 내림차순으로 stack을 유지해야하는 경우가 생긴다.

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