이재문

원문

리뷰

LLM 모델들 갑자기 팍 나오네

위기의식 느꼈나..

머리 터지겠네

원문

리뷰

원문

 
리뷰

원문

 
리뷰

문제: 

[BOJ 30897] 0으로 만들기 

알고리즘 : 애드혹, 누적합

https://www.acmicpc.net/problem/30897

풀이

예제 입력은 도움이 되지 않으니 입력 조건에 맞는 작은 입력을 만들어 봅시다

10

1 4 2 2 4 1 3 1 4 2

예제 입력이 이렇다고 가정하면 사실 본질은 여기서 +-를 통해 0이 되는 연속 되는 수열이 있냐는 문제로 바꿀 수 있는데

저 예제의 경우 

1*4*(2-2)*4*... 이렇게 하면 0을 곱하니까 무조건 0이 되기 때문이죠

하지만 일일이 전부 더하거나 빼면서 0이 되는게 있나 확인하면 O(N**2 ∗ 2**N) 걸릴거 같네요

여기서 A의 범위가 10000인데 N이 30000개인게 도움을 주는데

누적합으로 계속해서 더해나가면서 누적합이 적용된 앞리스트 인자가 +면 뒤에 인자에 -로 연산해주시면 누적합 배열이

1 -3 -1 1 -3 -2 1 ... 이런식으로 나오는데

이 범위가 [-10000, 10000]이 되게 됩니다

저 범위안에 모든 값들이 한번씩만 나온다고 하면 2만 1개이고

여기서 N의 갯수가 무조건 3만개 이상이므로 무조건 겹쳐서 나오는 값이 존재하는데

누적합 알고리즘 공식이 수열 A의 누적합 배열 S의 i+1부터 j까지의 누적합은 Sj-Si이고

Si == Sj가 되면 i+1부터 j까지의 합은 0입니다.

따라서 같은 값을 가지는 index 하나는 무조건 있으니 그것을 두개 찾아서 괄호 안에 본래의 연산을 해주고 나머지는 *로 묶으면 됩니다.

코드

import sys

input=sys.stdin.readline

n = int(input())

l = list(map(int, input().split()))
flag = True
s = l[0]
d = {l[0]:0}
for i in range(1, n):
    if s > 0:
        s -= l[i]
        try:
            x1 = d[s]
            x2 = i
            break
        except:
            d[s] = i
    elif s < 0:
        s += l[i]
        try:
            x1 = d[s]
            x2 = i
            break
        except:
            d[s] = i
    elif s == 0:
        flag = False
        x1 = i
        break
    
print('YES')
if flag:
    if s > 0:
        s *= -1
    for i in range(x1):
        print(f'{l[i]}*', end='')

    print(f'{l[x1]}*(',end='')
    for i in range(x1+1, x2+1):
        if s > 0:
            s -= l[i]
            print(f'-{l[i]}', end='')
        else:
            s += l[i]
            if i == x1+1:
                print(l[i], end ='')
            else:
                print(f'+{l[i]}', end='')
    if x2+1 == n:
        print(')')
    else:
        print(')*', end='')

        for i in range(x2+1,n-1):
            print(f'{l[i]}*', end='')
        print(l[n-1])
else:
    s = l[0]
    print(f'({l[0]}', end='')
    for i in range(1, x1):
        if s > 0:
            s -= l[i]
            print(f'-{l[i]}', end='')
        else:
            s += l[i]
            if i == x1+1:
                print(l[i], end ='')
            else:
                print(f'+{l[i]}', end='')
    print(')' ,end = '')
    for i in range(x1, n):
        print(f'*{l[i]}', end='')

코드 엄청 못 짰는데 암튼 이런식으로 하면 될듯하네요

논문 작성시 유용한 도구 모음

https://youngseokim.tistory.com/72

원문

리뷰

원문

https://openai.com/index/learning-to-reason-with-llms/

리뷰

원문

리뷰

OP-RAG에 대해서 말 할거면 왜 굳이 LongContext를 꺼내서 얘기하는지는 잘 모르겠음

OP-RAG가 실험적으로 증명할게 많이 없나 이생각도 하게 되는