SRP 단일 책임 원칙한 클래스는 하나의 책임만 가져야 한다.중요한 판단 기준은 변경. 변경이 있을 때 파급효과가 적어야 한다.객체의 생성과 사용을 분리클래스 하나에 너무 많은 것을 집어 넣지 말자. 문제가 발생했을 때 유지보수가 편리하게.. (한 변경에서 다른 책임의 변경으로의 연쇄작용은 최악) OCP 개방 폐쇄 원칙 ✦소프트웨어 요소는 확장에는 열려있어야 하며, 변경에는 닫혀있어야 한다.확장에 열려있다? 새로운 변경사항이 발생했을 때 유연하게 코드를 추가, 수정변경에 닫혀있다? 객체를 직접 수정하지 않고도 변경사항을 적용다형성을 활용자동차, 공연 배우 예시를 생각역할과 구현을 분리문제점구현 객체를 변경하려면 클라이언트 코드를 변경해야 한다.따라서, 객체 생성과 연관 관계를 맺어주는 별도의 조립, 설정..

https://www.acmicpc.net/problem/11727 🥕 아이디어 DP 문제에 약한 저는 N이 1일 때 부터 6일 때 까지 손수 그려보며 규칙을 찾고자 노력했습니다. N이 5일 때 `2 + 3` 타일로 나누어 생각했습니다.그리고 `중간에 겹치는 부분`에 들어갈 2*1 타일과 2*2타일을 생각했습니다.그렇게 나온 점화식은 `D[i] = 3 * D[i - 2] + 2 * D[i - 3]` 입니다. 다른 분들의 풀이를 보니 1 + 4 타일로 나누어 생각했던데, 점화식은 다르게 나오더라도 결국 같은 접근법입니다.  제출 코드public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in)..

서론지난 게시글(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 list d..

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 a..

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..