기본 콘텐츠로 건너뛰기

9251 : LCS (Dynamic Programming) [C,C++]

LCS 문제이다..!!

LCS 문제를 처음 풀어봤는데 DP 기본 문제이지만 이걸 어떻게 DP로 풀어라는 생각에

 DP로는 생각을 못하고 3시간동안 풀다가 계속 오답이 나서 

LCS 알고리즘을 검색해보니 DP로 간단히 풀 수 있었다. 와 이게 이렇게 되네?

처음 문제 풀이 
DP를 이용하지 않음(i와 j의 값을 계속 이동시켜 품) => 정답은 맞지만 시간이 초과됨.

두 번째 생각
스택을 이용해보자.
(i와 j의 값들을 vector<int> 템플릿 스택에 push 후
j가 max_size에 도달하면 pop하여 j의 값을 변경하는 식으로 진행.)
=> 정답은 맞지만 런타임 에러가 뜸.

결국 검색 후,
LCS 알고리즘 사용.
DP를 사용함으로써 메모리는 처음이나 두 번째보다는 많이 잡아먹지만
시간이 무척 빨라짐. 

LCS 알고리즘의 규칙 3가지

하나. 각 행,열이 0번째라면 그 값은 0이다.
둘. 비교하는 글자가 서로 같다면 그 값은 행렬의 ↖에 있는 값의 +1이다.
셋. 비교하는 글자가 서로 같지 않다면 그 값은 왼쪽 값이나 위의 값 중 더 큰 값이다.


if (i == 0 || j == 0)
 this->Array[i][j] = 0;
else
{
 if (A[i - 1] == B[j - 1])
  this->Array[i][j] = this->Array[i - 1][j - 1] + 1;
 else
 {
  this->Array[i][j] = this->Array[i - 1][j] < this->Array[i][j - 1] ? this->Array[i][j - 1] : this->Array[i - 1][j];
 }
}

<핵심 코드>

*Source of the problem = https://www.acmicpc.net/problem/2239

*문제 출처 : BAEKJOON ONLINE JUDGE

라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

11004 : K번째 수 [C++]

# include < iostream > # include < cstdio > # include < algorithm > int main ( ) { int * Number = new int [ 5000000 ] ; int N , K ; scanf ( " %d %d " , & N , & K ) ; for ( int i = 0 ; i < N ; i + + ) scanf ( " %d " , Number [ i ] ) ; std :: sort ( Number , Number + N ) ; printf ( " %d " , Number [ K - 1 ] ) ; return 0 ; }
댓글 쓰기
자세한 내용 보기

1149 : RGB Street Coloring (Dynamic Programming) [C,C++]

The key to this problem lies in understanding the principles. Let me explain the algorithm to solve the problem by using DP. First, you need the same storage space like input data's size. When you draw any color of the nth house, the space will contain the minimum value. If you paint the red in the second house, this value is sum of blue or green of the first house.  You must use DP because you must use the previous value.  Of course, you can also use the recursive algorithm to solve it. But if it gets bigger, it will take a lot of time.  If you paint the red in the nth house in the same way, you should add the lower value of the blue and green of the n-1th house.  Therefore, the minimum value can be found in the value of the storage space (n-1) index. <pesudo code> *Source of the problem =  https://www.acmicpc.net/problem/1149 *문제 출처 : BAEKJOON ONLINE JUDGE
댓글 쓰기
자세한 내용 보기

11478 : 서로 다른 부분 문자열의 개수 (미제) [C++]

# include < iostream > # include < vector > # include < string > using namespace std ; int main ( ) { string sInput ; getline ( cin , sInput , '\n' ) ; int Time = 1 ; int Count = 0 ; vector < string > Storage ; for ( int i = 0 ; i < sInput . size ( ) ; i + + ) { for ( int j = 0 ; ( j + Time - 1 ) < sInput . size ( ) ; j + + ) Storage . push_back ( sInput . substr ( j , Time ) ) ; Time + + ; } bool * Visited = new bool [ Storage . size ( ) * sizeof ( bool ) ] ; for ( int i = 0 ; i < Storage . size ( ) ; i + + ) { Visited [ i ] = true ; for ( int j = 0 ; j < Storage . size ( ) ; j + + ) { if ( i ! = j & & Storage [ i ] = = Storage [ j ] ) { Visited [ i ] = false ; Visited [ j ] = true ; break ; } } } for ( int i = 0 ; i < Storage . size ( ) ; i + + ) if ( Visited [ i ] ) Count ...
댓글 쓰기
자세한 내용 보기