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..

다익스트라 정리 다익스트라 풀이처음에 다익스트라로 n까지 최단 거리 구함. (구하면서 prev에 간선 정보들을 저장)prev를 이용하여 graph에서 해당하는 간선들을 삭제.다시 다익스트라를 돌려서 n까지 가는 최단 거리를 구함.고려한 점도시는 양방향으로 이동할 수 있다. (최단거리라면 양방향 둘 다 막힌다)다른 도시로 이동할 때 코스트가 다른 도로가 존재할 수 있다 ( 1->2 (1), 1->2 (2)) 이때 cost 가 1인 도로만 막힘탈출하지 못하는 경우는 없다.정답 코드더보기#include using namespace std;#define INF 1e9void dijkstra(int n, vector>>& graph, vector& distance, vector& prev..

다이나믹프로그래밍과 다익스트라 두 방법 모두 사용할 수 있습니다. 시간 복잡도시간 복잡도는 O(D + N)입니다.D는 고속도로의 길이, N은 지름길의 수입니다.문제에서 N ≤ 12, D ≤ 10,000이므로, 이 접근 방식은 충분히 효율적입니다. C++ DP 풀이.#include using namespace std;#define INF 1e9int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, d; cin >> n >> d; vector> graph[10001]; for (int i = 0; i > from >> to >> cost; if (to dist(d + 1, INF); dist[0] = 0; for (int ..