일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- android
- Rxjava
- NGINX
- 암호학
- Compose
- boj
- TEST
- androidStudio
- Kotlin
- livedata
- Gradle
- 코드포스
- 쿠링
- architecture
- 백준
- textfield
- Coroutine
- MiTweet
- Coroutines
- Hilt
- GitHub
- 코루틴
- Codeforces
- MyVoca
- pandas
- ProGuard
- AWS
- relay
- 프로그래머스
- Python
- Today
- Total
목록Problem Solving/BOJ (92)
이동식 저장소
LCS를 아시는 분 또는 9251. LCS 문제를 푸신 분들만 이 글을 읽으시기 바랍니다. 문자열 3개의 Longest Common Subsequence를 구하는 문제이다. Substring이 아님에 주의하자. 문자열 2개의 LCS는 DP를 적용하여 해결할 수 있다. 두 문자열 A와 B에 대해 다음과 같이 정의되는 dp 배열을 채우면 A와 B의 LCS와 그 길이를 구할 수 있다. if A[i] == B[j]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) 풀어서 설명해 보면 다음과 같다. 이것이 왜 성립하는지는 알고 있을 것이다. 1) A[i] == B[j] → (LCS의 길이) = (i와 j 이전까지의 L..
800문제 달성 기념. N개의 도시와 N-1개의 도로가 있다. 여기에서 도로망이 트리 형태임을 알 수 있다. 어떤 도시 A와 B를 연결하는 최단 경로는 A~LCA~B이다. 정답을 구하기 위해서는 이 경로에 속한 도로의 길이의 최댓값과 최솟값을 찾으면 된다. LCA를 O(logN)에 찾는 방법은 널리 알려져 있다. 따라서 우리가 할 일은 도로를 탐색하는 것이다. 그런데 도로가 최대 99999개네? 도로를 전부 탐색하면 O(N^2)이 되기 때문에 시간 제한에 걸릴 것 같다. 쿼리 1개당 O(logN) 안에 처리해야 할 것 같다. 답은 이미 나와 있다. LCA를 O(logN)에 구한 것처럼 도로도 O(logN)에 탐색하면 된다. LCA를 탐색할 때 "이 정점의 2^i번째 부모"를 찾은 것처럼, "이 정점부터 ..