알고리즘

이 영상은 프로그래밍 미디어에서 흔히 쓰이는 엄청나게 빠름(Blazingly Fast)이라는 표현의 실체를 탐구하며, 대규모 피보나치 수를 1초 안에 계산하는 도전을 통해 성능 최적화의 단계를 보여줍니다. 단순한 마케팅 용어를 넘어 수학적 원리인 고속 푸리에 변환(FFT)과 넘버 테오레틱 트랜스폼(NTT)을 프로그래밍에 적용하여 파이썬의 성능을 압도하고 하드웨어의 한계를 돌파하는 과정을 상세히 기록합니다. ### 1. 하드웨어 환경과 파이썬의 성능 한계 * 장비의 하향 평준화: 기존 메인 PC 대신 형의 오래된 PC를 활용해 우분투 서버를 구축하여 테스트 환경을 구성했습니다. * 파이썬의 선전: 파이썬은 대형 정수 계산 시 점근적으로 빠른 카라추바 곱셈 알고리즘을 사용하므로, 초보적인 정수 곱셈 방식을 쓰는 C 언어 코드보다 때때로 더 나은 성능을 보여주기도 합니다. * 목표 설정: 단순히 파이썬을 이기는 것이 아니라, 이론적으로

2026. 1. 5. 12:21 | 댓글: 0

# 알고리즘 성능을 1,600,000% 향상시키는 7단계 최적화 과정 이 영상은 '어드벤트 오브 코드 2022'의 문제(긴 문자열에서 14개의 서로 다른 문자 찾기)를 예시로 삼아, 동일한 시간 복잡도 내에서 구현 방식에 따라 성능이 얼마나 극적으로 달라질 수 있는지를 보여줍니다. 해시 세트를 사용하는 가장 기본적인 접근법에서 시작하여 비트 조작, 컴파일러 최적화, 그리고 멀티스레딩을 활용한 극한의 속도 개선 과정을 체계적으로 설명합니다. * 문제 정의: 14개의 고유 문자 찾기 * 매우 긴 문자열 속에서 연속된 14개의 문자가 모두 서로 다른 지점을 찾습니다. * 해당 지점을 찾으면 그 바로 다음 문자의 위치를 보고합니다. * 가장 직관적인 첫 해결책은 해시 세트를 사용하여 14개씩 문자를 넣고 길이를 확인하는 방식입니다. * 1단계 최적화: 조기 종료 도입 (92% 성능 향상) * 14개를 모두 넣은 뒤 확인하는 대신, 문자

2026. 1. 5. 11:40 | 댓글: 0

이 영상은 Rust와 C++의 표준 해시 테이블보다 10배 이상 빠른 '완벽한 해시 테이블(Perfect Hash Table)'을 구현하기 위한 여정과 그 과정에서 얻은 10가지 성능 최적화 팁을 상세히 다룹니다. * 해시 테이블의 중요성과 기본 원리 * 해시 테이블은 소프트웨어에서 가장 중요한 자료구조 중 하나로, 언어마다 딕셔너리, 연관 배열, 오브젝트 등 다양한 이름으로 불립니다. * 대중적인 해시 테이블은 범용적으로 설계되어 최적화되어 있으나, 특정 상황에서는 성능이 부족할 수 있습니다. * 요일 이름을 숫자로 매핑하는 예시에서, 첫 글자를 인덱스로 사용하는 간단한 해시 함수를 생각할 수 있습니다. * 하지만 'Thursday'와 'Tuesday'처럼 첫 글자가 같은 경우 '충돌(Collision)'이 발생하며, 이는 해시 테이블의 성능을 저하시키는 주요 원인이 됩니다. * 완벽한 해시 함수(Perfect Hash Function)의 개념

2026. 1. 5. 07:10 | 댓글: 0