백트래킹2

• 

  [Algorithm] LCS(최장 공통 부분 수열) LCS(최장 공통 부분 수열)에 대해서 공부하고 정리한 내용입니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적 부탁드립니다! LCS(최장 공통 부분 수열)이란? '두 문자열을 비교할 때 공통적으로 나타나는 부분 문자열 중 가장 긴 것' 이해를 위해 예를 들어 "ACAYKP" 문자열과 "CAPCAK" 문자열이 주어졌다면, ACAYKP CAPCAK 두 문자열을 비교할 때 공통적으로 나타나는 부분 문자들 중 가장 긴 것은 ACAK이고 길이는 4입니다. LCS(최장 공통 부분 수열) 동작 과정(LCS 길이 구하기) 위에서 예를 든 "ACAYKP"와 CAPCAK" 문자열의 LCS 길이를 구한다면 어떻게 구해야할지 생각해봅시다. ↪ LCS는 다이나믹 프로그래밍을 이용하여 풀 수 있는데, 2차원 배.. Algorithm 2022. 9. 10.

• 

  [BaekJoon 14003번] 가장 긴 증가하는 부분 수열 5(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net [문제 설명] 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는.. PS/BaekJoon 2022. 8. 18.