:: ADVANCE ::

BAEKJOON ONLINE JUDGE 1162 도로포장 https://www.acmicpc.net/problem/1162 다익스트라 + DP평소 다익스트라는 그냥 그래프의 개수만큼 정점을 탐색하는데,이 visit 정점 배열을 DP 배열로 놓고, DP[도시 개수][포장 가능 도로의 수]로 놓고 풀면 된다.다익스트라 구현 시 반복문 안에는 다른 도시로 영역을 넓힐 때 포장가능 할 때 포장하는 경우와 포장을 하지 않는 경우 둘 다 queue에 넣어주어 구현하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727..

BAEKJOON ONLINE JUDGE 1365 꼬인 전깃줄 https://www.acmicpc.net/problem/1365 LIS 문제최장 증가 부분 수열의 개수만큼이 잘 연결된 것이고, 나머지를 잘라주면 최소가 된다.잘은 모르겠지만 직접 예제를 만들어보고 알게됨.. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include int n;int size = 1;int lisArr[100000]; void lis(int num){ int s = 0, e = size, middle; if (lisArr[size - 1]

dovelet LIS http://183.106.15.130/30stair/LIS/LIS.php?pname=LIS C - 이진탐색 구현 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include int n;int num[500000];int parent[500000];int lisArr[500000];int size; void lis(int idx){ int s, e, middle; if (num[lisArr[size - 1]]

Algospot Longest Increasing Sequence https://algospot.com/judge/problem/read/LIS 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include int n;int lisarr[500], input[500];int size; void init(){ int i; for (i = 0; i

BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2012 2532 먹이사슬 https://www.acmicpc.net/problem/2532 1. 정렬선의 왼쪽 시작지점을 기준으로 정렬한다.왼쪽 시작지점은 오름차순으로, 왼쪽 시작지점이 같을 경우에는 오른쪽 끝 지점이 작은순으로 (내림차순)으로 정렬한다.2. 문제의 조건을 보면 같은 시작점, 같은 끝점을 지는 선분은 포함하지 않는다. 하지만 입력으로 들어올 수 있기 때문에 이를 무시해 준다.3. LIS (최장 길이 증가 부분 수열 Longest Increasing Subsequence)정렬한 값을 순서대로 LIS O(NlogN)을 구현한다. O(N^2)은 time limit난다. LIS (O(NlogN))은 이진탐색을 이용하여 구..