Mini

https://school.programmers.co.kr/learn/courses/30/lessons/64065 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* 시도1잘한점 : 숫자1개부터 size를 1개씩 증가시키면서 새로나온 숫자들만 answer에 담으면 최적해임.일단 밖의 {}를 제거하고, 괄호가 나올때까지 보고... 숫자들을 배열에 저장?그후, 중복되는것을 완전탐색으로 제거하고... 너무 복잡, 시간복잡도도 터질것 같은데?풀이1. 일단 {{ }}를 모두제거한다.2. 이후, " },{ " 기준으로 분할하면 깔끔하게 숫자만 추출할 수 있다.참고로 }는 메타문자이기때문에 앞에 \\ 2개를 붙여줘야..

https://www.acmicpc.net/problem/2156* 풀이1. 완전탐색으로 시도 i번째 포도주를 먹는다 안먹는다.문제 : 연속3번은 안된다는것을 어떻게 검사하지?비트? -> n=10000개 의비트 -> 불가능cnt변수? (연속으로 선택한 포도주 갯수) -> 트리에서 O로 갈때 1씩 증가시키기!상태 : (idx, cnt) 값 : 그 상태일때, 최대값* 전체코드#includeusing namespace std; typedef long long ll;ll n;ll dp[10004][4];ll arr[10004];//인덱스, 연속선택카운트ll dfs(int idx, int cnt) { if(cnt>=3) { return -987654321; //배제 } if(i..

https://www.acmicpc.net/problem/1480* 시도1N이작다? -> 조합이 여러번?(이 보석은 저가방에 넣고 ... 저 보석은 저가방에...) -> 비트마스크?무게작은순으로 정렬하면 되나?(그리디?) * 풀이그리디보다는 무식하게 완탐으로 시작할것.보석의 idx가 아닌, 가방의 상태들로 dfs 실행.상태를 생각해보자.[가방idx][남은용량][현재까지담은 보석의 집합]포인트는 가방기준 dfs, 현재까지담은 보석의 집합을 상태로 두는 것이다.현재가방에 보석을 담는다 or 안담는다로 완탐. & 메모보석은 for문으로 dfs내에서 완탐 필요.#includeusing namespace std; typedef long long ll;ll n,m,c;ll a[24];ll dp[14][24][1=..

https://www.acmicpc.net/problem/14863* 풀이cnt#includeusing namespace std; typedef long long ll;struct A { int a,b,c,d;};int n,k,ret;ll dp[104][100000+4]; //(idx, num) : 그떄 경우의수vector v;ll dfs(int idx, int cnt) { if(cnt >n>>k; for(int i=0;i>a>>b>>c>>d; v.push_back({a,b,c,d}); } cout ret 초기화 문제처음풀이는 ret=0 -> 오답결론 : ret는 불가능 && 매우 큰값으로 초기화 하라!

https://www.acmicpc.net/problem/5557* 풀이+ , - 2가지 경우의수완탐 -> 2^100 -> 불가dp?#includeusing namespace std; typedef long long ll;int n;int arr[104];ll dp[104][24]; //(idx, num) : 그떄 경우의수ll dfs(int idx, int num) { if(num 20) { return 0; } if(idx==n-1) { if(num==arr[idx]) { // cout>n; for(int i=0;i>arr[i]; } // cout시행착오마지막 숫자와 같은지 검사, 마지막숫자도 더하거나 빼는것이 ..

https://www.acmicpc.net/problem/14867*시도1dfs로 6가지 경우의수 탐색 -> 계속 fill A 만 호출되다 스택 오버플로우* 풀이가중치가 같은 최단거리는 ? bfs! 처음 찾은게 최단거리 보장but, 상태 : [a의 물][b의물] = [10만][10만] -> 메모리 초과상태관찰 -> 상태가 띄엄띄엄 있음 -> 즉, vis를 전부사용하지 않아도됨 -> map을 vis로 활용#includeusing namespace std; typedef long long ll;int a,b,c,d,ret=-1;map,int> vis;struct A { int q,w,cnt;};int main() { ios_base::sync_with_stdio(0); cin.tie(0); ..

https://www.acmicpc.net/problem/1600* 풀이bfs 상태 : y,x,이동가능횟수,거리vis[y][x][이동가능횟수] : 방문했는지원숭이가 갈수있는곳을 dy,dx배열로 만들어놓기m이 y의 길이임에 주의 (m*n 행렬임)#includeusing namespace std; typedef long long ll;int n,m,k,ret=-1;int vis[204][204][34], arr[204][204];int dy[]={0,1,-1,0};int dx[]={1,0,0,-1};int dy2[]={-2,-2,-1,-1,1,1,2,2};int dx2[]={-1,1,-2,2,-2,2,-1,1};struct A { int y,x,cnt,dist; };int main() { ios_ba..

https://school.programmers.co.kr/learn/courses/15009/lessons/121690?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* 풀이최단거리는 bfs상태 : { y, x, 점프사용여부, dist }단순한 bfs는 vis를 방문여부용도 && 거리용도로 사용, but 복잡한경우 dist라는 상태를 따로 분리하는게 좋겠다.이문제는 앞쪽에서 방문여부체크, 종료조건을 체크하는 bfs가 유리.bfs는 먼저 도착한게 최단거리다.3차원 bfs 이해하기세계를 2개로 나눠서 그려보자.세계간 이동가능 여부를 그려보자.공통) +-1로 이동가능안쓴경우 ) +-2..