본문 바로가기

algorithm

 (69)
백준 6549번 히스토그램에서 가장 큰 직사각형 https://www.acmicpc.net/problem/6549 아이디어:1. 오름차순을 유지하는 모노톤 스택2. 스택에는 pair 저장3. 결과는 long long형으로 저장 (중간에 int에서 long long으로 변환하거나 stack에 pair 저장)4. 스택에서 pop()할 때마다 top()으로 만들 수 있는 직사각형의 넓이 계산(i - S.top().second) * S.top().first(현재 사각형 위치) - (S.top() 사각형의 최초 등장 위치)5. 마지막에 스택을 비우면서 남은 스택 요소들로 만들 수 있는 직사각형의 넓이 계산(n - S.top().second) * S.top().first(마지막 위치) - (S.top() 사각형의 최초 등장 위치) S.top()은 항상 스택 내 ..
백준 3015번 오아시스 재결합 https://www.acmicpc.net/problem/3015 아이디어:1. 스택의 내림차순 유지2. 같은 키에 대한 처리가 핵심3. 스택에 들어가는 값은 { tmp, cnt } 로 cnt는 "스택 내에서 같은 키를 가진 사람 수"4. 같은 키 n명에 대해 등차수열의 합 n*(n+1)/2 생각해보면 정답 변수 ans는 int형이 아닌 long long형으로 정의해야한다. 추가 예제:7 2 4 1 2 2 5 1 (정답: 10)5 5 5 2 2 5 (정답: 8) 스택에 내림차순 적용하는 방식은 똑같다.cnt는 기본 1이다.내림차순 유지를 위해 pop()을 할 때, (tmp 정답 ans에 top()의 cnt (키 같은 사람 수)를 더해준다.만약 새로 들어온 수와 top()의 키가 같다면 cnt는 그만큼 더..
백준 17298번 오큰수 https://www.acmicpc.net/problem/17298 스택 1개, 배열 1개 쓰는 풀이 아이디어:1. 스택에 pair 저장2. 값을 저장하는 배열 arr[1000001]3. 일단 비어있으면 push, skip4. 2493번 탑, 6198번 옥상 정원 꾸미기 문제처럼 스택의 내림차순 유지 (ex. 5 → 2 → 1(top))5. S.top 보다 입력이 크면 입력보다 작거나 같을 때까지 모두 arr[S.top의 인덱스]에 tmp를 저장 (오큰수 기록)하고 pop6. 스택에 입력 push7. arr[스택에 남아있는 값들의 인덱스]에 모두 -1 저장 #include #include using namespace std;int arr[1000001];int main() { ios::sync_with_..
백준 6198번 옥상 정원 꾸미기 - 모노톤 스택 https://www.acmicpc.net/problem/6198 https://www.acmicpc.net/problem/17298의 하위호환 아이디어:1. 모노톤 스택 사용스택에는 2가지 문제 유형이 있는데, 첫번째는 괄호 지우는 것처럼 자연스러운 패턴을 찾는 것2번째는 6198번과 모노톤 스택처럼 스택 내부의 정렬(?)이다.https://www.youtube.com/watch?v=Z4R582bn7B82. 목표는 빌딩을 볼 수 있는 횟수의 총합3. 스택의 입력은 빌딩의 높이인데, 이걸 내림차순으로 정렬해서 더 낮은 값이 있으면 pop하는 로직이 필요하다.4. 첫 빌딩 높이는 그냥 push5. 다음 들어오는 빌딩부터만약, 스택 top이 입력 빌딩보다 작으면 pop하고 크거나 같으면 정답에 더한 뒤, 스..
백준 2504번 괄호의 값 https://www.acmicpc.net/problem/2504 풀이 참조: [백준 BOJ / C++] 2504번: 괄호의 값 아이디어:1. 스택과 이전 글자 사용2. 최종 결과 ans(초기값 0)와 중간 계산값 tmp (초기값 1) 사용3. 분배 법칙 활용X(A+B) = AX + BX4. 들어오는 ( 에 대해 미리 2를 곱하고5. 들어오는 ) 에 대해5-1. 스택이 비었거나 이전 문자가 ( 가 아니라면0 출력하며 종료5-2. 이전 문자가 ( 이면ans에 tmp를 더하고 tmp는 2로 나누기5-3. 이전 문자가 ( 이 아니면tmp를 2로 나누기6. [ 와 ] 도 똑같이 적용 ) 와 ] 에서만 계산하는게 아니라( 와 [ 에서도 곱셈을 해주면서 ) 와 ]에서 tmp를 더하고 나눗셈으로 tmp를 풀어주는 과..

티스토리툴바