모듈러 연산과 시간 초과의 관계

코테 준비를 하다 보면 정답이 너무 커지는 것을 막기 위해 특정 값으로 나눠서 리턴하라고 하는 경우가 있다

 

 

정답을 모듈러로 리턴하라고 하니깐 당연히 맨 마지막에 처리하면 된다고 생각했는데 그러면 시간 초과가 난다

우선 for 문 수행 중에 그냥 바로 모듈러를 수행하면 시간 초과를 피할 수 있다.

 

그 이유를 요약하자면 다음과 같다

1. 중간에 모듈러를 매번 수행하든 마지막에 수행하든 결과 자체는 동일하다.

2. 중간에 모듈러를 사용하는 것이 실행 시간에 이점이 존재한다.

 

1. 캐시 메모리 효율성

• CPU 캐시 메모리는 CPU가 자주 사용하는 데이터를 저장하는 작은 공간이다. 캐시 메모리는 메인 메모리(RAM)보다 훨씬 빠르게 접근 가능하다.
• 작은 값의 데이터는 더 작은 공간을 차지하므로, 캐시에 더 많이 저장될 수 있다. 이로 인해 CPU가 더 자주 캐시에서 데이터를 읽고 쓸 수 있어서 성능이 향상된다.
• 큰 값의 데이터는 캐시의 공간을 더 많이 차지하여, 캐시 미스(cache miss)의 가능성이 높아진다. 캐시 미스가 발생하면 CPU는 느린 메인 메모리에서 데이터를 읽어야 하므로 성능이 저하된다.

2. 연산 효율성

• 작은 값을 다루는 연산은 일반적으로 더 적은 CPU 사이클을 소모한다. CPU는 작은 값을 더 빠르게 처리할 수 있으며, 레지스터와 ALU(Arithmetic Logic Unit)도 작은 값을 처리하는 데 더 최적화되어 있다.
• 큰 값을 다루는 연산은 더 많은 CPU 사이클이 필요하다. 특히, 큰 값을 더하거나 곱할 때는 여러 레지스터를 사용하거나 여러 번의 연산을 수행해야 할 수 있다. 이는 전체 연산 속도를 저하시킨다.

3. 메모리 오버헤드 감소

• 작은 값은 프로그램의 메모리 사용량을 줄여준다. 이는 프로그램이 더 적은 메모리를 사용하게 하여, 메모리 관련 병목 현상을 줄여준다.
• 큰 값을 사용하면 메모리 사용량이 증가하여, 메모리 페이지 폴트(page fault)나 스왑핑(swapping)과 같은 문제가 발생할 수 있다. 이는 메모리 접근 시간을 늘리고, 결과적으로 성능 저하로 이어진다.