algorithm5 LIS알고리즘 최장 증가 부분 수열 LIS(Longest Increasing Subsequence) 최장 증가 부분수열이란 ? 더보기 임의의 수열이 주어질 때, 이수열에서 만들 수 있는 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분수열이라 한다. -나무위키- 예를 들어보자 3 5 7 9 2 1 4 8이란 수열있다. 위 수열에서 몇가지의 수를 선택하여 부분수열을 만들 수 있다. 이때 오름차순이면서 가장 긴 수열은 3 5 7 8 또는 3 5 7 9이다. 동적 계획법으로 최장 증가 부분 수열을 구해보겠다. 새로운 배열을Dp를 만들고 정의는 다음과 같다. Dp[i]는 배열의 [i]를 마지막 값으로 가지는 수열의 lis이다. index 0 1 2 3 4 5 6 7 A 3 5 7 9 2 1 4 8 Dp inde.. 2021. 8. 19. 동적 계획법(Dynamic Programing, Dp) 동적 계획법 - 위키백과, 우리 모두의 백과사전 수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 ko.wikipedia.org 동적 계획법 더보기 동적 계획법의 원리는 매우 간단하다. 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 많은 알고리즘 문제를 풀다보면 구했던 값을 불필요하게 계속 구하는 과정을 할 때가 있다. 다음 예시를 보자 예시 피보나치 수열을 만들어보자 int fib(int n) { if(n == 0) return 0; else if (n==.. 2021. 8. 5. 유클리드 호제법 유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘이다. https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 ko.wikipedia.org 24와 18의 최대 공약수를 구해보자 큰수를 작은수로 나누어 나머지를 구한다. 24=18*1+6 45와 38의 최대 공약수는 38과 7의 최대 공약수와 같다. 이성질을 재귀적으로 .. 2021. 7. 23. 소수 구하기 소수(prime number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다. https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 소수 (수론) - 위키백과, 우리 모두의 백과사전 좌측은 소수, 우측은 합성수. 소수란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다. 소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime number)는 1보다 큰 자연수 중 1과 자기 자신만을 ko.wikipedia.org 소수를 구하는 여러가지 알고리즘을 짜보고 시간복잡도를 비교해보자 첫번째 풀이 bool isprime(int num) { int cnt = 0; if (num == 2) return true;.. 2021. 7. 15. 이전 1 2 다음