bright

import math

m, n = map(int,input().split()) # m ~ n 사이 소수 구하기 

prime = [ True for i in range(1000001)]
prime[1] = False # 1 은 소수가 아님 

for i in range(2, int(math.sqrt(n))+1):
  if prime[i] == True:
    j = 2
    while i*j <= n : 
      prime[i*j] = False
      j += 1 

for i in range(m,n+1):
  if prime[i] : 
    print( i)

약수는 대칭적인 구조로 이루어져 있으므로, n 의 제곱근 까지만 구하면 된다. 

ex ) 8 ( 제곱근 : 약 2.9 ) 

1*8 = 2*4 = 4*2 = 8*1 

에라토스테네스의 체 알고리즘을 이용하여 n 까지의 모든 소수를 구하고나서, 

m~ n 까지 출력하면 간단하게 구현 가능하다. 

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

1. 분류 : 스택 / 큐 

2. 풀이 방법 

큰 수를 앞 쪽에 배치하는 문제이다. 가장 큰 수가 나올 때 까지 스택에 넣고 빼고를 반복한다. 

programmers.co.kr/learn/courses/30/lessons/42883

def solution(n):
    answer = 0
    
    dp = [0]* ( n+1 ) 
    dp[1] = 1 
    dp[2] = 2 
    
    if n < 3 : 
        answer = dp[n]
    else: 
        for i in range(3,n+1):
            dp[i] = ( dp[i-1]+ dp[i-2]  ) % 1000000007 
        answer = dp[n]  
    
    return answer

1. 분류 : 다이나믹 프로그래밍 

2. 풀이 : 

가장 기초적인 다이나믹 프로그래밍 문제이므로 잘 이해하고 넘어간다. 

왼쪽 부터 i-1 까지의 길이가 덮여 있으면, 2x1 을 채우는 경우의 수는 1가지 밖에 없다. 

왼쪽 부터 i-2 까지의 길이가 덮여 있으면 2x2 를 채우는 경우의 수는 2가지이지만, 모두 세로인 경우는 위의 방식에서도 count 되므로 가로로 채우는 경우의 수 1가지 라고 할 수 있다. 

따라서 점화식은 An = An-2 + An-1 이 된다. 

3. 유의사항 :

수가 아주 커질 수 있으므로  % 1000000007  처리를 어디서 하느냐에 따라서 효율성 문제가 걸릴 수 있다. 

나누기 연산한 값은 항상 동일하므로 dp 리스트 안에 넣는 과정에서 나눠 주자 

( answer 에 넣을 때 나누거나 return 할 때 나누면 효율성부분 점수 받기가 어렵다 ) 

def solution(n):
    answer = ''
    
    max_num = 3  # 해당 자리수에서 가장 큰 수, 즉 4444.... 
    cnt = 1 
    
    while n > max_num :
        cnt += 1 
        max_num += 3**cnt

    while n > 0 :
        if n > max_num - (max_num - max_num//3 +1 )//3 : 
            answer += '4'
            n -= 3**(cnt)
        elif n > max_num - ((max_num - max_num//3 +1)//3)*2 : 
            answer += '2'
            n -= 2*3**(cnt-1)
        else : 
            answer += '1'
            n -= 3**(cnt-1)

        max_num -= 3**cnt
        cnt -= 1 
    return answer

1. 분류 : 구현..?  

2. 풀이 방법 : 

1 자리 수 : 1 2 4 

2 자리 수 : 11 12 14 / 21 22 24 / 41 42 44 

3 자리 수 : 111 112 114 121 122 124 141 142 144 / ...  444 

n 자리 수의 갯수 : 3^n 

각 자리 수 별 가장 큰 수 ( 4로만 이루어진 수 ) : 3 + 3^2 + 3^3 .. 

step 1 )  내가 몇 자리 수 인지 인지하고 내 자리수에서 가장 큰 값을 찾는다. 

step 2 )  각 자리수의 숫자는 3 단위로 이루어 진다.  

            예를 들어, 2 자리 수인 경우에 상위 1/3 는 맨 앞자리가 4,  2/3 은 2, 마지막은 1 이다. 

            따라서, 자리별로 적절하게 빼 가면서 어떤 수가 올지 파악한다. 

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        table = {
            ')': '(',
            '}': '{',
            ']': '[',
        }
        
        for i in s:
            if i not in table:
                stack.append(i)
            elif not stack or table[i] != stack.pop():
                return False 
            
        return len(stack) == 0 

입력된 괄호 식이 올바른지 판단하는 문제. 

테이블에 없는 값이 들어오면 스택에 넣고 있는 값이 들어오면 스택에서 꺼내서 값이 맞는지 확인한다. 

딕셔너리 자료형을 활용해서 풀이한다. 

leetcode.com/problems/valid-parentheses/

x, y = map(int,input().split()) # 월 일 

month = [0,31,28,31,30,31,30,31,31,30,31,30,31]

day = [ 'SUN', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT' ]

today = 0 

for i in range(1,x):
  today += month[i]

today += y 

print ( day[today%7] )

n = input()
n = n.upper() 

cnt = [0] * 28 

for i in n :
  cnt [ ord(i)-65 ] += 1 

tmp = sorted(cnt)

if tmp[-1] != tmp[-2]:
  print( chr( cnt.index(tmp[-1]) +65 ))
else:
  print("?")

www.acmicpc.net/problem/1157

def solution(n):
    
    dp = [0]*100001
    
    dp[1] = 1 
    dp[2] = 1 
    
    for i in range(3,n+1):
        dp[i] = dp[i-1] + dp[i-2]
        
    answer = dp[n] % 1234567
    return answer

n = list(map(int,input()))
left, right = 0, 0

for i in range( len(n)//2 ):
  left += n[i]
  right += n[ len(n)-i-1 ]

if left == right :
  print("LUCKY")
else:
  print("READY")

# 시간초과 

n, m = map(int,input().split()) # 나무의 수, 필요한 길이 

trees = list(map(int,input().split()))

h = max(trees)

for i in range(h,0,-1):
  total = 0 
  for j in trees:
    if i < j : 
      total += j-i 
  
  if total >= m : 
    print(i)
    break

문제에서 나무의 최대값 이 매우 크게 잡혀 있는 것을 볼 수 있다. 

이렇게 그냥 풀면 당연히 시간초과가 나온다. 

# 정답 

n, m = map(int,input().split()) # 나무의 수, 필요한 길이 

trees = list(map(int, input().split()))
start, end = 1, max(trees)

while start <= end:
    mid = (start+end) // 2
    
    result = 0 
    for i in trees:
        if i >= mid:
            result += i - mid
    
    if result >= m:
        start = mid + 1
    else:
        end = mid - 1
print(end)

이분탐색을 적용하여 시간을 줄여야 한다. 

python3 로는 계속 시간초과 오류가 나서 pypy3 로 제출했다 : (