[TIL] 정글 94일차 - 나만의 무기

신승준·2022년 7월 1일
0

HTML

알고리즘

백준

  • 수학
      1. 최대공약수와 최소공배수
import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

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

result = -1

while True:
    if n >= m:
        n %= m
        
        if n == 0:
            gcd = m
            break
            
    else:
        m %= n
        
        if m == 0:
            gcd = n
            break
            
lcm = initial_n * initial_m // gcd

print(gcd, lcm)



프로그래머스

  • Level 1
    • 캐시
from collections import deque

def solution(cacheSize, cities):
    if cacheSize == 0:
        return 5 * len(cities)
    
    def lower(x):
        return x.lower()
    
    cities = list(map(lower, cities))
    cache = deque()
    result = 0
    
    for city in cities:
        if city in cache:
            cache.remove(city)
            cache.append(city)
            result += 1
            
        else:
            result += 5
            
            if len(cache) == cacheSize:
                cache.popleft()
                cache.append(city)
                
            else:
                cache.append(city)

    return result
  • cache hit를 한 경우에, 해당 city는 가장 최근에 참조된 것이니 맨 뒤로 보내줘서 가장 나중에 빠져야되는 city로 인식되게 해야되는데 이를 까먹고 놓쳐서 처음엔 실패했었다.
    • 맨 앞에 있는 것이 가장 먼저 들어온 것으로 인식하여, cache 공간이 꽉 찼을 경우, 가장 먼저 들어왔던 city를 빼도록 알고리즘을 구성하였다. 이는 queue 동작과 같다고 생각하여 queue를 사용했다.
    • list로 del이나 remove를 써도 되지만, 이는 삭제 시 요소들이 shift되어 시간 비용이 조금 늘어날 수 있다는 생각에, 삭제가 일어나도 shift되지 않는 queue를 사용했다.

언어

C

JavaScript

Python


궁금한 점

하루를 마치고

타임 스낵용으로 토론 배틀 아이디어가 나왔다.

profile
메타몽 닮음 :) email: alohajune22@gmail.com

0개의 댓글