구르는 돌에는 이끼가 끼지 않는다

https://programmers.co.kr/learn/courses/30/lessons/17680

위 문제는 어떻게 보면 불친절한 문제입니다. 문제를 푸는 사람 입장에서 문제에서 말하는 [

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.

]라는 전제 조거은 말근데로 캐기 교체 알고리즘을 풀지 않으면 풀수 없는 문제 입니다. 

예전에도 카카오 코테를 참여했을때도 다음 문제를 못풀었던 기억이 있네요. 

어쨋든 캐시 교체 알고리즘은 다음과 같습니다. 

캐시가 사용하는 리소스의 양은 제한되어 있고, 캐시는 제한된 리소스 내에서 데이터를 빠르게 저장하고 접근할 수 있어야 한다.

이를 위해 LRU 알고리즘은 메모리 상에서 가장 최근에 사용된 적이 없는 캐시의 메모리부터 대체하며 새로운 데이터로 갱신시켜준다.

라고 설명하고 있습니다. 

즉, 데이터의 접근을 빠르게 하기 위해서 나온 캐시 알고리즘이라고 생각하면 됩니다. 

캐시의 hits의 경우에는 캐시안에 데이터가 존재하므로 time값이 +1이 증가하고 

캐시 miss의 경우에는 캐시안에 데이터가 존재하지 않으므로 time값이 +5가 증가하게 됩니다. 

저는 다음과 같이 풀었습니다.

package com.ji.test;

import static org.junit.Assert.assertEquals;

import org.junit.jupiter.api.Test;

import com.ji.study.Cache;

public class CacheTest {
	
