목록Algorithm/스택 (18)
Mini
[알고리즘] 백준 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;..
[알고리즘] 백준 17298 오큰수 // 스택으로 탐색대상 줄이기
* 완탐풀이정방향으로 탐색하면서 나보다 큰 수를 찾는다.시간복잡도 : N(N-1)/2 -> 불가능역병향으로 탐색하면?5 입장에서 좌측을 탐색한다.3의 오큰수는 나(5)다.2입장에서 나를 오큰수로 가질만한게 있나? -> 없음 -> pass이때, 3의 오큰수는 이미 정해져있다. -> 탐색할 필요가 없었다!1입장에서도 나를 오큰수로 가질것이 없다8입장에서는 3을 볼필요가 없다.(이미 오큰수가 있음)오큰수가 없는것중 나(8)를 오큰수로 가질수있음 --> 내가 오큰수다.10입장에서 8의 오큰수는 나다.len만큼 다돌았는데 오큰수가 없으면, 오큰수가 없는것이다.하지만, 시간복잡도는 정방향과 비슷하다.시간복잡도가 많은원인 : 이미 오큰수가 있는 숫자(3 같은)를 탐색하는 비용이 크다.개선 : stack에 넣고, 오큰..
https://school.programmers.co.kr/learn/courses/30/lessons/64061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 의사코드 1.1. 0 0 0 0 0 0 0 1 0 3 0 2 5 0 1 4 2 4 4 2 3 5 1 3 1 일때, vector에 4,3 / 2,5,2 / 1,5,4,4,1 ... 이렇게 세로로 담는다. 2.2 바구니(s)와 현재탐색중인 stack(v[i-1])의 top을 비교하면서 같으면 s.pop && answer++ 다르면 s.push한다. 2. 전체코드 #include using nam..
https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net *의사코드 *요약 이해가잘안갔던 문제이다. ( ( ) 이면 num : 2 4 2 이고 sum에 4를 더해준다. 첫닫는과호를 만났을때 바깥괄호의 영향까지 포함해서 계산을 마치고 sum을 갱신하고, 이후 좌측괄호의 영향이 안가도록 num을 나눠준다 그리디 분류에도 속할것 같다. *전체코드 // Authored by : std-freejia // Co-authored by : Baaaaaaaaaa..
백준 10799 c++ // 스택응용 idea, 남은'('의 갯수를 활용하라
https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net * 의사코드 #include using namespace std; int n,ret; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); stack s; string str; cin >> str; for (int i = 0; i < str.size();++i) { if (str[i] == '(') { s.push('('); } else {..
https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net *괄호검사 알고리즘 왼괄호 ->push 오른괄호->빈스택인경우 -> wrong // -> 올바른짝이있는경우 ->pop ->안맞는짝인경우 ->wrong ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 작업후 (왼괄호가 )남아있는경우 ->wrong ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 유효하면 yes 아니면 no출력 * 내코드 #include using namespace std; string ..
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net *의사코드 및 전체코드 #include using namespace std; int n; stack s;//높이,인덱스 int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); /** * 1. 맨왼쪽에 {100,000,001 / idx 0} 의 탑이있다고 가정 => 0을 리턴하도록 * 2. 나보다 작은 타워는 쓸모없음 -> 모두 p..