kwang2134 님의 블로그

[Grind75-LeetCode] LRU Cache - Medium접근Doubly Linked List 풀이 LRU (Least Recently Used) 가장 최근에 사용되지 않은 캐시를 교체하는 알고리즘으로 오늘 문제에서 구현해야 할 내용이다. 구현해야 할 부분은 LRU 클래스의 생성자, get, put 메서드로 생성자의 경우 LRU 캐시의 크기를 넘겨받게 된다. get은 말 그대로 캐시에 들어있는 값을 반환하는 메서드로 캐시에 존재하지 않을 경우 -1을 반환한다. put은 캐시에 값을 넣는 메서드로 값은 key, value 형태로 주어진다. 이러한 교체 알고리즘을 구현하는 문제는 이 전에도 존재했었는데 아무래도 문제의 거의 막바지에 다다른 만큼 평범한 방식으론 풀 순 없지 않을까 싶다.  우선 내용..

1. 설계서설계가 마무리되고 구현을 시작하는 단계입니다. 설계가 진행되며 초기와 변경되었던 점과 프로젝트에 사용된 의존성 등 버전 명시를 목적으로 작성되었습니다.1.2. UseCase처음 진행되었던 유스케이스 설계입니다. 설계 초기 단계와 차이 없이 그대로 진행되었습니다.1.3. Package패키지 설계입니다. 설계 초기와 전체적인 패키지 구조는 변경되지 않았으나 클래스 설계가 진행되며 초기 구조와 변경 점이 존재합니다.com.kwang.board├── user│ ├── application│ │ ├── service│ │ │ ├── UserService.java│ │ ├── dto│ │ │ ├── UserDTO.java│ ├── domain│ │ ├──..

[Grind75-LeetCode] Task Scheduler - Medium 접근그리디풀이작업 스케줄러라는 문제로 주어지는 작업을 CPU가 처리하는데 몇 번의 인터벌이 필요한지 구하는 문제이다. 알파벳 대문자로 주어지는 작업이 들어있는 배열과 정수 n이 주어지는데 한 작업은 n의 시간이 지난 뒤에 다시 처리할 수 있는 규칙이 있다. n = 2라면 작업 A가 처리되고 2라는 시간이 흐른 뒤에 다시 처리가 가능해진다는 뜻이다. 1번째에 A가 처리되었다면 2 턴이 지나고 4번째부터 다시 처리가 가능하다.  문제의 설명에서와 예제에서 작업이 배열로 주어지지만 배열 순서에 상관없이 작업 처리가 가능하다고 나와있었다. 그렇다면 처리해야 할 횟수가 많은 작업을 적재적소에 배치하는 것이 중요한데 n이라는 쿨다운 시간이..

[Grind75-LeetCode] Minimum Height Trees - Medium접근리프 노드 제거풀이트리는 두 정점이 하나의 경로로 연결된 무방향 그래프로 사이클이 존재하지 않는 무방향 그래프는 트리라고 부를 수 있다. 트리는 루트에 따라 트리를 구성하는 높이가 달라지는데 이번 문제는 무방향 그래프에서 트리의 높이를 가장 낮게 구성할 수 있는 루트 노드들을 찾아 반환하는 문제이다. 무방향 그래프를 트리로 봤을 때 높이가 3이 최소가 된다면 3의 높이로 트리를 구성할 수 있는 루트 노드를 모두 찾는 것이다. 문제가 점점 어려워지고 있는 것 같다. 구할 수 있는 방법은 여러 가지가 있을 것이다. 각 정점 간의 거리를 구해 가장 멀리 있는 두 정점을 구하고 두 정점 가운데 정점을 루트로 사용하면 최소 ..

