배열의 모든 수의 쌍의 곱의 합을 O(N)에 구하는 방법

https://atcoder.jp/contests/abc177/tasks/abc177_c C - Sum of product of pairsAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 크기 N인 배열 $A_{1}, A_{2}, ..., A_{N}$이 주어진다. 이때, 이 배열의 가능한 모든 인덱스 쌍 (i,j)에 대해 $A_{i} * A_{j}$의 합을 어떻게 구할까? 여기서 i 가장 쉽게 생각할 수 있는 방법은 당연히 모든 인덱스 쌍을 순회해서 구하는 $O(N^{2})$방법이다. n = int(input())A =..

• format_list_bulleted 대수학
• · 2026. 8. 17.
• textsms

배열을 heap으로 만드는데 O(N)이면 충분하다

파이썬에서 주어진 리스트 배열 A를 heap으로 만드는 방법은 적어도 2가지가 있다. 첫번째는 빈 리스트를 만들고 heappush를 이용해서 하나씩 집어넣는 방법 A의 원소를 하나씩 순회해서 heappush하므로 O(NlogN)이다. 두번째 방법은 heapq에서 지원하는 heapify()를 사용하는 것이다. 집어넣기만 하면 주어진 배열을 바로 heap으로 만들어준다. 이 방법의 시간복잡도는... 놀랍게도 O(N)이다. 실제로 두 방법의 시간을 비교해보면.. import heapqimport randomimport time# 테스트할 데이터 크기 목록 (1만, 10만, 100만, 500만)data_sizes = [10000, 100000, 1000000, 5000000]print(f"{'Data Si..

• format_list_bulleted 프로그래밍/Python
• · 2026. 7. 21.
• textsms

정지 문제(Halting Problem) - 최고의 컴퓨터도 만들 수 없는 프로그램이 존재한다

1. 정지 문제(Halting problem) 프로그램을 만드는 사람이라면 누구나 이런 생각을 한다. "내가 만든 프로그램을 실행하면 정상적으로 종료될지, 무한 루프를 돌지, 실행하지 않고 아는 방법이 있을까?" 그러면 내가 짠 프로그램 D가 정상적으로 종료되는지, 무한 루프를 도는지 검사해주는 또 다른 프로그램 H를 만들면 되는거 아닌가? 그러한 프로그램 H가 존재한다고 가정해보자. H는 분석할 프로그램 D와 프로그램 D의 입력 I를 입력으로 받고, D가 정상적으로 종료하면 True 무한루프를 돌면 False를 유한 시간 내에 return하는 함수이다. 어떤 프로그램 P는 프로그램 H에 다음과 같이 물어본다."프로그램 D에 입력으로 프로그램 D를 주면 어떻게 되냐?" 만약 H가 정상적으로 종료된다라고 ..

• format_list_bulleted 컴퓨터과학(CS)
• · 2026. 7. 14.
• textsms

보이어 무어의 과반수 투표 알고리즘(Boyer-Moore Majority Vote Algorithm)

크기 n인 배열에 있는 원소들 중에서, 개수가 n//2 + 1개 이상인 원소가 하나 존재한다고 하자. 즉, 절반을 넘는 개수를 가진 원소가 무조건 하나가 있을때 이 원소를 찾고 싶다. 어떻게 찾을 수 있을까? 예를 들어 [2,2,1,3,2,2]에서 2는 개수가 4개있고 크기 6인 배열에서 이것이 과반수 이상의 원소이다. 가장 쉬운 방법은 O(N)으로 배열을 순회해서 각 원소의 개수를 모두 찾아 hash에 저장해둔다. 이 hash에서 가장 원소의 개수가 많은 원소를 찾으면 된다. 이러면 시간복잡도 O(N)에 공간복잡도 O(N)에 찾을 수 있다. class Solution: def majorityElement(self, nums: List[int]) -> int: h = {}..

• format_list_bulleted 컴퓨터과학(CS)
• · 2026. 6. 25.
• textsms

프로베니우스의 동전 문제(Frobenius coin problem)와 슈어의 정리(Schur's theorem)

1. 프로베니우스의 동전 문제(Frobenius coin problem) 서로 다른 두 동전 x원, y원이 있을때, 이 두 동전을 각각 적당한 개수를 사용하여, 만들 수 없는 금액중 가장 큰 값은? 이 문제의 정답을 프로베니우스의 수(Frobenius number)라고 부른다. 예를 들어 3원, 5원짜리 동전으로 만들 수 없는 가장 큰 금액은 7원이다. 이 말은 8원 이상의 금액은 무조건 만들 수 있다는 뜻이다. 주의할 점은 7원 밑의 금액 중에서 1,2,4원은 만들 수 없다는 것은 자명하다. 프로베니우스의 수는 x,y가 서로소(최대공약수가 1)일때만 존재한다. 이때, 프로베니우스의 수는 xy - x - y임이 알려져있다. 2. 일반화된 문제 일반적으로는, n개의 동전 $a_{1}, a_{2},...,..

• format_list_bulleted 정수론
• · 2026. 3. 30.
• textsms

어떤 정수의 밑을 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