https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 문제 승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다. '문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.' 승재를 도와 특정 문자열 S$S$,..

문제 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다. 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000) 출력 첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다. # pypy로 제출했다. import sys n = int(sys.stdin.readline()) def..

누적 합 Prefix sum 이번 포스팅에선 누적 합 알고리즘을 살펴보겠다. 꽤 간단하지만 알고리즘이지만, 의외로 모르는 사람이 꽤 있다. Let's Go 다음과 같은 문제가 있다. n_list = [n for n in range(1, 100)] 50번째부터 - 80번째까지의 수를 더한 값을 리턴하라. 누적 합 알고리즘을 사용하지 않는다면? 단순히 리스트를 50번째부터 80번째까지 뽑아서 계산하는 방식을 가장 먼저 떠올릴 것이다. 코드로 표현하면 다음과 같다. sum(n_list[49:79]) 겉으론 문제가 없어 보이지만, 누적 합을 구하라는 요청이 많아지면 상황이 달라진다. import time n_list = [n for n in range(1, 10000)] start = time.time() fo..

문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000 이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. CODE import sys a, b = map(int, sys.stdin.readline().split()) def multiply(arr): ans = 1 for n in arr: ans *= n return ans def small_num(i): d = 2 i_list = [] while i > 1: if i % d == 0: i = i / d i_list.append(d..

문제 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다. 출력 첫째 줄에 N을 출력한다. N은 항상 32비트 부호 있는 정수로 표현할 수 있다. 코드 import sys n = int(sys.stdin.readline()) n_list = list(map(int, sys.stdin.readline().split())) m = min(n_list) x = max(n_l..

import sys N = int(sys.stdin.readline()) class stacking: def __init__(self): self.top = [] def push(self, a): return self.top.append(a) def pop(self): if not self.top: return print(-1) else: pop_object = self.top.pop() return print(pop_object) def size(self): return print(len(self.top)) def empty(self): if len(self.top) > 0: return print(0) else: return print(1) def ttop(self): if not self.top: ..