전체 글

서론지난 게시글(LRU 알고리즘 파헤치기)로 LRU 알고리즘에 대해 OS와 HW 관점에서 알아봤습니다. 이번에는 Java를 이용해 이것을 구현하려면 어떻게 해야 할지 알아보고자 합니다. Java의 `LinkedHashMap`을 이용하면 편리하게 구현할 수 있습니다. LinkedHashMap?Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked li..

LRU페이지 교체 알고리즘 중에 하나로, Least Recently Used의 약자입니다. 즉, 가장 최근에 사용되지 않았던 것을 찾는 알고리즘입니다. 사실 페이지 교체를 위한 Optimal solution(가장 오랫동안 사용되지 않을 것을 선택하는 것)은 이론적인 방법이기 때문에 그것을 위한 근사 방법 중 하나입니다. 페이지 교체와 관련된 내용은 추후에 다뤄보고 여기서는 LRU에 대해서만 이야기하고자 합니다. LRU를 JAVA를 이용해 구현한 내용은 이 게시글을 참조하세요.   Implementing LRULRU 알고리즘을 구현하기 위해서는 다음과 같은 방식이 있습니다. Counter가장 단순하게 떠올릴 수 있는 방법 중 하나로, `clock register`를 이용하는 방식입니다...

https://leetcode.com/problems/combination-sum/ ✅ 체크 포인트 1. ArrayList를 깊은 복사 : ArrayList(comb); 2. Backtracking할 때 다음 시작 인덱스를 i 를 해야할까 i + 1 을 해야할까? 제출 코드 class Solution { public List combinationSum(int[] candidates, int target) { List answer = new ArrayList(); Arrays.sort(candidates); dfs(answer, new ArrayList(), candidates, target, 0); return answer; } private static void dfs(List answer, Array..

https://www.acmicpc.net/problem/7662 접근 방법 하나의 Priority Queue를 두 가지 기준으로 만들 수는 없으니, 결국 2개의 Priority Queue를 선언해야한다. Priority Queue의 종류 중 heapq를 사용하여 구현하였다. heapq는 기본적으로 min-heap으로 구성된다. 따라서, max-heap을 구성하기 위해서는 value에 음수를 취하여 넣고 pop할 때도 음수를 취하여 사용하면 된다. 이 문제의 핵심은 2개의 우선순위 큐를 동기화하는 것이다. 나는 해시 테이블 popHistory를 이용해 동기화를 처리하였다. 에서 key는 n를 나타내고, value는 해당 n이 몇 개 존재하는지를 나타낸다. pop할 때 value를 하나씩 감소한다면, 동기..

머리말 최근 구름LEVEL에서 알고리즘 먼데이 챌린지에 참가하고 있다. 해당 챌린지는 매주 월요일에 4문제를 2시간 안에 푸는 코딩 테스트를 진행하고, 그 다음 주에 해설 강의를 제공하는 챌린지이다. 코린이를 위한 프로그램 같지만,, 생각보다 어렵다는 점 😇 스탬프를 얻으면 소소한 간식도 얻을 수 있으니 추천ㅋㅋ 이번 주차의 1번 문제로 개미와 진딧물 문제로 그래프 문제가 나왔다. 접근법 처음에는 BFS 문제인 줄 알고, 개미집 위치를 queue에 모두 넣고 bfs 순회하며 거리를 계산했다. 제출하니 시간초과로 통과하지 못했다. 문제를 단순하게 생각해보자. 입력 값의 범위가 작다! ➡️ 완전 탐색 개미집과 수액의 거리를 완전탐색하며 Manhattan distance 거리를 계산하고, 그 거리가 m 보다 ..

https://www.acmicpc.net/problem/3190 머리말 아, 뱀 게임 로직 짜는 거구나,, 재밌겠다,, 처음에는 뱀의 위치 정보를 어떻게 구현해야 할지 고민을 하다가 큐가 문득 떠올랐다. 자료구조 때 배운 것을 바로 적용할 수 있는 능력을 키우자! 접근 방법 차근차근 해결하면 된다. 맵 정보를 저장하는 graph 리스트에 사과 위치를 2로 저장하였다. dx, dy 방향 전환을 동, 북, 서, 남 형식으로 저장하여 방향에 맞게 circle로 돌 수 있도록 하였다. cnt는 게임의 시간 정보를 나타내는 변수로, 이것을 logs 배열에 존재하는지 확인 후 방향 전환을 고려하였다. 뱀의 위치 정보를 저장하는 snake 리스트를 큐(deque)를 사용하여 이동할 때 머리는 push, 꼬리는 po..

https://www.acmicpc.net/problem/1865 머리말 문제를 보고, 아 negative cycle 찾는 문제이구나 싶었다. 그래프에서 최단 경로를 탐색하는 방법 중 다익스트라와 벨만 포드가 있는데, 다익스트라는 Greedy 알고리즘이기 때문에 반드시 간선들이 non-negative weights을 만족해야 한다. 한편, 벨만 포드는 Dynamic Programming 알고리즘으로 negative weights를 가져도 정상적으로 동작한다! 접근 방법 edge relaxation을 N-1번 수행한다. 그때 만들어진 distance 배열은 최단 경로이다. edge relaxation을 N번째 수행했을 때, 더 짧은 경로를 발견한다면 negative weight cycle이 존재한다는 결론..

키워드 일기 7월 # 토익: 다음 달에 있을 토익 공부를 위해 단어, ets 기출 1권을 풀었다. 꾸준히 하자고 다짐했지만 건너뛴 날도 있다 😇 7월 말까지만 해도 LC 귀가 뚫렸다고 생각했었다. (과거형) # 정보처리기사: 대학 동기들이 다 따길래 나도 따라 쳐봤다. 외우는 게 너무 귀찮았지만 필기 합격! 실기 시험은 언제더라 # 제주도 여행(8日-15日): 교회 친구들과 다녀왔는데 스쿠버 다이빙도 처음 해보고,, 이것저것 별거 다해서 행복했다ㅋㅋ 다음에도 모일 수 있겠지? 8월 # 토익: 시험 결과가 나왔는데,, 저번보다 RC는 75점 올랐는데 LC는 35점 떨어졌다 ㅋㅋ. 졸업을 위해서 땄지만 공부한 게 아쉬워서 한 번 더 시험 칠까 고민 중이다. LC 진짜 자신 있었는데 점수 폭망 # 스미싱: 여..