반응형 전체 글282 백준 2568번 전깃줄 - 2 - 스위프트(Swift) 풀이 1. 전깃줄들을 A를 기준으로 오름차순 정렬한다. 2. 1번 결과에서 B만 모아 만든 배열에서 가장 긴 증가하는 부분 수열을 구한다. 3. (N - LIS길이)가 없애야 하는 전깃줄의 최소 개수이며, LIS에 속하지 않는 전깃줄이 제거해야하는 전깃줄이다. 1. 전깃줄들을 A를 기준으로 오름차순 정렬한다. 2565번 문제에서 제거해야 하는 전깃줄 목록까지 추가로 구하는 문제이다. 기본 원리는 아래와 같다. 백준 2565번 전깃줄 - 스위프트(Swift) 풀이 1. 전깃줄들을 A를 기준으로 오름차순 정렬한다. 2. 1번 결과에서 B만 모아 만든 배열에서 가장 긴 증가하는 부분 수열의 길이를 구한다. 3. N - LIS가 없애야하는 전깃줄의 최소 개수이다. 1. 전깃줄 please-amend.tistory.c.. 2022. 2. 7. 백준 2565번 전깃줄 - 스위프트(Swift) 풀이 1. 전깃줄들을 A를 기준으로 오름차순 정렬한다. 2. 1번 결과에서 B만 모아 만든 배열에서 가장 긴 증가하는 부분 수열의 길이를 구한다. 3. N - LIS가 없애야하는 전깃줄의 최소 개수이다. 1. 전깃줄들을 A를 기준으로 오름차순 정렬한다. 먼저 (A-B) 쌍으로 이루어진 전깃줄을 A를 기준으로 오름차순 정렬해준다. 전깃줄이 교차하지 않으려면, A 오름차순으로 정렬했을 때 B도 오름차순이어야 한다. A는 증가하는데, B는 감소하면 전깃줄이 교차한다. 2. 1번 결과에서 B만 모아 만든 배열에서 가장 긴 증가하는 부분 수열의 길이를 구한다. 전깃줄을 최소 개수로 제거해서 교차가 없게 만들려면, 남는 전깃줄의 개수를 최대로 만들어야 한다. 즉, 가장 긴 증가하는 부분 수열을 구하면 된다. N이 작기 .. 2022. 2. 7. 백준 2162번 선분 그룹 - 스위프트(Swift) 풀이 1. 모든 선분 쌍에 대해 두 선분이 서로 만난다면 union 한다. 2. union 과정에서 집합의 크기를 기록한다. 3. 전체 집합의 개수와 가장 큰 집합의 크기를 출력한다. 1. 모든 선분 쌍에 대해 두 선분이 서로 만난다면 union 한다. 서로 만나는 두 선분을 같은 그룹으로 묶어주어야 한다. 유니온 파인드의 union 연산을 해준다. 선분 교차 알고리즘은 17387번에서 썼던 걸 그대로 썼다. 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 2. union 과정에서 집합의 크기를 기록한다. 마지막에 가장 큰 그룹의 크기를 출력해야 하기 때문에 union 과정에.. 2022. 2. 7. 백준 1799번 비숍 - 스위프트(Swift) 풀이 + 그림 설명 1. 백트래킹으로 비숍을 하나씩 놓아본다. 2. 현재 비숍들이 놓인 상태를 대각선 비트 마스킹으로 표시한다. 3. 검은색 칸과 흰색 칸을 따로 생각해서 구한다. 1. 백트래킹으로 비숍을 하나씩 놓아본다. 비숍을 하나씩 놓아본다. 각 칸을 순차적으로 순회하면서 해당 칸에 비숍을 놓는 경우와 놓지 않는 경우를 다 해보면 된다. 다음칸으로 넘어갈 때는 비숍의 경로가 겹치면 안 되기 때문에 현재 체스판의 상황을 같이 넘겨주어야 한다. 2. 현재 비숍들이 놓인 상태를 대각선 비트 마스킹으로 표시한다. 현재 체스판 상태를 N*N짜리 배열로 넘겨주는 것은 비효율적이다. 어차피 비숍은 대각선으로만 이동할 수 있으므로, 대각선마다 비숍이 위치하는지 여부만 넘겨주자. 현재 칸이 속한 두 종류의 대각선을 모두 확인해서, 두.. 2022. 2. 6. 백준 17143번 낚시왕 - 스위프트(Swift) 풀이 + 그림 설명 1. 모든 상어를 순회하면서 현재 열에서 가장 가까운 상어를 잡는다. 2. 모든 상어를 순회하면서 각 상어를 O(1)에 이동시킨다. 3. 상어들을 이동시킬 때 딕셔너리를 이용해서 위치가 중복되면 가장 큰 상어만 남긴다. 1. 모든 상어를 순회하면서 현재 열에서 가장 가까운 상어를 잡는다. 먼저 한 열 오른쪽으로 이동한 뒤 상어를 잡는다. 잡아야 할 상어는 모든 상어를 순회해서 결정한다. 한번 상어를 잡을 때 O(RC)의 시간복잡도가 든다. 2. 모든 상어를 순회하면서 각 상어를 O(1)에 이동시킨다. s가 최대 1,000까지 가능하다. 1,000칸을 시뮬레이션으로 모두 이동시킬 경우 상어 이동에만 O(1000*RC)의 시간 복잡도가 들게 되어 시간 초과가 발생한다. 각 상어를 O(1)에, 즉 모든 상어 .. 2022. 2. 5. 이전 1 ··· 37 38 39 40 41 42 43 ··· 57 다음 반응형
