일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
Tags
- 알고리즘 공부
- 알고리즘트레이닝
- 자바
- 책을알려주는남자
- 책알남
- C
- 채권
- 화장품
- 돈
- C++
- 투자
- 다독
- 주식
- 프로그래머스 알고리즘 공부
- 독후감
- 알고리즘공부
- JavaScript
- 지혜를가진흑곰
- algorithmStudy
- 재테크
- Java
- 자바스크립트
- algorithmTest
- 경제
- 독서
- algorithmtraining
- 서평
- 성분
- 백준알고리즘
- 프로그래밍언어
Archives
- Today
- Total
반응형
목록2025/01 (1)
탁월함은 어떻게 나오는가?
[Algorithm] 최장 공통 부분 수열(Longest Common Subsequence)로 공부하는 동적 프로그래밍(Dynamic Programming)
오늘은 LCS 알고리즘을 공부해보겠다.LCS 문제는 두 문자열의 부분 수열을 비교하는 문제로, DP를 활용하여 해결하는 문제이다. DP를 사용하는 이유LCS 문제에서 DP가 적절한 이유는 중복되는 부분 문제와 최적 부분 구조를 가지기 때문이다.1. 중복되는 문제- 두 문자열을 비교하다 보면, 같은 부분 문자열을 여러 번 계산하게 된다. 예를 들어, DP배열을 사용하지 않는다면 dp[i][j]를 계산할 때 dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1] 같은 부분을 반복적으로 계산해야 한다.- DP는 이러한 중복 계산을 한 번만 계산하고 저장하여, 다시 계산하지 않도록 하는게 큰 아이디어이다. 이로 인해서 계산량을 크게 줄일 수 있다.2. 최적 부분 구조- 부분 문제들의 ..
[Snow-ball]프로그래밍(컴퓨터)/Algorithm
2025. 1. 1. 11:52
반응형