import sys from collections import deque input = sys.stdin.readline n = int(input()) q = deque([i for i in range(1, n+1)]) while len(q)!=1: q.popleft() q.append(q.popleft()) print(q[0]) 큐로 풀면 되는 아주 간단한 문제다 시간 복잡도 deque는 double-linked list로 구현되어 있음 그래서 양 끝의 요소의 추가/삭제가 O(1)을 만족 반면, Python의 list는 fixed size memory blocks(array)로 구현되어 있음. 링크드 리스트처럼 보이지만 고정된 사이즈의 메모리를 갖는 array 따라서 리스트의 마지막 원소 삭제는 O(1..

import sys input = sys.stdin.readline DIV = 1000000009 dp = [1, 2, 4, 7] for _ in range(int(input())): # 방법의 총 수 dp, 순서 바꾸는 것도 포함이네.. n = int(input()) for i in range(len(dp), n): # 알아서 1, 2, 3이 각각 들어갈 것 -> 겹치는게 없음 dp.append((dp[i-1] + dp[i-2] + dp[i-3]) % DIV) print(dp[n-1]) 점화식은 발견 했는데 시간 초과, 메모리 초과를 어떻게 해결해야할지 생각해내는게 어려웠다. 이를 해결한 방법은 다음과 같다. 1. 모든 테스트케이스는 같은 DP 값을 가지니 DP를 global 하게 사용 2. 이미 있는..

import sys input = sys.stdin.readline n = int(input()) dp = [0] * (n+2) dp[0], dp[1], dp[2] = 0, 1, 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n]) 간단한 피보나치 문제!

def solution(people, limit): boat = [] people.sort() light = people[0] idx = 0 for i in range(len(people)-1, -1, -1): if idx > i: break person = people[i] if person + light > limit: # 가장 가벼운 사람이랑도 못앉으면 혼자 가야지 boat.append(person) continue # 가장 가벼운 사람이랑은 같이 앉아갈 수 있다! 그럼 앉아가슈 if idx < i: boat.append(person + light) idx += 1 light = people[idx] continue # 앉아갈 짝이 없으면 혼자 가렴 boat.append(person) return ..

dictionary 하나로 풀어보려고 했는데 도저히 각이 안나와서 그냥 dictionary 2개를 썼다 그래서 풀이가 좀 더럽긴하지만,, 일단 맞았으니 올려본다 def solution(genres, plays): album_by_genre = {} # genre, (play, index) plays_by_genre = {} # (genre, plays) for i, play in enumerate(plays): g = genres[i] if g in plays_by_genre: plays_by_genre[g] += play album_by_genre[g].append((play, i)) else: plays_by_genre[g] = play album_by_genre[g] = [(play, i)] for..

백준 '9375번, 패션왕 신해빈' 문제와 완전 똑같기 때문에 풀이도 똑같다. 해당 문제 풀이는 여기 참고! def solution(clothes): closet = {} for cloth, type in clothes: if type not in closet: closet[type] = 1 closet[type] += 1 answer = 1 for k, v in closet.items(): answer *= v return answer - 1