본문 바로가기

Algorithm123

Swift) 백준 17425번 (약수의 합) 요구능력 : 시간을 고려하여 TestCase문제를 풀 수 있느냐.. 문제설명 : 이 문제는 브루트포스로 접근하면 바로 시간초과가난다.. 필자가 그랬다. TestCase문제는 브루트포스로 낚시를 하기때문에 답을 미리 만들어 놓은다음 테스트케이스에 따른 결과를 도출하는게 좋다. 아래 코드를 보면 dp[i*j] += i 가 적혀있다. i는 배수를 의미한다. i가 2라고 가정해보면 2의배수에 전부 2를 더하는것이다. j는 1부터 1씩 더해진다. dp[2 * 1] += 2 dp[2 * 2] += 2 dp[2 * 3] += 2 . . . 왜 저렇게 구하는거지? 라고 하면 그냥 이게 약수 구하는데는 제일효율적 같은 연산을 여러번 반복 하지않고 한번에 하기 때문이다. 우리가 구하고자 하는수는 100만까지라서 dp[10.. 2021. 8. 25.
Swift) 백준 17427번 (약수의 합 2) 요구능력 : 약수에 대해 이해하고 있느냐 코드설명 : 정말 신박하다. 4를 생각해보자. [1], [1, 2], [1, 3], [1, 2, 4] 이렇게 1이 4번, 2가 2번, 3이 1번, 4가 1번나온다. 다른 수도 마찬가지로 이와 같은 규칙을 갖고있다. 이 규칙을 식으로 나타내보면 n / i * i가 되는것이다. 4/ 1 = 4 ; 4 * 1 = 4 4/ 2 = 2 ; 2 * 2= 4 4/ 3 = 1 ; 1 * 3 = 3 4/ 4 = 1 ; 1 * 4 = 4 4 + 4 + 3 + 4 = 15가 된다. n/i * i를 한것이다. 다른 블로그들에는 10이 많이 적혀있어서 나는 4를 예시로 들어봤다. 후기 : 시간초를 보고 혹시 이게안될까 싶었는데.. 역시나 안됐다.. 처음시도한 코드는 시간초과... 역시나.. 2021. 8. 25.
Swift) 백준 1037번 (약수) 요구능력 : 약수에 대해 이해하고 있느냐 코드설명 : 여기서 중요한 점은 진짜 약수가 모두 주어진다는 것이다. 만약 12가 구하려는 수 이면 1, 2, 3, 4, 6, 12가 있는데 조건대로 1과 12는 제외하고보면 2, 3, 4, 6이 있다. 여기서 양쪽 끝에 숫자만 곱하면 구하려는 수가 나온다. 후기 : 약수에 대해서 알고만 있으면 무난한문제 let nCount = Int(readLine()!)! let nArr = readLine()!.split(separator: " ").map{Int($0)!} print("\(nArr.min()! * nArr.max()!)") 2021. 8. 25.
Swift) 백준 4375번 (1)(종료조건 EOF) 요구능력 : EOF를 쓸줄아느냐, 기본적인 수학 코드설명 : 1. 문제에서 별도의 종료조건이 없기 때문에 EOF를 사용한다. 이 때, 스위프트에서는 별도의 EOF가 없기 때문에 while문에서 코드와 같이 받아주면된다. commandLineTool에서도 입력받을 때 ctrl + d를 입력해주면 EOF를 쓸수있다. 2. next에는 1, 11, 111등이 들어갈 것인데, 이게 나누어 떨어지면 n의 배수이다. 3. next를 1, 11, 111, ... 를 만드려고 (next * 10) + 1 을 해준다. 4. 갑자기 next %= Int(n)! 을 왜? 사실, 안해도 답은 나온다. 나도 여기서 많이 헤맸는데, 알아보니 더 큰 수로 넘어가면 Int의 범위를 초과하기 때문에 컴파일에러가 나타나는 것이었다. 범.. 2021. 8. 24.