needreview

🖍️ 겪은 문제문제 해결 아이디어가 안떠올랐다. 완전 탐색으로 풀면 시간 초과였다. 역시나 DP였다.🔍 해결 방법DP최소 단위를 설계한다.dp[n]을 n무게일 때 최대 가치라고 하자.점화식을 세운다.dp[i] = max(dp[i], dp[i - weight[i]] + value[i]);포인트는 순회를 거꾸로 K에서부터 1씩 줄여나가며 한다는 것이다.1에서 부터 돌면 점화식에서 더 작은 값을 이용하기 때문에, 이미 계산한 물건을 또 담을 수 있다.📇 코드#include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, K; ..

🖍️ 겪은 문제한 글자씩 이동시켜가면서.. 누적해서 탐색해야하나? 생각을 했는데 풀이 방법이 떠오르질 않았다.보통 이러면 DP더라.🔍 해결 방법A문자열에 대한 인덱스 i, B문자열에 대한 인덱스 j를 1씩 증가시켜가면서 LCS값을 누적하며 계산해서 최종적으로 [A문자열 길이][B문자열 길이]를 알아낸다. -> DP로 풀이해야 한다.DP설계하기 : dp[i][j]를 A문자열의 i번째 문자까지 부분 문자열과, B문자열의 j까지 부분 문자열 간의 LCS 길이라고 하자.점화식 세우기dp[i][j]가 같으면 현재 비교하는 문자 이전 까지 비교한 거에 1더한거 => dp[i][j] = dp[i-1][j-1] + 1같지 않으면 A에서 하나 빼고 & B 그대로, A 그대로 & B에서 하나 뺀거 중에 더 큰 LCS값..

🔍 다익스트라 해결 포인트그래프 자체를 vector> buses[N]; 으로 선언해서 a->b로 이어지는 간선을 buses[a].push_back({b, 비용}); 이렇게 표현한다.그래프를 탐색할 때는 Priority Queue를 사용해서 비용이 작은 순서로 순회하도록 한다.선언은 오름차순이면 priority_queue> pq;내림차순이면 priority_queue, vector>, less> pq;시작 노드부터 출발해서 누적된 거리를 담기 위한 dist 배열은 최댓값으로 초기화한다.📇 코드#include #include #include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.ti..

🖍️ 실패한 원인드래곤 커브 구현 방법을 생각하는 과정에서 방향 변화에 규칙이 있을 것 같다고 유추는 하였으나,규칙을 발견을 못했고, 공식으로 풀어내지 못함 ㅜㅜ (결국 답안을 보고 풀이했다...)🔍 해결 방법드래곤 커브 n세대는 드래곤 커브 n-1세대의 방향을 역순으로 해서, +1한 뒤(반시계 90도 회전) %4를 하면 된다.(x+1)%4까지는 계산해봤는데 역순일거라고 생각을 전혀 못했다.회전을 하게되면 방향의 순서가 바뀌게 되어서 역순이 되는데 그걸 캐치를 못했다... 다음에 비슷한 문제가 나오면 생각해서 풀 수 있도록 잘 익혀두자!!📇 코드#include #include #include #include #include using namespace std;const int SIZE = 101;b..