kwang2134 님의 블로그

[Grind75-LeetCode] Coin Change - Medium접근dp풀이주어진 동전을 가지고 원하는 금액을 만들 수 있는지 만들 수 있다면 최소 몇 개의 동전을 사용해야 하는지 구하는 문제이다. 동전의 개수는 무한대로 주어지고 동전을 100원짜리, 500원짜리처럼 특정 값의 동전이 주어지기 때문에 주어진 값의 동전만 사용해서 만들어야 한다. 원하는 금액을 맞출 수 있으면 만드는데 필요한 최소 동전 개수를 구하고 만들 수 없다면 -1을 반환한다. 문제에 주어지는 내용이 동전일 뿐이지 비슷한 내용의 문제가 매우 많은 전형적인 dp 문제이다. dp 배열을 통해 Bottom-Up 방식으로 값을 채워나가면 해결이 되는 문제이다. public int coinChange(int[] coins, int ..

[Grind75-LeetCode] Implement Trie (Prefix Tree) - Medium접근Trie풀이이 문제는 Trie 자료 구조를 통한 삽입, 검색, 접두사 검색을 구현하는 문제이다. 이 문제를 풀기 위해서는 우선 Trie 자료 구조에 대해 알아야 한다.  Trie란 문자열을 검색하고 저장하기 위해 최적화된 트리 기반 구조이다. 단어 집합을 다루는 데 효율적이며, 주로 자동 완성, 접두사 검색, 사전 구현 등에 사용된다. 기본적인 트리 구조를 따르기 때문에 자식 노드와 마지막인지를 나타내는 플래그를 가진다. 기본적으로 한 문자 단위로 쪼개져 저장이 된다. 아래는 Trie에 저장된 모습이다.현재 Trie에 apple, app, aproach, ban, banana, call, cash라는 ..

[Grind75-LeetCode] Clone Graph - Medium접근재귀풀이노드 객체로 주어진 무방향 그래프를 형태 그대로 복제하는 문제이다. 그래프를 형태 그대로 복제하면 되는 간단한 문제이지만 참조 값을 복사하는 얕은 복사가 아닌 깊은 복사를 진행해야 통과가 가능한 문제이다. 말 그대로 참조 값이 주어지는 노드와 동일할 경우 통과하지 못한다.  public Node cloneGraph(Node node) { if (node == null) return null; Map map = new HashMap(); return clone(node, map); }이번 문제의 경우 Map을 사용해줬는데 원본 객체를 Key로 사용하고 복사한 객체를 Value로 ..

[Grind75-LeetCode] Binary Tree Level Order Traversal - Medium 접근재귀풀이이진트리를 레벨별로 List에 담아 출력하는 문제이다. 이진트리는 TreeNode 형태로 현재 노드의 값, 왼쪽 서브트리, 오른쪽 서브트리를 가지는 객체 형태로 주어진다.예제 1번으로 주어지는 트리의 모습인데 각 레벨별 노드 값을 List> 형태로 반환해야 하는데 현재 트리에선 루트 노드인 레벨 0 [3], 레벨 1 [9, 20], 레벨 2 [15,7]로 [ [3], [9,20], [15,7] ] 형태의 결과를 반환해야 한다. 이 문제 또한 재귀를 이용해 간단하게 풀 수 있는 문제로 리스트의 인덱스와 트리의 레벨을 매칭시켜 각각 해당하는 위치에 넣어주면 된다. public Lis..

[Grind75-LeetCode] 3 Sum - Medium접근투 포인터풀이주어지는 정수 배열에서 각자 다른 3개의 숫자가 더해서 0이 되는 경우를 모두 구하는 문제이다. 숫자가 3개인 만큼 단순한 반복으로 접근하게 되면 성능이 매우 떨어져 통과를 하지 못할 것이다. 그래서 이번 문제는 하나의 숫자를 고정하고 두 개의 포인터를 사용해 체크해 보는 투 포인터를 사용하였다. 정렬된 배열을 순회하며 숫자 하나를 고정해 두고 포인터 하나는 고정된 숫자 바로 다음 그리고 나머지 포인터는 배열의 끝에서 시작하여 세 숫자의 합이 0보다 작으면 왼쪽 포인터를 오른쪽으로 이동하고 0보다 크다면 오른쪽 포인터를 왼쪽으로 이동한다. 이 과정을 반복하여 세 숫자가 0이 되는 경우를 다 찾게 된다.  public List..

[Grind75-LeetCode] Longest Substring Without Repeating Characters - Medium접근Set슬라이딩 윈도우슬라이딩 윈도우 성능 향상풀이문자열 내 부분 문자열 중 가장 긴 부분 문자열의 길이를 구하는 문제이다. 겹치는 문자 없이 부분 문자열을 이루어야 하는 조건이 있고 단순한 Set을 이용한 방법과 Map을 이용한 슬라이딩 윈도우 알고리즘 그리고 Map 대신 배열을 사용하여 성능을 향상 시킨 슬라이딩 윈도우 순서로 진행할 예정이다. 우선 Set을 사용한 방법이다. 가장 직관적이고 쉬운 방법으로 각 인덱스에서 2중으로 반복문을 돌며 Set에 추가해 이미 존재하는 원소라면 반복을 중단하고 길이를 반환하여 최댓값을 구하는 방식이다. 가장 간단하고 쉬운 방법이지만..

[Grind75-LeetCode] 01 Matrix - Medium접근bfsdp풀이0과 1로 이루어진 2차원 배열을 통해 각 인덱스에서 제일 가까운 0까지의 거리가 얼마나 되는지 구하는 문제이다. 문제를 보니 늘 사용하던 bfs를 통해 풀면 될 거 같은 문제였다.    private static final int[] dx = {0, 0, -1, 1};    private static final int[] dy = {1, -1, 0, 0};    public int[][] updateMatrix(int[][] mat) {        int[][] res = new int[mat.length][mat[0].length];        Queue que = new LinkedList();        for..

[Grind75-LeetCode] Insert Interval - Medium접근구현풀이2차원 배열로 각 구간이 주어지고 새로운 구간이 주어질 때 병합된 최종 구간은 어떻게 되는지 구하는 문제이다. 새로운 구간과 기존 구간이 겹치는 곳만 조작을 해주면 되는 문제이다. 예제2 번을 예시로 설명하겠다.Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]Output: [[1,2],[3,10],[12,16]]기존 구간1~2, 3~5, 6~7, 8~10, 12~16새로운 구간4~8겹치는 구간3~5, 6~7, 8~10겹치는 구간을 연결3~10결과1~2, 3~10, 12~16이렇게 새로운 구간을 삽입하며 기존 구간과 겹치는 부분을 병합하..

[Grind75-LeetCode] Maximum Subarray - Medium 접근카데인 알고리즘 (Kadane's Algorithm)풀이Grind75의 2주 차 마지막 문제로 LeetCode에서 풀어보는 첫 Medium 난이도 문제이다. 이 문제는 주어진 트리 내 서브트리의 합 중 최댓값을 구하는 문제이다. 주어지는 트리가 int 배열의 형태이기 때문에 사실상 배열 내 연속되는 부분의 최댓값을 구하는 것과 동일하다. 보통 연속되는 부분의 최댓값을 구할 때 브루트 포스를 사용해 구해주면 간단하긴 하지만 아래의 추가 내용으로 "만약 이 문제를 O(n) 성능으로 해결하는 법을 찾았다면 분할 정복 방법으로 도전해 봐라"라는 문구가 있기에 이 문제는 O(n) 성능으로 해결이 가능하다는 말인 거 같다. 그렇다면..

[Grind75-LeetCode] Middle of the Linked List - Easy접근구현풀이노드로 주어지는 리스트에서 가운데 노드를 구하는 문제이다. 만약 가운데 노드가 두 개라면 두 번째 노드를 선택한다. 짝수일 경우 가운데 노드가 두 개이기 때문에 뒤쪽을 선택하는 것이다. 문제 자체는 정말 간단하다. 배열로 주어졌다면 배열의 길이를 반으로 나눠 해당 인덱스를 반환하면 되겠지만 노드로 주어져 잠깐 생각을 하게 만드는 거지 큰 차이는 없다. head 노드로부터 next를 계속 탐색하여 총길이를 구한 뒤 중간 값 노드까지 포인터를 옮겨주는 방식으로 문제를 풀었다.    public class ListNode {        int val;        ListNode next;        Li..