Python 랜덤 해시를 이용한 해시 충돌 피하기

1. python dict의 내부 구현 원리 간단하게 Python에서 dict {key:value}는 내부적으로 2가지 배열을 가지고 구현된다 indices : 어떤 위치에 데이터가 있는지 인덱스만 기록 entries: 데이터가 들어온 순서대로 [해시값, key, value]를 저장 초기 상태는 보통 8칸으로 시작하고, indices = [-1,-1,-1,-1,-1,-1,-1,-1] entries = [] 만약 {} 빈 dict에 {10:3}으로 저장한다면...? key의 hash값을 계산하고 배열 크기로 나눈 나머지를 구한다. 10의 hash는 10이고, 이를 8로 나눈 나머지 2를 구해 indices의 2번 칸에 넣는다. indices = [-1,-1,0,-1,-1,-1,-1,-1] 그리고 entr..

• format_list_bulleted 프로그래밍/Python
• · 2026. 8. 25.
• textsms

배열의 모든 수의 쌍의 곱의 합을 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

직접 구현하는 것보다 내장함수를 제대로 쓸 수 있으면 속도가 빠르다

알고리즘을 공부하면서 내장함수를 쓰는게 좋을까? 직접 구현하는게 좋을까?는 누구나 고민하는 부분이다. 크기 n인 배열에서 최댓값을 구하고자 할때 어떻게 하는가? max(A)로 바로 구하거나, for문을 돌아서 최댓값을 갱신해서 찾는다. 어떻게 해도 둘의 시간복잡도는 O(N)이다. 그렇지만 실행시간에는 확실한 차이가 있다. gemini를 이용해 실제 둘의 실행시간의 테스트 코드를 짜서 비교해본다. import timeimport random# 1. 테스트 환경 셋팅N = 1000000 # 100만 개의 데이터print(f"🚀 테스트 데이터 생성 중... (크기: {N}개)")A = [random.randint(1, 1000000) for _ in range(N)]print("✅ 데이터 준비 완료!\n")..

• format_list_bulleted 프로그래밍/Python
• · 2026. 7. 20.
• 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