초이의 끄적끄적

단계별풀기 - 기본수학2

# 4948 베르트랑 공준 (실버2)

• 각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.
• point. 시간초과 에라토스테네스의 체 사용해서 소수 구하기

def isprime(m, n):
    count = 0
    prime = [True] * n  # n개의 [True]가 있는 리스트 생성
    for i in range(2, int(n ** 0.5) + 1):  # n의 제곱근까지만 검사
        if prime[i]:  # prime[i]가 True일때
            for j in range(2 * i, n, i):  # prime 내 i의 배수들을 False로 변환
                prime[j] = False

    for i in range(m, n):
        if i > 1 and prime[i] == True:  # 1 이상이면서 남은 소수들을 출력
            count+=1
    return count

while True:
    n = int(input())
    n_count = 0
    if n==0:
        break
    print(isprime(n+1,n*2+1)) # n< <=2n

단계별풀기 - 기본수학2

#2581 소수 (실버4)

• M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.
• 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.
• point. 소수란 2보다 큰 자연수 중에서 1과 자기 

M = int(input())
N = int(input())
prime = []

for i in range(M,N+1):
    cnt = 0
    if i == 1:
        continue
    for j in range(2,i):
        if i%j == 0:
            cnt += 1
    if cnt == 0:
        prime.append(i)

if len(prime) == 0:
    print(-1)
else:
    print(sum(prime), min(prime))

#2581 소인수분해 (실버4)

• N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

N = int(input())
i = 2
while N != 1: # 분해가 전부 될때까지 반복
    if N % i == 0:
        N = N/i
        print(i)
    else:
        i += 1

# 1929 소수 구하기 (실버2)

• M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 
• 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
• point. 시간 초과 주의 

시간초과 코드

M, N = map(int,input().split())
for i in range(M,N+1):
    cnt = 0
    if i == 1:
        continue
    for j in range(2,i):
        if i%j == 0:
            cnt += 1
    if cnt == 0:
        print(i)

개선 1 ) 제곱근 사용하여 소수 구하기 (시간 4040ms나옴)

N의 약수는 무조건 sqrt(N) 범위에 존재한다.

만약 N이 12라 할때, 12의 제곱근은 약 3.46이다.
12의 약수는 1, 2, 3, 4, 6, 12 이다.
여기서 1과 12를 제외했을 때 이는 2 * 6, 3 * 4, 4 * 3, 6 * 2의 결과이다.

이들의 관계는 몫이 커지면 나누는 값이 작아지거나 나누는 값이 커지만 몫이 작아지는 반비례 관계이다. 결국 N의 절반(제곱근)까지 향하게 되면 이후 몫과 나누는 값이 반대로 바뀌게만 되는 상황이다.

따라서 N의 제곱근까지 나누어 떨어지는지 여부를 조사하면 더 빠르게 소수판별을 할 수 있다.

def isPrime(num):
    if num==1:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num%i == 0:
                return False
        return True

M, N = map(int, input().split())

for i in range(M, N+1):
    if isPrime(i):
        print(i)

개선 2 ) 에라토스테네스의 체를 사용하여 소수 구하기 (시간 252ms 나옴)

소수(x)의 배수는 약수로 무조건 x를 포함하게 된다.
따라서 절대 소수의 배수는 소수가 될 수 없다. 이를 이용한 것이 에라토스테네스의 체이다.
누구나 알고있는 가장 작은 소수인 2부터 시작해서, 2의 배수를 다 지웠으면, 지워지지 않은 수 중에서 다음 값인 3의 배수를 지워나가고 이를 계속해서 반복해 나가면 소수만 남게된다.
마치 체에 걸러서 남는 것들만 뽑아내는 방식이라고 생각하면 된다.

m, n = map(int, input().split())

def isprime(m, n):
  n += 1                            # for문 사용을 위한 n += 1
  prime = [True] * n                # n개의 [True]가 있는 리스트 생성
  for i in range(2, int(n**0.5)+1): # n의 제곱근까지만 검사
    if prime[i]:                    # prime[i]가 True일때
      for j in range(2*i, n, i):    # prime 내 i의 배수들을 False로 변환
        prime[j] = False

  for i in range(m, n):
    if i > 1 and prime[i] == True:  # 1 이상이면서 남은 소수들을 출력
      print(i)

isprime(m, n)

※ 참고 : 소수 판별법 알고리즘

단계별풀기 - 기본수학2

#1978 소수찾기 (실버4)

• 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.
• point. 소수란 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로 나누어떨어지지 않는 자연수이다.

n = int(input())
n_list = list(map(int, input().split()))
n_count = 0

for i in n_list:
    count = 0
    if i == 1:
        continue
    for j in range(2,i):
        if i%j == 0:
            count +=1
    if count == 0:
        n_count +=1
print(n_count)

단계별풀기 - 기본수학1

# 10757 큰 수 A+B (브론즈5)

