본문 바로가기
반응형

알고리즘207

백준 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.
백준 3015번 오아시스 재결합 - 스위프트(Swift) 풀이 + 그림 설명 어디서 많이 본 것 같은 느낌이 나면서도 중복 처리가 힘들었던 문제. 일단 기본 아이디어는, X보다 더 큰 사람 Y가 나오는 순간, 이제 Y보다 뒤에 있는 사람들은 X를 볼 수 없으므로 X를 더 이상 고려하지 않아도 된다는 것이다. 배열을 순차 탐색하면서 증가 때마다 무슨 일이 일어나고.. 왠지 스택을 쓰면 뭔가 될 것 같은 느낌이다. 아래와 같이 [3, 2, 2, 1, 2]로 주어진 상황이라고 하자. 손으로 풀어보면 그림과 같이 8쌍이 서로 볼 수 있다. 왼쪽부터 순차 탐색할 것이므로 A와 B가 서로 볼 수 있다면, 더 우측에 있는 B차례에서 카운트+1을 해줄 것이다. 아까 말했던 기본 아이디어, 더 큰 사람이 올 때까지 이제 스택에 일단 한 명씩 담자. 계속 더 작은 사람만 담다보면 스택 내부는 항상.. 2022. 1. 8.
반응형

티스토리툴바