fatalite

문제 문제 난이도 : 실버 2 문제 분류 : DP 문제 리뷰 DP 문제당.. 문제 소스 코드 #include #include #include #include #include #include #include #include using namespace std; int DP[1001]; int Arr[1001]; void Init() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } int main() { Init(); //Input int n; cin >> n; for (int i = 1; i > Arr[i]; DP[i] = Arr[i]; } for (int i = 2; i

문제 문제 난이도 : 프로그래머스 2단계 문제 정답률 : 42% 문제 분류: BFS, DFS, 다익스트라(내 풀이) 문제 리뷰 복잡복잡하다. 다익스트라 살짝 응용된 버전 PQ에 comp랑 Point struct 빠르게 구현할 수 있어야겠다. 내일 넥토리얼 코딩테스트를 본다. 못 풀겠는건 포기하고 최대한 풀 수 있도록 해야겠다. 문제 소스코드 #include #include #include #include using namespace std; struct Point{ int x; int y; Point(int a, int b){ x = a; y = b; } }; struct comp{ bool operator()(pair& a, pair& b){ return a.first > b.first; } }; in..

문제 난이도 : 프로그래머스 3단계 정답률 : 60% 분류 : DFS, BFS, Union-Find(서로소 집합) 문제 리뷰 보자마자, 유니온 파인드 문제라고 생각했다. 기존에 구현했던 유니온 파인드의 경우, 1. X에 포함 되는 (X + n) 번 째 원소가 있다고 가정하고, 2. Y에 X를 Union하는 상태를 가정하면, Y

문제 문제 난이도 : 프로그래머스 1단계 문제 분류 : 그리디 문제 리뷰 않이 1단계인데 헤맸다... 문제 소스코드 #include #include #include #include using namespace std; int solution(int n, vector lost, vector reserve) { int answer = 0; vector Vec(n+2, 1); Vec[0] = 0; Vec[n+1] = 0; sort(lost.begin(), lost.end()); sort(reserve.begin(), reserve.begin()); for(int i : reserve){Vec[i] = 2;} for(int i : lost){Vec[i]--;} for(int i = 1; i < n + 1; i+..

문제 문제 난이도 : 프로그래머스 4단계 문제 분류 : 다이나믹 프로그래밍 문제 리뷰 환형이라서 헛짓거리 하다가... 1시간 20분 만에 아이디어 떠올리고 호다닥 풀었다... 그래도 조금은 성장했나보다 ㅠ 문제 소스 코드 #include #include #include using namespace std; int solution(vector money) { int answer = 0; int n = money.size(); int DP1[1000001]; int DP2[1000001]; // DP[1] = 1 // DP[2] = 2 // DP[3] = 3 // DP[4] = 4 // DP[5] = 8 // 1 2 3 1 5 // 1 2 3 1 // 2 3 1 5 DP1[0] = 0; DP2[0] = 0;..

문제 문제 난이도 : 프로그래머스 4단계 문제 분류 : 다이나믹 프로그래밍 문제 리뷰 내가 이게 DP 문제라는 걸 몰랐다면 풀 수 있었을까..? 그리고 처음에는 DP[i][j] 이런 식으로 둬서 덧붙일때 + 만 고려되었다. 테스트 케이스는 맞길래 뭐지 했는데, - 일 경우에는 - (최소값)으로 해야지 최대값으로 갱신할 수 있다. 물론 질문하기에 자세하게 해설해 놓은게 있지만, 기억용으로... 문제 소스코드 #include #include #include #include using namespace std; int solution(vector arr) { int answer = -1; vector IntArr; vector OperArr; IntArr.push_back(-1); OperArr.push_ba..

문제 문제 난이도 : 3단계 문제 분류 : 다이나믹 프로그래밍 문제 리뷰 저번에 풀어본 문제와 비슷하고 그것보다 쉬워서 금방 풀었다. 만약 BFS 같은 탐색을 사용하였다면, 조합이 폭발적으로 상승해서 시간 초과나 메모리 초과가 뜨지 않았을까 싶다. 초등학교 때 배웠던 경우의 수 개념을 사용하면 좋은 문제이다. Base Case로 DP[1][2 ~ N]과 DP[2 ~ N][1]를 처리해준다. 한 가지 밖에 없거나, 가는 길에 개울이 있다면 0이 된다. DP[i][j]는 j,i로 가는 경우의 수를 저장한다. DP[i][j]로 오는 방법은 DP[i-1][j] + DP[i][j-1] 이므로 이를 사용하면 되고, 만약 개울이 있다면 0으로 처리한다. 문제 소스코드 #include #include #include ..

문제 링크 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이 문제를 풀려고 했는데, 2차원 DP 문제일까 생각을 해봤지만, 고민해봐도 비교하는 것과 규칙이 생각나지 않아서 해설을 봤다. 잘 알려진 문제인 것 같다 최장 부분 증가 수열, LIS라고 불리는 문제이다. 근데 이거의 베이스 문제가 이미 풀었던 문제였더라, 아마 해답 보고 다시 생각해보지 않아서 그랬나보다.. 복습을 해야겠다. DP 문제의 핵심은 어떻게 부분 문제로 나눌 것인가가 핵심인 것 같다. 다양한 시도가 필요해보인다. 11053번: 가장 긴 증가하는 부분 수열 수..

문제 문제 난이도 : 실버 1 문제 분류 : 다이나믹 프로그래밍 문제 리뷰 나머지 연산 생각해볼 필요가 있을 듯 하다 문제 소스코드 #include #include #include #include #include #include #include #include using namespace std; long long DP[1001][10]; void Init() { ios_base::sync_with_stdio(false); cin.tie(NULL); std::cout.tie(NULL); } int main() { Init(); int n; cin >> n; for (int i = 0; i < 10; i++) { DP[1][i] = 10 - i; } for (int i = 2; i

문제 분류 문제 난이도 : 실버 1 문제 분류 : 다이나믹 프로그래밍 문제 리뷰 DP[j]를 j 개를 구매하는데에 걸리는 카드의 수로 정의한다.당연하게도, DP[0] = 0첫 번째 루프(i=1)에는 P_1만을 이용한다. DP[j] = P_1 * j가 된다.두 번째 루프(i=2)부터 비교를 해야한다. DP[j] = max(DP[j - 2] + P_2, DP[j]) 초록색 부분은 i = 1일 때의 값이었을 것이다....따라서 DP[j] = max(DP[j - i]+ P_i, DP[j])가 된다. 문제 소스코드 #include #include #include #include #include #include #include #include using namespace std; long Price[10001]; ..