fatalite

문제 문제 난이도 : 프로그래머스 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 ..

Problem 난이도: 프로그래머스 2단계 분류: 스택이라는데,, set과 pair 써서 풀었다. for문쓰면서 erase 할 생각하지말자. 이럴거면 vector써도 똑같았을듯? 아무튼 list를 두자는 아이디어는 괜찮았던듯. Solution #include #include #include #include using namespace std; vector solution(vector prices) { vector answer; set List; answer.resize(prices.size(),0); for(int i = 0; i < prices.size()-1; i++){ List.insert({i, prices[i]}); set ListCopy = List; for(pair p : ListCopy){..

Problem 난이도 : 프로그래머스 2단계 분류 : 큐, Deque 코멘트: 간단하게 짜는 버릇을 들이자. Solution #include #include #include #include using namespace std; int solution(int bridge_length, int weight, vector truck_weights) { int answer = 1; deque OnBridge; deque WaitingTruck; for(int a : truck_weights){ WaitingTruck.push_back(a); } //one loop = 1s; int CurrentWeight = 0; while(!WaitingTruck.empty() || !OnBridge.empty()){ ans..

Problem 난이도: 프로그래머스 2단계 분류: Queue, STL Deque Solution #include #include #include #include #include #include #include using namespace std; int solution(vector priorities, int location) { int answer = 0; deque q; for(int i =0; i< priorities.size(); i++){ q.push_back({priorities[i],i}); } int cnt = 0; while(!q.empty()){ pair p = q.front(); q.pop_front(); cnt++; for(int i = 0; i < q.size(); i++){ if..

Problem 난이도: 프로그래머스 1단계 분류: 스택 Solution #include #include #include using namespace std; vector solution(vector arr) { vector answer; answer.push_back(arr[0]); for(int i = 0; i < arr.size(); i++){ if(answer.back() == arr[i]){ continue; }else{ answer.push_back(arr[i]); } } return answer; }