컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 해결 알고리즘 똑같이 이분탐색을 쓴 LIS 알고리즘을 이용해주는데 이 때, 진짜 LIS 수열을 출력해주는 것이 어려운 문제였다. https://kimmessi.tistory.com/191?category=871925 [알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력 최장 증가 부분 수열 (LIS)이란? 어떤 수열에서 수열의 일부 원소..

https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 문제 해결 알고리즘 LIS알고리즘 (최장 증가 부분 수열 알고리즘)을 써준다. 이 때, $O(n \mathrm{log} n)$ 알고리즘을 사용한다 (이분 탐색). https://kimmessi.tistory.com/191?category=871925 [알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력 최장 증가 부분 수열 (LIS)이란? 어떤 수열에서..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 해결 알고리즘 에라토스테네스의 체를 사용해서 N까지의 모든 소수를 구해준 후에 모든 연속되는 합이 N이 되는지 확인한다. (이 때, MAX == 4000001보다 연속합이 많다면 무시한다.) 두 포인터로 구할 수도 있다. 소스 코드 일반 이중for문 ver #include #define MAX 4000001 using namespace std; bool isPrime[MAX]; int N, prime[MAX], pos = 0, result = 0; int main(){ cin >> N; for(int i=2;i

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제 해결 알고리즘 크루스칼 알고리즘으로 풀어준다. 이 때 두 도시로 분할하는 것이므로 마지막 간선이 제일 큰 값을 가질테니까 마지막 간선의 값만 빼주면 최소값이 나온다. 그리고 find_parent함수를 int find_parent(int x){ if(parent[x] == x) return x; else return find_parent(parent[x])..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 해결 알고리즘 다익스트라로 푸는 문제. 노드의 제한이 그렇게 크지 않기 때문에 우선순위 큐로 굳이 안 풀어도 되는 문제이지만 썼다. 아래의 링크에 다익스트라 알고리즘이 설명되어있다. https://kimmessi.tistory.com/185?category=871925 [알고리즘] 다익스트라 - 선형 탐색, 우선순위 큐 다익스트라 알고리즘 (Dijkstra'..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 해결 알고리즘 별들 각각의 거리와 번호들을 전부 그래프에 push를 해주고난 다음 크루스칼 알고리즘을 이용해서 풀면 된다. https://kimmessi.tistory.com/74?category=871925 [알고리즘] 그리디 알고리즘 - 최소비용신장트리, 스케줄 짜기 탐욕 알고리즘이란? 작은 사례로 나누지 않고 탐욕스러운 선택을 sequence로 계속하면 답에 가까워진다. 선택과정(sele..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 해결 알고리즘 v_1에서 시작하는 다익스트라와 v_2에서 시작하는 다익스트라를 구해준 후에 양방향 그래프라는 점을 이용해서 1에서 $v_1$으로 가는 최단 경로 + $v_1$에서 $v_2$로 가는 최단 경로 + $v_2$에서 N으로 가는 최단 경로 1에서 $v_2$으로 가는 최단 경로 + $v_2$에서 $v_1$으로 가는 최단 경로 + $v_1$에..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 알고리즘 주어진 수(i)들을 정렬하고 순서대로 1~k까지 수(j)에서 뺀 후 그 값이 0보다 크거나 같으면 dp[j]에서 dp[j-v[i]]을 더해준다. 소스 코드 #include using namespace std; int n, k; int result = 0; int main(){ cin >> n >> k; vector v(n); vector dp(k+1); for(int i=0;i>..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 해결 알고리즘 다익스트라를 써주는 문제. 하지만 노드의 수 제한이 20000까지이므로 그냥 선형탐색으로 풀면 무조건 시간초과가 날 수밖에 없다. 그렇기 때문에 우선순위 큐를 이용해 정답을 구하자. 아래의 링크에 다익스트라 알고리즘이 설명되어있다. https://kimmessi.tistory.com/185?category=871925 [알고리즘] 다익스트라..

https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제 해결 알고리즘 0만 없으면 참 간단한 문제인데.. 0 때문에 어려웠다. 구현이 빡셌던 문제 우선 글자 수별로 구분해줘야하는데 글자 수가 1일 때, 2일 때, 3이상일 때로 구분해준다 글자 수가 1일 때, 숫자가 0이면 0을 출력해주고, 0이 아니면 1을 배열 값에 넣어준다. 글자 수가 2일 때, if(num == 10 || num == 20) v[1] = 1; else if((11