순열 사이클 분할에 대해 알아보기

1. 순열 사이클 1부터 n까지 정수 n개로 이루어진 배열을 순열이라고 부른다. 예를 들어 [3,2,4,5,1]은 길이가 5인 순열이다. 배열의 인덱스를 '현재 위치', 배열의 값을 '다음에 갈 곳'으로 생각하고 인덱스 > 값으로 향하는 방향 그래프를 만들 수 있다. 즉, [3,2,4,5,1]은 1 > 3, 2 > 2, 3 > 4, 4 > 5, 5 > 1로 간선을 이으면 다음과 같이 방향 그래프를 만들 수 있다. 위 그래프는 2개의 사이클 1 > 3 > 4 > 5, 2 > 2가 있다. 이 사이클들을 순열 사이클이라고 부른다. 전체 순열을 여러개의 독립적인 순열 사이클로 분할하는 것을 '순열 사이클 분할'이라고 부른다. 길이 n인 순열에는 반드시 사이클이 생긴다. 왜냐하면 먼저 1부터 n까지 1개씩만 ..

• format_list_bulleted 알고리즘/순열 사이클 분할
• · 2025. 12. 19.
• textsms

파이썬 리스트로 구현하는 연결리스트 탐색, 삽입, 삭제연산 + 원형 연결리스트

1. 기본 세팅 after[i] = i번 위치의 다음 위치 before[i] = i번 위치의 이전 위치 A[i] = i번 위치의 실제 데이터 #노드 수n = 8#데이터A = [3,1,7,2,5,4,9,10]#다음 위치, 이전 위치after = [-1]*8before = [-1]*8 단일 연결 리스트면, after나 before 하나만 사용해서 한방향으로 연결하고 이중 연결 리스트면 after, before 모두 사용해서 양방향으로 연결 0 > 1 > 2 > 3 > 4 > 5 > 6 > 7로 연결되어있다고 가정하자 반대로 0 for i in range(n-1): after[i] = i+1for i in range(1,n): before[i] = i-1print(after)pr..

• format_list_bulleted 알고리즘/연결리스트
• · 2025. 12. 9.
• textsms

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