LIS NlogN 연습의 전형적 형태 입력이 간단해서 쉬웠다. https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 풀이방법은 정말 lis 구현밖에 없다.... #include #define INF 123456789 using namespace std; vector v; vector in; int main(){ int n,tmp; scanf("%d", &n); for(int i=0; i

오버킬 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net lis의 nlogn이 주제였으므로 의도치않게 오버킬을 했다. 입력받은 값을 pair에 넣고 정렬 후 lis구하기. #include #define INF 123456789 using namespace std; vector v; vector input; int main(){ v.push_back(-INF); int n,a,b; scanf("%d", &n); for(int i=0; i

일단 나는 이 문제를 LIS nlogn 구현 문제 밀다가 발견한거기 때문에 알고리즘 접근에 있어서의 문제는 없었다. https://www.acmicpc.net/problem/13711 13711번: LCS 4 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] www.acmicpc.net https://jason9319.tistory.com/113 [최장 증가 수열] LIS(Longest Increasing Subsequence) 이번 글에서는 DP중에서 특별한 케이스인 LIS에 대해 얘기해보..

노안이 왔나 '-' 이랑 '_' 를 구분을 못해서 맞왜틀했다 ㅠㅠㅠㅠ https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 출력 예시를 보고 잘 구현하라고 하는데 출력 예시를 보고 잘 구현하라고밖에 말을 못하는 문제 #include using namespace std; int n; void recur(int k){ for(int i=0; i

귀찮았던 문제. https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 그냥 너무나도 귀찮았던 나머지 입력이 홀수로 들어오면 2를 잘 빼줘서 5의 배수 꼴로 만들어준 다음 잘 계산했고 입력이 짝수로 들어오면 10의자리와 1의자리를 분리해서 계산해줬다. #include using namespace std; int main(){ int n; scanf("%d", &n); if(n==1 || n==3){ printf("-1"); return 0; } int ans = 0; if(n%10 == 1){ ans+=3; n-=6; } if(n%10 == 3){ ans+=4; n-=8..

실버작 2 Hamming Distance 자체는 좀 귀찮은 개념이긴 한데 이 문제에선 굳이 Hamming Distance를 구할 필요가 없다. 그냥 각 문자 자리에서 가장 많이 등장하는 문자를 Hamming Distance의 합이 가장 작은 DNA의 문자자리에 그대로 넣어주기만 하면 된다 #include using namespace std; char arr[1234][56] = {0}; char ans[56] = {0}; int a,c,g,t; int main(){ int n,m; scanf("%d %d", &n, &m); for(int i=0; i