첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
출력
주어진 수들 중 소수의 개수를 출력한다.
코드
count = int(input())
numbers = list(map(int, input().split()))
answer = 0
for i in numbers:
div_count = 0
for j in range(1, i+1):
if i % j == 0:
div_count += 1
if div_count == 2:
answer += 1
print(answer)
PyPy는 Python 코드를 해석하고 실행할 수 있는 가상 머신입니다. Python 인터프리터보다 빠르도록 설계되었으며 일부 Python 코드에서 CPython보다 2~3배 빠를 수 있습니다. PyPy는 JIT(Just-In-Time) 컴파일러를 사용하여 Python 코드를 기계어로 컴파일하여 속도를 향상시킵니다. 또한 PyPy는 Python 코드를 최적화하는 데 사용할 수 있는 다양한 기능을 제공합니다.
Python과 PyPy의 주요 차이점은 PyPy는 Python 코드를 JIT 컴파일하는 반면 Python은 Python 코드를 해석한다는 것입니다. JIT 컴파일은 프로그램 실행 시점에 Python 코드를 기계어로 번역하는 프로세스입니다.
이렇게 하면 Python 코드를 해석하는 데 필요한 시간과 리소스를 절약할 수 있습니다.PyPy는 Python 인터프리터보다 빠르도록 설계되었지만 Python 인터프리터보다 메모리 집약적일 수도 있습니다. 특정 응용 프로그램에 가장 적합한 구현은 구현의 속도, 메모리 사용량 및 기타 요인에 따라 달라집니다.
pycharm은 파이썬언어로 코딩할 수 있는 ide입니다. 프로젝트를 생성할 때 인터프리터를 설정할 수 있는데
pypy3를 설치해서 인터프리터를 연결하면 파이참에서 pypy3로 코딩할 수 있습니다. 그렇다곤 하지만 python과 pypy의
꿍은 도비의 자유를 위해 영어를 가르치기로 결심했다. 하지만 도비는 바보라 ABC부터 배워야 한다.
그래서 꿍은 영어 문장과 알파벳 하나가 주어지면 그 알파벳이 문장에서 몇 번 나타나는지를 세는 문제들을 내주었다. 하지만 도비는 마법사고 컴공도 마법사다.
여러분은 도비를 위해 문제의 답을 알려주는 프로그램을 만들수 있을것이다!
입력
입력은 몇 개의 줄들로 이루어진다.
각 줄에는 하나의 소문자와 영어 문장이 공백으로 구분되어 주어진다.
각 문장은 길이가 1에서 250이며 입력의 마지막은 #이다.
출력
출력의 각 줄은 입력으로 주어진 소문자와 그 소문자 알파벳이 나타난 횟수로 이루어진다. 이때 문장에서 해당 알파벳이 소문자로 나타나던 대문자로 나타나던 모두 세야 한다.
코드
import sys
while True:
line = sys.stdin.readline().rstrip()
if line == '#':
break
alphabet = line[0]
line = str.lower(line[2:])
print(alphabet, line.count(alphabet))
import sys
k, n = map(int, sys.stdin.readline().split())
lan_list = sorted([int(sys.stdin.readline()) for _ in range(k)])
max_len = max(lan_list)
min_len = 1
answer = 0
while min_len <= max_len:
mid_len = (max_len + min_len) // 2
count = sum([lan // mid_len for lan in lan_list])
if count >= n:
answer = mid_len
min_len = mid_len + 1
else:
max_len = mid_len - 1
print(answer)
시간초과 나온 코드
import sys
k, n = map(int, sys.stdin.readline().split())
lan_list = [int(sys.stdin.readline()) for _ in range(k)]
div = sum(lan_list) / n
while True:
div_list = [int(i / div) for i in lan_list]
if sum(div_list) != n:
div -= 1
else:
break
print(int(div))
해결
랜선의 길이를 담은 리스트를 만들고 리스트의 최댓값을 구한다.
최솟값은 1
최댓값과 최솟값의 중간값을 구하고 해당 값을 기준으로 랜선을 잘라서 만들 수 있는 개수를 구한다.
중간값을 각각의 랜선에 나누면 값이 나오는데 이걸 전부 더하면 몇개가 만들어지는지 알 수 있다.
이렇게 더해진 값이 n보다 크면 answer에 저장하고 최솟값을 중간값에 1을 더한 값으로 변경한다
n보다 작으면 최댓값을 중간값에 1을 빼서 변경한다
이러한 반복을 최솟값이 최댓값보다 작거나 같을 때 까지 반복해서 최종적으로 answer를 반환하면 된다
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
코드
일반적인 파이썬 정렬 코드이다
import sys
count = int(sys.stdin.readline())
my_list = [int(sys.stdin.readline()) for _ in range(count)]
for i in sorted(my_list):
print(i)
해결
음.. 뭔가 이상하다
처음 맞췄던 방법은 출제자가 의도한 방법이 아닌것 같아서 병합정렬이랑 계수정렬을 사용해서 코드를 작성했는데
틀렸거나 시간초과 결과가 나온다... 이상하다
병합정렬
import sys
def mergeSort(A, p: int, r: int):
if p < r:
q = (p + r) // 2
mergeSort(A, p, q)
mergeSort(A, q + 1, r)
merge(A, p, q, r)
def merge(A, p: int, q: int, r: int):
i = p
j = q + 1
t = 0
tmp = [0 for i in range(len(A))]
while i <= q and j <= r:
if A[i] <= A[j]:
tmp[t] = A[i]
i += 1
else:
tmp[t] = A[j]
j += 1
t += 1
while i <= q:
tmp[t] = A[i]
i += 1
t += 1
while j <= r:
tmp[t] = A[j]
j += 1
t += 1
i = p
t = 0
while i <= r:
A[i] = tmp[t]
i += 1
t += 1
count = int(sys.stdin.readline())
my_list = [int(sys.stdin.readline()) for _ in range(count)]
mergeSort(my_list, 0, len(my_list) - 1)
for i in my_list:
print(i)
계수정렬
import sys
# 계수 정렬
def counting_sort(A: list):
k = max(A)
c = [0 for _ in range(k + 1)]
for j in range(len(A)):
c[A[j]] += 1
for i in range(1, k + 1):
c[i] += c[i - 1]
b = [0 for _ in range(len(A))]
for j in range(len(A) - 1, -1, -1):
b[c[A[j]] - 1] = A[j]
c[A[j]] -= 1
return b
count = int(sys.stdin.readline())
my_list = [int(sys.stdin.readline()) for _ in range(count)]
for i in counting_sort(my_list):
print(i)
APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다.
이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다. 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, ..., z)로만 구성되어있다고 가정하자. 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여할 수 있다. 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 "abba"은 수열 1, 2, 2, 1로 나타낼 수 있다.
해시 값을 계산하기 위해서 우리는 문자열 혹은 수열을 하나의 정수로 치환하려고 한다. 간단하게는 수열의 값을 모두 더할 수도 있다. 해시 함수의 정의에서 유한한 범위의 출력을 가져야 한다고 했으니까 적당히 큰 수 M으로 나눠주자. 짜잔! 해시 함수가 완성되었다. 이를 수식으로 표현하면 아래와 같다.
해시 함수의 입력으로 들어올 수 있는 문자열의 종류는 무한하지만 출력 범위는 정해져있다. 다들 비둘기 집의 원리에 대해서는 한 번쯤 들어봤을 것이다. 그 원리에 의하면 서로 다른 문자열이더라도 동일한 해시 값을 가질 수 있다. 이를 해시 충돌이라고 하는데, 좋은 해시 함수는 최대한 충돌이 적게 일어나야 한다. 위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 충돌이 일어나기 때문에 나쁜 해시 함수이다. 그러니까 조금 더 개선해보자.
어떻게 하면 순서가 달라졌을때 출력값도 달라지게 할 수 있을까? 머리를 굴리면 수열의 각 항마다 고유한 계수를 부여하면 된다는 아이디어를 생각해볼 수 있다. 가장 대표적인 방법은 항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것이 있다. 이를 수식으로 표현하면 아래와 같다.
보통 r과 M은 서로소인 숫자로 정하는 것이 일반적이다. 우리가 직접 정하라고 하면 힘들테니까 r의 값은 26보다 큰 소수인 31로 하고 M의 값은 1234567891(놀랍게도 소수이다!!)로 하자.
이제 여러분이 할 일은 위 식을 통해 주어진 문자열의 해시 값을 계산하는 것이다. 그리고 이 함수는 간단해 보여도 자주 쓰이니까 기억해뒀다가 잘 써먹도록 하자.
입력
첫 줄에는 문자열의 길이 L이 들어온다. 둘째 줄에는 영문 소문자로만 이루어진 문자열이 들어온다.
입력으로 주어지는 문자열은 모두 알파벳 소문자로만 구성되어 있다.
출력
문제에서 주어진 해시함수와 입력으로 주어진 문자열을 사용해 계산한 해시 값을 정수로 출력한다.
코드
length = int(input())
line = input()
total = [(ord(line[i]) - 96) * 31 ** i for i in range(length)] # 수열의 합 연산
result = sum(total) % 1234567891 # 나머지 연산
print(result)
해결
문제에서 해싱하는 식을 주기 때문에 문제를 잘 읽고 해싱 공식만 파이썬 코드로 만들면 된다
