본문 바로가기

백준

(322)

[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..

[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과 자기 자신만을 약수로 가지는 수 입니다. 간단한 소수 판별 알고리즘 그렇다면 해당 수가 소수인지 아닌지 어떻게 판별할까요? 아주 간..

[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 의 설탕은 들고갈..

[BOJ] 백준 2775 부녀회장이 될테야 (Swift) 문제 풀이 이 문제는 다이나믹 프로그래밍 기법을 사용해서 쉽게 풀이할 수 있습니다. 먼저, 0층의 i호에는 i명이 산다. 라는 문제의 지문을 이용해서 0층, 1층, 2층... 바텀업 방식으로 답을 도출할 수 있다는 아이디어를 얻을 수 있습니다. 4호까지 있다고 가정하고 DP 테이블을 어떤식으로 채워나갈지 확인해보시죠..! 2층 3호는 어떤식으로 채워줘야 할까요?? 2층 3호 = 1층 1호 + 1층 2호 + 1층 3호 일 것입니다. n층 1호는 0층 1호가 1이기 때문에, 무조건 1이 될 수 밖에 없습니다. 1층 2호 = 0층 1호 + 0층 2호 겠죠?? 하지만 이것은 1층 1호 + 0층 2호 라고 해도 되겠죠?? 1층 3호는 어떨까요?? 1층 3호 = 0층 1호 + 0층 2호 + 0층 3호 겠네요. 0층..

[BOJ] 백준 10250 ACM 호텔 (Swift) 문제 https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 풀이 먼저, 도착한 손님의 순서대로 방 배정을 하는 방법에 대해 이해를 해야합니다. 층(H) 수가 6, 방(W) 수가 3이라고 가정을 해보겠습니다. 101 -> 201 -> 301 -> 102 -> 202 -> 302 -> 103 -> ... -> 603 의 순서로 될 것입니다. 그렇다면 먼저 N번째 손님이 갈 층 수를 어떻게 구해야할까요? 층 수 구하기 층 수는 단순히 N % ..

[BOJ] 백준 2869 달팽이는 올라가고 싶다 (Swift) 문제 https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 풀이 낮에는 A미터 올라가고, 밤에는 B미터 미끄러진다. 주의해야 할 점이 A미터를 올라갔을 때, 정상에 올라갔다면 미끄러지지 않는다. while문을 통해서 구할 수 있겠지만, 이 문제는 시간제한이 0.15초 입니다. 또한 A, B, V의 범위가 (1 ≤ B < A ≤ V ≤ 1,000,000,000) 이므로, A = 2, B = 1, V = 1,000,000,000 이라면... 약 10억번의 연산을 수행하는 while문으로는 시간안에 해결할 수 없..

이전 1 ··· 29 30 31 32 33 34 35 ··· 41 다음

티스토리툴바