알고리즘5 LRU 알고리즘이란 무엇인가? ▏목적 ◦ LRU 알고리즘 이해하기 ▏시작하는 말 정처기 자격증 준비했을 때 이론을 공부했었다. 그런데 마침 오늘 프로그래머스에서 문제를 보는데 LRU를 사용해야 하는 문제였다. 그래서 오늘은 그 LRU알고리즘을 설명해보려고 한다. ▏LRU 란 무엇인가? LRU (Least Recently Used) : 가장 오랫동안 참조하지 않은 페이지를 교체하는 기법 페이지 교체 알고리즘들의 종류중 하나로 가장 최근에 사용되지 않은 페이지를 제거하는 알고리즘이다. 대표적인 방법으로 전에 포스팅했던 Queue 형식을 생각하면 된다. ▏원리 크기가 4인 배열이 있다고 가정했을 때, 처음 4번은 들어온 순서대로 넣어주면 된다. 하지만 오른쪽 처럼 숫자 5를 넣으려고 한다면 가장 먼저 넣었던 1 (오래된 데이터)를 제거하고.. 2021. 8. 20. 하노이의 탑이란 무엇인가? ▏목적 ◦ 하노이의 탑 알고리즘 이해하기 ◦ 하노이의 탑 알고리즘 JAVA로 구현하기 ▏시작하는 말 오늘은 하노이의 탑 을 공부해봤다. 이름이 새로워서 내가 모르는 것인 줄 알았으나 어릴적 다들 한 번씩은 해봤던 놀이였다. 가지고 놀았던 게임을 제대로 분석하고 공부해서 코드로 구현해보니 더 재미있고 신기했다. 그럼 이제 그 하노이의 탑을 설명해보도록 하겠다. ▏하노이의 탑 하노이의 탑 규칙은 큰 원반이 아래, 작은 원반이 위로가게 해서 원반을 3개의 기둥사이에서 옮기는 것 이다. 원반은 1번에 1개씩만 옮길 수 있고, 모든 원반은 크기가 다르며 큰 원반이 작은 원반 위로 가서는 안되는 규칙이 있다. 또 최소한의 이동으로 목표 기둥으로 옮겨야 한다. ▏원리 왼쪽 기둥부터 편의상 1, 2, 3번 기둥이라고 .. 2021. 7. 2. 유클리드 호제법 이란 무엇인가? ▏목적 ◦ 유클리드 호제법 알고리즘 이해하기 ◦ 유클리드 호제법 JAVA로 구현하기 ▏시작하는 말 요즘 팀 프로젝트 작업을 하고 있어 알고리즘 공부하는 것이 뜸했다. 그래서 오늘은 일찍부터 일어나 공부를 시작해봤다. 오늘 공부한 것은 유클리드 호제법이란 알고리즘으로 최대공약수를 재귀적으로 구하는 방법이다. 예전에 내가 최대공약수 문제를 풀 때 정사각형으로 만드는 방법을 얼핏 봤었는데 그것을 오늘 제대로 공부했고 이제 설명해보려고 한다. 오늘도 역시 직접 그림판으로 그린 것이라 비율이 정확히 맞지는 않는것을 유념하고 봐줬으면 좋겠다. ▏유클리드 호제법 각 변의 길이가 22 와 8인 직사각형으로 예를 들어 설명해보겠다. 위 도형에서 짧은 변(8)을 한 변으로 하는 정사각형으로 나누면 8 x 8 정사각형 2개.. 2021. 7. 1. 검색(탐색) 알고리즘 이란 무엇인가? ▏목적 ◦ 검색 알고리즘 이해하기 ▏시작하는 말 알고리즘 공부를 하기 위하여 프로그래머스 Lv 2문제들을 꾸준히 하루에 한 문제씩 풀어나가는 중이다. 나는 알고리즘을 따로 배워본 적 없이 JAVA의 기초 지식만 있었기 때문에 1 / 3 정도 풀고 나니 남은 문제들은 구현은 해도 효율성이 좋지 않거나 손쉽게 풀 수 없는 문제들만 남았다. 때문에 나는 제대로 된 알고리즘 개념부터 공부해야겠다는 생각을 했다. 그래서 오늘부터 알고리즘 하나씩 공부한 후 이 블로그에 정리해보려고 한다. 오늘 공부한 것은 검색알고리즘으로 선형 검색과 이진 검색이다. ▏정의 선형 검색 : 무작위로 늘어놓은 데이터 집합 일 때 적절한 검색 알고리즘 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합 일 때 적절한 검색 알고리즘 해시법.. 2021. 6. 18. JAVA 로 다익스트라 구현하기 | 목적 ◦ 다익스트라 알고리즘 Java로 구현하기 | 시작하는 말 다익스트라의 개념, 순서가 이해가 안된다면 다익스트라란 무엇인가 이 포스트를 먼저 보고 오면 좋다. | 초기 설정 다익스트라를 만들기에 앞서 변수 두가지를 설정해줘야 한다. distance변수는 각 노드에 갈 수 있는 최단거리를 저장한다. visit변수는 해당 노드를 방문 했는지를 체크할 변수다. int distance[] = new int[N]; //최단거리들을 저장할 배열을 만든다. boolean visit[] = new boolean[N]; //해당노드 방문여부를 체크할 배열을 만든다. | 예제 (JAVA) public class Dijkstra { private static int n; private static int maps[.. 2021. 5. 13. 이전 1 다음 반응형
