반응형 Problem Solving242 백준 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. 백준 18436번 수열과 쿼리 37 - 스위프트(Swift) 풀이 수열과 쿼리 시리즈 중에 하나. 변화하는 수열에서 구간 내 짝수/홀수 개수를 묻는 쿼리를 여러 번 수행해야 한다. 쿼리 종류가 2가지이지만, 결국 한 가지인 거랑 똑같은데, 짝수 아니면 홀수니까 둘 중 하나만 카운트하는 세그먼트 트리를 두고, 만약 반대를 물어보면 구간 길이에서 물어본 것의 반대 개수만큼을 빼주면 된다. 짝수/홀수 중 한 종류만 카운트하게 두었기 때문에 update 작업을 할 때 조심해야 한다. 짝수 -> 짝수 또는 홀수 -> 홀수로의 업데이트를 할 때는 결국 변화가 없는 것과 같다. (구체적인 값은 중요하지 않고 짝수/홀수 여부만 상관있기 때문에.) 따라서 만약 짝수를 카운트하는 세그먼트 트리를 뒀다면, 짝수 -> 홀수로 변하면 -1을 해주고, 홀수 -> 짝수로 변하면 +1을 해주면 된.. 2022. 1. 12. 이전 1 ··· 43 44 45 46 47 48 49 다음 반응형
