이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 111 번째 글 입니다.

  • Part 1 - 백준(1003번): 피보나치 함수
  • Part 2 - 백준(1010번): 다리놓기
  • Part 3 - 백준(1012번): 유기농 배추
  • Part 4 - 백준(10159번): 저울
  • Part 5 - 백준(10164번): 격자상의 경로
  • Part 6 - 백준(1018번): 체스판 다시 칠하기
  • Part 7 - 백준(1018번): 체스판 다시 칠하기
  • Part 8 - 백준(1022번): 소용돌이 예쁘게 출력하기
  • Part 9 - 백준(10775번): 공항
  • Part 10 - 백준(10816번): 숫자 카드2
  • Part 11 - 백준(10816번): 숫자카드 2
  • Part 12 - 백준(10819번): 차이를 최대로
  • Part 13 - 백준(10830번): 행렬 곱셈
  • Part 14 - 백준(10844번): 쉬운 계단수
  • Part 15 - 백준(10868번): 최소값
  • Part 16 - 백준(1092번): 배
  • Part 17 - 백준(11003번): 최솟값 찾기
  • Part 18 - 백준(1102번): 발전소
  • Part 19 - 백준(11048번): 이동하기
  • Part 20 - 백준(11053번): 가장 긴 증가하는 부분 수열
  • Part 21 - 백준(11054번): 가장 긴 바이토닉 부분 수열
  • Part 22 - 백준(11055번): 가장 긴 증가하는 부분 수열2
  • Part 23 - 백준(11057번): 오르막 수
  • Part 24 - 백준(1120번): 문자열
  • Part 25 - 백준(11403번): 경로 찾기
  • Part 26 - 백준(11404번): 플루이드
  • Part 27 - 백준(1149번): RGB 거리
  • Part 28 - 백준(11559번): puyo puyo
  • Part 29 - 백준(11655번): ROT13
  • Part 30 - 백준(1167번): 트리의 지름
  • Part 31 - 백준(11722번): 가장 감소하는 부분 수열
  • Part 32 - 백준(12015번): 가장 긴 증가하는 부분 수열(LIS) 2
  • Part 33 - 백준(12851번): 숨바꼭질2
  • Part 34 - 백준(12852번): 1로 만들기 2
  • Part 35 - 백준(12865번): 평범한 배낭
  • Part 36 - 백준(1300번): K번째 수
  • Part 37 - 백준(1325번): 효율적인 해킹
  • Part 38 - 백준(13549번): 숨바꼭질3
  • Part 39 - 백준(13913번): 숨바꼭질4
  • Part 40 - 백준(14002번): 가장 긴 증가하는 부분 수열 4
  • Part 41 - 백준(1431번): 시리얼 넘버
  • Part 42 - 백준(1436번): 영화감독 숌
  • Part 43 - 백준(14499번): 주사위 굴리기
  • Part 44 - 백준(14888번): 연산자 끼워넣기
  • Part 45 - 백준(14889번): 스타트와 링크
  • Part 46 - 백준(14891번): 톱니바퀴
  • Part 47 - 백준(15658번): 연산자 끼워넣기 2
  • Part 48 - 백준(15686번): 치킨 배달
  • Part 49 - 백준(1697번): 숨바꼭질
  • Part 50 - 백준(1697번): 숨바꼭질
  • Part 51 - 백준(1707번): 이분 그래프(Bipartite Graph)
  • Part 52 - 백준(1708번): 볼록 껍질
  • Part 53 - 백준(17136번): 색종이 붙이기
  • Part 54 - 백준(1717번): 집합의 표현
  • Part 55 - 백준(17298번): 오큰수
  • Part 56 - 백준(17626번): Four Squares
  • Part 57 - 백준(18870번): 좌표 압축
  • Part 58 - 백준(1890번): 점프
  • Part 59 - 백준(1918번): 후위 표기식
  • Part 60 - 백준(1929번): 소수 구하기
  • Part 61 - 백준(1963번): 소수 경로
  • Part 62 - 백준(1965번): 상자넣기
  • Part 63 - 백준(1976번): 여행가자
  • Part 64 - 백준(1987번): 알파벳
  • Part 65 - 백준(1992번): 쿼드트리
  • Part 66 - 백준(2003번): 수들의 합2
  • Part 67 - 백준(20040번): 사이클 게임
  • Part 68 - 백준(2042번): 구간 합 구하기
  • Part 69 - 백준(2108번): 통계학
  • Part 70 - 백준(2110번): 공유기 설치
  • Part 71 - 백준(2156번): 포도주 시식
  • Part 72 - 백준(2193번): 이친수
  • Part 73 - 백준(2231번): 분해합
  • Part 74 - 백준(2250번): 트리의 높이와 너비
  • Part 75 - 백준(2293번): 동전 1
  • Part 76 - 백준(2294번): 동전 2
  • Part 77 - 백준(2343번): 기타 레슨
  • Part 78 - 백준(2468번): 안전 영역
  • Part 79 - 백준(2512번): 예산
  • Part 80 - 백준(2529번): 부등호
  • Part 81 - 백준(2565번): 전깃줄
  • Part 82 - 백준(2581번): 소수
  • Part 83 - 백준(2583번): 영역구하기
  • Part 84 - 백준(2630번): 색종이 만들기
  • Part 85 - 백준(2644번): 촌수계산
  • Part 86 - 백준(2667번): 단지번호붙이기
  • Part 87 - 백준(2751번): 수 정렬하기 2
  • Part 88 - 백준(2798번): 블랙잭
  • Part 89 - 백준(2904번): 수학은 너무 쉬워
  • Part 90 - 백준(2986번): 파스칼
  • Part 91 - 백준(3015번): 오아시스 재결합
  • Part 92 - 백준(3190번): 뱀
  • Part 93 - 백준(3190번): 벽 부수고 이동하기
  • Part 94 - 백준(4195번): 친구 네트워크
  • Part 95 - 백준(4948번): 베르트랑 공준
  • Part 96 - 백준(4963번): 섬의 개수
  • Part 97 - 백준(4991번): 로봇 청소기
  • Part 98 - 백준(5373번): 큐빙
  • Part 99 - 백준(5437번): 불
  • Part 100 - 백준(6171번): 땅따먹기
  • Part 101 - 백준(6603번): 로또
  • Part 102 - 백준(6603번): 로또
  • Part 103 - 백준(7562번): 나이트의 이동
  • Part 104 - 백준(7568번): 덩치
  • Part 105 - 백준(7576번): 토마토
  • Part 106 - 백준(7579번): 앱
  • Part 107 - 백준(7785번): 회사에 있는 사람
  • Part 108 - 백준(9012번): 괄호
  • Part 109 - 백준(9020번): 골드바흐의 추측
  • Part 110 - 백준(9184번): 신나는 함수 실행
  • Part 111 - This Post
  • Part 112 - 백준(9421번): 소수상근수
  • Part 113 - 프로그래머스: 가장 큰 정사각형 찾기
