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] 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] Counting Bits - Easy접근비트 연산풀이0부터 정수 n까지의 모든 숫자에 1이 몇 개 포함되어 있는가 구하는 문제이다.  n = 5 라면 0, 1, 2,..., 3, 4, 5 각 숫자의 1 개수를 배열에 담아 반환하면 된다. 이전 Number of 1 Bits와 같이 비트 조작 유형에 속하는 문제로 비트 연산자를 사용해야 하는 문제인 것 같다.  비트 조작 문제도 맞지만 dp를 사용해야 하는 문제이다. dp를 사용하지 않아도 풀 수는 있어서 난이도가 easy인지 모르겠는데 dp와 비트 조작을 같이 써서 풀면 easy라 하기엔 조금 난이도가 있지 않나? 싶다. public int[] countBits(int n) { int[] result ..

[Grind75-LeetCode] Maximum Profit in Job Scheduling - Hard접근dp이진 탐색풀이Job 스케줄러를 통해 얻을 수 있는 최대 이득을 구하는 문제이다. 시작 시간이 들어있는 배열, 종료 시간이 들어있는 배열 그리고 이익 값이 들어있는 배열이 주어진다. Job은 비선점 방식으로 수행이 되며 어떤 작업이 끝나는 시간에 다른 작업을 시작할 수 있다. 각 작업의 시간과 이득을 객체로 합쳐 놓고 종료시간을 기준으로 정렬한 뒤 dp와 이진 탐색을 통해 풀면 된다. 풀었던 방법과 성능이 제일 좋았던 코드는 알고리즘 자체는 동일하고 리스트를 사용하냐 배열을 사용하냐 정도의 차이였기 때문에 성능이 제일 좋았던 배열을 사용한 코드를 바로 들고 왔다. class Job { ..

[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 배열을 생성하고 ..

[Grind75-LeetCode] Partition Equal Subset Sum - Medium접근dpdfs풀이주어진 정수 배열 내의 값을 동등한 부분 합으로 만들 수 있는지 검사하는 문제이다. 예제 1번처럼nums = [1,5,11,5] -> [1, 5, 5] and [11]동일한 부분합으로 분리할 수 있는지 확인하는 것이다. 예제 1번이 [1, 5, 5]와 [11]로 분리되어 원소들을 더 한 값이 배열에 존재하는가와 같은 문제 이해를 잘못할 수 있는데 nums = [3,3,3,4,5] -> [3,3,3] and [4,5] 위처럼 단순히 부분합이 같은 두 집합으로 분리하는 것이다. public boolean canPartition(int[] nums) { int target = 0;..