alpyrithm_알파이리즘

1837 암호제작 www.acmicpc.net/problem/1837 1837번: 암호제작 원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 www.acmicpc.net 문제 풀기 전 공부할 것 : 큰 수 연산 풀이 k보다 작은 소수로 p가 나누어 떨어지면 좋지 않은 암호이기 때문에 k보다 작은 소수들을 찾아야 한다. k보다 작은 소수를 찾았다면 각각의 소수로 p를 나눌 수 있는지 확인하고 그 결과를 출력하면 된다. p, k = map(int, input().split()) prime = [False, False] + [True] * (k-2) for i in..

1244 스위치 켜고 끄기 www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 문제 풀기 전 공부할 것 : 구현 풀이 on_off를 통해 1이면 0으로 바꾸고 0이면 1로 바꿀 수 있도록 한다. 학생수만큼 for문을 돌면서 남학생인 경우, 여학생인 경우로 나눠서 스위치 작업을 진행한다. 출력할 때 20개씩 끊어서 출력한다. import sys input = sys.stdin.readline on_off = {1:0, 0:1} n = int(input()) ..

5347 LCM www.acmicpc.net/problem/5347 5347번: LCM 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀기 전 공부할 것 : 수학, 정수론 유클리드 호제법 풀이 a와 b의 최소 공배수를 구하는 방법은 a와 b를 곱하고 a와 b의 최대 공약수를 나누는 방법이 있다. 따라서 최대 공약수를 구하는 gcd 함수를 정의한다. 유클리드 호제법을 이용한다. 그리고 최소 공배수를 구한다. import sys input = sys.stdin.readline def gcd(a, b): while b: mod = b b = a % b ..

10211 Maximum Subarray www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍, 누적 합 풀이 연속하는 부분 배열의 원소의 합이 가장 큰 것을 찾는 문제이다. dp를 이용해서 해결할 수 있다. 연속하는 부분 배열이기 때문에 이전의 값에서 현재 값을 더한 값(dp[i-1]+arr[i])과 현재 값(arr[i])을 비교해서 더 큰 값을 저장하면 된다..

2776 암기왕 www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 문제 풀기 전 공부할 것 : 이분 탐색, 정렬 풀이 1 수첩1에 있는 숫자를 set으로 입력받는다.(같은 숫자를 여러 번 봐도 하나만 적혀 있으면 된다.) list로 받으면 시간 초과가 발생한다. 수첩2에 있는 숫자를 for문을 통해 반복하면서 수첩1에 있는 숫자인지 확인한다. import sys input = sys.stdin.readline t = int(input()) for _ in range..

11441 합 구하기 www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 문제 풀기 전 공부할 것 : 누적 합 풀이 구간의 합을 구하는 문제로 누적합을 이용하면 쉽게 해결할 수 있다. 누적합 cum array를 구한다. cum에 nums[0]을 넣어둔다. for문으로 반복하면서 cum의 마지막 숫자(지금까지 누적합)와 현재 nums를 더하면 만들 수 있다. i, j 구간의 합을 출력한다.(i..

1431 시리얼 번호 www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루 www.acmicpc.net 문제 풀기 전 공부할 것 : 정렬 풀이 n과 시리얼 번호를 입력받는다. 모든 자릿수의 합(숫자만)을 구하는 sum_num 함수를 정의한다. 시리얼 번호를 lambda 함수를 통해 길이, 모든 자릿수의 합, 사전 순으로 정렬한다. 시리얼 번호를 하나씩 출력한다. import sys input = sys.stdin.readline def sum_num(s): res = 0 for i ..

13241 최소공배수 www.acmicpc.net/problem/13241 13241번: 최소공배수 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다� www.acmicpc.net 문제 풀기 전 공부할 것 : 수학, 정수론, 유클리드 호제법 풀이 두 수를 a, b로 입력받는다. a와 b의 최소공배수는 a x b / gcd(a, b)[a, b의 최대공약수]이다. 따라서 a, b의 최대공약수를 함수 gcd를 이용해서 구한다. 그리고 a x b / gcd(a, b)를 출력한다. a, b = map..