퉁탕퉁탕 만들어보자

LRU알고리즘 - Least Recently Used 가장 오랫동안 참조되지 않은 아이템를 없애버리는 알고리즘이다. 보통은 Cache에서 많이 사용된다. cache는 사이즈나, 저장할 수 있는 개수가 정해져 있기 때문에 꽉차있는 상태에서 새로운 item을 put하려면 누군가를 삭제해야한다. 이때 누구를 삭제할지를 고르는 알고리즘이라고 볼 수 있다. LRU외에도 뭐 가장 들어온지 오래된 친구를 삭제한단다던지 (FIFO), 가장 적은 횟수 참조된 친구를 삭제한다던지 (LFU) 여러방식이 있지만 널리 쓰이는 것은 LRU이다. LRU의 경우에는 그러면 가장 오랫동안 참조되지 않았는지를 트래킹하기위해서 참조를 할 때마다 그 참조를 map의 맨 앞으로 넣어준다. 그래서 LinkedHashMap이 쓰이게 되는데, L..

바이너리 서치는 좀더 빨리 찾기 위함으로 기본 개념은 가운데서 일단 찾고 작으면 왼쪽에서 , 크면 오른쪽에서 찾는 문제이다. 개념은 간단한데. 계속 time limit exceed가 났다. mid = left + (right-left)/2; 로 하면 exceed가 안되고 mid = (left + right) /2 하면 exceed가 난다. 추측으론 left + right가 큰수가 되어서 그런것 같은데, 자료형 오버플로우가 날 수 있으니 앞으로 저 방식으로 mid값을 구하는게 좋을것같다. 자세한 설명은 https://www.quora.com/Why-do-people-use-mid-low+-high-low-2-instead-of-low+high-2

https://www.hackerrank.com/challenges/coin-change/problem?isFullScreen=true The Coin Change Problem | HackerRank Given a list of 'm' coin values, how many ways can you make change for 'n' units? www.hackerrank.com 문제) 갖고있는 동전 배열이 있다. 배열의 각각의 수는 동전의 값을 의미한다 (1원, 3원..) 동전의 갯수는 무한이라고 친다. n원을 거슬러줘야 할 때, n원을 만드는 동전의 조합의 수를 구하라 예제) Sample Input 타겟금액, 동전갯수 동전 액면가들 4 3 1 2 3 Sample Output 4 Explanation ..

https://leetcode.com/problems/coin-change/ Coin Change - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 저번 코테에서 DP를 DP인줄 알면서 못풀었기 때문에 DP 20문제 도전하겠다. 20문제 풀고 DP 못풀면 코테 포기한다 문제) 갖고있는 동전 배열이 있다. 배열의 각각의 수는 동전의 값을 의미한다 (1원, 3원..) 동전의 갯수는 무한이라고 친다. n원을 거슬러줘야 할 때, n원을 만들기 위한 가장 적은 수의 동전..

동적프로그래밍은 간단하게 생각하면, 이전에 도출된 해를 가지고 그 다음 해를 구하는 식으로 푸는것이다. 그러면 이게 문제를 점화식으로 나타낼 수 있는데, 점화식만 도출해 내면 코드는 아주 짧다. 가장 유명하고 쉬운 문제는 피보나치 수열이다. 피보나치 수열은, 처음 두 값이 주어진다. 수열의 n번째 값을 F(n) 이라고 할 때, F(0) = 0, F(1) = 1 이 주어진다. 그 다음으로 오는 수는 바로 이전 두 값의 합이다. F(0) = 0, F(1) = 1 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(2) + F(1) = 1 + 1 = 2 F(4) = F(3) + F(2) = 2 + 1 = 3 ... [0,1, 1, 2, 3, 5, .... ] 이렇게 나가게 되며, 점화식으로..