YJLee-devlog 🍎

1. 문제 특정 숫자가 소수인지 아닌지 판별하는것이 아닌, 2부터 주어진 수까지 범위 내의 모든 소수를 찾는 알고리즘인 에라토스테네스의 체를 구현 2. 문제 설계 1인 소수가 아니므로, 배열에 1번째 원소에는 0을 저장하고 2부터 주어진 수까지 각 수를 배열에 그에 대응하는 위치에 원소를 저장함 가장 작은 소수인 2부터 그의 배수들을 배열에서 모두 0으로 지워나가면 소수만 남게됨 따라서, 주어진 수가 N이라면 O(N log N)에 특정 범위내의 모든 소수를 찾을 수 있음 특정 수가 소수인지 아닌지를 판별하는 문제에서는 제곱근 까지 나누어보는 것이 효율적이고, 특정 범위 내의 모든 소수를 찾을 때는 에라토스테네스의 체를 활용하는 것이 효율적임 3. 전체 코드 //MARK: - 에라토스테네스의 체 //MA..

1. 문제 주어진 수가 소수인지 아닌지 판별하는 문제 2. 문제 설계 완전탐색으로 2부터 특정 숫자까지 나누어 떨어지는지 일일히 확인하면서 O(N)에 소수를 판별할 수도 있지만, 가장 작은 소수인 2부터 시작해서 나누어 떨어진다면, 그의 제곱수로는 확인해볼 필요가 없으므로 현재 소수인지 아닌지 판별하려고 하는 숫자가 2부터 시작하는 수의 제곱수보다 작거나 같을 때 까지 그 수로 나누어 떨어지는지 확인하게 되면 보다 더 효율적으로 소수를 판별할 수 있음. 쉽게 말하면 2부터 현재 판별하려는 수의 제곱근 까지 나누어 보는 것이랑 동일함 위 알고리즘은 O(root(N))의 시간복잡도를 가짐 3. 전체 코드 //MARK: - adv. 소수 판별 //MARK: - Framework import Foundation..

1. 문제 조합(Combination)을 손쉽게 구할 수 있는 파스칼 삼각형을 구현 2. 문제 설계 n C 0 = 1, n C n = 1은 n개 중에서 0개, n개 중에서 n개를 뽑는 경우의 수이므로 1, 즉 2차원 배열(파스칼 삼각형)의 (i, 0), (i, i)는 모두 1로 채울 수 있음 그리고 나를 결정하기 위해서는 나의 왼쪽 위 대각선 값과 바로 위 값을 더해줌으로써 구할 수 있고, 최종적으로 n C r을 알기 위해서는 2차원 배열(파스칼 삼각형)의 (n, r)의 원소를 출력함으로써 값을 얻을 수 있음 3. 전체 코드 //MARK: - 파스칼 삼각형 //MARK: - Framework import Foundation //MARK: - Function func solution() -> Void { ..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 특정 숫자가 소수인지 아닌지 판별하는 것은 제곱근까지 직접 나누어보는 것이 빠르지만, 특정 범위내의 모든 소수를 구하기 위해서는 에라토스테네스의 체가 O(N log N)으로 더 효율적임 따라서 2부터 2 * n 까지의 모든 소수를 구하고, n + 1 부터 2 * n(n보다 크고 2 * n 보다 작거나 같은) 소수의 개수를 구함으로써 문제를 해결할 수 있음 5. 전체 코드 // // main.swift // Chebyshevtheo // // Created by 이영재 on 2022/03/08. //MARK: - chebyshevtheo //MARK: - Framework import Foundation //MARK: - Function func g..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 소인수 분해는 어떠한 수를 소수로 분해하는 것을 말함 가장 작은 소수인 2부터 시작해서 해당 숫자가 1이될 때까지 증가하면서 나누게 되면, 소인수 분해를 구현할 수 있음 2로 나누어지지 않는 것은 4로 나누어지지 않듯이 3, 5, 7 모두 마찬가지인 것을 알 수 있음 5. 전체 코드 // // main.swift // Pfactorization // // Created by 이영재 on 2022/03/08. //MARK: - pfactorization //MARK: - Framework import Foundation //MARK: - Function func solution() -> Void { //MARK: - Input guard let N:..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 시작과 끝은 1로 고정되어 있고, n - 1, n, n + 1로만 이동할 수 있는 조건과 x부터 y로 최소한의 이동횟수 조건을 모두 만족해야함 규칙을 찾아야 하는 문제이지만, 규칙을 찾는 것이 매우 까다로움 y - x(두 지점의 거리)가 1이거나 2면 시작과 끝이 1로 고정되어 있으므로, 각각 1과 2가 최소 이동횟수 두 지점의 거리가 3이상인 경우부터 직접 손으로 써내려가 보면, 각 이동횟수에 대한 y-x(두 지점의 거리)의 최대값(maxDistance)들을 비교함으로써 규칙을 찾을 수 있음 y - x(maxDistance)가 4, 6, 9, 12일 때를 기점으로 이동횟수가 증가하는 것을 볼 수 있고, 그 주기가 2번인 것을 알 수 있음 5. 전..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 각 나무의 위치를 나타내는 정수는 모두 다르고, 가까운 위치(오름차순)로 주어짐 따라서 각 정수의 차에 대한 최대공약수가 같은 간격으로 최소한의 나무를 심을 수 있는 값임을 알 수 있음 가로수의 위치를 나타내는 정수의 최고 크기가 1,000,000,000 이므로, 완전 탐색으로 해당 나무가 심어져 있는지 확인 하기 위해 최악의 경우 O(N)으로(최대공약수가 1인 경우) 문제를 해결할 경우, 시간 내에 해결하지 못할 수 있음 따라서, 주어진 정수 중 최대값과 최소값의 차이를 같은 간격(최대공약수)로 나누게 되면, 최대로 필요한 간격을 구할 수 있고 + 1을 하게 되면 총 나무의 개수를 구할 수 있음. 이미 심어져 있는 나무의 개수는 문제에서 주어졌으..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 문제의 크기가 1,000,000 이므로 1,000,000 팩토리얼을 연산할 수 없을 뿐더러 저장할 수 있는 수 자료형도 없음 따라서, 다른 시선으로 접근을 해야함 끝자리 0의 개수는 10의 거듭제곱 즉, 2와 5의 곱으로 이루어져 있기 때문에 n 과 m에 대하여 2와 5로 각각 몫이 1이 될 때 까지 나누면서 2와 5의 개수를 저장함 마찬가지로, Combination의 공식에 의해 m과 n-m에 대해서도 2와 5의 개수를 저장함 2와 5의 곱셈으로 이루어져 있고, Combination 공식에 의해 n의 2의 개수 및 5의 개수에서 m과 n-m의 2의 개수 및 5의 개수를 제외시켜줌 10은 2와 5의 짝이 맞아야 하므로 최종적으로 구한 2와 5의 개..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 2차원 배열을 구성하여 왼쪽 위와 바로 위의 값을 더하여 자신을 결정하는 형태인 파스칼 삼각형을 구성 파스칼 삼각형에 저장되어 있는 값은 각 행이 n C m을 뜻하므로 해당 원소 값을 출력함으로써 문제를 해결함 5. 전체 코드 // // main.swift // CombinationPascal // // Created by 이영재 on 2022/03/08. //MARK: - combinationpascal //MARK: - Framework import Foundation //MARK: - Function func solution() -> Void { //MARK: - Input guard let input = readLine()?.componen..

1. 문제 2. 입출력 3. 입출력 예시 벌집 문제와 동일 전체코드는 여기에서 확인할 수 있습니다.