Algorithm

[알고리즘] 백준 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로 구현 마지막 배열을 순회..

[알고리즘] 백준 15353 큰수 // 문자열, 덧셈

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..

[알고리즘] 백준 14391 종이조각 // 비트마스킹, 1차원을 2차원으로 바꾸는힘

* 요약차원을 2차원으로 바꾸는힘i*m + j 암기!!!!i*m + j 공식이 어떻게 2차원 배열을 1차원으로 변환하는지 설명예를 들어 2x3 배열이 있다고 해보죠:1 2 34 5 6이 공식이 작동하는 방식을 단계별로 설명하겠습니다:각 행(i)마다 건너뛰어야 하는 개수:첫 번째 행(i=0): 0개 건너뜀 (0*m)두 번째 행(i=1): m개 건너뜀 (1*m)세 번째 행(i=2): 2m개 건너뜀 (2*m)열 위치(j)를 더하기:j=0: 첫 번째 열j=1: 두 번째 열j=2: 세 번째 열예시로 (1,2) 위치의 경우:i=1, j=2, m=3일 때1*3 + 2 = 5즉, 1차원 배열에서 5번 위치가 됨이렇게 변환하는 이유:비트마스크는 1차원으로만 동작2차원 위치를 1차원으로 고유하게 매핑해야 함각 위치가 겹치..

[알고리즘] 백준 2234 성곽 // 비트마스킹, vis의 값에 의미를 부여하라, i번째 비트끄기

https://www.acmicpc.net/problem/2234 * 풀이1connted component, 구역수 세기는 잘 풀었다.int dfs, 전체에대해 dfs돌리면서 cnt를 세면됨방문조건에 bit가 들어간다.dy,dx에 따라 동서남북을 체크하고 해당비트가 꺼져있으면 next로 이동한다.문제는 벽을하나씩 부스는것이 문제다.첫풀이벽을하나씩 부스면서 (i번째 bit를 끄면서) 똑같이 dfs를 돌리고, 원복하면 될거라고 생각했다.문제점이웃한 벽도 같이 부서줘야함매번 dfs 돌기전에 vis를 초기화 해줘야함현재는 벽제거후 그곳에서만 dfs호출, 벽을제거한후 모든 지점에서 dfs를 호출해야 완탐이됨//n^2 C 1 * 4(동서남북) 벽제거 memset(vis,0,sizeof(vis)); f..