a,b = map(int,input().split())
print(a+b)

# 1011 Fly me to the Alpha Centaur! (실버1) 

point. 규칙찾고 식으로 표현하기

t = int(input())

for _ in range(t):
    x, y = map(int,input().split())
    distance = y - x
    count = 0  # 이동 횟수
    move = 1  # count별 이동 가능한 거리
    move_plus = 0  # 이동한 거리의 합
    while move_plus < distance :
        count += 1
        move_plus += move  # count 수에 해당하는 move를 더함
        if count % 2 == 0 :  # count가 2의 배수일 때, 
            move += 1  
    print(count)

단계별풀기 - 기본수학1

# 10250 ACM 호텔 (브론즈3)

풀이1) 단순 숫자 세기 (시간 112ms 나옴)

for _ in range(int(input())):
    H, W, N = map(int, input().split())
    count = 0
    for i in range(1,W+1):
        for j in range(1,H+1):
            count +=1
            if count == N:
                print(j*100+i)

풀이2) point. 규칙 찾기 (시간 84ms)

• 손님이 몇 층에 머물지는 N%H와 같고, 몇 번에 머물지는 N//H+1
• 단, N%H가 0일 경우에는 가장 꼭대기층이므로 H층, N//H 에 머문다

for _ in range(int(input())):
    H, W, N = map(int, input().split())
    a = N%H
    b = N//H+1
    if a == 0:
        a = H
        b -= 1
    print(a*100+b)

# 2775 부녀회장이 될테야 (브론즈2)

• 0층 : 1 2 3 4 ...
• 1층 : 1 3 6 10 ..
• 2층 : 1 4 10 20 ..
• => 0층은 1~호수까지, 1층부터 1호는 1 고정, 나머지는 현재값과 전값 더하기

for _ in range(int(input())):
    k = int(input()) #층
    n = int(input()) #호
    apart = [i for i in range(1,n+1)] #0층
    for j in range(k): #층 수만큼 반복
        for k in range(1,n): # 0번째는 1 고정이니까 1~n-1까지
            apart[k] +=apart[k-1] #층별 사람 변경
    print(apart[-1]) #마지막수 출력

# 2839 설탕 배달 (브론즈1)

• sugar가 음수가 되면 설탕이 나누어떨어지지 않는 것이기 때문에 -1 반환
• 5배수가 될때까지 설탕 -3 봉지 +1, 5배수이면 5로 나눈 몫 봉지에 더하기

sugar = int(input())
bag = 0
while sugar >= 0 :
    if sugar % 5 == 0 :  # 5의 배수이면
        bag += (sugar // 5)  # 5로 나눈 몫을 구해야 정수가 됨
        print(bag)
        break
    sugar -= 3
    bag += 1  # 5의 배수가 될 때까지 설탕-3, 봉지+1
else :
    print(-1)

단계별로 풀기 - 기본수학 1 => point.규칙찾기

# 2292 벌집 (브론즈2)

point. 수열 1 + 6 + 12+ 18 .. 6n

n = int(input())
first = 1
room = 1
if n == 1:
    print(1)
else:
    while True:
        first += 6*(room)
        room += 1
        if n <= first:
            print(room)
            break

# 1193 분수찾기 (브론즈2)

point. 규칙찾기

X = int(input())
stage, key_X = 1, 1
while key_X + stage <= X:
    key_X += stage
    stage += 1
    #print(stage, key_X)
step = X - key_X
x, y = step + 1, stage - step
if stage % 2 == 0:
    print('{}/{}'.format(x, y))
else:
    print('{}/{}'.format(y, x))

# 2869 달팽이는 올라가고 싶다 (브론즈2)

point. 시간초과 안나게 하기, 식 구하기

1) 시간 초과 남(실패)

A, B, V = list(map(int, input().split()))
count = 1
result = 0
while True:
    result += A
    if result >= V:
        break
    else:
        result -= B
        count += 1
print(count)

2) 식 구하기 - 정상에 도달하면 떨어지지 않는다.

