현재 백준 실버4
골드1 문제 기준 15점, 실버4 8점
그냥 자기 티어에 맞는 문제를 푸는 것이 가장 좋다.

그 동안에 진행했던 알고리즘에서 다시 봐야하거나 인상깊었던 문제를 다시 짚어보는 시간을 갖도록 하겠다.

백준 1016

min, max = map(int, input().split())
M = int(max**0.5)
P_n = [False, False, True] + [True]*(M-2)
P_n[4::2] = [False]*(M//2-1)
for i in range(3, M+1, 2):
    if P_n[i]:
        P_n[i+i::i]=[False]*len(P_n[i+i::i])

prime = []
for idx, ele in enumerate(P_n):
    if ele:
        prime.append(idx)
li = [i**2 for i in prime]
#print("li : ", li)

result_li = [1]*(max-min+1)
sw = True
for i in li:
    if sw and i <= min:
        if min%i != 0:
            diff = i - min % i
            result_li[diff::i] = [0] * len(result_li[diff::i])
        else:
            result_li[::i] = [0] * len(result_li[::i])
    else:
        if sw: sw = False
        diff = i - min
        result_li[diff::i] = [0] * len(result_li[diff::i])

print(sum(result_li))

결과

구현하는 과정에서 소수 리스트 구현

소수 리스트를 구현하는 실행 시간이 꽤 길다

경우에 따라 구현하지 않고 중복되는 소인수를 그대로 처리하여도 시간은 적을 수 있다.

백준 1049

import sys
from math import ceil
input = sys.stdin.readline

N, M = map(int, input().split())
min_pack_unit = [*map(int,input().split())]

for _ in range(M-1):
    pack_unit = [*map(int,input().split())]
    if min_pack_unit[0] > pack_unit[0]:
        min_pack_unit[0] = pack_unit[0]
    if min_pack_unit[1] > pack_unit[1]:
        min_pack_unit[1] = pack_unit[1]

if min_pack_unit[0] > min_pack_unit[1]*6:
    min_pack_unit[0] = min_pack_unit[1]*6

print(min(N//6*min_pack_unit[0]+N%6*min_pack_unit[1], ceil(N/6)*min_pack_unit[0]))

import sys
from math import ceil
input = sys.stdin.readline

N, M = map(int, input().split())
min_pack_unit = [*map(int,input().split())]

for _ in range(M-1):
    pack_unit = [*map(int,input().split())]
    min_pack_unit[0] = min(min_pack_unit[0], pack_unit[0])
    min_pack_unit[1] = min(min_pack_unit[1], pack_unit[1])
min_pack_unit[0] = min(min_pack_unit[0], min_pack_unit[1]*6)

print(min(N//6*min_pack_unit[0]+N%6*min_pack_unit[1], ceil(N/6)*min_pack_unit[0]))

결과

조건문 -> max로 구현
실행 시간은 차이 없음

백준 2217

import sys
input = sys.stdin.readline
N = int(input())
num = {}
rope =[]
for _ in range(N):
    n = int(input())
    rope.append(n)
    if n not in num:
        num[n]=1
    else:
        num[n]+=1
rope.sort()
rope = {i for i in rope}
#print(rope)

tmp, result = N, 0
for i in rope:
    a = i*tmp
    result = max(result, a)
    tmp -= num[i]
print(result)

결과

리스트 중복 인자 없애기 : set casting

입력 인자가 sort X -> dictionary로 중복 수 세기

리스트

len

complexity of len() : O(1), very fast

slicing

li=[]
for i in range(9):
    li.append(i)

li[:3]='****&'
print(li)

['*', '*', '*', '*', '&', 3, 4, 5, 6, 7, 8]

3번째 인자를 넣지 않은 slicing은 대입연산으로 iterable하게 작동한다. 하지만

li=[]
for i in range(9):
    li.append(i)
li[:3]='****&'
print(li)
li=[]
for i in range(8):
    li.append(i)
li[::2]='**'*2
print(li)

['*', '*', '*', '*', '&', 3, 4, 5, 6, 7, 8]
['*', 1, '*', 3, '*', 5, '*', 7]

위 코드처럼 3번째 인자가 주어졌을 경우는 대입되는 element의 수를 len(li[::2])로 맞춰주어야 한다.

주의할 점

li=[]
for i in range(9):
    li.append(i)
print(len(li))
print(li)
li[:3][1:]='!@#$%'
print(li[:3][1:])
print(len(li))

9
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[1, 2]
9

-> li[:3][1:] 와 같은 2중 슬라이싱은 대입 연산에 의미가 없으며 출력만이 의미를 갖는다.

백준 1837

def is_hard(a, n):
    if n == 2:
        return ("GOOD", )
    if a % 2 == 0:
        return "BAD", 2
    save = [True] * (n // 2)
    for i in range(3, int(n ** 0.5) + 1, 2):
        if save[i // 2]:
            k = i * i
            save[k // 2::i] = [False] * ((n - k - 1) // (2 * i) + 1)
    for i in range(1, n // 2):
        if save[i] and a % (2 * i + 1) == 0:
            return "BAD", 2 * i + 1
    return ("GOOD", )

print(*is_hard(*map(int, input().split())))

결과

소수 리스트 생성에 백준 1016에서 내가 구현한 것보다 완성도 있는 코드이다.

함수 내부 참조

함수 내부에서는 외부에서 선언한 변수의 값을 수정할 수 없다.

• 참조하고 있는 object의 element 수정 가능(참조값이 변하지는 않으므로)

* 연산

n=3
result = [[0]*n]*n
print(result)
for i in result:
    print(id(i))

[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
2855280441408
2855280441408
2855280441408

각 element의 id가 동일하므로 하나라도 변경하면 모두 바뀐다.

if-else 한줄로

백준 10773

from sys import stdin
input()
l=[]
for i in map(int, stdin):
    l.append(i) if i else l.pop()
print(sum(l))

위 코드와 같이 if else 한줄로 쓰는 것이 가능하다.