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