Mini

https://school.programmers.co.kr/learn/courses/30/lessons/258707 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr1. 시행착오1. 완탐 ? -> 경우의수 : 선택안함, 좌측선택, 우측선택, 둘다선택 (4) ^ 1000(n) ->불가2. dp?상태 : [idx][round][mycard] == 1000*1000*1000 == 10억 -> 메모리초과 -> 불가// mycard (내가 갖고있는 카드)부분을 정수 1개의 상태로 표현 불가능 -> 불가!3. 그리디? 부분최적해가 전체최적해가 된다. 2. 의사코드0. 매순..

https://www.acmicpc.net/problem/170691. 의사코드1. dfs("끝" 좌표, 상태 :가로 세로 대각) 의 상태 기록이 필요함2. 기저사례 : 범위밖, 벽이있음 -> 해당 경우의수는 "0" 개로 처리 -> 배제시키기3. 좌표가 n-1인경우 -> 정답 -> 1개의 정답으로 처리.4. 논리부분 : 케이스에 맞게 [초기화, 논리, 리턴] 해주면 끝. 2. 시행착오1. 상태가 대각(2)일때 y-1, x-1도 벽인지 체크해줘야함2. dfs 호출부에서 (0,0,0)이 아닌 (0,1,0) 으로 호출해야함 // 끝좌표가 (0, 1) 이므로. 3. 전체코드#include using namespace std;typedef long long ll;ll n, a[33][33], dp[33][33][..

https://www.acmicpc.net/problem/1010 1. 시행착오1. 팩토리얼을 dp에 담으면 되지앟나?2. long long의 범위도 벗어난다.. 오버플로우3. 5C2 = 5*4 / 1*2 로 간소화하기 && 그때그때 나눗셈 계산 -> 오버플로 방지 2. 의사코드1. 이문제는 mCn 문제로 간소화 할 수 있다.즉, (1, 3, 4) 순서쌍 하나만 있으면 그것을 안겹치는 경우로 생각하면 된다. 2. nCr 간소화 버전을 코드로 구현하면 끝이다.ex) 5C2 = 5*4*3 (m~m-2) / 1*2*3(r=1부터 위 수행횟수만큼 증가)  2. 전체코드#include typedef long long ll;using namespace std;ll tc, n,m, dp[34];//n!의 값ll df..

https://www.acmicpc.net/problem/1149 1. 의사코드1. 완탐 -> 3C1 을 N번반복 -> 3^1000 -> 불가2. dp? 3. 상태 : [idx][색깔] 1000(n개)*3(빨,노,파)에 가능!3.5 값 : 그 상태일때, 비용의 최소값4. 완탐기반으로, 위에서 칠한색을 제외한 2개중 최소값을 dp에 저장함. 2. 추가정보 필요시 해결방법위에서 무슨색을 칠했는지 알아야하기때문에 , b[idx] 배열에 기록해둠. 3. 전체코드#include typedef long long ll;using namespace std;int n, k,dp[1004][3],a[1004][3];int b[1004]; //해당 idx에 어느색을 칠했는지int dfs(int idx, int color) ..

https://www.acmicpc.net/problem/12865 1. 불가능한경우를 먼저 ret하라int dfs(int idx, int weight) { //기저사례 //!조건불만족하면 리턴! 이 return이 먼저와야함!! -> 그래야 배제가능. // 안그러면, 조건불만족 인데 idx==n인 경우도 유효한 경우로 카운팅됨. if (weight > k) { return -987654321; } if (idx == n) { return 0; }idx==n return 0이 먼저오는 경우 : 조건불만족인데 n에 도달한경우도 유효한 경로로 카운팅이 되어버린다.. 2. 의사코드0 번베낭을 담는다, 안담는다1번 베낭을 담는다 안담는다 ... 로 완탐하고dp[idx][weight] 의 상태를 배열에 저장해..

https://www.acmicpc.net/problem/2098 1. 외판원순회 특징1. {a,b,c} 집합을 "방문"한 상태에서 d로 가는 최소값과{b,a,c} 집합을 "방문"한 상태에서 d로 가는 최소값은 같다.즉, {a,b,c} 집합안에서 최소값인 경로(a->b->c 등)는 dp를 채우면서 저장된다.2. 2->3->1->2와3->1->2->2 는 같은 경로이다.따라서, 출발점은 아무거나(1번도시) 로 하자. 1.5. 비트 1111 만드는법1 하면된다!10000 -1 == 1111이렇게하면, 모든도시방문한 비트가 만들어진다! 2. 의사코드1. dfs(현재도시, 방문한도시체크용 비트)dfs(0, 1) 로 시작한다. //(0번도시부터 시작, 0번도시 방문표시==1)2. 기저사례 : 모든도시를 방문한경우..

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)www.acmicpc.net 1. 의사코드1. 완탐기반, 상태를 배열에 저장함2. 상태 : idx==해당날짜3. 아래 그림을 그리고 참고하면서 max 식을 만들어낸다.max { 상담하는경우는 그때 이익을 더함 vs return 받은 이전값을 그대로 씀 }이값을 배열에 저장한다.#include typedef long long ll;using namespace std;//dp[i] : i날짜일때 최대수..

https://www.acmicpc.net/problem/2240 2240번: 자두나무자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어www.acmicpc.net1. 탑다운디피1. 디피는 기본적으로 "상태"를 "배열"에 저장하고이미 저장된 경로는 더 연산안하고 배열에 저장된 값을 사용하는 것이다.2. 이문제에서 "상태"는 {idx, 위치, 이동제한} 이다. 그 값은 그상태일때, 획득가능한 자두의 최대값이다. 2.비트연산자1. 나무위치가 1,2로 주어졌지만 이를 0, 1로 바꾸면 코드가 매우 간결해지는 장점이 생긴다.2. 장점 : if(0) , if(1)로 바로 활용가능..