용어 메모 라틴어 단어에서 유래 각서 ( 기억하다 )는 미국 영어로 흔히 메모(memo)라고 줄여 부르는데, 함수의 결과를 기억할 만한 것으로 변환한다는 뜻이다.

컴퓨팅에서 메모이제이션은 반복적인 결과 계산을 제거하고 동일한 입력을 처리하는 함수에 대한 반복 호출을 방지함으로써 컴퓨터 프로그램 속도를 높이는 데 사용됩니다.

메모이제이션이란 무엇인가

목차

• 메모이제이션이란 무엇인가요?
• 메모이제이션을 사용하는 이유>
• 메모이제이션은 어디에 사용하나요?
• 메모 유형
• 동적 프로그래밍에서 메모화 기술은 어떻게 사용됩니까?
  • 하향식 접근 방식
  • 상향식 접근 방식
• Memoization은 Tabulation과 어떻게 다른가요?
• 메모를 위한 코딩 연습 문제
• 자주 묻는 질문
  • 1) DP보다 메모이제이션이 더 좋은가요?
  • 2) 메모이제이션은 캐싱과 동일한가요?
  • 3) 왜 메모이제는 하향식인가요?
  • 4) 메모이제이션은 재귀를 사용합니까?
  • 5) 도표화 또는 메모화를 사용해야 합니까?
  • 6) 메모이제이션은 어디에 사용되나요?
  • 7) 왜 메모이제이션이라고 불리는가?
  • 8) 메모이제이션은 어떻게 시간 복잡도를 줄여주나요?
  • 9) 메모이제이션과 캐싱의 차이점은 무엇인가요?
  • 10) 왜 표 작성이 메모 작성보다 빠른가요?
• 결론

메모이제이션은 왜 사용되나요?

메모는 특정 형태의 메모입니다. 캐싱 에서 사용되는 것 동적 프로그래밍 . 캐싱의 목적은 프로그램 성능을 향상하고 나중에 사용할 수 있는 데이터에 대한 액세스를 유지하는 것입니다. 기본적으로 하위 문제에 대해 이전에 계산된 결과를 저장하고 동일한 하위 문제에 대해 저장된 결과를 사용합니다. 이렇게 하면 동일한 문제에 대해 계속해서 계산해야 하는 추가 노력이 줄어듭니다. 그리고 우리는 동일한 문제가 계속해서 발생한다면 그 문제는 본질적으로 반복적이라는 것을 이미 알고 있습니다.

메모이제이션은 어디에 사용하나요?

우리는 메모이제이션 기술을 사용할 수 있습니다. 이전에 계산된 결과를 사용 그림 속으로 들어옵니다. 이런 종류의 문제는 주로 다음과 같은 상황에서 사용됩니다. 재귀 , 특히 다음과 관련된 문제의 경우 중복되는 하위 문제 .

동일한 하위 문제가 계속해서 반복되는 예를 들어보겠습니다.

메모 기능을 사용할 위치를 보여주는 예:

  Let us try to     find the factorial of a number    .>

아래는 재귀적 방법 숫자의 계승을 찾으려면:

int 계승(unsigned int n)
{
만약 (n == 0)
1을 반환합니다.
n * 계승(n – 1)을 반환합니다.
}

이 재귀적 방법을 사용하면 어떻게 될까요?

위 코드 조각에 대한 전체 코드를 작성하면 코드에 2가지 메서드가 있다는 것을 알 수 있습니다.

1. factorial(n) 2. main()>

이제 2, 3, 9, 5의 계승을 찾는 것과 같이 계승을 찾기 위한 여러 쿼리가 있는 경우에는 계승() 메서드를 4번 호출해야 합니다.

factorial(2) factorial(3) factorial(9) factorial(5)>

Factorial을 찾는 재귀적 방법

따라서 숫자 K개의 계승을 찾는 데 필요한 시간 복잡도는 다음과 같다고 말하는 것이 안전합니다. 오(N*K)

• 에) 특정 숫자의 계승을 찾으려면
• 화살) 계승() 메서드를 K 번 호출합니다.

Memoization이 그러한 문제에 어떻게 도움이 될 수 있습니까?

위의 문제에서 9의 팩토리얼을 계산하는 동안 다음과 같은 사실을 알 수 있습니다.

C++ 분할 문자열

• 우리는 2의 계승을 계산하고 있습니다
• 우리는 또한 3의 계승을 계산하고 있습니다.
• 그리고 5의 계승도 계산하고 있습니다.

따라서 계산을 처음 수행할 때 각 개별 계승의 결과를 저장하면 단 O(1) 시간 내에 필요한 숫자의 계승을 쉽게 반환할 수 있습니다. 이 과정은 다음과 같이 알려져 있습니다. 메모 .

