간단한 백트래킹 문제이다. queue를 사용해서 0의 좌표값들을 저장해서 사용했는데, 이런식으로는 처음 사용해봐서 애를 좀 먹었다. /* ************************************************************************** *//* *//* ::: ::: ::: *//* Problem Number: 2239 :+: :+: :+: *//* ..

위상정렬을 사용하면 쉽게 풀 수 있습니다. [그래프/정렬/유향] 위상정렬 / Topological Sorting위상정렬 / Topological Sorting 유향 비순환 그래프(Directed Acyclic Graph, DAG) 에서 각 노드들을 선형 순서로 나열하는 방법입니다. 여기서 유향 비순환 그래프란, 방향이 있는 그래프 중에 사이클이 없chanhhh.tistory.com1516번 문제와 거의 동일한 문제. 단 w의 값을 출력해주면 됩니다.#include #include #include #define fastio ios::sync_with_stdio(0), cin.tie(0)using namespace std;int main() { fastio; int t; cin >> t; for (i..

세번째 작은 수 찾는 프로그램. 우선 처음 접근을 next_permutation을 통해 찾으려고 했는데, 해당 함수는 1,1,1 과 같은 중복된 숫자에 대해서 순열을 찾지 않는다는 것을 깨달았습니다. 이는 모든 요소가 동일하기 때문에 사전 순으로 더 이상의 다른 순열이 존재할 수 없기 때문입니다.  int i = 0; do { if (i == 2) { cout  그래서 dfs로 변경해서 풀었는데, 갯수가 10^8개가 되면서 dfs로 전부 찾으려고 하니까 시간 초과가 났다.생각해보니, 가장 작은 수 4개만 찾으면 세번째로 작은 수를 찾을 수 있을거라 판단하고 코드를 작성하여 해결했다. 정답 코드.#include #include #include #define fastio ios::sync_..

이분탐색으로 풀었습니다. 중간에 입실론 오차범위 때문인지 오답이 되고 res의 범위를 탐색하는 과정에서 res0으로 걸어서 시간초과에 빠지게 된 경우도 생겨서 double형의 범위나 이분탐색의 무한루프에 대해서 다시 한번 생각하는 문제가 되었습니다.#include #include #include #define fastio ios::sync_with_stdio(0), cin.tie(0)using namespace std;int n;double l;int main() { fastio; cin >> n >> l; vector w(n); vector x(n); for (int i = 0; i > x[i]; for (int i = 0; i > w[i]; double s = 0.0, e = l, mi..

DP문제입니다. 헷갈리는 흐름을 정리하기 위해서 글을 씁니다.dp[i - j]는 문제를 이해하는 데 매우 중요한 부분입니다. 이 부분을 명확히 이해하는 것이 문제 해결의 핵심입니다.dp[i - j]가 의미하는 것dp[i]는 i개의 카드를 구매할 때 지불할 수 있는 최대 금액입니다. 그렇다면, dp[i - j]는 i - j개의 카드를 구매할 때 지불할 수 있는 최대 금액을 의미합니다.다시 말해서, 이미 i - j개의 카드를 최대로 구매한 상태에서 j개의 카드가 들어있는 카드팩을 추가로 구매했을 때의 최댓값을 계산하는 것입니다.구체적인 예시로 살펴봅시다:만약 i = 4, 즉 4개의 카드를 구매하려고 한다면, 우리는 다음과 같이 생각할 수 있습니다:j = 1일 경우:dp[4 - 1] = dp[3]: 이미 3개..