Mini

https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr * 시도문제를 예시로 이해하려고 시도 -> 실패시키는대로만 하면 되는문제..알고리즘이 주어진것을 코드로 옮기는 능력을 보고싶은듯 * 풀이분리불가 && 균형잡힌 문자열 찾는방법?substr 사용법잘못 : substr( a, b) 가 a부터 b까지 Xa부터 b개를 가져오는것임substr(a) // a부터 끝까지substr(a,3) // a부터 3개앞뒤를 자르려면?u = substr(1, u.size()-2)괄호 방향을 뒤집어서 뒤에 붙이기rever..

https://school.programmers.co.kr/learn/courses/30/lessons/12979?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이N이 2억이기때문에, 완탐, dp는 불가능 합니다.그리디, 수학적으로 풀어야 합니다.prev를 마지막의 커버된 아파트의 위치로 정의합니다.w가 주어지면, 2*w+1의 범위는 커버가 가능한것은 추론했음.(station - w -1 ) -prev로 a구간의 길이를 구함구간을 하나하나 보지않고 숫자 뺄셈연산으로 한번에 처리한것이 키포인트.a구간을 2*w+1로 나누고, 올림하면 필요한 기지국의 갯수가 됨. 엣지케이스엣지케이스..

https://school.programmers.co.kr/learn/courses/30/lessons/60059 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr시도1lock 의 y,x에 좌물쇠를 대보면서 전부 1인지 체크하는 방법오답포인트 : 자물쇠, 열쇠 둘다 (0,0)에서 시작한다고 가정반례 : 열쇠가 좌물쇠 좌측위에 있는경우도 가능함.#include using namespace std;vector> key, loc, origin;vector> rot(vector> origin){ vector> ret(24, vector(24, 0)); // int ret[24][24]; for(i..

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

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

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

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

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