이우의 개발일지

백준 9251번 LSC 문제   문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.예제 입력 1 ACAYKPCAPCAK예제 출력 1 4  LCS 문제 풀이 이 문제를 처음 봤을 때, LCS. 즉, 최장 공통 부분수열(Longest Common Subsequence)을 말하는 것이기 때문에 주어진 예제에 어떻게 해야 최장 문..

DP, 다이나믹 프로그래밍이란? -> 하나의 문제를 단 한번만 풀도록 하는 알고리즘 설계 기법입니다. Why DP를 사용할까?그냥 사용하면 사실 재귀방식과 똑같이 사용할 수 있다. 하지만, 일반적인 코딩테스트 같은 경우 시간제한이 걸려있기 때문에 동일한 작은 문제를 여러번 풀면 무조건적으로 시간초과가 뜨게 된다.  예를 들어, 피보나치 수열을 그 예로 들 수 있다.#include int dp(int x){ if( x == 1) return 1; if( x == 2) return 1; return dp(x - 1) + dp ( x - 2); } 위 처럼 코딩을 하게 된다면, 50번째만 가도 굉장히 오래 걸리게 된다.  #include int d[100];int dp(int x){ ..

소프티어 징검다리 문제  입력예제1 5 3 2 1 4 5 출력예제1 3 징검다리 풀이 이 문제는 최장 증가 부분 수열 알고리즘을 이용해서 풀이를 하는 문제이다.  최장 증가 부분 수열 알고리즘(LIS)이란? 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 합니다. LIS 알고리즘에는 DP 알고리즘을 사용하는 것이 유리하다. 아래 방식처럼 전체의 값을 1로 정의하고 만약 원래 값보다 체크하는 값이 크다면 max를 써서, 값을 새로 넣어주는 식으로 정의할 수 있다. for (int k=0; k 처음에는 이 문제를 재귀함수를 써서 사용을 했는데, 시간 복잡도가 O(2^n)이 나와서 시간초..