알고리즘

문제 링크 https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 문제 문제 풀이 유클리드 호제법을 사용해 나온 최대공약수에 대해 출력할 때 문자열 1을 최대공약수만큼 반복 출력하도록 한다. a, b = map(int, input().split()) if a < b: a, b = b, a while b != 0: a = a % b a, b = b, a print("1" * a)

문제 링크 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 문제 문제 풀이 t = int(input()) for i in range(t): a, b = map(int, input().split()) mul = a * b while b != 0: a = a % b a, b = b, a print(int(mul / a))

문제 링크 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 문제 풀이 유클리드 호제법을 이용하는 문제이다. 유클리드 호제법에서는 숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b의 최대 공약수가 a와 b의 최대공약수 와 같다.기존 b를 a에 / a를 b로 나누어 나온 나머지를 b에 대입하는 과정을 반복하여b가 0이 나올 경우 a가 최대공약수가 된다. 예)(18, 12) => (12, 6) => (6, 0)b가 0이 되는 a값은 6이므로 6이 18과 12의 최대공약수가 된다. 최소공배수는 a, b의 곱..

문제 링크 https://www.acmicpc.net/problem/10430 10430번: 나머지 첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000) www.acmicpc.net 문제 문제 풀이 A, B, C = map(int, input().split()) print((A + B) % C, ((A % C) + (B % C)) % C, (A * B) % C, ((A % C) * (B % C)) % C, sep='\n')

문제 링크 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 문제 풀이 n, k = map(int, input().split()) ar = [i for i in range(1, n + 1)] index = 0 res = [] for _ in range(n): index += k - 1 if index >= len(ar): index = index % len(ar) res.append(str(ar.pop(index))) print("", sep='')

문제 링크 https://www.acmicpc.net/problem/10824 10824번: 네 수 첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000) www.acmicpc.net 문제 문제 풀이 a, b, c, d = map(str, input().split()) print(int(a + b) + int(c + d))

문제 링크 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제 문제 풀이 insert, remove를 이용해 간단하게 풀려고 시도해봤지만 시간 초과가 나타났다. 문제에 나타난 입력 개수가 많기 때문에 시간을 잘 고려해야한다. insert, remove 대신에 append, pop을 이용하면 시간복잡도를 O(N)에서 O(1)까지 줄일 수 있다. 아이디어를 찾기 어려워 나도 블로그를 많이 찾아봤는데 너무 좋은 아이디어가 있어 참고했다! 스택을 이용..

문제 링크 https://www.acmicpc.net/problem/11655 11655번: ROT13 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. www.acmicpc.net 문제 문제 풀이 아스키코드 관련 문제이다. 소문자, 대문자 나누어서 계산을 해주어 새 문자열을 만들어주고 각 문자열에 대해 종류를 벗어나는 것만 유의해주면 된다. s = input() result = '' for c in s: if 'a'