[Grind75-LeetCode] Find All Anagrams in a String - Medium접근슬라이딩 윈도우풀이문자열 s 내에서 애너그램 부분 문자열 p가 존재하는지 찾는 문제이다. p 문자열을 애너그램으로 만들 수 있는 s의 시작 인덱스를 모두 찾아 리스트에 담아 반환하면 된다. 단순하게 맵에 p의 문자 등장수를 담아둔 뒤 각 자리마다 반복을 통해 계산해 보니 당연하게도 시간초과가 나왔다. 그러니 이 문제는 s의 길이가 m, p의 길이가 n이라면 적어도 O(m * n)의 복잡도 보다 빠른 방법으로 해결되어야 한다.  슬라이딩 윈도우 기법을 사용하면 s를 한 번의 순회로 해결이 가능하기 때문에 O(n)의 시간 복잡도로 해결이 가능하다. public List findAnagrams(Str..

[Grind75-LeetCode] Word Search - Medium접근dfs풀이2차원 배열에 문자들이 저장되어 있고 문자들을 이어 주어진 단어를 만들 수 있는지 검사하는 문제이다. 상하좌우로 단어를 연결할 수 있기 때문에 dfs를 사용해 풀어주었다. private static final int[] dx = {-1, 1, 0, 0}; private static final int[] dy = {0, 0, -1, 1}; public boolean exist(char[][] board, String word) { for (int i = 0; i 상하좌우 이동을 위한 배열을 만들고 2차원 배열을 순회하며 주어진 단어의 첫 번째 문자와 배열에 들어있는 문자가 같을 때 dfs를 시작한..

[Grind75-LeetCode] Letter Combinations of a Phone Number - Medium접근dfs풀이휴대폰 자판에 있는 알파벳을 가지고 나올 수 있는 모든 조합을 구하는 문제이다. 입력으로 여러 개의 숫자가 문자열로 주어지고 해당 숫자칸에 있는 알파벳들의 조합을 구해야 한다. 문자열이 "23"으로 주어졌을 때 2에 해당하는 a, b, c와 3에 해당하는 d, e, f를 조합하는데 각각 번호의 알파벳을 한 개씩 사용해서 조합을 만들어야 한다. 즉 2번과 3번의 알파벳이 한 개씩 사용된 ad, ae, af는 가능하지만 각 번호의 알파벳을 두 번 사용한 ab, de 같은 경우는 불가능하다.  private static final String[] DIGITS_MAP = { ..

[Grind75-LeetCode] Container With Most Water - Medium 접근투 포인터풀이수직선의 길이가 들어있는 배열이 주어지고 수직선 두 개를 선택해 컨테이너를 만들 때 가능한 컨테이너의 넓이 중 가장 큰 넓이를 반환하는 것이다. 그러기 위해선 기둥이 될 두 수직선을 골라야 하는데 투 포인터를 사용해 최댓값을 찾는다. public int maxArea(int[] height) { int start = 0; int end = height.length - 1; int maxArea = 0; while (start 시작과 끝에서 각 포인터가 시작되고 각 포인터가 만날 때까지 모든 넓이를 찾게 된다. 현재 포인터를 기준으로 넓이를..

[Grind75-LeetCode] Construct Binary Tree from Preorder and Inorder Traversal - Medium접근dfs풀이전위 순회, 중위 순회 순서가 담긴 배열을 통해 이진트리를 만들어내는 문제이다. 전위 순회의 경우 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 순회가 되고 중위 순회의 경우 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순서로 순회가 된다. 즉 전위 순회 배열을 루트로 사용하고 중위 순회 배열을 통해 양쪽 서브트리를 찾는 방식으로 진행해야 한다. public TreeNode buildTree(int[] preorder, int[] inorder) { return treeBuilder(preorder, inorder,..

[Grind75-LeetCode] Unique Paths - Medium접근dp조합풀이m x n 좌표 평면 위에서 왼쪽 상단 (0,0)에서 출발해 오른쪽 하단 (m-1, n-1)까지 갈 수 있는 고유의 경로를 구하는 문제이다. 고유 경로는 겹치지 않는 모든 이동 경로를 말하며 이동은 오른쪽, 아래 방향으로만 가능하다. dfs를 통해서도 찾을 순 있지만 중복 계산이 많이 발생하고 모든 경로 탐색으로 최적화를 위해 메모이제이션 배열을 사용하게 될 텐데 그럼 그냥 처음부터 dp를 통해 푸는 것이 효율적이다.  public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for(int i = 0; i dp 배열을 생성하고 ..