Mini

https://www.acmicpc.net/problem/17471* 행동영역dfs 구역체크는 노드1곳에서만 시작해라 * 오답정리이전에 dfs를 모든노드에서 하고있었음그런데, 연결확인을 위해서는 첫노드에서 시작하는것만으로 충분함!필요없이 반례) 1-2 / 3-4 인경우1,2,3이 구역1에 묶일때, visit 체크를 맨위에서 해주기때문에 {1,2,3}은 한구역이라고 잘못판단함.애초에 구역 1에서 dfs를 했으면 이런 문제가 없음! * 의사코드전체 코드의 흐름을 단계별로 정리: 1. **입력 처리**    - N개의 구역과 각 구역의 인구수 입력    - 각 구역별로 인접한 구역 정보를 입력받아 양방향 그래프 생성 2. **모든 가능한 분할 시도** (비트마스킹 활용)    - 1부터 2^N-1까지 모든 경..

https://www.acmicpc.net/problem/1285* 행동영역상태가 2개면 비트마스킹을 생각하라* 풀이일단 시간복잡도가 2^40 아닌가? -> 각행, 각열을 완탐but, 행만 완탐후, 열은 최적해가 정해져있음 -> 직접뒤집을필요x, 상태가 2개이므로 절반보다 크면 뒤집고 아니면 안뒤집으면 됨 -> 2^20핵심은 동전의 상태가 2개-> 0과 1 비트 숫자 1개로 상태를 저장하는 것임배열에 넣는경우, 뒤집는 연산 for(~~~) 을 직접해야함.a[i] : 행 i 의 상태 저장재귀함수go(here) : here번째 행의 동전을 뒤집은경우, 안뒤집은경우동전을 뒤집는 연산을 ~ 으로 구현백트래킹으로 완전탐색리턴조건n이 다찼을때,각 열 (|) 을 탐색 할 변수 i : 1, 2, 4, 8 ... // ..

* 풀이11, 11, 111, ....을 str로 구함 -> 숫자 * 10 +1 으로 대체가능예시에서 12자리는 long long의 범위를 벗어남 -> 직접 num을 구하기 금지, 모듈러 연산을 이용#include using namespace std;using ll = long long;ll n;ll ret;vector nums;int main() { ios_base::sync_with_stdio(0); cin.tie(0); string str="1"; for(int i=0;i>n) { for(auto num : nums) { if(n * 풀이2구하는것 : num % n == 0 이되는 n의 자릿수자릿수를 저장할 변수 필요 (str. size() 금지..

* 풀이1a^b를 for문으로 구하는방법중간중간에 %c복잡도가 터진다. O(20억) * 풀이2이걸 재귀함수로 /2 해가면서 구하면log2 b 로 줄일수있다! b가 홀수인경우, a를 1번더 곱해주면된다. ( 2^5 = 2^2 * 2^2 * 2^1)각각의 18번째줄의 return 문을 만나면서, 계산한 값을 위로 계속 전달해준다!!return을 받은 위쪽 노드는 15번째 줄부터 수행하면서 다시 계산후, 위 노드에게 값을 전달한다.최초 호출 노드를 만나면 main에서 값이 출력된다. * 전체코드

* next_permutation 풀이 단점 : 시간복잡도가 nCr * n 이다. -> 터짐주의점 : arr이 아니고 v를 돌려야함.#include using namespace std;using ll = long long;ll n, m, ret;vector arr;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; if(m > 200000) { cout v(n-2,0); // 조합용 벡터 v.push_back(1); v.push_back(1); for (int i = 0; i >tmp; arr.push_back(tmp); } do { ..

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

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

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