일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- livedata
- Hilt
- 암호학
- MiTweet
- android
- architecture
- Compose
- textfield
- boj
- Gradle
- 백준
- pandas
- GitHub
- androidStudio
- 쿠링
- Codeforces
- Coroutine
- 코드포스
- 프로그래머스
- MyVoca
- Coroutines
- relay
- AWS
- Rxjava
- Python
- NGINX
- Kotlin
- TEST
- 코루틴
- ProGuard
- Today
- Total
목록Problem Solving (108)
이동식 저장소
코로나 새내기들에게 꼭 필요한 문제 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 학교 지도가 연결 그래프로 주어진다. 학교의 모든 건물을 탐방하는 경로 중 피로도가 최대일 때와 최소일 때의 차이를 구해야 한다. 피로도는 지나간 오르막길의 개수의 제곱으로 계산하므로, 오르막길을 가장 많이(또는 적게) 지나가는 경우를 구해야 한다. 건물 $N$개와 입구까지 총 $N+1$개의 노드를 연결하는 트리에는 간선이 $N$개 존재한다. 지문은 거창하지만, 그냥 최소 스패닝 트리 문제이다..
골드 재활 중~ 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 대충 쓰레기를 최대한 피해서 목적지에 도달하면 되는 문제이다. 그런데 지문이 진짜 쓰레기 수준이라 제대로 읽지 않으면 틀리기 매우 쉽다. 함께 자세히 읽어 보자. 쓰레기를 밟지 않는 것을 우선으로 해야 한다. 쓰레기 옆을 지나가는 건 그 다음이다. 쓰레기 옆을 지나가는 행동의 기준은 a) 비어있는 칸을 지나가는데 b) 그 칸의 상하좌우에 쓰레기가 있는 경우이다. 따라서 쓰레기가 있는 칸 옆에 쓰레기가 있다면 쓰레기 옆..
거의 1달만에 푸는 문제라 쉬운 걸로 풀어봤다. 19582번: 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여 2220년에도 “2220 신촌지역 대학생 프로그래밍 대회 동아리 연합 수시 대회”가 성공적으로 개최된다. SUAPC은 이제 모든 학생이 즐길 수 있도록 다양한 난이도의 대회가 1년에 수시로 열리며, www.acmicpc.net $N$개의 대회가 주어진다. 지금까지 모은 상금이 $x[i]$원 이하라면 대회에 참여할 수 있고, $x[i]$원보다 많다면 대회에 참여할 수 없다. 이때 적어도 $N-1$개의 대회에 참여할 수 있는지 구하는 문제이다. 시간 초과 풀이 적어도 $N-1$개의 대회에 참여한다는 말은 $N-1$개 또는 $N$개의 대회에 참여한다는 말과 같다. 일단 $N$개의 대회에 모두 ..
단계별로 풀어보기 따라가는 중. 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net $N$명의 사람과 $N$개의 일이 있다. $i$번 사람이 $j$번 일을 할 때의 비용 $D[i][j]$가 주어질 때, 비용을 최소로 하면서 각 사람에게 하나의 일을 할당해 보자. 딱 봐도 dp이고, 선택된 일의 집합을 표현해야 하므로 비트마스크 dp를 적용할 수 있다. 마침 $N$이 20으로 매우 작기도 하고. 현재 남아있는 일의 집합을 $j$(비트마스크)일 때 $i$번 사람에게 일을 할당하여 얻을 수 있는 비용의 ..
펜윅 트리를 모른다면 다음 글을 참고하자. 펜윅 트리 (바이너리 인덱스 트리) 블로그: 세그먼트 트리 (Segment Tree) 에서 풀어본 문제를 Fenwick Tree를 이용해서 풀어보겠습니다. Fenwick Tree는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. Fenwick Tree를 구현하려면, 어떤 수 X www.acmicpc.net 기본적인 펜윅 트리는 점 업데이트, 구간 쿼리를 각각 로그 시간에 수행할 수 있다. 하나의 수를 로그 시간에 업데이트하고, 구간의 합을 로그 시간에 구할 수 있다는 뜻이다. 반대로 구간 업데이트와 점 쿼리도 각각 로그 시간에 수행할 수 있다. 어떻게요? 수열 $A$에 대해 구간 업데이트와 점 쿼리를 수행해야 한다고 가정하자. 수열 $..