반응형 펜윅트리10 백준 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. 백준 2243번 사탕상자 - 스위프트(Swift) 풀이 CLASS 6 따기 중인데, 이제 3문제 밖에 안 남았다:) 세그먼트 트리 문제. 구간합 문제라 더 구현이 간단한 펜윅트리로 풀었다. 펜윅트리 구현만 할 줄 알면 단순 적용만 하면 된다. 플래티넘 5 문제 중에는 이렇게 조금 난이도 있는 자료구조/알고리즘을 단순 적용하는 문제들이 꽤 있다. 사탕들은 아래와 같이 관리한다. candy[i] = 맛 순위가 i인 사탕 개수 먼저 n번째 사탕을 찾을 때를 보면, n번째로 맛있는 사탕의 맛 순위는 candy[1...k]의 구간합이 최초로 n이상이 되는 k(lower bound)가 된다. 사탕을 넣거나 뺄 때는 candy[i]에 원하는 개수만큼을 더하거나 빼면 된다. 이렇게 계속 변화하는 배열의 구간합을 구해야 하므로, 펜윅트리를 쓸 수 있다. 2022. 1. 10. 이전 1 2 다음 반응형
