목록Algorithm (427)
Mini
[알고리즘] 백준 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를 뒤집음 ..
[알고리즘] 백준 2109 순회강연 // 그리디 , pq, 최대값은 최소를 적게 or 최대를 많게
https://www.acmicpc.net/problem/2109* 풀이1day기준 오름차해서 각각 day에서 비싼거 뽑으면 될듯?참고) pq에 줄 cmp는 struct로 줘야함struct cmp { bool operator()(const pair& p1, const pair& p2) { return p1.first * 풀이2day기준 오름차, 내림차 -> 오름차 선택최대 = 최소를 적게 or 최대를 많게 -> 최소를 적게 선택pq.size에 day의미 부여greater(최소힙) => 돈 적은거 pop#include using namespace std;typedef long long ll;int n,ret;vector> v;priority_queue,greater> pq; //최소힙i..
[알고리즘] 백준 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로 구현 마지막 배열을 순회..
https://www.acmicpc.net/problem/15353* 요약long long을 벗어난 덧셈은 문자열로 받아서 뒤 한자리씩 더하라, carry 처리 철저히.숫자를 문자로 바꾸려면 + '0' 하면됨. // 1 + '0' == '1'string에도 pop back 쓸수있음 * 풀이1이 코드의 알고리즘을 단계별로 요약하면:자릿수 맞추기 (Leading Zero)두 수의 길이를 비교짧은 수의 앞에 0을 붙여서 길이를 같게 만듦예: "123"과 "45" → "123"과 "045"덧셈 수행 (Right to Left)오른쪽(일의 자리)부터 왼쪽으로 진행각 자리에서:같은 자리의 두 숫자를 더함이전 자리에서 올림(carry)이 있으면 1 더함합이 10 이상이면 carry=1로 설정현재 자리의 값(sum%1..
[알고리즘] 백준 5430 AC // 덱, 구현
https://www.acmicpc.net/problem/5430 * 풀이1#include using namespace std; int t;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >>t; while(t--) { string s1,s2; int n; cin>>s1>>n>>s2; deque d; if(s2!="[]") { s2 = s2.substr(1,s2.size()-2); // [, ] 날리기 string buf=""; for(auto c : s2) { if(c==',') { d...
[알고리즘] 백준 13244 Tree // tree의 조건 암기
https://www.acmicpc.net/problem/13244* Tree의 조건노드수 == 간선수+1 이어야함모두 연결되어 있어야함 // connected component 는 int dfs 결과가 n과 같아야함 * 전체코드#include using namespace std; int t,n,m, vis[1004];vector adj[1004];int dfs(int here) { vis[here]=1; int ret=1; for(auto nxt : adj[here]) { if(vis[nxt]) continue; ret += dfs(nxt); } return ret; }int main(){ ios_base::sync_with_stdio(0); cin.t..