Algorithm
-
[BOJ] 11653번Algorithm/Baekjoon Online Judge 2022. 3. 12. 14:28
https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net Python3 code 1 if __name__ == '__main__': N = int(input()) for i in range(2, int(N**0.5)+1): while N % i == 0: print(i) N //= i if N > 1: print(N) 입력받은 N에 대해서 2부터 N의 제곱근까지의 수들로 나누기를 진행했다. 나누는 수는 제곱근보다 클 수 없기 때문에 반복문의 범위를 제곱근까지로 정하였다. 만약 N이 i로 나누어진다면 나눈 수 i를 출력하고 i로 나눌 수 있을 때까지 반복해서 나누었다. 마지..
-
[BOJ] 2581번Algorithm/Baekjoon Online Judge 2022. 3. 12. 13:43
https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net Python3 if __name__ == '__main__': M = int(input()) N = int(input()) prime = [] for number in range(M, N+1): is_sosu = 1 if number == 1: continue for i in range(2, number): if number % i == 0: is_sosu = 0 break if is_sosu: prime...
-
[BOJ] 1978번Algorithm/Baekjoon Online Judge 2022. 3. 12. 13:27
https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net Python3 if __name__ == '__main__': N = int(input()) cnt = 0 number = list(map(int, input().split())) for n in number: is_sosu = 1 if n == 1: continue for i in range(2, n): if n % i == 0: is_sosu = 0 break if is_sosu: cnt += 1 print(cnt) 입력받을 수의 개수를 N에 저장하고 numbe..
-
[BOJ] 10757번Algorithm/Baekjoon Online Judge 2022. 3. 12. 01:47
https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net Python3 if __name__ == '__main__': A, B = map(int, input().split()) print(A+B) 다른언어였다면 문제가 됐겠지만 파이썬에서는 너무나도 쉽게 해결할 수 있다. 파이썬에서는 정수 자료형인 Integer형에서 오버플로우가 없다. c언어였다면 long타입일 정수값도 파이썬에서는 int로 처리한다. 이게 가능한 이유는 Arbitary-precision arithmetic 때문이다. Arbitary-precision arithmetic은 메모리양이 정해져 있..
-
[BOJ] 2775번Algorithm/Baekjoon Online Judge 2022. 3. 12. 01:30
https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net Python3 if __name__ == '__main__': test = int(input()) for _ in range(test): K = int(input()) N = int(input()) floor = [i for i in range(1, N+1)] for k in range(K): for n in range(1, N): floor[n] += floor[n-1] print(floor[N-1]) testcase의 개수를 받은 후..
-
[BOJ] 10250번Algorithm/Baekjoon Online Judge 2022. 3. 12. 00:37
https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net Python3 N명의 사람이 호텔에 왔다고 했을 때 결국 방의 위치는 1층의 1번방 부터 차례대로 H층의 1번방까지, 이후에 1층의 2번방부터 H층의 2번방까지 차례대로 1번방->2번방->3번방.... 순으로 배정된다. 따라서 방의 층수는 N명의 사람이 왔을 때 H층까지 사람을 배정하고 남은 나머지가 된다. 몇 번째 방인지는 N명의 사람을 H로 나누었을 때 몇번 째 열에 해당하는 지를..
-
[BOJ] 2869번Algorithm/Baekjoon Online Judge 2022. 3. 12. 00:01
https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net Python3 주어진 문제 그대로 반복문을 사용하여 구현한 결과 100 99 1000000000 예제 입력에서 오랜시간이 걸렸다. 1.5초 시간제한에 걸릴게 분명했고 다른 방법을 생각했다. 새롭게 생각한 방식은 어쨋든 마지막에 정상을 오르기 위해서 A만큼 올라가려고 하루를 쓴다고 생각하는 것이다. 그러면 V-A만큼을 몇일을 걸려 올라가게 되는지 생각하면 된다. 이때는 낮에 올라가고 밤에 미끄러지는 것을 모두 생각하여 하루에 A-B만큼 올라갈테니 이것으로 ..
-
[BOJ] 1193번Algorithm/Baekjoon Online Judge 2022. 3. 11. 23:36
https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net Python3 우선 구간을 나누자고 생각했고 구간을 나누려고 보니 [1/1], [1/2, 2/1], [1/3, 2/2, 3/1] ..... 이런식으로 1, 2, 3, 4 개로 한 줄에 들어갈 수 있는 수의 개수가 1씩 늘어나는 것을 보았다. 저 값들을 차례로 더해갈 때 X보다 커지는 순간 어느 라인에 속하는지 알 수 있을 것으로 생각했다. 따라서 처음에는 반복문을 통해 1부터 차례로 더해가며 X보다 커질 때를 찾았는데 이 방법은 한 라인에서 몇 번째 수인지 알기도 번거로웠다. 또한 값이 커질 때를 찾게되기 때문에 값이 커지기 전..