자연수 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로 푼 코드더보기/* ************************************************************************** *//* ..

나무는 (x, y)라고 해놓고선 r,c로 들어왔다. 문제가 날 속임. (그래서 틀림...ㅠㅠ)결국 맞췄을땐 vector로하면 시간초과가 난다는 것을 알게 되었다. 처음에 문제 잘 읽고 시간 제한 보긴했지만 구현 문제라서 그냥 주어진 상황대로 풀었다. 둘을 비교했을때, 나무의 수가 커지면 커질수록 더 차이가 난다.# Let's calculate the complexity of both versions of the code to compare their potential performance.# Old Version (using vector):# In the old version, we have:# - Spring: Sorting the entire vector by age each spring, which..