O(1)에 스택의 최솟값을 찾는 min stack 기법?

https://www.acmicpc.net/problem/8858 은행원이 현금 보유액 S를 가지고 있다. 고객이 입금을 하러 온다면, 입금 금액을 기록하고 고객이 가져온 현금을 새 봉투에 넣은 다음, 이전 입금 봉투 위에 쌓는다. 입금 봉투는 이처럼 스택 구조로 쌓이게 된다. 고객이 X원을 출금하러 온다면, 봉투 스택이 비어있는 경우 전액을 현금 보유액 S에서 지급 봉투에 든 금액들 중 가장 작은 금액보다 X가 작다면, 전액을 현금 보유액 S에서 지급 그렇지 않다면, 봉투 스택의 맨 위에서부터 하나씩 꺼낸 다음, 필요한 금액을 충당 마지막에 꺼낸 봉투에서 일부 금액만 사용하면, 남은 돈은 현금 보유액 S로 넣는다. 만약 모든 봉투를 다 사용했는데 X를 다 지급하지 못하면 남은 금액은 현금 보유액 S에..

• format_list_bulleted 알고리즘/자료구조(스택,큐,해시맵)
• · 2025. 11. 27.
• textsms

대표자가 같으면 union하지 말아야한다 (union by rank 주의점)

https://atcoder.jp/contests/abc420/tasks/abc420_e E - Reachability QueryAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp n개의 정점과 0개의 간선이 주어진다. 각 정점은 1번부터 n번까지 번호가 있고, 처음에 모든 정점은 흰색이다. q개의 쿼리가 주어지는데 각 쿼리는 3종류중 하나이다. 1) u와 v를 무방향 간선으로 연결 2) v가 흰색이면 검은색으로 바꾸고 검은색이면 흰색으로 바꿈 3) 정점 v에서 검은색 정점에 0개 이상의 간선을 타고 도달할 수 있는지 검사한다..

• format_list_bulleted 알고리즘/분리집합
• · 2025. 8. 27.
• textsms

Paper2Code: Automating Code Generation from Scientific Papers in Machine Learning

https://arxiv.org/abs/2504.17192?utm_source=pytorchkr&ref=pytorchkr Paper2Code: Automating Code Generation from Scientific Papers in Machine LearningDespite the rapid growth of machine learning research, corresponding code implementations are often unavailable, making it slow and labor-intensive for researchers to reproduce results and build upon prior work. In the meantime, recent Large Languag..

• format_list_bulleted AI 논문/AI trend research
• · 2025. 8. 21.
• textsms

Python의 리스트 인덱싱은 생각보다 비용이 비싸다

변수가 많으면 리스트로 변수 수를 줄여서 인덱싱하여 각 원소에 접근하는데, 이 비용이 생각보다 비싸다. 몇번 반복 안하면 무시할정도긴 해도 수천만번, 수억번이상 반복하면 이 비용을 무시할 수 없을정도로 커진다 변수가 3개 필요한 경우 리스트를 이용해서 길이가 3인 리스트를 만들고 다음과 같은 코드를 작성하였다. import times = time.time()for _ in range(40320): b = [0,0,0] score = 0 for _ in range(50): b[0] = 1 b[1] = 1 b[2] = 1 for _ in range(120): score += (b[0]+b[1]+b[2]..

• format_list_bulleted 프로그래밍/Python
• · 2025. 8. 19.
• textsms

좌표평면 위의 모든 점들에서 거리 합이 가장 가까운 점을 찾는 방법

https://atcoder.jp/contests/abc419/tasks/abc419_c C - King's SummitAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 좌표평면 위의 n개의 점들이 1초에 팔방향으로 움직이거나 멈춰있을 수 있다. 이때, 모든 점들이 하나의 점에 모인다고 할때, 걸리는 최단 시간을 구한다면? -----------------------------------------------------------------------------------------------------------------..

• format_list_bulleted 기하학
• · 2025. 8. 18.
• textsms

중간에서 만나기3 - 부분집합의 합이 s가 되는 경우의 수를 세는 놀라운 방법

1. 중간에서 만나기(meet in the middle) 중간에서 만나기 알고리즘은, 다익스트라 알고리즘처럼 전형화된 그런 알고리즘은 아니다. 다이나믹 프로그래밍 같은 알고리즘이라고 해야할까 완전탐색의 시간복잡도가 매우 높을 때, 이를 절반으로 줄이는 기법이다. 가능한 경우의 수를 절반씩 나누어 탐색한 뒤 그 결과를 조합하여 정답을 찾는 방식이다. 예를 들어 브루트포스가 $O(2^{N})$으로 매우 높은 경우, $O(2^{N/2})$로 줄일 수 있을때 효과적이다. N = 40인 경우만 해도 아예 불가능한 정도가 $10^{6}$정도로 가능해진다 예를 들어 주어진 수열 A에서 부분집합의 합이 S가 되는 경우의 수는 몇가지일까? 부분집합의 개수는 $2^{N}$이므로, 시간복잡도는 $O(2^{N})$ 1)..

• format_list_bulleted 알고리즘/중간에서 만나기
• · 2025. 7. 4.
• textsms