Algorithm/스택

[틀림] 프로그래머스 큰수만들기 // 스택, 그리디

https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* 시도1min heap에 제거대상을 k 개선택vis에 기록앞에서부터 제거대상인지 보고, 제거예제3이 반례였음 * 풀이스택이용top 계속 pop 해주기, k--완료후, stack에 남은숫자가 정답엣지케이스, k가 남은경우는 stack에서 k개를 제거해줘야함.#include using namespace std;priority_queue ,greater> pq;vector v;int vis[10]; //제거대상stack s;string solutio..

[알고리즘] 백준 9935 문자열폭팔 // 폭팔은 스택, 끝문자만 비교하라

https://www.acmicpc.net/problem/9935*풀이1 1. 입력 받기: - 문자열 s (원본 문자열) - 문자열 t (폭발 문자열)2. 변수 초기화: - n = s의 길이 - len = t의 길이 - stk = 빈 스택 (문자 저장용)3. 원본 문자열 s 순회: for i = 0부터 n-1까지: - 현재 문자 s[i]를 스택에 push - 만약 스택의 top이 s[i]와 같고, 스택 크기가 len 이상이면: - tmp = 빈 문자열 (임시 저장용) - for j = 0부터 len-1까지: - tmp에 스택의 top을 추가 - 스택에서 pop - tmp를 뒤집음 ..

[알고리즘] 백준 6549 히스토그램 // 스택 심화, 암기..

https://www.acmicpc.net/problem/6549 * 풀이스택문제는 오름차순, 내림차순, 같은경우를 나눠생각이중에서 계산해야 되는 걸 골라야함!이문제는 내림차 일때, 기존의 막대들이 확장불가 ( 확정) -> 계산을 드가면됨.이때, 패딩을 0으로 줘서 마지막도 강제 내림차로만들고 i = n+1 까지 돌려서, 마지막에 자동계산토록 함 특이한점은 pop을 한후에 전전 막대의 idx 차이를 너비로 사용 #include using namespace std;typedef long long ll;ll n, arr[100000+4];// int main(){ ios_base::sync_with_stdio(0); cin.tie(0); while(1) { cin>>n; if(n..

[알고리즘] 백준 3015 오아시스 재결합 // 스택 심화

https://www.acmicpc.net/problem/3015* 풀이stack은 그림을 그려놓고 하면된다.크게 3가지경우로 생각하라.오름차순나보다 작은것들과 1쌍, pop내림차순위에서 나보다 작은것은 걸러졌음, stack에 원소가 있다면, 무조건 나보다 큰것이 보장. 나보다 큰애와 1쌍을 이룬다. 같은경우를 추가로 생각해야한다.pop은 하되, cnt(//현재 사람의 연속 카운트)를 저장해놓는 idea같은거 뒤에 작은게옴 -> 정답 1쌍 추가 (위와동일) , cnt=1로 리셋같은거 뒤에 큰게옴 -> 이전 막대기의 cnt를 더해줘야함, cnt=1로 리셋같은거 뒤에 같은게옴 -> 현재cnt를 이전 막대기의 cnt +1로 갱신, 스택에넣기cnt 시작을 1로하고, 오름차순일때 ret+1 하는대신 ret+직전c..

[알고리즘] 백준 15926 현욱은 괄호왕이야 // stack, 괄호검사 심화

https://www.acmicpc.net/problem/15926* 풀이1우측괄호를 만나면 cnt+=2 하는 풀이문제점중간에 ( 가 낑겨있는 경우 를 고려못함. #include using namespace std;typedef long long ll;int n,ret;stack stk;string s;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>s; int cnt=0; for(auto c : s) { // cout * 풀이2상태를 배열에 저장함stack에 index를 push 우측괄호를 만난경우, 현재와 top의 index의 배열값을 1로 저장d[i] = d[stk.top()] = 1로 구현 마지막 배열을 순회..

[알고리즘] 백준 1725 히스토그램 // 스택

https://www.acmicpc.net/problem/1725* 풀이히스토그램 문제를 직관적으로 이해하는 방법은 이렇습니다:"뻗어나가기" 관점:각 막대는 자신의 높이를 유지하면서 양옆으로 최대한 뻗어나가려고 합니다예를 들어 높이 4인 막대는 "높이 4를 유지하면서 얼마나 넓은 직사각형을 만들 수 있을까?"를 생각하는 것입니다"막히는 지점" 찾기:뻗어나가다가 자신보다 낮은 높이를 만나면 거기서 멈춰야 합니다이것이 바로 우리가 스택에서 pop을 하는 시점입니다스택의 역할:스택은 "아직 더 뻗어나갈 수 있는 막대들"의 모음입니다새로운 막대를 만났을 때, 이 막대보다 높은 것들은 더 이상 뻗어나갈 수 없으므로 pop하고 계산합니다이렇게 생각하면 너비 계산도 이해하기 쉽습니다:스택이 비었다는 것은 "왼쪽으로 ..

[알고리즘] 백준 6198 옥상정원꾸미기 // 스택, 역발상, 자기중심적 사고, st.size() 도 의미가 있다.

* 풀이유사문제들의 풀이의 공통점계산이 끝난 원소를 바로 while문으로 pop 하는 특징(top 나보다 작은 top -> 나를 볼수없음 -> pop 남은 스택의 원소갯수 = 나를 볼수있는 빌딩의 갯수!예시 낚시예시는 관리인 시점에서 탐색중인 current가 아니라 탐색이 끝난 element 관점으로 서술되어있다.이러면, 상태관리가 어려워진다.문제 해결에서 "현재 위치(current)"를 중심으로 생각하는 것은 매우 좋은 접근 방법이런 관점이 유용한 이유는: 1. 문제를 더 작은 단위로 나눌 수 있음    - "전체 빌딩이 몇 개를 볼 수 있는가?" 대신    - "현재 빌딩(나)에 대해서는 어떤 일이 일어나는가?" 2. 상태 관리가 쉬워짐    - 현재 시점에서 필요한 정보만 유지    - 이 문제에..

[알고리즘] 백준 17299 오등큰수 // 스택

https://www.acmicpc.net/problem/17299* 풀이오큰수의 유사문제stack을 이용해서 오큰수를 찾은 애들을 지워버린다. => 시간복잡도를 줄임F[cur]이 F[top]보다  더큰경우 -> cur이 오큰수임, 기록, pop, 반복push(cur)남아있는 애들은 오큰수가 없는애임 -> -1 기록* 전체코드#include using namespace std;typedef long long ll;ll n;vector arr;stack> s;ll F[1000000+4],ans[1000000+4];ll ret;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n ; for (int i = 0; i > tmp;..