Plite
전자오락 공방
Plite
전체 방문자
오늘
어제
  • 분류 전체보기 (274)
    • 프로젝트 (18)
      • 완성 프로젝트 (3)
      • 프로젝트 진행 내역 (15)
    • 공부 및 정리 (241)
      • 백준 코드 (222)
      • C++ (8)
      • DirectX (2)
      • Unreal Engine (6)
      • 프로그래밍 패턴 (3)
    • 기타 (12)
      • 기타 주저리 (10)
    • 게임과 취미 (1)
    • 대문 (1)

블로그 메뉴

  • 홈
  • 프로젝트
  • 취미, 일상
  • 백준 프로필

공지사항

  • [Read Me]
  • 제 블로그에 방문하신 것을 환영합니다.

인기 글

태그

  • 최소 스패닝 트리
  • 정수론
  • LCA
  • 투포인터
  • 큐
  • 기하
  • 세그먼트 트리
  • C++
  • 이분탐색
  • 트라이
  • 그래프
  • 스택
  • 구현
  • 브루트포스
  • 트리
  • SCC
  • KMP
  • 위상 정렬
  • 누적합
  • 동적계획법
  • 수학
  • 정렬
  • 백준
  • 조합론
  • 문자열
  • 백트래킹
  • 우선순위큐
  • 분할정복
  • UC++
  • 유니온 파인드

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Plite

전자오락 공방

[C++]백준 - 9251번 문제
공부 및 정리/백준 코드

[C++]백준 - 9251번 문제

2021. 8. 1. 17:30

9251번: LCS (acmicpc.net)

 

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

 

9251번 : LCS


LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

입력


첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

 

출력


첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

 


 

생각해 볼 점


LCS는 매우 유명한 문제입니다.

 

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

 

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전

최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하나가 되기도 한다.) 컴퓨터 과학에

ko.wikipedia.org

 

위의 내용을 참고하여 풀었습니다.

 

코드


#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() 
{
    string A, B;
    cin >> A;
    cin >> B;
    int len_A = A.length();
    int len_B = B.length();
    
    int **dp = new int*[len_A + 1];     //동적 프로그래밍
    
    dp[0] = new int[len_B + 1];
    fill_n(dp[0], len_B, 0);
    for(int i = 1; i < len_A + 1; i++)
    {
        dp[i] = new int[len_B + 1];
        fill_n(dp[i], len_B + 1, 0);
        
        for(int j = 1; j < len_B + 1; j++)
        {
            if(A[i - 1] == B[j - 1])    //더 긴 수열 발견 시 + 1 
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    cout << dp[len_A][len_B];

    
    for(int i = 0; i < len_A + 1; i++) delete[] dp[i];
    delete[] dp;

	return 0;
}

 

그 외


 

저작자표시 (새창열림)

'공부 및 정리 > 백준 코드' 카테고리의 다른 글

[C++]백준 - 1912번 문제  (0) 2021.08.05
[C++]백준 - 11049번 문제  (0) 2021.08.01
[C++]백준 - 7569번 문제  (0) 2021.08.01
[C++]백준 - 1929번 문제  (0) 2021.08.01
[C++]백준 - 7576번 문제  (0) 2021.08.01
    '공부 및 정리/백준 코드' 카테고리의 다른 글
    • [C++]백준 - 1912번 문제
    • [C++]백준 - 11049번 문제
    • [C++]백준 - 7569번 문제
    • [C++]백준 - 1929번 문제
    Plite
    Plite
    개발 일지, 게임 이야기 등을 적어두는 공간입니다.

    티스토리툴바