반응형 세그먼트트리11 백준 12837번 가계부 (Hard) - C++ 풀이 1. 세그먼트 트리를 이용하여 update / sum 쿼리를 수행한다. 1. 세그먼트 트리를 이용하여 update / sum 쿼리를 수행한다. 계속 변화하는 배열에서 구간 쿼리를 수행하는 문제는 세그먼트 트리를 이용하여 해결할 수 있다. 1번 쿼리가 들어올 경우 p번째 값을 x만큼 업데이트하는 연산을, 2번 쿼리가 들어올 경우 p번째 원소부터 q번째 원소까지의 구간합을 구해주면 된다. #include #include using namespace std; typedef long long ll; struct Segtree { int n; vector tree; Segtree (vector& X) { n = X.size(); tree.resize(n*4); init(X, 0, n-1, 1); } void in.. 2022. 6. 29. 백준 5676번 음주 코딩 - C++(cpp) 풀이 1. 구간 내 음수의 개수를 저장하는 세그먼트 트리와 0의 개수를 저장하는 세그먼트 트리를 둔다. 2. 주어진 쿼리의 구간에 0이 하나도 없는 경우, 음수의 개수가 홀수개이면 결과값도 음수, 짝수개이면 양수이다. 3. 주어진 쿼리의 구간에 0이 한 개 이상 있는 경우, 결과값은 0이다. 1. 구간 내 음수의 개수를 저장하는 세그먼트 트리와 0의 개수를 저장하는 세그먼트 트리를 둔다. 값의 변경이 계속 이루어지는 상황에서 구간에 대한 쿼리를 수행해야 하므로 세그먼트 트리를 이용하여 해결할 수 있다. 구간곱이 양수인지, 음수인지, 0인지만 알면 되기 때문에 음수의 개수, 0의 개수를 기록하는 두 개의 세그먼트 트리를 만들어준다. 2. 주어진 쿼리의 구간에 0이 하나도 없는 경우, 음수의 개수가 홀수개이면 결.. 2022. 5. 31. 백준 3770번 대한민국 - C++(cpp) 풀이 + 그림 설명 1615번 문제와 똑같고, 대신 테스트 케이스가 여러 개 주어지는 문제이다. 1615번은 Swift로는 시간 초과가 나서 못 풀었어서 이 문제도 그냥 C++로 도전. 서쪽을 기준으로 작은 수부터 차례로 동쪽과 연결해준다. 1, 2가 연결 완료된 상태이고, 이제 서쪽의 3번에 2개의 고속도로(3-2와 3-5)를 설치해야 하는 상황이라고 하자. 3-2로 가는 고속도로 먼저 설치해야 하는데(이유는 나중에), 이 고속도로를 설치할 때 생기는 교차점의 개수는 동쪽에서 2 초과인 곳 [3, 4, 5]에 연결된 고속도로 개수의 합과 같다. 이미 존재하는(검은색) 고속도로들은 전부 서쪽에서는 3(빨간 선의 시작점)보다 위에 있다. 따라서 방금 설치한 빨간색 고속도로와 교차하려면 동쪽에서는 2(빨간 선의 도착점)보다 아.. 2022. 1. 12. 백준 1572번 중앙값 - 스위프트(Swift) 시간초과 해결 스위프트로 문제 풀면 절반은 TLE를 맞는.. 오늘 벌써 두 번째 TLE인데 이번엔 좀 신기한 상황이었다. 이 문제 바로 전에 1615번 문제에서 이유를 알 수 없는 TLE를 맞았는데, Swift로 맞은 사람이 없길래 포기하고 바로 C++로 풀었는데 이 문제는 Swift로 맞은 사람이 있었다...! 결국 언어 한계가 아니라 내 코드 문제라는 건데.. 코드가 길지도 않은데 대체 어디서 시간을 잡아먹는 건지 알 수가 없었다. 예전에 C++로 풀이할 때, 메모리 접근 시간 때문에 TLE를 맞은 적이 있었다. 로직은 그대로 두고 2차원 배열 행과 열만 바꿔서 저장했더니 통과가 됐었다. 그래서 설마 이것도 메모리 접근에서 시간을 잡아먹는 건가 싶어 클래스 안에 타고 들어가는 시간 줄이려고 클래스로 따로 뺐던 펜윅.. 2022. 1. 12. 백준 1615번 교차개수세기 - 스위프트(Swift) 시간초과 해결 못함 또 TLE가 났는데, 이번엔 해결을 못하겠어서 결국 C++로 제출했다ㅠㅠ 추측하고 있는 이유는 1. 튜플 정렬 때문 2. 지금까진 대부분 N=100,000이었는데 이번엔 200,000이라..? 채점 현황 가서 Swift로 맞은 사람이 있는지 봤는데 제출한 사람조차 없었다. 그래서 빠르게 포기하고 C++로ㅠㅠ 아래는 TLE 받은 Swift 코드 import Foundation class FenwickTree { var tree = Array(repeating: 0, count: 2001) func sum(to: Int) -> Int { var ret = 0 var pos = to while (pos > 0) { ret += tree[pos] pos &= (pos - 1) } return ret } func.. 2022. 1. 12. 이전 1 2 3 다음 반응형
