어떤 정수의 밑을 2로 하는 로그값 $log_{2}x$을 정확하게 구하는 방법

어떤 정수 n이 주어졌을때, n보다 작거나 같으면서 가장 가까운 2의 거듭제곱이 필요할때가 있다 구체적으로 $2^{x} = n$을 만족하는 정수 x를 찾고 싶을 때가 있다. 제일 쉬운 방법은? import mathn = int(input())print(int(math.log2(n))) 근데 얘는 문제가 n이 엄청 크면 실수오차 발생으로 틀릴 수 있다는거 이를 피하는 방법은 2씩 직접 곱해서 찾는 방법이 있고 import mathn = int(input())x = 0v = 1while v n: break x += 1 print(x) 그런데 이 방법은 O(logN)이다. 메소드 중에 bit_length()라는 메소드가 있다 어떤 정수를 이진수로 표현할때 그 이..

• format_list_bulleted 알고리즘/비트마스킹
• · 2026. 3. 25.
• textsms

더블링(doubling, binary lifting, 희소배열,sparse table)에 대해 배우기

https://deepdata.tistory.com/972 희소 배열(sparse table) 자료 구조 배우기https://cp-algorithms.com/data_structures/sparse-table.html Sparse Table - Algorithms for Competitive ProgrammingSparse Table Sparse Table is a data structure, that allows answering range queries. It can answer most range queries in $O(\log n)$, but its trdeepdata.tistory.com 희소 배열(sparse table)로도 알려진 더블링(doubling) 기법은 어떤 횟수 K를 2의 거듭제..

• format_list_bulleted 알고리즘/희소배열(더블링)
• · 2026. 1. 1.
• textsms

모노토닉 스택(monotonic stack)을 이용한 나보다 큰 첫 번째 수 찾기 문제(오큰수,NGE,next greater element)

1. 모노토닉 스택(monotonic stack) 스택 내부의 원소들을 항상 오름차순, 혹은 내림차순 상태를 유지하도록 만드는 자료구조 나보다 크거나, 작은 숫자가 언제 처음 나오는지를 찾는데 유용하다. 알고리즘 문제에서 보통, "배열에서 나보다 크면서 오른쪽에 있는 수 중 첫번째 수는?" 예를 들어, [5,3,1,4,2]가 있다고 하자. 각 숫자에 대해서 "오른쪽에 있는 나보다 큰 첫번째 수"들을 모두 O(N)에 찾으라고 한다면? 스택 []을 두고, 왼쪽부터 오른쪽 차례대로 순회한다. 스택이 비어있으니까 [5] 2번째 3이 들어오는데, 스택의 마지막 수 5가 3보다 더 크므로 그대로 입장 [5,3] 3번째 1이 들어오는데 스택의 마지막 수 3이 1보다 더 크므로 [5,3,1] 4번째 4가 들어오는데 ..

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

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

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