가치투자자

LRU (Least Recently Used) 알고리즘 코딩테스트 문제에 나온 LRU 알고리즘에 대해 정리해보고자 한다. LRU 알고리즘은 페이지 교체 알고리즘이기에 페이지 교체 알고리즘에 대해 간단하게 살펴보고 가자. 1. 페이지 교체 알고리즘 페이지 교체 알고리즘은 새로운 페이지를 실행하려고 하지만 메모리가 없을 때 기존의 어떤 페이지를 교체할지 결정하는 알고리즘이다. 이러한 알고리즘에는 다음과 같은 종류들이 있다. 1) FIFO (First-in, First-Out) 메모리에 적재된 순서대로 내보내는 알고리즘으로, 큐(queue)를 이용해 저장할 수 있다 장점 : 구현이 간단하고 이해하기 쉽다 단점 : 중요한 페이지가 오래 있었다는 이유만으로 교체되어야 하며, Belady의 모순이라는 현상으로 인해..

Programmers : [1차] 캐시 🔗 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/17680 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💬 문제 처음 이 문제를 읽었을 때, 문제 내용을 읽었을 때 주어진 변수들이 어떻게 작동해서 주어진 결과값이 나왔는지 이해하기 쉽지 않았다. 이 문제의 핵심은 캐시 교체 알고리즘 LRU이다. LRU가 무엇인지 먼저 알아보자. LRU 알고리즘 (Least Recently Used) LRU 알고리즘은 페이지 교체 알고리즘 중 하나로, 사용한지(참조..

백준 1080번 : 행렬 🔗 문제 링크 https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 💬 문제 그리디(greedy) 알고리즘 에 대해 충분히 이해한 후 문제를 풀 것을 추천드린다. 전형적인 그리디 문제인 동전 문제와 달리 결코 쉽지 않았다. 0과 1로만 이루어진 행렬 A와 B가 주어진다. - 행렬 A와 B의 크기는 같다 행렬 A의 원소 일부분을 뒤집어 행렬 B로 만들고, 뒤집는데 필요한 횟수의 최솟값을 구하면 된다. - 행렬 A에서 3 x 3 크기로만 원소..

백준 11047번 : 동전 0 🔗 문제 링크 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 💬 문제 그리디(greedy) 알고리즘 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다. 동전의 종류는 N개이며, 각 동전의 개수는 많이 존재한다. N종류의 동전을 사용하여 K 금액을 만들려고 한다. - 이때 필요한 동전 개수의 최솟값을 구해주면 된다 💡 입력값 받아오기 JavaScri..

해시 (Hash) 해시는 무엇일까? 또 해시 테이블은 해시랑 같은것일까? 이에 대해 차근차근 살펴보고자 한다. 1. 배열 vs 해시 테이블 일반적으로, 데이터를 저장하고 활용하는 방법으로 배열(Array)을 떠올릴 수 있다. 아래의 예시를 보면, menu에 push를 통해 새로운 값을 추가할 수도 있고, for문 등을 통해 특정 값을 찾아볼 수도 있다. 즉, 배열은 특정 값을 찾기 위해 인덱스 0번부터 끝까지 탐색하는 선형 검색(Linear Search) 방식을 사용한다. 따라서 n개의 요소를 가진 배열을 순차적으로 검색하기에 시간 복잡도는 O(n) 이며, 살펴봐야 할 요소가 늘어날수록 시간은 무한히 늘어난다. const menu = [ { "icecream": 1000 }, { "coke": 1500 ..

Programmers : 의상 🔗 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💬 문제 해시(hash) 에 대한 이해가 있다면, 충분히 풀 수 있는 문제였다. 해시에 대해 익숙하지 않다면, 아래 글을 참고해보길 바란다. https://valueengine.tistory.com/55 [자료구조] 해시 (Hash) 해시 (Hash) 해시는 무엇일까? 또 해시 테이블은 해시랑 같은것일까? 이에 대해 차근차근 살펴보고자 한다. 1. 배열..