kwang2134 님의 블로그

[NeetCode-LeetCode] Longest Common Subsequence - Medium접근dp풀이가장 긴 공통 부분 수열의 길이를 구하는 문제이다. 바로 전에 풀었던 문제와 유사한 형태로 이번에는 숫자가 들어있는 배열이 아닌 문자열을 비교하여 구해야 한다. 예시를 보면 text1 = "abcde", text2 = "ace"라는 입력이 주어졌을 때 가장 긴 공통 부분 수열은 "ace"로 길이인 3이 정답이 된다. text1에서 순서대로 부분 수열을 만들었을 때 "ace"를 만들 수 있기 때문이다. 2차원 dp 카테고리의 문제인 만큼 dp를 사용해 풀면 된다. public int longestCommonSubsequence(String text1, String text2) { ..

[NeetCode-LeetCode] Longest Increasing Subsequence - Medium접근이진 탐색풀이가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다. 그냥 증가하는 수열이 아니라 strictly increasing subsequence로 엄격한(?) 증가하는 부분 수열이다. 문제만 보고 이해가 잘 안 갔었는데nums = [0,1,0,3,2,3]위와 같은 배열이 있을 때 일반적인 증가하는 수열은 [0,1], [0,3], [2,3] 이렇게 최대 길이가 2인 부분 수열만 존재한다. 그러나 엄격하게 증가하게 증가하는 부분 수열의 경우 원소들을 증가하는 형태에 맞춰 삽입하여 수열을 만든다고 생각하면 된다. 예를 들어 [0,1]이라는 부분 수열이 만들어지고 그다음 0이 왔을 때 해당 원소..

[NeetCode-LeetCode] Maximum Product Subarray - Medium 접근dp풀이배열 내 연속된 원소들의 곱의 최댓값을 구하는 문제이다. 연속된 원소가 곱해졌을 경우에만 값으로 인정된다. [2, 3, -2, 4]라는 배열이 존재한다면 연속된 2, 3의 곱인 6은 값이 될 수 있지만 3, 4 사이엔 -2가 존재해 계산이 불가능하다. 원소는 음수 양수 모두 존재하기 때문에 가장 큰 값을 얻기 위해선 양수의 곱만 신경 쓸 것이 아니라 음수와 음수를 곱하는 경우도 신경을 쓰고 계산해야 한다.  public int maxProduct(int[] nums) { if (nums.length == 0) { return 0; } i..

[NeetCode-LeetCode] Decode Ways - Medium 접근dp풀이숫자를 문자로 해독할 때 해독한 문자열이 몇 가지로 표현할 수 있는지 구하는 문제이다. 숫자는 1부터 26까지 알파벳과 매칭되고 26을 넘어가는 경우 27이 아닌 2와 7로 나눠져 해석된다. 그렇다 보니 10~26 사이의 숫자들도 나눠서 해석될 수 있다. 17이라는 숫자가 있는 경우 17로 해석되어 q가 될 수 도 있고 1과 7로 나눠져 ag로 해석이 될 수 도 있기 때문에 이렇게 해석될 수 있는 모든 경우의 수를 구해야 한다.  dp 문제로 앞에서부터 체크하며 값을 쌓아나간다. public int numDecodings(String s) { if (s == null || s.isEmpty() || s...

[NeetCode-LeetCode] Palindromic Substrings - Medium 접근중심 확장풀이팰린드롬을 만족하는 부분 문자열을 찾는 문제이다. 문자열 내에 존재하는 모든 부분 문자열에 대해 팰린드롬을 검사하고 개수를 반환하여야 한다. 똑같은 문자라도 문자열 내 위치가 다르다면 한 개의 부분 문자열로 취급한다. 예시에 있는 "aaa" 문자열의 경우에도 첫 번째 두 번째 세 번째 a 모두 개별 문자로 취급하여 "aaa" 문자열의 총 부분 팰린드롬 문자열은 "a", "a", "a", "aa", "aa", "aaa"로 6개의 팰린드롬 부분 문자열을 가지고 있다.  팰린드롬이란 데칼코마니처럼 문자열을 앞으로 읽어도 뒤로 읽어도 동일한 문자열을 말한다. 팰린드롬 문자열인지 검사를 하기 위한 방법은 ..

[NeetCode-LeetCode] House Robber II - Medium접근dp풀이바로 전에 풀었던 집 터는 문제 2편이다. 연속된 집을 털 수 없는 규칙은 동일하나 이번엔 집이 원형으로 이루어져 있다는 점이다. 전 문제는 집이 직선 형태로 이루어져 있기 때문에 연속된 집만 털지 않고 처음부터 끝까지 진행하면 되었으나 이번에는 원형으로 첫 집과 마지막집이 연결되어 있기 때문에 해당 부분을 고려해야 한다.  원형으로 집이 연결되어 있다지만 첫 번째 집과 마지막 집만 연결되어 있는 거 기 때문에 특별히 추가로 신경 쓸 내용은 많지 않다. 첫 번째 집을 턴다면 마지막 집을 털지 않으면 되는 것이고 마지막 집을 턴다면 첫 번째 집을 털지 않으면 되는 것이기 때문이다. 이렇게 두 가지 케이스로 나눠서 이 ..

[NeetCode-LeetCode] House Robber - Medium접근dp풀이집을 약탈하여 최대한 많은 돈을 모으는 문제로 배열엔 집에서 약탈할 수 있는 돈의 금액이 들어있다. 조건으로 집을 연속하여 터는 경우 경보가 울려 경찰이 오기 때문에 연속되게 약탈을 할 수는 없다. dp를 사용하면 해결되는 문제이다. public int rob(int[] nums) { if (nums.length == 0) { return 0; } if (nums.length == 1) { return nums[0]; } int[] dp = new int[nums.length]; dp[0] = nums[..

[NeetCode-LeetCode] Pacific Atlantic Water Flow - Medium접근bfsdfs풀이태평양과 대서양으로 물이 흘러갈 수 있는지 확인하는 문제이다. 문제를 읽었을 때 이해가 빠르게 되는 문제는 아니었다. 좌표에는 물의 깊이 값이 들어있고 특정 좌표에서 물은 상하좌우로 흐를 수 있고 좌표의 다음 칸이 기존 좌표의 값과 동일하거나 더 작아야 흘러갈 수 있다는 그런 내용인 거 같았다. 결론은 특정 좌표에 물이 두 바다에 모두 도달이 가능한 지 체크하는 문제인 것 같았다.  그렇다면 양쪽 바다에서 시작해 모든 좌표를 체크하고 도달 가능한 두 좌표가 겹치는 부분을 찾으면 될 것이다.  private static final int[] dx = {-1, 1, 0, 0}; p..

[NeetCode-LeetCode] Design Add and Search Words Data Structure - Medium 접근접근 방법풀이단어 추가와 검색을 가능이 가능한 데이터 구조를 디자인하는 문제이다. 단어 추가의 경우 입력받는 단어를 데이터 구조 내 저장하는 로직을 수행하고 검색의 경우 데이터 구조 검색하고자 하는 단어가 저장되어 있는지 확인하는 로직이다. trie 파트에 있는 문제로 trie를 사용하여 풀어야 하는 문제로 전에 풀었던 문제는 검색 단어가 그대로 주어졌기 때문에 특별히 신경 쓸 부분이 없었지만 이번에는 "." 점의 형태로 패턴 매칭을 수행해야 하기 때문에 좀 더 복잡해졌다고 볼 수 있다. 기존 삽입 부분과 베이스는 이전에 풀었던 코드를 그대로 들고왔다. class Node ..

[NeetCode-LeetCode] Subtree of Another Tree - Easy접근재귀풀이어떤 트리 내부에 동일한 서브트리가 존재하는지 검사하는 문제이다. 정확하게 주어진 서브트리와 일치해야 한다 즉 기존 트리 내부에 서브트리와 동일한 부분이 존재하지만 밑에 추가로 자식 노드가 존재하거나 하는 경우엔 동일한 서브트리라 볼 수 없다. 위와 같은 형태에 왼쪽 트리에 4, 1, 2라는 동일한 구조가 있는데 2 노드 밑에 0이라는 자식 노드가 있기 때문에 다른 서브트리라 판단하고 false가 된다.  public boolean isSubtree(TreeNode root, TreeNode subRoot) { if (root == null) { return false..