본문 바로가기
반응형

Problem Solving242

백준 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.
백준 15824번 너 봄에는 캡사이신이 맛있단다 - 스위프트(Swift) 풀이 서브 태스크 문제로 small N과 large N 각각 점수가 매겨져 있어 small N만 통과해도 부분점수를 받을 수 있다. 먼저 small N에 맞게 풀이를 떠올리는 것은 쉽다. 결국 최소와 최대만 필요하므로 2개를 뽑아 그 2개가 (최소, 최대)가 되는 경우의 수를 각각 세서 곱해주면 된다. 이때 정렬을 하면 경우의 수를 쉽게 구할 수 있다. [1, 3, 4, 10, 11]이 있고 (3, 11)이 각각 최소, 최대가 되는 경우의 수를 구해보자. 3보다 크고 11보다 작은 숫자는 [4, 10]이 있으므로 이것들이 각각 있는 경우와 없는 경우를 고려하면 2^2가지이다. 모든 경우의 수를 나열하면 [3, 11], [3, 4, 11], [3, 10, 11], [3, 4, 10, 11]이 되겠다. 이렇게 풀.. 2022. 1. 9.
반응형

티스토리툴바