devbelly

문제 www.acmicpc.net/problem/12014 알고리즘 LIS, 이분 탐색 풀이 $N$일 동안의 주가가 주어졌을 때, $K$일 동안 첫날을 제외하고 직전 날 산 주가보다 비싸게 구매할 수 있는지를 묻고 있습니다. 유명한 Longest Increasing Subsequence 문제입니다. 다이나믹 프로그래밍으로 $O(N^2)$에 해결 가능합니다. 하지만 주어지는 테스트케이스가 100개에 $N$제한이 1만이므로 해당 알고리즘을 사용하면 시간 초과가 발생합니다. 처음에 정렬된 배열을 하나 갖고 시작합니다. 처음이므로 정렬된 빈 배열을 갖고 있습니다. $N$개의 값을 순차적으로 보며 해당 값을 정렬된 배열 어디에 위치한지 찾습니다. 정렬된 배열에서 위치를 찾는 것이므로 이분 탐색으로 찾을 수 있습니..

함수 템플릿 함수 템플릿은 함수의 일반화 서술입니다. int나 double형과 같은 구체적인 데이터형을 포괄하는 일반형으로 함수를 정의합니다. 어떠한 데이터형을 템플릿에 매개변수로 전달하면 컴파일러는 그 데이터형에 맞는 함수를 생성합니다. 필요성 기존에 int 두 개를 더하는 함수를 작성했다고 합시다. 그리고 double형 두 개가 주어졌을 때 더하려고 합니다. 함수 오버로딩을 통해 매개변수 리스트를 달리하여 해결할 수도 있습니다. 하지만 이러한 상황이 반복적으로 일어난다면 함수 작성 도중 실수할 수도 있을뿐더러 시간 또한 낭비됩니다. c++ 함수 템플릿 기능은 이 과정을 자동화해줍니다. 다음은 함수 템플릿을 설정하는 코드입니다. template Any custom_add(Any a, Any b) { r..

디폴트 매개변수 디폴트 매개변수는 함수 호출에서 실제 매개변수를 생략했을 경우에 실제 매개변수 대신 사용되는 값입니다. 호출 시 매개변수의 개수가 다르더라도 결국 같은 함수를 호출하는 것입니다. #include using namespace std; int PLUS(int a, int b = 1) { return a + b; } int main() { int x = 5; int y = 7; cout

일반적인 함수의 작동 컴파일 작업의 최종 산출물은 기계어 명령으로 이루어진 실행 프로그램입니다. 프로그램 실행 시 운영체제는 이 명령들을 컴퓨터의 메모리에 로드하고 각 명령들은 자신의 주소를 갖게 됩니다. 프로그램에서 함수의 호출이 이루어진다면 함수 호출 명령 다음에 있는 명령의 주소를 메모리에 저장하고 스택에 매개변수를 복사합니다. 그 후 호출한 함수가 시작되는 위치로 이동하게 됩니다. 호출된 함수는 실행되고 자신의 리턴 값을 레지스터에 복사하고 저장해두었던 주소의 명령으로 돌아오게 됩니다. Inline 함수의 필요성 및 특징 이렇게 자신이 돌아올 위치를 기억하고 점프를 수행했다가 돌아오는 행동은 함수를 사용하는데 시간이 많이 걸립니다. Inline 함수는 컴파일러가 함수호출 부분을 그에 대응되는 함수..

문제 www.acmicpc.net/problem/10573 알고리즘 DP 풀이 해당 수가 증가하는 수 인지 판별하고, 증가하는 수라면 그 수보다 작은 증가하는 수를 찾는 문제입니다. 증가하는 수를 판별하는 건 어렵지 않으니 다음 문제인 개수를 찾는 문제를 생각해봅시다. 증가하는 수의 구조는 최적 부분 구조를 만족하게 됩니다. 현재의 수가 증가하는 수라면 맨 앞자리 하나를 제거한 수 또한 증가하는 수를 만족하기 때문입니다. $cache [i][j]$= j부터 증가하는 수를 i자리 만들었을 때, 가능한 개수 $cache [i][j]$를 갖고 갱신할 수 있는 상태는 j이하의 수를 맨 앞자리에 붙이는 것입니다. 즉 다음 상태는 $cache [i+1][k]$ (단, k는 j이하의 수이다) 입니다. 나머지의 아이디..

문제 www.acmicpc.net/problem/17365 알고리즘 트라이 + DP 풀이 문래빗어 사전에 적혀있는 단어수와 그 단어들이 주어졌을 때, 해석하려는 문자열의 가능한 경우의 수를 묻고 있습니다. 해석하려는 문자열을 $str$이라 하겠습니다. (아래에서 언급하는 $str [a:b]$ 는 $str$ a번째 인덱스부터 b번째 인덱스까지의 부분 문자열입니다) $cache [i]$= i+1번째 문자열까지 해석했을 때, 가능한 경우의 수 $cache [i+1]$은 다음 상태들의 합입니다. $cache [i]$에서 가능한 개수 * 단어들 중 $str [i+1]$와 매칭 가능한 개수 , cache [i-1] * 단어들 중 $str [i:i+1]$와 매칭 가능한 개수... (매칭이 가능하다는 것은 문래빗어 정..

문제 www.acmicpc.net/problem/17291 알고리즘 DP 풀이 기준년도 1년 2월에 개체가 +1 생겼을 때, $N$년도후의 개체수를 묻고 있습니다. 홀수년도에 태어난 개체는 3번 분열 후 죽고, 짝수년도에 태어난 개체는 4번 분열 후 죽습니다. DP는 최적해를 구할 때(최댓값, 최솟값)뿐만 아니라 순차적으로 진행해나가는 문제에서도 사용할 수 있습니다. $cache[i]$=$i$년도에 존재하는 개체수 위와 같이 설정하고 풀어나가면 됩니다. 코드 #include #define rep(i,n) for(int i=0;i N; cache[0]=cache[1] = 1; for (int i = 1;i < N;++i) { cache[i + 1] = cache[i] * 2; //cache[i-3], ca..

문제 www.acmicpc.net/problem/3257 알고리즘 다이나믹 프로그래밍 풀이 문자열 A,B와 그들을 섞은 C가 주어졌을 때 C의 문자들이 A에 속한 문자인지 B에 속한 문자인지 찾는 문제입니다. 단 C에서 문자열 A와 B는 원래 문자열의 순서를 유지합니다. C에서 A와 B가 원래 순서를 유지하므로 C[1:]로 문제가 작아졌을 때 주어진 A,B 또한 A[1:],B 또는 A,B[1:]로 좁혀나갈 수 있습니다. 부분구조가 성립하므로 다이나믹 프로그래밍을 사용하도록 합시다. $cache[i][j]$ = A문자열을 $i$번째까지 해결하고 B문자열을 $j$번째까지 해결했을 때, 해야하는 선택 즉 $cache[i][j]$값에 1이 들어있다면 $cache[i-1][j]$에서 A를 선택한 것이고, 반대로 ..