17070번. 파이프 옮기기 1 과 같은 문제이지만 N(3 ≤ N ≤ 32)의 범위가 굉장히 넓기 때문에 dp를 적용해야만 풀 수 있습니다.  + int형을 return값으로 가지게 되면 오버플로우가 나므로 ll을 사용하여 풀어야 합니다.완전탐색으로 풀었지만, 시간초과가 나게 되어서 dp에 대한 고민을 많이 해볼 수 있는 문제였습니다.#include #include using namespace std;using ll = long long;#define fastio ios::sync_with_stdio(0), cin.tie(0)ll n;ll dx[] = {1, 1, 0};ll dy[] = {0, 1, 1};ll dfs(ll y, ll x, ll dir, vector> &b, vector>> &v..

자연수 n을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.여기에서 연속된 소수의 합이라고 해서 처음 접근법을 에라토스테네스의 체로 소수를 거르고, 소수들의 배열을 만들어서 누적합을 만드는 식으로 진행하였다. 에라토스테네스의 체의 수행시간은 O(nloglogn)이고 누적합 탐색 O(n^2)으로 시간초과에 걸렸다.시간초과 누적합더보기#include #include using namespace std;int n;int pn[4000001];int conPn[4000001];int sumPn[4000001] = {0};int primeNumberSieve() { for (int i = 2; i > n; int count = 0; int sumPnSize = 0; sumPnSize = pri..

위상정렬 / Topological Sorting 유향 비순환 그래프(Directed Acyclic Graph, DAG) 에서 각 노드들을 선형 순서로 나열하는 방법입니다. 여기서 유향 비순환 그래프란, 방향이 있는 그래프 중에 사이클이 없는 그래프를 말합니다. 위상 정렬은 보통 의존 관계를 해결할 때 사용되며, 그래프 내에서 어떤 일의 순서를 정하거나 작업 간의 선후 관계를 정의하는 문제를 풀 때 유용합니다.위상 정렬의 조건그래프는 반드시 유향 비순환 그래프(DAG)이어야 합니다.유향(Directed): 간선의 방향이 있다.비순환(Acyclic): 사이클이 존재하지 않는다. 즉, 위상 정렬은 순환하는 경로가 있으면 불가능합니다.위상 정렬의 동작 원리위상 정렬의 핵심은 선행 조건을 만족하는 노드부터 순차적..

LIS의 플래티넘 버전. 수열 문제들을 풀다보면 어렵지 않게 풀 수 있다.11053번. 가장 긴 증가하는 부분 수열11054번. 가장 긴 바이토닉 부분 수열11055번. 가장 큰 증가하는 부분 수열11722번. 가장 긴 감소하는 부분 수열12015번. 가장 긴 증가하는 부분 수열 212738번. 가장 긴 증가하는 부분 수열 314002번. 가장 긴 증가하는 부분 수열 4dp로 풀면 O^2이므로 이진탐색을 이용하여 현재 수열들을 교체해가며 뽑아주고, 마지막 indices의 요소를 사용하여 parent를 역추적하여 뽑아내주면 된다.import Foundationvar arr: [Int] = []var sequence: [Int] = []var indices: [Int] = []var parent: [Int]..

17088 c++ 등차수열 변환.dfs로 풀었는데, 복사생성자를 인수로 받아서, 메모리 초과가 났다. dfs에서는 꼭 조심해줘야 하는 것을 다시 깨달았습니다.그래서 고쳐서 레퍼런스로 제출했는데, 시간초과가 났습니다. 수열의 길이가 10,000까지 될 수 있어서 각 항목에 대해 3가지 선택지를 가지므로, 완전 탐색하는 경우의 수는 (3^n) = 3^100000이 되는 것을 깨달았습니다. 그래서 수열로 접근하여 풀었습니다.dfs로 푼 코드더보기/* ************************************************************************** *//* ..