Recent Posts
Recent Comments
Archives
- Today
- Total
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- Visual Studio Code
- BFS
- filezila server
- 삼성 알고리즘
- dynamic programming
- ubuntu
- 동적계획법
- cube sound
- 시뮬레이션
- 다이나믹 프로그래밍
- apache
- 공연
- baek joon
- 백준
- dp
- 넓이 우선 탐색
- dfs
- Algorithm
- 춤
- 그래프
- 비주얼 스튜디오 코드
- C++
- simulation
- 아파치
- sw expert academy
- Graph
- 알고리즘
- 배틀
- BOJ
- 우분투
Link
댄코 - 댄싱코딩
[9251] LCS 본문
풀기전에 '뇌를 자극하는 알고리즘'이라는 책에서 예제를 본적이 있어 비교적 쉽게 풀 수 있었다.
using namespace std;
int main(){
char N1[1001];
char N2[1001];
int d[1002][1002]={};
scanf("%s",N1);
scanf("%s",N2);
int len1 = strlen(N1);
int len2 = strlen(N2);
for(int i = 0;i<=len1;i++){
d[i][0] = 0;
}
for(int i = 0;i<=len2;i++){
d[0][i] = 0;
}
for(int i = 1;i<=len1;i++){
for(int j = 1;j<=len2;j++){
if(N1[i-1] == N2[j-1]){
d[i][j] = d[i-1][j-1]+1;
}else{
d[i][j] = max(d[i-1][j],d[i][j-1]);
}
}
}
printf("%d\n",d[len1][len2]);
}
점화식은 다음과 같다.
두 문장의 길이가 모두 0일때 --- d[i][0], d[0][i] = 0
두 문장의 맨 끝 글자가 같을때 --- d[i][j] = d[i-1][j-1]+1
두문장의 길이가 0이 아니고 끝글자가 다를때 --- d[i][j] = max(d[i-1][j], d[i][j-1])
두문장의 맨 끝글자가 같으면 두 문장의 전 글자까지 계산한 d[i-1][j-1]에다 1을 더하면 d[i][j]가된다.
두문장의 끝글자가 다르면 문자1의 맨 끝글자와 문장2의 문장 끝에서 두번째 글자가 같을 수 있고 그 반대의 순서도 가능하므로
둘중 큰값을 d[i][j]에 넣는다.
'코딩 > 알고리즘' 카테고리의 다른 글
[2156] 포도주 시식 (0) | 2017.07.01 |
---|---|
[2293] 동전1 (0) | 2017.07.01 |
[2965] 캥거루 세마리 (0) | 2017.06.30 |
[1463] 1로 만들기 (0) | 2017.06.30 |
[2579] 계단오르기 (0) | 2017.06.30 |
Comments