메모 기능을 사용한 솔루션(메모 기능은 어떻게 작동하나요?):

9의 계승값을 먼저 찾고 개별 하위 문제의 결과를 저장하면 O(1)에서 각 입력의 계승값을 쉽게 인쇄할 수 있습니다.

따라서 메모이제이션을 사용하여 팩토리얼 번호를 찾는 데 드는 시간 복잡도는 다음과 같습니다. 에)

• 에) 가장 큰 입력의 계승을 찾으려면
• 오(1) 각 입력의 계승을 인쇄합니다.

메모 유형

메모이제이션의 구현은 문제 해결을 담당하는 매개변수 변경에 따라 달라집니다. 메모이제이션 기술에 사용되는 캐싱에는 다양한 차원이 있으며, 다음은 그 중 일부입니다.

• 1D 메모: 모든 함수 호출 후에 값이 일정하지 않은 인수가 하나만 있는 재귀 함수입니다.
• 2D 메모: 모든 함수 호출 후에 값이 일정하지 않은 인수가 두 개만 있는 재귀 함수입니다.
• 3D 메모 : 모든 함수 호출 후에 값이 일정하지 않은 인수가 3개만 있는 재귀 함수입니다.

동적 프로그래밍에서 메모화 기술은 어떻게 사용됩니까?

동적 프로그래밍은 하위 문제가 중복되고 최적의 하위 구조 속성이 있는 문제를 효율적으로 해결하는 데 도움이 됩니다. 동적 프로그래밍의 기본 개념은 문제를 더 작은 하위 문제로 나누고 나중에 사용할 수 있도록 결과를 저장하여 결과를 반복적으로 계산할 필요를 없애는 것입니다.

동적 프로그래밍 솔루션을 공식화하는 데는 두 가지 접근 방식이 있습니다.

1. 하향식 접근 방식: 이 접근 방식은 메모이제이션 기술 . 그것은 다음과 같이 구성됩니다 재귀 그리고 캐싱 . 계산에서 재귀는 함수를 반복적으로 호출하는 과정을 나타내고, 캐시는 중간 결과를 저장하는 과정을 나타냅니다.
2. 상향식 접근 방식: 이 접근 방식은 다음을 사용합니다. 표 기술 동적 프로그래밍 솔루션을 구현합니다. 이전과 동일한 문제를 해결하지만 재귀는 발생하지 않습니다. 이 접근 방식에서는 반복이 재귀를 대체합니다. 따라서 스택 오버플로 오류나 재귀 프로시저의 오버헤드가 없습니다.

동적 프로그래밍에서 메모화 기술이 사용되는 방법

Memoization은 Tabulation과 어떻게 다른가요?

표 작성과 메모

자세한 내용은 다음을 참조하세요. 도표화와 메모화

메모에 대한 코딩 연습 문제

Memoization에 관해 자주 묻는 질문(FAQ)

1: DP보다 메모가 더 좋나요?

메모이제이션은 동적 프로그래밍 문제를 해결하기 위한 하향식 접근 방식입니다. 각 문제를 해결하여 반환된 값에 대해 메모를 작성하므로 이를 메모이제이션이라고 합니다.

2: 메모이제이션은 캐싱과 동일한가요?

메모는 실제로 특정 유형의 캐싱입니다. 캐싱이라는 용어는 일반적으로 향후 사용을 위한 모든 저장 기술(예: HTTP 캐싱)을 의미할 수 있지만 메모이징은 보다 구체적으로 값을 반환하는 캐싱 기능을 의미합니다.

3: 왜 메모이제는 하향식인가요?

하향식 접근 방식은 큰 문제를 여러 하위 문제로 나눕니다. 하위 문제가 이미 해결된 경우 답변을 재사용하세요. 그렇지 않으면 하위 문제를 해결하고 결과를 일부 메모리에 저장하십시오.

4: 메모이제이션은 재귀를 사용하나요?

메모는 문제 해결을 위해 하향식 접근 방식을 따릅니다. 재귀와 캐싱으로 구성됩니다. 계산에서 재귀는 함수를 반복적으로 호출하는 과정을 나타내고, 캐시는 중간 결과를 저장하는 과정을 나타냅니다.

5: 도표화 또는 메모화를 사용해야 합니까?

모든 하위 문제를 해결해야 하는 문제의 경우 표 작성은 일반적으로 일정한 요소로 메모 작성보다 성능이 뛰어납니다. 이는 표에 재귀 오버헤드가 없어 스택 메모리에서 재귀 호출 스택을 해결하는 시간이 줄어들기 때문입니다.
원래 문제를 해결하기 위해 하위 문제를 해결해야 할 때마다 하위 문제는 느리게 해결되므로, 즉 필요한 계산만 수행되므로 메모하는 것이 좋습니다.

