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/