▼ 목록 보기

목차

▼ 내리기

골드5 : 동적계획법 문제이다.

풀이

dp[i][j] = (i, j)번째 수열의 원소를 포함했을 때, 가지는 최장 수열의 길이

dp[i][j] = max(dp[i-1][j-1]~dp[0][0])

하지만 실제 구현을 이런식으로 하게 되면, $O(n^4)$ 로 시간 초과가 날 것이다. 따라서 i번째 원소를 업데이트 한 이후에, dp의 값이 사용이 되는지 확인할 필요가 있다.

무조건적으로 이전 원소(i)를 본 뒤에는 값이 큰 상태로 유지되며, 다음 상태의 최장 길이는 이 값으로부터 도출될 수 밖에 없다. 따라서 최적화가 가능하다.

Code


#include <iostream>
#include <string>
using namespace std;
int dp[1001] = {0,};

int main(){
    string a, b;
    cin >> a >> b;
    
    for (int i = 0; i < a.size(); i++) {
        int temp[1001];
        for (int j = 0; j < b.size(); j++) {
            temp[j] = dp[j];
        }
        for (int j = 0; j < b.size(); j++) {
            if (a[i] == b[j]) {
                int maxvalue = 0;
                for (int k = 0; k < j; k++) {
                    if (temp[k] > maxvalue) {
                        maxvalue = temp[k];
                    }
                }
                
                dp[j] = maxvalue+1;
                
            }
        }
//        for (int k = 0; k < b.size(); k++) {
//            cout << dp[k] << " ";
//        }
//        cout << '\n';
    }
    
    int ans = 0;
    for (int i = 0; i < b.size(); i++) {
        if (ans < dp[i]) {
            ans = dp[i];
        }
    }
    
    cout << ans << '\n';
    return 0;
}

Reference

백준(9251번) - LCS