NEVER ENOUGH

안녕하세요. 오늘은 가장 긴 증가하는 부분 수열, LIS 알고리즘에 대해 알아보겠습니다. 사실 예전에도 LIS에 대한 글을 쓴 적이 있었는데요.다시 보니 정말 몹쓸 글이어서 조금 놀랐습니다.그래서 이번에는 LIS에 대해 조금 덜 못 써 보겠습니다.LIS우선 LIS는 부분 수열 중 숫자들이 순 증가(strictly increasing)하는 수열입니다.'1 2 4'는 순 증가이지만 '1 4 4'는 순 증가가 아닌 단조 증가입니다. LIS는 아주 전통적인 알고리즘이고 동적 계획법과 그리디 해법 두 가지가 가장 유명합니다.동적 계획법 풀이수열의 인덱스를 받아서 해당 인덱스부터 시작하는 LIS의 길이를 반환하는 함수를 작성해볼게요.기저 사례굳이 기저 사례를 처리해주지 않아도 동작합니다.대신 시작 인덱스 하나의 원..

안녕하세요 오늘은 배낭 문제 알고리즘에 대해 알아보겠습니다.배낭 문제는 주어진 N개의 아이템 중에서 무게 W까지 넣을 수 있는 배낭에 최대 이익 V가 되도록 고르는 알고리즘이에요. 배낭 문제는 직관적으로 이해하기 힘든 dp 알고리즘 중 하나인데요.정확하게 말하면 0-1 배낭 문제가 어렵고 분할가능한 배낭 문제는 그나마 괜찮습니다. 우선 두 문제 모두 "무게 한도 안에서 최대 이익을 갖도록 아이템을 선택한다"는 점은 같습니다.0-1은 물건을 넣거나(1) 넣지 않거나(0) 둘 중 하나인 반면 fractional은 물건을 분할할 수 있다는 점이 달라요.아래에서 천천히 알아보겠습니다.분할가능한 배낭 문제 (Fractional KnapSack Problem)분할가능한 배낭 문제에서는 주어진 아이템을 더 작은 무게..

안녕하세요. 오늘은 C++에서 최대공약수와 최소공배수를 구해보겠습니다. C++에서 사용하는 정형적인 최대공약수 알고리즘은 유클리드 호제법이 있는데요.호제법은 공약수를 구하는 알고리즘이라는 뜻이에요. 오늘은 유클리드 호제법을 자세하게 분석하기 보다는 동작을 살펴보면서 코드로 옮기는 것만 설명해볼건데요.암호학에서는 자주 사용하는 알고리즘이니 관심이 있으시다면 찾아보는 것도 괜찮을 것 같습니다.최대공약수최대공약수는 정수들의 공통적인 약수 중에서 가장 큰 놈을 말합니다.https://ko.wikipedia.org/wiki/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98 최대공약수 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 수론에서, 정수들의 공약수(公約..

안녕하세요. 오늘은 C++에서 소수를 판별하는 방법들을 알아볼게요. 소수는 1과 자기 자신만을 약수로 가지는 수입니다. 대신 1은 소수가 아니에요. 소수 판별은 가끔 코테에서 나올 때 자신이 없어지는 유형 중 하나인데요.C++에서는 정형적인 해결 방법이 있으니 기억해두면 유용할 것 같습니다. 방법 1. 직관적으로 구하기 ( O(N) )쉽게 떠올릴 수 있는 방법이에요.  일일이 나눠주면서 약수가 있는지 검사하는 방법입니다. 바로 코드를 볼게요.bool isPrime(int n) { if (n == 1) return false; for (int i = 2; i  방법 2. 제곱근 이용하기 ( O(√N) )위와 같은 과정을 거치면서 실행시간을 더 줄이는 방법이 있습니다. 제곱근을 이용하는 건데요. 어떤 수의..