본문 바로가기

알고리즘25

LRU Cache Algorithm(Least Recently Used) LRU 알고리즘이란? 해석 그대로 가장 오래된 데이터를 없애고 새로운 데이터를 넣는 알고리즘이다. 캐시에서 사용되는 알고리즘 캐시는 많은 데이터를 담지 못하므로 이러한 페이지 교체 알고리즘이 필요하다. 이중연결리스트를 사용하여 node를 관리한다. 설명 ListNode로 사용할 클래스를 만든다. 접근 성능 개선을 위해 Map을 사용하여 key의 존재 유무를 빠르게 찾을 수 있다. head는 새로 들어올 node를 nodeList에 연결해 주기 위한 역할(next만 사용) tail은 삭제될 node를 가리키기 위한 역할 (prev만 사용) put 메서드 새로운 노드 생성 키 존재 여부확인 존재하는 경우, Listnode에서 해당 키를 가진 노드를 삭제 후 inserToHead 호출 존재하지 않은 경우, 또.. 2019. 11. 3.
단어 변환(프로그래머스, Java) 문제링크: https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 | 프로그래머스 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> programmers.co.kr 알고리즘 설명: 한글자씩 바꿔가면서 맞는 단어가 있다면 그 값.. 2019. 10. 24.
디스크 컨트롤러(프로그래머스, Java) 문제링크: https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 | 프로그래머스 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를들어 - 0ms 시점에 3ms가 소요되는 A작업 요청 - 1ms 시점에 9ms가 소요되는 B작업 요청 - 2ms 시점에 6ms가 소요되는 C작업 요청 와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다. 한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 programmers.co.kr 알고리즘 설명: 작업이 진행된 시간동안 들어온 다른 작업.. 2019. 10. 20.
예산(프로그래머스, Java) 문제링크: https://programmers.co.kr/learn/courses/30/lessons/43237 코딩테스트 연습 - 예산 | 프로그래머스 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다. 1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다. 2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 programmers.co.kr 알고리즘 설명 빠르게 예산에 맞는 상한 값을 찾아내는 것이 핵심이다.. 2019. 10. 19.
프림 알고리즘(Prim's algorithm) 프림 알고리즘이란? 가중치가 있는 연결된 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘 그래프에 간선이 많이 존재하는 밀집 그래프인 경우 적합하다. 시간 복잡도 - O(ElogV), 그래프가 충분히 뺵빽한 경우 피보나치 합을 이용하여 더 빠르게 값을 구할 수 있다. 설명 그래프에서 하나의 노드를 선택한 후 트리를 만든다. 그래프의 모든 간선이 들어있는 집합을 만든다. 모든 노드들을 방문하기 전까지 반복 ->트리 자체와 연결된 간선들 중에서 가중치가 가장 작은 간선을 선택 후 연결되어 있는 노드로 넘어감. 반복이 끝났을 때 최소비용 신창트리가 완성! 관련 문제 섬 연결하기 - https://eoghks0521.tistory... 2019. 10. 17.
섬 연결하기(프로그래머스, Java) 문제링크: https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 | 프로그래머스 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 알고리즘 설명: 가장 cost가 싼 간선으로 모든 노드를 연결하는 알고리즘이다. 양 방향으로 간선의 cost값을 알기 위해서 배열을 사용하여 두 방향 (A -> B, B -> A)의 cost를 넣어놓았다. 노드 0부터 탐색을 시작한다. 0부터 시작하므로 visited[0] = true 메서드 재귀호출하여 탐색한다. 재귀호출은 노드(섬)의 개수만큼 호출을 하고 변수 count를 만들어 재귀 호출한 횟수를 체크한다. 이중 for문으로 탐.. 2019. 10. 16.

티스토리툴바