[틀림] 프로그래머스 외벽점검 // 원형배열, 순열

https://school.programmers.co.kr/learn/courses/30/lessons/60062 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* 풀이n이 작음 (15) -> 비트마스킹? -> 내부에서 순서도 중요하네? -> 그냥 순열?idx가 사람의수이면서 && dist의 index 역할j는 weakArr(weak를 시작점에따라 바꾼것) 의 index임dist를 앞부터 weakArr에 집어 넣어보는 완전탐색 방법.원형배열 구현 , 거리가 중요한경우결론 : startIdx기준으로 뒤넣고, 앞넣을때 배열 size만큼 더해주면된다.vector make(int startIdx, vector&..

[맞음] 백준 12891 비밀번호 DNA // 슬라이딩 윈도우

https://www.acmicpc.net/problem/12891 * 풀이n = 1백만O(n) 풀이 필요슬라이딩 윈도우==구간(m)을 유지갱신 하면서map에 저장각 구간마다 적은게있는지 검사#includeusing namespace std; typedef long long ll;ll n,m,ret;string str;vector v;map mp;int a,b,c,d;int check() { if(mp['A'] >n>>m>>str; cin>>a>>b>>c>>d; int s=0; int e=0; //안포함 for(int i=0;i

[틀림] 백준 2018 수들의 합 5 // 투포인터, 배열없는, n=천만이면 O(N)

https://www.acmicpc.net/problem/2018* 시도1누적합만들고이진탐색으로 찾으면 될듯?메모리초과 (1천만배열)시간초과 (n log 1천만 ) == 천만 * 23 -> 23억o(N)에 풀어야한다. * 풀이이문제는 메모리제한이 32MB -> 1천만 배열불가능s,e가 index인 동시에, 값의 역할도 해야함!엣지케이스 확인n=1 ) break문에 걸려서 잘처리됨마지막 부분 해보기break에 걸려서 자기자신이 카운팅이 안됨 -> ret=1 로 시작#includeusing namespace std; typedef long long ll;ll n,ret;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>..

[틀림] 백준 1456 거의소수 // 대소비교 최적화방법, 소수판별

https://www.acmicpc.net/problem/1456* 풀이1체 알고리즘 => 소수들 벡터에 저장 ( 루트b까지만 보면됨 )ex) 25까지의 거의소수를구해야함5까지만 소수를 구하면됨. 구해야됨.10^14 -> long도 초과, 10^7 -> 1천만 -> ok 5를넘어가면 (6부터는 6^2 = 36 ...) 거의소수가 될수없음.1. 소수에대해2. 소수들을 제곱해가면서 a이상, b이하인지 체크for(auto i : v) { int cnt=0; for(ll j=i*i;j=a) cnt++; } ret+=cnt;}문제 : j를 계속 곱하기때문에 overflow 발생 * 풀이2이항정리를 이용한 대소비교이렇게하면 77777^10을 계산해야될것을, 77777^9으로 개선할수있음.for(aut..

[틀림] 백준 1167 트리의 지름 // 거리는? bfs, 트리개념

https://www.acmicpc.net/problem/1167* 풀이(최단) 거리는? 무조건 bfs어느한곳에서 최장거리노드 -> 지름의 노드 중1개증명 : 귀류법찾은 노드에서 시작해서 가장먼곳을 찾으면 지름의 두쌍을 찾은것임. 주의1-idx임에주의vis를 n+1까지 돌리고찾을때도 n+1까지 찾아야함bfs2번주의vis[node1]=1로 시작해야함vis[1]=1 아님.#includeusing namespace std; typedef long long ll;int v,ret;int vis[100000+4];vector> adj[100000+4]; // int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>v; for..

[틀림] 백준 13023 ABCDE // vis 초기화(백트래킹) 필요한 이유

https://www.acmicpc.net/problem/13023* 백트래킹 복습depth가 5이상인지 검사이때, vis=0으로 백트래킹 필요즉, 원복시키면서 완탐을 하려고 원상복귀를  하는것이다.완탐을하려면 원복이 필요!  * 풀이#includeusing namespace std; typedef long long ll;int n,m,ret;int vis[2004];vector adj[2004];int dfs(int cur, int depth) { if(depth==5) { cout>n>>m; for(int i=0;i>a>>b; adj[a].push_back(b); adj[b].push_back(a); //a와 b가 친구 -> 양방향맞음 } for(int ..