메모이제이션(피보나치, 시소 짝꿍)

메모이제이션이란?

간단하게 말하면

기록을 통해 답을 빠르게 찾는 방식이라고 할 수 있다

 

메모이제이션이란 동일한 계산을 반복해야할 때

이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여

프로그램 실행 속도를 빠르게 하는 기법이다

 

메모리에 저장하여 중복을 제거하면서 프로그램 실행 속도를 빠르게 할 수 있어서

동적 계획법(DP)에서 중요한 기법이다

 

 

피보나치 수열

가장 대표적인 메모이제이션의 예는 피보나치 수열이다

 

피보나치 수열이란

첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다

1항부터 6항까지 나열하면 

 

1, 1, 2, 3, 5, 8

 

피보나치 수열을 코드로 표현하면 아래와 같다

def fibo(n):
	if n < 2:
		return n
	else:
		return fibo(n-1) + fibo(n-2)

하지만 이처럼 작성할 경우 중복 연산이 발생한다

fib(1)의 경우 1번만 호출하면 되지만

 

fib(4) → 3번

fib(6) → 8번

 

호출되어 n이 큰 경우 엄청난 중복 연산이 발생한다

 

메모이제이션을 활용하면 이런 문제점을 해결할 수 있다

 

메모이제이션을 활용한 피보나치 수열은 아래와 같다

memo = [0, 1]

def fibo_memo(n):
    l = len(memo)
    if l < n:
        for i in range(l, n):
            memo.append(fibo_mem[i - 1] + fibo_memo[i - 2])
    return memo[n - 1]

1. 피보나치 값을 저장할 리스트를 생성

2. 저장된 피보나치 값을 꺼내 연산을 수행

3. 수행한 새로운 피보나치 값을 리스트에 추가

 

시간 복잡도

기존처럼 재귀만을 사용한 경우 : O(2^n)

메모이제이션을 활용한 경우 : O(n)

 

 

프로그래머스 LV 2 - 시소 짝꿍

 

문제 설명

어느 공원 놀이터에 시소가 하나 설치 되어 있습니다. 이 시소는 중심으로부터 2, 3, 4 거리의 지점에 좌석이 하나씩 있습니다.

이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다. 사람들의 몸무게 목록이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하시오.

 

조건

몸무게는 100 ~ 1000

몸무게를 담은 배열의 길이는 2 ~ 100000

 

예시

weights = [ 100, 180, 360, 100, 270] 이 주어지면

{100, 100} 은 서로 같은 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 360} 은 각각 4(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 270} 은 각각 3(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{270, 360} 은 각각 4(m), 3(m) 거리에 마주보고 앉으면 균형을 이루기 때문에

4를 리턴합니다

 

 

 

해결 방법

2중 for문으로 해결할 수 있으나 시간 초과가 발생한다

메모이제이션을 활용하면 효율적으로 문제를 해결할 수 있다

 

1. 메모이제이션에 활용할 배열을 생성

weights는 100 ~ 1000이므로 1000 size 배열을 생성한다

초기화 시 모든 항의 value는 0이다

 

int[] temp = new int[1001];

 

2. 존재하는 몸무게의 경우 새로운 배열에 저장

현재 몸무게를 존재하는 몸무게와 비교해야 하므로 이미 존재하는 몸무게들을 배열에 담는다

 

ArrayList<Integer> injec = new ArrayList<>(); // 존재하는 몸무게를 담는 배열 injec
for(int j=0;j<temp.length;j++){
   if(temp[j]!=0) // 존재하는 몸무게면
      injec.add(j);
}

 

3. 현재 몸무게와 injec에 존재하는 몸무게의 최대공약수를 구해 문제해결

만약 현재 몸무게가 180이고 injec 중 한개의 몸무게가 270이면 둘의 최대 공약수는 90이고

 

180/90 = 2

270/90 = 3

 

둘은 2 : 3이므로 시소 짝꿍이 될 수 있다

 

즉, 최대 공약수를 구하고 이를 통해 나눈 값이 

1 : 1 or 1 : 2 or 2 : 3 or 3 : 4 이면

시소 짝꿍이 된다

 

for(int j=0;j<injec.size();j++){
	int uclid = findGCD(weights[i], injec.get(j)); // 최대공약수
    	int cnt1 = weights[i]/uclid; // 현재 몸무게 / 최대공약수
    	int cnt2 = injec.get(j)/uclid; // injec 중 하나의 몸무게 / 최대공약수
    	if(isvalid(cnt1, cnt2)){
       		answer+=temp[injec.get(j)];
    	}
}

 

4. 현재 몸무게 메모

 

temp[weights[i]]++;

 

weights는 100 ~ 1000이므로 최대 1000번 돌면서 temp를 통해 현재 존재하는 몸무게를 확인할 수 있다

즉, 메모이제이션을 통해 효율을 높힐 수 있다

 

 

전체 코드

import java.util.*;

class Solution { 
    public static int findGCD(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return findGCD(b, a % b);
        }
    }
    
    public boolean isvalid(int cnt1, int cnt2){
        int tmp;
        if(cnt1>cnt2){
            tmp = cnt1;
            cnt1 = cnt2;
            cnt2 = tmp;
        }
        if((cnt1==cnt2) || (cnt1==1&&cnt2==2) || (cnt1==2&&cnt2==3) || (cnt1==3&&cnt2==4))
            return true;
        return false;
    }
    
    public long solution(int[] weights) {
        long answer = 0;
        int[] temp = new int[1001];
        for(int i=0;i<weights.length;i++){
            ArrayList<Integer> injec = new ArrayList<>();
            for(int j=0;j<temp.length;j++){
                if(temp[j]!=0)
                    injec.add(j);
            }
            for(int j=0;j<injec.size();j++){
                int uclid = findGCD(weights[i], injec.get(j));
                int cnt1 = weights[i]/uclid;
                int cnt2 = injec.get(j)/uclid;
                if(isvalid(cnt1, cnt2)){
                    answer+=temp[injec.get(j)];
                }
            }
            temp[weights[i]]++;
        }
        for(int i=0;i<temp.length;i++){
            if(temp[i]!=0){
                System.out.println("i : " + i + " temp[i] " + temp[i]);
            }
        }
        
        return answer;
    }
}

핵심

DP처럼 작은 연산으로 쪼개는 기법에서 사용하기 좋다

 

메모리를 소비한다는 단점이 있다