반응형 펜윅트리10 백준 11505번 구간 곱 구하기 - C++(cpp) 풀이 1. 펜윅트리를 이용해서 업데이트와 누적곱을 연산을 구현한다. 2. 또 다른 펜윅트리를 이용해서 대상 구간 내에 0이 있는지 체크한다. 1. 펜윅트리를 이용해서 업데이트와 누적곱을 연산을 구현한다. 계속 변화하는 수열에서 구간곱을 구해야한다. 세그먼트트리 또는 펜윅트리를 사용한다. 아래 코드에서는 펜윅트리를 사용하였다. 구간곱 펜윅트리 구현은 아래와 같이 하였다. 초기 트리 배열의 값을 0이 아닌 1로 초기화한다. 나눗셈은 페르마의 소정리를 이용해 역원을 곱해주는 것으로 처리한다. b번째 수를 c로 업데이트 하는 연산은, 원래 값이 x라고 하면 b번째 수를 x로 나눈 뒤, 다시 c를 곱해주는 연산을 해주면 된다. 이때 x로 나누는 연산을 x의 모듈러 역원을 곱해주는 것으로 처리해준다. 어차피 출력해야 하.. 2022. 2. 16. 백준 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. 백준 1777번 순열복원 - 스위프트(Swift) 풀이 + 그림 설명 1~N에 대해 i보다 뒤에 나오면서 더 작은 수의 개수가 주어졌다. 따라서 큰 수부터 내림차순으로 뒤에 빈자리가 inversionSequence[i]개 있게 되는 곳에 놓으면 된다. 큰 수부터 고려해주고 있기 때문에, 빈자리의 의미는 앞으로 더 작은 수가 위치할 자리이기 때문이다. 먼저 가장 큰 5부터 자리를 찾아주자. 5의 Inversion Count가 2이므로 뒤에 빈자리가 2개가 되는 곳에 놔야 한다. 그림으로 보면 3번째 자리가 되겠다. 그럼 뒤에 빈자리가 x개가 되는 곳을 어떻게 찾을까? 순차 탐색으로 뒤에서부터 하나씩 세면 당연히 O(N^2)으로 시간 초과가 난다. 세그먼트 트리로 시간문제를 해결할 수 있다. 해당 자리가 비어있는지 여부를 배열로 둬서, 맨 뒤에서부터의 index까지의 구간합이.. 2022. 1. 12. 이전 1 2 다음 반응형
