일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- MiTweet
- AWS
- Kotlin
- pandas
- TEST
- architecture
- Coroutine
- livedata
- Python
- NGINX
- ProGuard
- android
- Compose
- Coroutines
- Codeforces
- 코드포스
- Rxjava
- 백준
- relay
- Hilt
- 암호학
- MyVoca
- androidStudio
- 쿠링
- GitHub
- Gradle
- boj
- 코루틴
- 프로그래머스
- textfield
- Today
- Total
목록Problem Solving (108)
이동식 저장소
이거 하나 푸느라 4일동안 다른 생각을 못 했다. 지금의 나는 이 정도인 것 같다. ㅠㅠ 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주어진다. 이는 A번 문제는 B번 문제보다 먼저 푸는 것이 좋다는 의미이다. 항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 가장 쉬운 문제부터 가장 어려운 문제까지 푸는데, '먼저 풀면 좋은 문제'를 고려해야 한다. 제일 먼저 떠오른 해결책은 dfs였다. 1번 문제부터 차례대로 '먼저 풀면 좋은 문제'를 난이도 순으로 모두 푼 다음 본 ..
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번째 부모"를 찾은 것처럼, "이 정점부터 ..