반응형 알고리즘207 백준 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. 백준 16946번 벽 부수고 이동하기 4 - 스위프트(Swift) 풀이 + 그림 설명 1. DFS를 돌면서 인접한 빈칸들을 union 한다. 2. union 할 때 각 집합의 크기를 기록해둔다. 3. 각 벽마다 상하좌우의 빈칸 집합의 크기를 더한다. 1. DFS를 돌면서 인접한 빈칸들을 union 한다. 빈칸들이 인접해있으면 인접한 빈칸을 모두 방문할 수 있다. 따라서 인접한 빈칸들을 유니온 파인드를 사용해 하나의 집합으로 처리해준다. 2. union 할 때 각 집합의 크기를 기록해둔다. 방문할 수 있는 빈칸의 개수를 알아야 하기 때문에 각 집합의 크기를 구해둬야 한다. 두 집합을 union 할 때 크기도 같이 합쳐서 기록해두자. 3. 각 벽마다 상하좌우의 빈칸 집합의 크기를 더한다. 어떤 벽을 부수면, 벽 때문에 막혀있던 상하좌우 칸들이 연결되게 된다. 따라서 어떤 벽을 부쉈을 때 방문.. 2022. 2. 5. 이전 1 ··· 26 27 28 29 30 31 32 ··· 42 다음 반응형
