[Python] 알고리즘
-
[1850] 최대공약수 (Python)[Python] 알고리즘/Silver 2021. 11. 18. 16:11
[문제] https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 알고리즘 분류는 수학, 정수론, 유클리드 호제법 입니다. 파이썬에 math 모듈에서 최대공약수를 구할 수 있습니다. [코드] import sys import math A, B = map(int, sys.stdin.readline().split()) A, B = min(A, B), max(A, B) print("1" * math.gcd(A, B))
-
[1904] 01타일 (Python)[Python] 알고리즘/Silver 2021. 11. 17. 23:02
[문제] https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 알고리즘 분류는 다이나믹 프로그래밍 입니다. N 2진 수열 개수 1 1 1 2 00, 11 2 3 001, 100, 111 3 4 0000, 0011, 1001, 1100, 1111 5 5 00001, 00100, 10000, 00111, 10011, 11001, 11100, 11111 8 이 과정을 거치면 점화식을 구할 수 있습니다. [코드] import sys li = [1, 2] for ..
-
[2193] 이친수 (Python)[Python] 알고리즘/Silver 2021. 11. 15. 18:09
[문제] https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 알고리즘 분류는 다이나믹 프로그래밍 입니다. 1자리 이친수 : 1 2자리 이친수 : 10 3자리 이친수 : 100, 101 4자리 이친수 : 1000, 1001, 1010 ... 이 과정을 거치면 점화식을 구할 수 있습니다. [코드] import sys li = [1, 1] for i in range(2, 91): li.append(li[i - 2] + li[i - 1]) N ..
-
[1748] 수 이어 쓰기 1 (Python)[Python] 알고리즘/Silver 2021. 11. 11. 14:49
[문제] https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 알고리즘 분류는 수학, 구현 입니다. N이 3자리 숫자라면 1 ~ 9 까지의 자릿수, 10 ~ 99 까지의 자릿수, 100 ~ N 까지의 자릿수를 더해야 합니다. (1 ~ 9 까지는 9자리 / 10 ~ 99 까지는 90 * 2자리) [코드] import sys N = int(sys.stdin.readline()) if N < 10: print(N) else: sum = 0 for i in range(len(str(N)) - 1): sum += 9 * (10 ** i) * (i + 1) print(sum + (..
-
[17479] 정식당 (Python)[Python] 알고리즘/Silver 2021. 11. 10. 21:51
[문제] https://www.acmicpc.net/problem/17479 17479번: 정식당 일반메뉴는 noodle 2개로 20,000원, 특별메뉴는 cutlet 2개와 friedrice 1개로 32,000원, 둘이 합쳐 52,000원으로 서비스메뉴 하나를 주문할 수 있다. www.acmicpc.net 알고리즘 분류는 자료 구조, 해시를 사용한 집합과 맵 입니다. 메뉴와 메뉴의 가격을 dict()에 저장하고, 나중에 조건을 적용하여 문제를 풉니다. 서비스메뉴를 반드시 주문하는 것이 아닙니다. [코드] import sys A, B, C = map(int, sys.stdin.readline().split()) dt_A = dict() dt_B = dict() li_C = list() for i in r..
-
[23056] 참가자 명단 (Python)[Python] 알고리즘/Silver 2021. 11. 9. 19:58
[문제] https://www.acmicpc.net/problem/23056 23056번: 참가자 명단 첫째 줄에 학급 수인 $N$과 학급당 신청 가능한 인원수 $M$이 주어진다. ($N$은 짝수이고 $2\leq N \leq 10$, $1\leq M \leq 10$) 둘째 줄부터 신청된 순서대로 학생의 학급과 이름이 주어진다. 학생의 학급은 www.acmicpc.net 알고리즘 분류는 문자열, 정렬 입니다. 참가자 명단은 학급 오름차순, 이름의 길이, 사전 순 순서로 정렬합니다. (다중 정렬 필요) [코드] import sys N, M = map(int, sys.stdin.readline().split()) li = list() dt = dict() while True: join = sys.stdin.r..
-
[18115] 카드 놓기 (Python)[Python] 알고리즘/Silver 2021. 11. 8. 16:42
[문제] https://www.acmicpc.net/problem/18115 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. www.acmicpc.net 알고리즘 분류는 자료 구조, 덱 입니다. 덱(deque)은 양방향 큐이므로 앞, 뒤에서 값을 추가할 수 있습니다. 파이썬에서 덱은 from collections import deque를 쓰면 사용 가능합니다. [코드] import sys from collections import deque N = int(sys.stdin.readline()) li = list(map(int, sys.st..
-
[13414] 수강신청 (Python)[Python] 알고리즘/Silver 2021. 11. 5. 15:01
[문제] https://www.acmicpc.net/problem/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 알고리즘 분류는 자료 구조, 해시를 사용한 집합과 맵 입니다. 시간 제한이 1초이므로, input() 대신 sys.stdin.readline()을 사용하고 Dictionary를 사용해야 합니다. (List로 하면 시간초과입니다.) [코드] import sys K, L = map(int, sys.stdin.readline().split()) dt = dict() for i in..