a, b, v = list(map(int, input().split()))
v = v-a #정상에 도달하면 안떨어지니까 b빼고
if v % (a-b) == 0: 
    print(v//(a-b) +1) # v-a로 이미 횟수 한번을 셋으니까 +1
else:
    print(v // (a - b) + 2) # & 나누어떨어지지 않아서 +1

단계별풀기 - 문자열

# 1152 단어의 개수 (브론즈2)

s = list(input().split())
print(len(s))

# 2908 상수 (브론즈2)

point. arr[::-1] 역순으로 출력하기

A, B = input().split()
A_re = int(A[::-1])
B_re = int(B[::-1])
print(max(A_re,B_re))

# 5622 다이얼 (브론즈2)

point. 문자열 위치 알려주기 .index()

dial = ['ABC', 'DEF', 'GHI', 'JKL', 'MNO', 'PQRS', 'TUV', 'WXYZ']
S = input()
time = 0
for j in range(len(S)):
    for i in dial:
        if S[j] in i:
            time += dial.index(i)+3
print(time)

# 2941 크로아티아 알파벳 (실버5)

point. 문자열 치환 - 문자열.replace("검색문자", "치환문자")

s = input()
cro = ["c=", "c-", "dz=", "d-", "lj", "nj", 's=', "z="]
count = 0
for i in cro:
    s = s.replace(i, "*")

print(len(s))

# 1316 그룹 단어 체커 (실버5)

point. 단어에서 두 글자씩 비교해서 앞 글자가 처음 등장하는 인덱스보다 뒤 글자가 처음 등장하는 인덱스가 더 작으면 뒷 글자는 앞서 이미 등장한 글자가 나온다. 따라서 그룹 단어가 아니다. 

문자열 위치 알려주기 - 문자열.find("검색문자") => 검색문자가 처음 나온 위치 반환, 없으면 -1 반환

result = int(input())
for _ in range(result):
    word = input()
    for i in range(1, len(word)):
        if word.find(word[i-1]) > word.find(word[i]):
            result -= 1
            break
print(result)

# 1021 유기농 배추 (실버2)

point. dfs & dfs로 풀때 최대재귀 한도 설정하기 & 방향벡터 사용

#풀이 1
import sys
sys.setrecursionlimit(10000) # 최대재귀 한도설정

T = int(input()) # 테스트 케이스 갯수
B, ck = [], [] 
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1] # 방향 설정


def dfs(x,y):
    global B, ck
    if ck[x][y] == 1:
        return
    ck[x][y] = 1
    for i in range(4): # 4방향 확인
        xx, yy = x + dx[i], y + dy[i]
        if B[xx][yy] == 0 or ck[xx][yy] == 1:
            continue
        dfs(xx,yy) # 1이고 체크 안되어 있으면 dfs돔


def process():
    global B, ck
    M, N, K = map(int, input().split())
    B = [[0 for i in range(50+2)] for _ in range(50+2)] #배추밭
    ck = [[0 for i in range(50 + 2)] for _ in range(50 + 2)] #체크
    for _ in range(K):
        X, Y = map(int, input().split())
        B[Y+1][X+1] = 1 #배추가 있는곳 1로 변경
    ans = 0
    for i in range(1, N+1):
        for j in range(1, M+1):
            if B[i][j] == 0 or ck[i][j] == 1:
                continue
            dfs(i,j)
            ans +=1
    print(ans)


for _ in range(T):
    process()

# 풀이 2
import sys
sys.setrecursionlimit(100000) # 최대 재귀한도 설정

def dfs(x, y):
    visited[x][y] = True 
    directions = [(-1,0),(1,0),(0,-1),(0,1)] #방향
    for dx, dy in directions:
        nx, ny = x+dx, y+dy
        if nx<0 or nx>=n or ny<0 or ny >=m:
            continue
        if array[nx][ny] and not visited[nx][ny]:
            dfs(nx,ny)

for _ in range(int(input())): # 테스트 케이스 만큼
    m,n,k = map(int, input().split())
    array = [[0]*m for _ in range(n)] # 배추밭
    visited = [[False]*m for _ in range(n)] # 체크 확인용
    for _ in range(k): # 배추가 있는 좌표에 1
        y,x = map(int, input().split())
        array[x][y]=1
    result = 0
    for i in range(n):
        for j in range(m):
            if array[i][j] and not visited[i][j]: #배추가 있는데 방문안한 곳이면
                dfs(i, j)
                result+=1
    print(result)

단계별 풀기 - 문자열

#11654 아스키 코드 (브론즈5)

point. 아스키코드 변환 함수 ord()

n = input()
print(ord(n))

# 11720 숫자의 합 (브론즈2)

point. 각자리 더하기 - 숫자 문자로 받아서 각 자리수 숫자로 더하기

n = int(input())
n_num = input()
sum = 0
for i in n_num:
    sum += int(i)

print(sum)

# 10809 알파벳 찾기 (브론즈2)

point. 문자열 위치 찾기 함수 s.find()

s = input()
result = []
alpa = 'abcdefghijklmnopqrstuvwxyz'
for i in alpa:
    result.append(s.find(i))

for i in result:
    print(i, end=" ")

# 2675 문자열 반복 (브론즈2)

point. 문자곱은 반복횟수

tc = int(input())
for i in range(tc):
    R, S = input().split()
    result = ""
    for i in S:
        result += i*int(R)
    print(result)

# 1157 단어 공부 (브론즈1)

point. 문자 개수 세기 count() / 문자 위치 index()

s = input()
s_up = s.upper()
apla = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
result = []
for i in apla:
    result.append(s_up.count(i))

if result.count(max(result)) > 1:
    print("?")
else:
    max_index = result.index(max(result))
    print(apla[max_index])