	@Test
	void test() {
		
		Cache test = new Cache();
		
		assertEquals(50, test.solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"}));
		assertEquals(21, test.solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"}));
		assertEquals(60, test.solution(2, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}));
		assertEquals(52, test.solution(5, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}));
		assertEquals(25, test.solution(0, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA"}));
		assertEquals(16, test.solution(2, new String[]{"Jeju", "Pangyo", "NewYork", "newyork"}));
		
	}

}

package com.ji.study;

import java.util.LinkedList;
import java.util.Queue;

public class Cache {
	
	public static int solution(int cacheSize, String[] cities) {
		int excuteTime = 0;
		Queue cacheQueue = new LinkedList<String>();

		if (cacheSize == 0) {
			excuteTime = cities.length * 5;
		} else {

			for (String city : cities) {
				city = city.toLowerCase();

				if (cacheQueue.contains(city)) {
					cacheQueue.remove(city);
					excuteTime++;
				} else {
					if (cacheQueue.size() >= cacheSize)
						cacheQueue.poll();
					
					excuteTime = excuteTime + 5;
				}
				
				cacheQueue.offer(city);
				
			}

		}

		return excuteTime;
	}

}

동적계획법

책 [코딩인터뷰 완전분석]에서는 알고리즘 문제를 보았을때 재귀로 풀기 적당한 문제인지 파악하는 문장 키워드는 다음 3가지를 예시로 들었다.

• "n번째 ... 를 계산하는 알고리즘을 설계하라"
• "첫 n개를 나열하는 코드를 작성하라"
• "모든 ... 를 계산하는 메서드를 구현하라"

위와 같은 문장이 100프로 재귀 문제가 아닐 수도 있겠지만 괸장히 도움이 되는 팁이기도 하다.

상향식 접근법

bottom-up approach, 가장 직관적인 경우가 많음

간단한 경우들에 대한 풀이법을 발견하는 것부터 시작

하향식 접근법

top-down approach, 덜 명확해서 복잡해 질 수 있음

문제에 대해 생각하기에 가장 좋은 방법

반반 접근법

상향식, 하향식 접근법 외에 데이터를 절반으로 나누는 방법

예를 들어 이진 탐색이 반반 접근법을 이용한 탐색임

병렬 정렬 또한 반반 접근법을 이용한 정렬임

재귀적 해법의 단점

재귀적 알고리즘은 공간 효율성이 나빠질 수 있음

재귀가 한번 발생할 때 마다 스택에 새로운 층이 추가됨

이는 재귀의 깊이가 n일 때 O(n) 만큼의 메모리를 사용하게 된다는 것을 의미

모든 재귀적 알고리즘은 순환적으로 구현될 수 있지만, 순환적으로 구현된 코드는 때로 훨신 더 복잡할 수 있음

동적계획법&메모이제이션

동적 프로그램은 거의 대부분 재귀적 알고리즘과 반복적으로 호출되는 부분문제를 찾아내는 것이 관건

이를 찾은 뒤 나중을 위해 현재 결과를 캐시에 저장

어떤 사람은 하향식 동적 프로그래밍을 메모이제이션(memoization)이라 부르고 오직 상향식 접근법만 '동적 프로그래밍'으로 부리기도함

동적프로그램 적용 예

하향식 동적 프로그래밍

• 피보나치 수열int fibonacci(int i){ if(i == 0) return 0; if(i == 1) return 1; return fibonacci(i-1) + fibonacci(i-2); }

위 식을 트리 형태로 표시를 해보면 각 노드는 두개의 자식 노드를 갖음

각 노드는 두 경우로 분기됨

따라서 수행 시간은 대충 O(2^n)이 됨

재귀 트리를 보면 fib(3)은 두번 호출, fib(2)는 세번 호출 됨

많은 노드들이 중복되어 호출됨

이러한 노드의 중복을 캐시에 저장하고 나중에 저장된 값을 사용하면 효율적이 됨

이를 메모이제이션(memoization)이라고 함

다음 코드는 메모이제이션을 적용하여 fibonacci(i)의 결과를 캐시에 저장하는 부분임

int fibonacci(int n){ 
	return fibonacci(n, new int[n+1]); 
} 

int fibonacci(int i, int[] memo){ 
	if(i == 0 || i == 1) return i; 
    if(memo[i] == 0) { 
    	memo[i] = fibonnacci(i-1, memo) + fibonacci(i-2, memo); 
    } return memo[i]; 
}

위와 같이 코드 수정시 O(N) 시간으로 돌아가게됨

상향식 동적 프로그래밍

위 하향식 프로그래밍으로 푼 문제를 상향식으로 변경이 가능함

int fibonacci(int n){ 
	if(n == 0) return 0; 
    else if(n == 1) return 1; 
    int[] memo = new int[n]; 
    memo[0] = 0; memo[1] = 1; 
    for(int i=2; i<n; i++){ 
    	memo[i] = memo[i-1] + memo[i-2]; 
    } 
    return memo[n-1] + memo[n-2]; 
 }

위 코드에서 memo[i]는 memo[i+1]과 memo[i+2]를 계산할 때만 사용 될 분 그 뒤에는 전혀 사용 되지 않음

그래서 이름 memo테이블 말고 변수 몇 개를 사용해서 풀수도 있음

int fibonacci(int n) { 
	if(n == 0) return 0; 
    int a = 0; 
    int b = 1; 
    for(int i = 2; i < n; i++){ 
    	int c= a+b; a=b; b=c; 
    } 
    return a+b; 
}

(feat. 예전에 프로그래머스 문제중에 피보나치를 재귀로 풀었다가 똑같은 overflow가 발생하여 위와 같이 반복문 형태로 풀었던 기억이 있었다. 결국 이와 같이 푸는 방식도 일종으 동적계획법이라는 것을 알수 있었다. 상향식 동적 프로그래밍이 단순하게 생각하여 적용해 볼 수 있는 방식이라는 것을 이해할 수 있었다.)

http://www.yes24.com/Product/Goods/44305533

https://github.com/jshag90/TIL/blob/master/Java/210521-HashSet%EA%B3%BC%20HashMap%EB%B9%84%EA%B5%90.md