일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- architecture
- 쿠링
- Rxjava
- Coroutines
- 코루틴
- Codeforces
- 백준
- ProGuard
- 코드포스
- MyVoca
- Python
- Coroutine
- TEST
- pandas
- android
- MiTweet
- 암호학
- NGINX
- Gradle
- textfield
- boj
- GitHub
- Hilt
- Compose
- androidStudio
- relay
- AWS
- Kotlin
- livedata
- 프로그래머스
- Today
- Total
목록Problem Solving (108)
이동식 저장소
코드포스에는 왜 이리 지루한 사람이 많은가? Problem - 455A - Codeforces codeforces.com 지문이 헷갈리기 쉽게 쓰여 있어서, 일단 문제를 정확히 이해하자. $n$개의 정수 $a_{1},~a_{2},~\cdots,~a_{n}$이 있다. 임의의 $a_{k}$를 골라 지우고, 모든 $a_{k}-1$과 $a_{k}+1$을 지운다. 예를 들어 $2$를 하나 지웠다면 모든 $1$과 $3$도 지워야 한다. 이때 얻을 수 있는 점수는 $a_{k}$점이다. 수를 하나 지우면 양 옆의 수도 없어져서 골치아픈 문제이다. 만약 $a_{k}-1$만 지워지는 조건이었다면 골드 하위 수준의 문제였을 것이다. 그러나 아주 간단한 제한을 걸면 이 문제 역시 골드 하위급으로 만들어버릴 수 있다. 바로 수..
Problem - 327A - Codeforces codeforces.com 0과 1로 이루어진 길이 $N$짜리 수열이 있다. 이 수열에서 연속된 구간 $[i,~j]$를 단 한 번만 골라 구간 안에 있는 모든 0을 1로, 1을 0으로 뒤집는다. 뒤집은 후에 1은 최대 몇 개 있을 수 있을까? 이 문제는 제한이 매우 작아서 $O(N^{3})$에도 풀 수 있지만, $N$이 커지더라도 풀 수 있는 방법을 생각해 보자. Maximum Subarray 먼저 Maximum subarray라는 개념을 알아야 한다. Maximum subaray는 배열의 끝 칸에서 끝나는 부분합 중 최댓값을 구하는 알고리즘이다. 식으로 쓰면 $ms[i]$는 $[1,~i]$ 구간에서 $i$를 포함하는 부분합 중 최댓값을 의미한다. 배열 ..
1615번: 교차개수세기 첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j번 정점을 연결하는 간선이 있다는 의미이다. www.acmicpc.net 뭔가 많이 본 듯한 문제이다. 어디서 봤나 했더니 2568번 전깃줄 문제와 매우 유사하다. 물론 풀이가 유사하다는 건 아니고 그림이 비슷하다는 소리. 이 문제에서는 전깃줄이 교차하는 횟수를 세어야 한다. 문제에 두 전깃줄이 교차하는 조건이 주어져 있는데, 계산의 편의를 위해 왼쪽에 있는 정점을 오름차순으로 살펴보면서, 각 정점의 전깃줄이 다른 전깃줄과 몇 번 교차하는지 계산해 보자. 왼쪽 정점 $i$와 오른쪽 정점 $j$에 연결된 전깃줄을 $(i, ~..
14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 블록 사이에 빗물이 얼마나 고이는지 구하는 문제이다. 2차원 공간의 바닥은 막혀 있다고 가정한다. 바닥이 막혀 있으므로 물이 빠져나갈 수 있는 방향은 왼쪽 또는 오른쪽이다. 설마 물이 위로 증발하지는 않을 것이고.. 그렇다면 블럭을 제외한 모든 빈 공간을 물로 채운 후, 왼쪽 또는 오른쪽으로 빠져나가는 물을 제외하면 된다. 2차원 공간에 다음과 같이 물을 채운다. 검은색은 블록이다. 왼쪽과 오른쪽으로 물이 얼마나 빠져나갈 수 있는지 시뮬레이션해 ..
어떻게 문제 제목이.. 20925번: 메이플스토리 첫째 줄 사냥터 수 $N$ ($1 \le N \le 200$)과 방학 기간을 분 단위로 나타낸 $T$ ($1 \le T \le 1\,000$)가 주어진다. 다음 $N$개의 줄에는 $i$번째 사냥터의 특징인 입장에 필요한 최소 경험치 $c_i$와 $1$분마 www.acmicpc.net 딱 봐도 DP 문제이다. DP 식만 잘 정의하면 된다. 사냥터의 번호를 $i$, 현재 시간을 $j$라 할 때, 다음 두 가지의 식을 생각해볼 수 있다. $dp[i][j]$: 지금부터 얻을 수 있는 경험치의 최댓값 $dp[i][j]$: 현재까지 얻을 수 있었던 경험치의 최댓값 저장된 값이 미래의 값인지, 과거의 값인지가 다르다. 처음에는 1번 식으로 풀어보려 했으나, 사냥터에 ..