일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 쿠링
- Rxjava
- 백준
- Kotlin
- textfield
- MyVoca
- 코드포스
- livedata
- activity
- Python
- AWS
- Gradle
- 프로그래머스
- boj
- androidStudio
- 암호학
- android
- relay
- GitHub
- TEST
- Codeforces
- Compose
- architecture
- 코루틴
- Coroutine
- Coroutines
- ProGuard
- pandas
- MiTweet
- Hilt
- Today
- Total
목록boj (89)
이동식 저장소
펜윅 트리를 모른다면 다음 글을 참고하자. 펜윅 트리 (바이너리 인덱스 트리) 블로그: 세그먼트 트리 (Segment Tree) 에서 풀어본 문제를 Fenwick Tree를 이용해서 풀어보겠습니다. Fenwick Tree는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. Fenwick Tree를 구현하려면, 어떤 수 X www.acmicpc.net 기본적인 펜윅 트리는 점 업데이트, 구간 쿼리를 각각 로그 시간에 수행할 수 있다. 하나의 수를 로그 시간에 업데이트하고, 구간의 합을 로그 시간에 구할 수 있다는 뜻이다. 반대로 구간 업데이트와 점 쿼리도 각각 로그 시간에 수행할 수 있다. 어떻게요? 수열 $A$에 대해 구간 업데이트와 점 쿼리를 수행해야 한다고 가정하자. 수열 $..
10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 2042번 구간 합 구하기 1에서는 수가 하나씩 바뀌므로 세그먼트 트리 또는 펜윅 트리를 이용하여 문제를 풀 수 있다.. 그런데 이 문제에서는 $[l,~r]$ 구간의 값이 바뀐다. 따라서 일반적인 세그먼트 or 펜윅 트리를 이용해 값을 갱신하면 한 번의 갱신에 최대 $O(NlogN)$의 시간이 걸리고, 시간 초과를 받을 수밖에 없다. 일반적으로 쿼리 문제에서는 쿼리를 로그 시간 안에 해결해야 한다...
11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 원래 건물을 잇는 모든 길은 양방향이었는데, 공사 때문에 몇몇 길이 일방통행으로 바뀌어 버렸다. 이제 두 건물 사이를 오가려면 일방통행 길을 최소한 몇 개나 양방향으로 바꿔야 하는지 알아보자. 흠.. 그런데 쿼리가 최대 3만 개 주어진다. 매번 길을 탐색하면 시간 초과가 날 것 같다. 따라서 모든 $s,~e$ 쌍에 대해 정답을 미리 구해 놓아야 한다. 풀이 다익스트라 또는 플로이드 와샬 알고리즘으로 풀 수 있다. 두 방법 모두 주어지는 단방향 간선 $u,~v$에..
2248번: 이진수 찾기 N(1 ≤ N ≤ 31)자리의 이진수가 있다. 이러한 이진수 중에서, L(1 ≤ L ≤ N)개 이하의 비트만 1인 것을 크기 순으로 나열했을 때, I번째로 나오는 이진수를 구해내는 프로그램을 작성하시오. 이진수 www.acmicpc.net $N$자리의 이진수 중에서 1인 비트가 $L$개 이하인 이진수를 오름차순으로 정렬했을 때, $I$번쨰 이진수를 구하는 문제이다. 이진수는 0으로 시작할 수 있음에 주의하자. 이진수를 결정하려면 이진수의 각 자리가 0인지 1인지 결정해야 한다. 현재 자리가 0과 1 중 무엇인지 결정하려면, 현재 자리를 0(또는 1)로 결정했을 때 몇 개의 이진수를 만들 수 있는지 알아야 한다. 문제를 쉽게 만들기 위해, $N$자리의 이진수를 만드는 데 1을 정확..
이루어지지 않는 꿈인줄만 알았던 6++ 달성. 6++부터는 플레 문제가 많이 나오는데, 모르면 배운다는 마인드로 철저하게 시간 제한 걸고 풀었다. 2시간 안에 못 풀면 30분마다 힌트 하나씩 보는 식으로. 새로운 알고리즘 Trie를 배웠다! 어려운 문제일 줄 알았는데 생각보다 간단한 알고리즘이었다. 구현도 한 번만에 성공했고. 그런데 마지막 문제가 진짜 전설이었다;; Trie 문제인데, 시간 초과와 메모리 초과 쌍검으로 때리니까 버틸 수가 없다;;;;;; 19585번: 전설 Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수 www.acmicpc...