helloahram

1. 문제두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다예를 들어, ACAYKP 와 CAPCAK 의 LCS 는 ACAK 가 된다 2. 요구사항시간 제한 0.1초메모리 제한 256MB 3. 알고리즘 분류* 다이나믹 프로그래밍* 문자열 4. 접근 방식 ㄷㅎ님이 기깔나게 설명해 주신 LCS 알고리즘을 이용하여 풀었다 LCS 알고리즘 정리한 내용 문제에서 문자열 A "ACATKP" 과 문자열 B "CAPCAK" 을 비교한 내용을 표로 정리하면 아래와 같다  0ACAYKP00000000C0011111A0112222P0112223C0122223A0123333K0123344 0 인 행렬을 추가한 이유는 비교 과정에서 대각선 +1 과 왼쪽/ 위쪽 비교를 위해서 추가했고,그렇기 때..

LCS 알고리즘Longest Common Subsequence 최장 공통 부분 수열 또는 Longest Common Substring 최장 공통 부분 문자열  Longest Common Substring두 개 이상의 문자열에서 연속적으로 나타나는 가장 긴 부분 문자열 찾기 부분 문자열은 주어진 문자열의 연속된 부분을 의미한다원래 문자열에서 특정 시작 위치에서부터 특정 끝 위치까지의 모든 문자를 포함한다이는 문자들이 연속적으로 이어져 있어야 하며, 반드시 전체 문자열의 일부분이어야 한다ex. 문자열 abcde 에서 bcd 는 부분 문자열이지만 acd 는 부분 문자열이 아니다 Longest Common Substring 찾는 방법 1. 문자열 A, 문자열 B 를 한 글자씩 비교해 보기2. 두 문자가 다르다면..

1. 문제계단에 쓰여 있는 점수가 주어질 때 점수의 최댓값 구하기1. 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다 2. 연속된 세 개의 계단을 모두 밟아서는 안 된다3. 마지막 도착 계단은 반드시 밟아야 한다2. 요구 사항* 계단의 개수는 300 이하의 자연수 * 계단에 쓰여 있는 점수는 10,000 이하의 자연수 3. 알고리즘 분류* 다이나믹 프로그래밍 4. 접근 방식계단을 올라가는 것만 생각하지 말고, 이미 올라간 상태에서 이전에 내가 어떤 계단을 밟고 올라올지를 생각하는 방식으로 접근한다1) 직전 계단 (n-1) 을 밟고 올라온 경우는 세번 연속 계단을 오를 수 없으므로 그 이전 계단은 n-3 번째 계단이다2) 두 칸 전 (n-2) 계단을 밟고 올라온 경우  i 번째 계단까지 올라왔을 때까지의..