백준 1929번 Swift 알고리즘 연습

문제 난이도가 실버3이길래 긴장하고 풀었는데 초반에 값이 잘 나와서 방심하고 있었다.

역시나 실버3인 이유가 있었다. 시간 비용을 최소화할 수 있는 알고리즘을 찾아야 했다.

특정 범위 내에서 소수를 찾는 것은 타 문제들과 비슷하지만,

이 문제에서는 '에라토스테네스의 채' 알고리즘을 아느냐를 묻는 문제였다.

 

물론 나는 그게 뭔지 몰랐기 때문에 2-3번 시간초과 오류로 답을 내지 못했다.

 

에라토스테네스의 채와 관련이 있다는 것도

https://sapjilkingios.tistory.com/43

Swift) 백준 1929번 (소수구하기)

위 블로그를 통해 알게 되었고 위 블로그에서 소개해놓은 '동빈나' 유튜브를 참고하여 개념을 습득하였다.

결국 스스로 답을 내지 못했지만 억울하진 않았던 그런 문제였다...

 

 

이 문제를 풀면서 생각한 논리적 흐름은

1. 처음 값과 끝 값 사이의 자연수를 전부 배열에 담아준뒤
2. 배열 내의 값들이 소수인지 확인하고
3. 소수로 판정된 값들을 출력한다.

위와 같은 방식으로 진행했을 경우 시간 초과 오류가 발생했고

 

 

에라토스테네스의 채 논리는 다음과 같다.

1. 특정 범위의 값들 중 2의 배수를 전부 지워준다.
2. 특정 범위의 값들 중 3의 배수를 전부 지워준다.
3. 4의 배수는 이미 2의 배수를 지울 때 포함 되었으니 skip
4. 특정 범위의 값들 중 3의 배수를 전부 지워준다.
5. 6의 배수는 이미 3의 배수를 지울 때 포함 되었으니 skip
6. 위와 같은 형태를 반복해준다.

이론만 봐서는 이게 왜 더 빠른지 바로 이해가 안될 수 있다.

나도 직접 예시를 따라가며 값들을 print하며 흐름을 따라가보니 왜 더 빠르게 연산이 되는지 감이 잡혔다.

 

 

* 1929번

let nm = readLine()!.split(separator: " ").map{Int($0)! }

var arr: [Int] = Array(repeating: 0, count: nm[1] + 1)
for i in 2...nm[1] {
    arr[i] = i
}

for j in 2...nm[1] {
    if arr[j] == 0 {continue}
    for k in stride(from: j + j, through: nm[1], by: j) {
        arr[k] = 0
    }
}

for k in nm[0]...nm[1] {
    if arr[k] != 0 {
        print("\(arr[k])")
    }
}

 

 

정리(Today I Learned)

1. stride는 반복문에 주로 쓰이는 함수이다. 특정 범위안에서 특정 구간만큼 건너뛰며 값을 반환하는 역할을 한다.