Swift (356) 썸네일형 리스트형 [BOJ] 백준 11653 소인수분해 (Swift) 문제 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 풀이 소인수분해란, 소수들만의 곱으로 나타내는 것을 의미합니다. 에라토스테네스의 체를 사용해 소수들만으로 나누어 떨어지는지 확인해도 되지만.. 그냥 2부터 나누어 떨어지는지 확인하고, 나누어 떨어지지 않으면 값을 올려주고 확인하고.. 반복하는 방법으로도 풀이할 수 있습니다. n이 최대 1000만이기 때문에 시간안에 해결할 수 있지만, 시간을 줄일 수 있는 방법이 있을까요? n = ab 라면, a와 b중 둘 중 하나는 $\sqrt{n}$ 보다 작은 성질이 있습니다. 따라서 n이 1000만에 가까운 소수여도, $\.. [BOJ] 백준 2581 소수 (Swift) 문제 https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 풀이 소수를 판별하는 방법에 대해 알면 쉽게 풀 수 있는 문제입니다. https://dev-mandos.tistory.com/91 [알고리즘] 간단한 소수 판별 알고리즘 (Swift) 소수 소수(Prime Number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 입니다. 간단한 소수 판별 알고리즘 그렇다면 해당 수가 소수인지 아닌지 어떻게 판별할까요? 아주 간단한 방식 dev-mand.. [알고리즘] 에라토스테네스의 체 (Swift) 에라토스테네스의 체 에라토스테네스의 체 알고리즘은 고대 그리스 수학자인 에라토스테네스가 만들어낸 소수를 찾는 알고리즘 입니다. 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체' 라고 불린다고 하네요. 방법 예를 들어 1 ~ 100까지의 숫자 중 소수를 찾는다고 생각해 봅시다. 먼저, 1부터 100까지의 수를 쭉 써줍니다. 코드상으로는 101만큼의 크기인 Boolean Array를 true로 초기화를 해줬습니다. 표로 나타내보면, 이렇게 나타낼 수 있겠네요. 1은 소수가 될 수 없기에 제거해줍니다. 2를 제외한 2의 배수를 제거합니다. 3을 제외한 3의 배수를 제거합니다. 이제 다음 차례로는 4를 제외한 4의 배수를 제거해야겠죠? 하지만 4는 2의 배수이기 때문에, 이미 다 지워졌습니다. 다음.. [BOJ] 백준 1978 소수 찾기 (Swift) 문제 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 풀이 소수 판별 알고리즘을 사용해서 풀이할 수 있습니다. 소수 판별 알고리즘에 대해 모른다면 아래 포스팅에서 한 번 확인해보고 가셔도 좋을 것 같습니다. https://dev-mandos.tistory.com/91 [알고리즘] 간단한 소수 판별 알고리즘 (Swift) 소수 소수(Prime Number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 입니다. 간단한 소수 판별 알고리즘 그렇다면 해당 수가 소수인지 아닌지 어떻게 판별할까요? 아주 간.. [알고리즘] 간단한 소수 판별 알고리즘 (Swift) 소수 소수(Prime Number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 입니다. 간단한 소수 판별 알고리즘 그렇다면 해당 수가 소수인지 아닌지 어떻게 판별할까요? 아주 간단한 방식으로 소수인지 판별할 수 있습니다. 단순히 2부터 자기 자신의 수 - 1 까지의 수 중에서 나누었을 때, 나머지가 0이 되는 수가 하나라도 존재하면 소수가 아닙니다. 이 방식의 경우 시간 복잡도는 $O(n)$이 될 것입니다. 시간 복잡도를 줄일 수 있는 방법이 있을까요?? 개선된 소수 판별 알고리즘 X를 2로 나누었을 때, 나머지가 0이라면 2는 X의 약수입니다. 그렇다면 X는 절대로 소수가 될 수 없겠죠? X를 2로 나누었을 때, 몫 도 X의 약수 입니다. 이러한 성질을 이용해서 시간 복잡도를 줄일 수.. [BOJ] 백준 10757 큰 수 A + B (Swift) 문제 https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 Swift에서는 파이썬과 달리 BigInteger를 제공하지 않고 있습니다. 그래서 직접 문자열을 통해서 구현을 해주어야 합니다. 실제로 덧셈을 하는것과 비슷하게 구현하기 위해서 맨 뒷자리 수 부터 계산을 해주어야 겠다는 생각을 했습니다. 또한 덧셈을 할 두 수의 길이가 다르다면, 작은 수에 0을 붙여줘야 할 것입니다. 그리고 한자리 수의 덧셈을 진행했을 때, 올림이 되는 경우 (9 + 8 = 17) 올림처리를 해주어야 합니다. 마지막으로 모든 자리수에 맞춰 계산을 한 후, 올림처리가 되어있다면.. [BOJ] 백준 2839 설탕 배달 (Swift) 문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 이 문제는 어떤 알고리즘을 사용하여 풀 수 있을까요? 봉지가 3, 5의 단위로만 존재하고 5가 3의 배수가 아니기 때문에, 그리디 알고리즘으로는 풀 수 없습니다. 그래서 다이나믹 프로그래밍 기법을 떠올릴 수 있습니다. 다이나믹 프로그래밍은 점화식만 세우면 쉽게 풀 수 있습니다. DP 테이블을 어떤식으로 채울 수 있을까요? 봉지가 3, 5의 단위로만 존재하기 때문에, 1, 2, 4 의 설탕은 들고갈.. [Swift] 컬렉션 자료형에 대해 알아보자 - 2 (Dictionary) 지난 포스팅에서는 컬렉션 자료형 중 Array에 대해 알아보았습니다. 이번 포스팅에서는 Dictionary에 대해 알아보겠습니다. Dictionary란? Dictionary는 요소가 키-값 쌍인 컬렉션이고, 구조체로 되어있네요! 또한 Dictionary는 일종의 해시 테이블이고, 순서가 보장 되어 있지 않습니다. 특이하게 요소중 key가 Hashable을 채택하고 있어야하는데, Swift에서 제공하는 기본 자료형들은 대부분 Hashable 프로토콜을 준수하고 있습니다. 여기서 Hashable이 머냐.. 하면 Hashable은 Equatable 프로토콜을 준수하고 있고.. 이 Equatable 프로토콜은 == 과 같은 연산자를 사용할 때, 사용되는 프로토콜 인데, 어떤 프로퍼티를 가지고 값이 같은지 아닌지.. 이전 1 ··· 31 32 33 34 35 36 37 ··· 45 다음
