반응형 세그먼트트리11 백준 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. 백준 2517번 달리기 - 스위프트(Swift) 풀이 + 그림 설명 문제를 요약하면, 각 선수에 대해 나보다 앞에 있으면서 큰 사람의 수 + 1을 구해라 이다. N이 500,000이므로 브루트포스로 2중 for문을 도는 O(N^2)으로는 당연히 시간 초과가 난다. 이런 Inversion Counting 문제는 세그먼트 트리(펜윅트리)로 해결 가능하다. (머지 소트를 쓰는 방법도 있다.) 아래와 같은 상황이라고 하자. 나보다 앞에 있으면서 큰 사람의 수를 카운트해주기 위해서, 작은 수부터 오름차순으로 고려해줄 것이다. 그리고 아직 고려 안했는지 여부를 저장하는 배열을 하나 더 두자. 아직 고려를 안 했으면 1이고 고려했으면 0이다. 따라서 초기에는 전부 1. 이제 실력이 낮은 사람부터 [1, 7, 9, 23, 56] 순으로 아직 고려 안했는지 여부[1...(index-1).. 2022. 1. 12. 백준 3653번 영화 수집 - 스위프트(Swift) 풀이 + 그림 설명 CLASS 6에 펜윅트리로 풀 수 있는 문제가 또 남아있길래ㅎㅎ 이제 1 문제만 더 풀면 CLASS 6 딸 수 있다!! 먼저 DVD가 쌓여있는 상황을 어떻게 표현할지부터 생각해야 한다. 간단하게 아래로 갈수록 항상 숫자(index)가 커지도록 매기는 방법을 떠올렸다. 이렇게 되면 x번 DVD를 뽑을 때 위에 놓인 DVD의 수는 index[x]보다 작은 index의 개수가 된다! 따라서 isIndexExist[i] = index 중 i라는 수가 존재하는가로 두면, index[x]보다 작은 index의 개수는 isIndexExist[1...(x-1)]의 구간합이 된다. 만약 3번 DVD를 뽑아야 하는 차례이면, 먼저 3번 DVD의 위치(index)를 확인한다. index[3]은 3이다. 3보다 작은 inde.. 2022. 1. 11. 백준 7578번 공장 - 스위프트(Swift) 시간초과 해결 또 돌아온 시간 초과 해결 글ㅎㅎ CLASS 6 문제 훑어보다가 펜윅트리로 또 쉽게 풀리는 문제가 있어서 풀기 시작. 바로 전 문제에서 펜윅트리를 구현해둬서 거의 복붙 수준으로 풀 수 있었다. 근데.. 또 TLE를 맞았다. 일단 풀이를 간단히 하자면, 먼저 기계 식별 번호를 인덱스 번호로 치환하자. 이제 아래 라인을 기준으로 왼쪽부터 차례로 윗 라인과 대응시켜보자. 아래 4와 위의 4를 연결하는 선을 그었는데, 후에 3, 2, 1을 연결하는 선을 그을 때, 방금 그은 선과 교차할 것이다. 위쪽 라인에서는 4보다 왼쪽에 있고, 아래쪽 라인에서는 4보다 오른쪽에 있기 때문에 교차할 수밖에 없다. 즉, 아래쪽 라인을 기준으로 왼쪽부터 차례로 대응시켜나갈 건데, 위쪽 라인에서는 x보다 왼쪽에 있고, 아래쪽 라인.. 2022. 1. 11. 이전 1 2 3 다음 반응형
