반응형 Problem Solving242 백준 2581번 소수 - 스위프트(Swift) 풀이 1. 에라토스테네스의 체를 이용하여 1 이상 10,000 이하의 자연수에 대해 소수 여부를 구한다. 2. M부터 N까지 순회하면서 최소 소수와 소수들의 합을 구한다. 1. 에라토스테네스의 체를 이용하여 1 이상 10,000 이하의 자연수에 대해 소수 여부를 구한다. 에라토스테네스의 체를 이용하면 O(NloglongN)에 1 이상 N이하인 모든 자연수에 대해 소수 여부를 구할 수 있다. N이 최대 10,000이기 때문에 굳이 에라토스테네스의 체를 사용하지 않아도 1~(i-1)까지로 전부 나눠봐서 소수인지 판별하는 O(N^2)을 알고리즘을 사용해도 시간 내에 통과가 가능하다. 2. M부터 N까지 순회하면서 최소 소수와 소수들의 합을 구한다. M부터 N까지 단순 순회하면서 소수들만 골라 더하고, 처음으로 나오.. 2022. 2. 10. 백준 2133번 타일 채우기 - 스위프트(Swift) 풀이 + 그림 설명 1. dp[index][first][second][third] = index번째 열의 각 행 상태가 first, second, third일 때, index열부터 남은 열을 모두 채우는 경우의 수 2. 현재 열의 상태에 따라 가능한 모든 경우의 수를 더한다. 1. dp[index][first][second][third] = index번째 열의 각 행 상태가 first, second, third일 때, index열부터 남은 열을 모두 채우는 경우의 수 다이나믹 프로그래밍을 이용한다. dp[index][first][second][third]를 위와 같이 정의한다. first, second, third는 0일 때는 비어있음, 1일 때는 채워져 있음을 나타낸다. 최종적으로 구해야하는 것은 dp[0][0][0][0.. 2022. 2. 9. 백준 1022번 소용돌이 예쁘게 출력하기 - 스위프트(Swift) 풀이 1. (r1, c1)부터 (r2, c2)까지 직접 채운다. 2. 가장 길이가 긴 숫자의 길이를 구한다. 3. 포맷에 맞춰 출력한다. 1. (r1, c1)부터 (r2, c2)까지 직접 채운다. 단순 구현 문제이다. r, c 범위가 절댓값 5000까지인데, (-5000, -5000)부터 (5000, 5000)까지 전부 구해도 총 연산 횟수 10^8로 시간 초과가 나지 않는다. 하지만 10^8개의 Int를 선언하면 메모리 초과가 난다. 문제에서는 다음과 같은 조건을 두고 있다. 0 ≤ r2 - r1 ≤ 49 0 ≤ c2 - c1 ≤ 4 따라서 실제 2차원 배열은 정답이 될 50*5 사이즈로만 선언해둔다. 그리고 소용돌이를 채울 때, 50*5 범위에 들어가는 것들만 정답 배열에 기록하고 범위 밖인 것은 그냥 스.. 2022. 2. 9. 백준 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. 이전 1 ··· 32 33 34 35 36 37 38 ··· 49 다음 반응형