6: 메모이제이션은 어디에 사용되나요?

메모이제이션은 비용이 많이 드는 함수 호출의 결과를 캐시하고 동일한 입력이 다시 발생할 때 이를 반환함으로써 컴퓨터 프로그램 속도를 높이는 데 사용되는 최적화 기술입니다.

7: 왜 메모이제이션이라고 부르나요?

메모이제이션(memoization)이라는 용어는 라틴어 memorandum(기억하다)에서 유래했는데, 이는 일반적으로 미국 영어로 memo로 축약되며, 이는 함수의 결과를 기억할 무언가로 변환하는 것을 의미합니다.

8: 메모이제이션은 어떻게 시간 복잡성을 줄여주나요?

동일한 문제를 계속해서 해결하려면 시간이 걸리고 전체 프로그램의 런타임 복잡성이 증가합니다. 이 문제는 특정 입력에 대해 이미 계산된 문제 결과를 저장할 캐시나 메모리를 유지함으로써 해결할 수 있습니다. 따라서 동일한 문제를 다시 계산하고 싶지 않은 경우 메모리에 저장된 결과를 사용하여 시간 복잡도를 줄일 수 있습니다.

9: 메모이제이션과 캐싱의 차이점은 무엇인가요?

메모화는 실제로 입력을 기반으로 함수의 반환 값을 캐싱하는 특정 유형의 캐싱입니다. 캐싱은 보다 일반적인 용어입니다. 예를 들어 HTTP 캐싱은 캐싱이지만 메모이제이션은 아닙니다.

10: 왜 표 작성이 메모 작성보다 빠른가요?

표 작성은 반복적이며 하위 문제를 해결하는 데 재귀 호출에 따른 오버헤드가 필요하지 않기 때문에 일반적으로 메모 작성보다 빠릅니다.

메모이제이션(Memoization)은 함수 호출 결과를 캐시하고 동일한 입력이 다시 발생할 때 캐시된 결과를 반환함으로써 재귀적이거나 계산 비용이 많이 드는 함수의 실행 속도를 높이기 위해 컴퓨터 과학에서 사용되는 기술입니다.

메모이제이션의 기본 아이디어는 주어진 입력 세트에 대한 함수의 출력을 저장하고 동일한 입력으로 함수가 다시 호출되면 캐시된 결과를 반환하는 것입니다. 이 기술은 특히 자주 호출되거나 시간 복잡도가 높은 함수의 경우 계산 시간을 절약할 수 있습니다.

메모이제이션 구현에 대한 단계별 가이드는 다음과 같습니다.

메모이제이션을 사용하여 최적화하려는 기능을 식별하세요. 이 함수는 동일한 입력에 대해 반복적이고 비용이 많이 드는 계산을 수행해야 합니다.

함수의 캐시된 결과를 저장할 사전 개체를 만듭니다. 사전의 키는 함수에 대한 입력 매개변수여야 하며 값은 계산된 결과여야 합니다.

그리드 레이아웃

함수 시작 시 입력 매개변수가 캐시 사전에 이미 있는지 확인합니다. 그렇다면 캐시된 결과를 반환합니다.

입력 매개변수가 캐시 사전에 없으면 결과를 계산하고 입력 매개변수를 키로 사용하여 캐시 사전에 저장합니다.

계산된 결과를 반환합니다.

다음은 사전을 사용하여 메모이제이션을 구현하는 Python 코드 예제입니다.

파이썬3

>

>

>

위 코드에서는 피보나치 수열의 n번째 숫자를 계산하는 fibonacci라는 함수를 정의합니다. 우리는 함수 호출의 결과를 저장하기 위해 캐시라는 사전 객체를 사용합니다. 입력 매개변수 n이 캐시 사전에 이미 존재하는 경우 캐시된 결과를 반환합니다. 그렇지 않으면 fibonacci 함수에 대한 재귀 호출을 사용하여 결과를 계산하고 이를 반환하기 전에 캐시 사전에 저장합니다.

메모이제이션은 반복적이고 비용이 많이 드는 계산을 수행하는 많은 기능의 성능을 최적화하는 데 사용될 수 있습니다. 함수 호출 결과를 캐시함으로써 불필요한 계산을 방지하고 함수 실행 속도를 높일 수 있습니다.

결론

메모는 프로그래밍 개념이며 모든 프로그래밍 언어에 적용될 수 있습니다. 절대적인 목표는 프로그램을 최적화하는 것입니다. 일반적으로 이 문제는 프로그램이 과도한 계산을 수행할 때 나타납니다. 이 기술은 동일한 문제에 대해 다시 계산할 필요가 없도록 계산된 모든 이전 결과를 캐시합니다.

관련 기사:

• Python에서 데코레이터를 사용한 메모
• 자바스크립트 메모