컴맹의 컴퓨터공학과에서 살아남기

DFS로 풀기.이때 해당되는 각 row를 compress해준 후에 maps 업데이트.기본적으로 compress는 left상으로 구현되어있으니 (i가 작은 것부터 합치기), right 나 down 같은 경우에는 리스트를 reverse해서 compress하고, 이후에 나온 값을 다시 reverse해주기. import sysinput = sys.stdin.readlineN = int(input())maps = [list(map(int, input().split())) for _ in range(N)]def compress(line): arr = [x for x in line if x != 0] res = [] i = 0 while i

LLM · Transformer 핵심 정리0. 전체 큰 그림Transformer는 Attention(Q/K/V)과 FFN을 반복적으로 쌓아토큰을 점점 더 문맥적으로 의미 있는 벡터로 만드는 모델이다.LLM은 이 Transformer를 decoder-only 구조로 사용해다음 토큰을 예측하는 생성 모델이다.1. Transformer 구조Transformer의 한 layer(block)는 다음 구성으로 이루어진다.입력 토큰 벡터→ Multi-Head Self-Attention (Q/K/V)→ Residual + LayerNorm→ Feed-Forward Network (FFN)→ Residual + LayerNorm Attention만으로는 Transformer가 아니다.Attention + FFN + R..

최소 문의 개수를 구해줘야하기 때문에, 0-1 bfs를 써서 문제를 풀었다.이 문제는 특정 i,j에 도달했을 때, 1. 밖에서 i,j 까지 열었던 문의 개수를 저장2. 죄수 1이 i,j까지 가기 위해 열었던 문의 개수 저장3. 죄수 2가 i,j까지 가기 위해 열었던 문의 개수 저장 이렇게 dist에 문의 개수를 저장해야됨.그리고 나서 각 i,j 에서 더해준 후, 해당 부분이 만약에 문이라면 -2를 해줘서 보정을 해줘야 함. from collections import dequen = int(input())INF = float('inf')def bfs(sx, sy, board, h, w): dist = [[INF]*w for _ in range(h)] queue = deque() queue.append..

fast doubling 피보나치def fib(n): if n==0: return (0,1) a,b = fib(n//2) c = a*(2*b-a) d = a*a + b*b return (c,d) if n%2==0 else (d,c+d)에리스토테네스의 체is_prime = [True]*(n+1)is_prime[0]=is_prime[1]=Falsefor i in range(2,int(n**0.5)+1): if is_prime[i]: for j in range(i*i, n+1, i): is_prime[j]=False유클리드 호제법 (GCD)def gcd(a,b): while b: a,b = b,a%b retur..

N 이 매우 크기 때문에, Fast Doubling 피보나치 를 사용해야됨.F(2k) = F(k) * (2*F(k+1) − F(k))F(2k+1) = F(k+1)^2 + F(k)^2이 방식으로 F(n)을 구할 수 있음, 호출 그림을 보면,fib(45) └─ fib(22) └─ fib(11) └─ fib(5) └─ fib(2) └─ fib(1) └─ fib(0)이렇게 호출해서 구하는 것 알 수 있음.완성 코드import sysMOD = 1000000def fib(n): if n==0: return (0,1) a,b = fib(n//2) # n, n+1 c = a*(2*b - a) % M..

분할정복 문제.우선 x 좌표로 sorting한 다음, 분할을 해서 비교하기분할 한 후, 현재 기준 가장 작은 d를 구함. 이후, 현재 기준 d 보다 x좌표 거리가 작은 애들만 후보로 둠.그 후보들 중, y 좌표간 거리가 d보다 큰 애들 제외, 작은 애들 중에서 min 거리를 구함. 첨에 그냥 보면 분할정복 문제인지 모를 수 도 있을 것 같다.import sysinput = sys.stdin.readlinen = int(input())def dist(a,b): return (a[0]-b[0])**2 + (a[1]-b[1])**2def closest(points): n = len(points) if n = d: break d = min(d, dist(strip[i], strip[j..

이건 분할정복으로 풀면 된다.반씩 나누면서 재귀로 풀면 통과~메인 함수로 푼 이유는, 혹시나 시간 초과 뜰까봐 그렇게 풀었다.저번에 메인함수 안에서 지역으로 쓴거랑, 그냥 전역으로 쓴거랑 코드는 같은데, 시간 초과 결과가 다른걸 봤다.import sysinput = sys.stdin.readlinedef main(): n, b = map(int, input().split()) MOD = 1000 matrix = [list(map(lambda x:int(x)%MOD,input().split())) for _ in range(n)] def mat_mul(x,y): nonlocal MOD, n result = [[0]*n for _ in range(n)] for i in range(n)..

첨에 dp로 풀려고 했는데, 당연하게도 메모리 초과.다음 방법으로는 단순하게 분모에 있는 팩토리얼 부분을 pow(x,-1)할라고 했더니 모듈러 연산이 안된다고한다나 뭐라나..$$a / b % MOD$$ 이게 안된대!def modinv(x): return pow(x, MOD - 2, MOD)이렇게 하면, 모듈러 역원 (Modular Inverse)모듈러에서는 나누기 대신 이렇게 계산한다.$x^{MOD-1} \equiv 1 \pmod{MOD}$$x^{MOD-2} \equiv x^{-1} \pmod{MOD}$ import sysinput = sys.stdin.readlineMOD = 1000000007n, k = map(int, input().split())# factorial 계산def fact(N, ..

처음에는 단순하게 모든 조합을 구해서 조합 합을 구하는 방식으로 했는데,, 예상했던대로 시간초과 ㅎ시간초과난 코드from itertools import combinations, productdef check_win(comb, dice): a_dice = [dice[c] for c in comb] b_dice = [d for d in dice if d not in a_dice] dice_num = [i for i in range(6)] a_dice_comb = list(product(range(6), repeat=len(a_dice))) b_dice_comb = list(product(range(6), repeat=len(b_dice))) win = 0 lose = 0..

튜브도 하나의 node로 생각해서 풀어야하는 문제. 첨에는 연결되어있는 모든 역을 넣었더니 시간초과가 났다.import sysfrom collections import defaultdict, dequeinput = sys.stdin.readlinen, k, m = map(int, input().split())dict = defaultdict(list)adj = [[] for _ in range(n + m + 1)]for t in range(1, m+1): tube = list(map(int, input().split())) tube_node = n + t for s in tube: adj[s].append(tube_node) adj[tube_node].append(s) q = deq..