Ustory

Problemhttps://leetcode.com/problems/minimum-suffix-flips/ Sol초기 '0'으로만 이루어진 문자열 s의 특정 인덱스 i부터 n-1까지 flip 했을때 '0'과 '1'로 이루어진 target과 똑같아 질 수 있는 최소 flip 수를 세는 문제 해결 방법👀 처음에 단순하게 생각해서 그냥 반복문으로 풀었습니다. for문이 안팎으로 돌다보니까 최소의 수를 보장할 수도 없고 시간복잡도가 O(n^2)이 나오는 효율 바닥 코드가 나왔습니다. 혹시나 했는데 역시나 test case는 통과했지만 submit을 하니까 Time Limit Exceeded가 떴습니다. T.T  class Solution: def minFlips(self, target: str) -> in..

꾸준히 잘 써오다가 28일차 TIL을 놓쳐버렸어요 🥲 다시 킵고잉~Problemhttps://leetcode.com/problems/iterator-for-combination/Sol오늘 문제는 주어진 문자로부터 주어진 길이의 1. 모든 조합을 생성하고 2. 다음 조합을 반환하고 3. 다음 조합이 있는지 확인하는 class CombinationIterator를 완성하는 문제였습니다. combinations을 사용한 코드와 그렇지 않은 코드 2가지로 해결해보았습니다.itertoools.combination 사용👀 Python 내장 모듈인 ‘itertools’의 combinations를 활용하면, 입력된 반복 가능한(iterable) 객체에서 주어진 길이의 조합을 생성할 수 있습니다.  from iter..

Problemhttps://leetcode.com/problems/find-the-original-array-of-prefix-xor/ SolXOR 연산으로 prefix된 배열을 통해서 원래의 배열을 찾는 문제: 주어진 배열의 각 요소는 해당 위치까지의 누적 XOR 값을 나타내며, 원래 배열을 복원하는 것이 목적! 해결 방법👀 복원해야하는 origin_arr를 초기화하고, 반복문을 통해 prefix 배열의 값에 차례대로 접근하여 원래 값을 찾아내는 방식으로 해결하였습니다.1. origin_arr : 찾으려고 하는 원래 배열- 첫번째 원소는 pref의 첫 번째 원소와 동일2. 반복문- origin_arr[i] = pref[i] 번째와 pref[i-1] 번째 값을 XOR 한 값(^)3. 정답 시간복잡도 O..

Problemhttps://leetcode.com/problems/subrectangle-queries/ Sol✅ 주어진 메소드 2개를 이용하여 class SubrectangleQueries를 완성하는 문제class SubrectangleQueries 는 'rows x cols' 크기의 직사각형을 정수 matrix 로 받아들입니다. method 1) updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)왼쪽 위 좌표가 (row1, col1)이고 오른쪽 아래 좌표가 (row2, col2)인 부분 직사각형의 모든 값을 newValue로 업데이트지정된 부분 직사각형의 범위 내의 모든 값을 새로운 값으로 변경한다는 의미method 2) ..

Problemhttps://leetcode.com/problems/capacity-to-ship-packages-within-d-days/ Solclass Solution: def shipWithinDays(self, weights: List[int], days: int) -> int: # days 동안 다른 항구로 짐 옮기기 # i 번째 짐 무게 == weights[i] 주어진 순서대로 실어야함 # 각 날마다 컨베이어 벨트 위의 짐들을 배로 옮길거야 # weight

Problemhttps://leetcode.com/problems/count-square-submatrices-with-all-ones/ Sol0과 1로 만들어진 행렬(matrix)에서 1로 만들 수 있는 정사각형의 최대 개수를 구하는 문제  Dynamic Programming 어떤 단계에 있을 때 처음부터 여기에 어떻게 왔는지는 중요하지 않다. 바로 그 앞 단계에서 어떻게 여기까지 왔는지 중요 특정 위치 i에 도착해있다고 가정하고  '그럼 그 전에도 어떻게든 알아서 잘 왔겠지' 라는 생각으로 푸는 형식입니다.  🌱 참고Dynamic Programming lectures Dynamic Programming lectures www.youtube.com문제는 짧은데 생각해내는데 너무 오래걸려서 냅다 유튜브..

Problemhttps://leetcode.com/problems/partition-array-for-maximum-sum/ Sol주어진 배열 arr를 최대 길이 'k'인 연속된 배열로 분할하고, 각 부분 배열의 모든 값을 그 부분 배열의 최대값으로 바꾼 후 배열의 합을 최대값을 구하는 문제 (변경된 배열의 최대합 구하기!)  해결 방법👀 작은 부분 문제를 해결하고 전체 문제를 해결하는 DP(Dynamic Programming)을 사용하였습니다. tab라는 저장 배열을 만들어주고 결과를 저장하며 업데이트하는 방식으로 구현했습니다.Bottom-UP1. tab : 배열 arr의 최대합을 저장하는 배열으로, 0으로 초기화2. 외부 반복문(i) : 1부터 n까지  - i : 배열 arr의 인덱스, tab[i]..

Problemhttps://leetcode.com/problems/count-sorted-vowel-strings/ Sol모음 (a, e, i, o, u)를 가지고 길이가 n인 사전순으로 정렬된 모음 문자열의 개수를 계산하는 문제 해결 방법 1: Combination👀  오늘은 문제를 보자마자 중복조합으로 풀어야겠다고 생각해서 math.comb을 사용해서 해결했습니다. 1. 중복 조합 : [식1] 선택할 수 있는 항목이 r개 일때, 중복을 허용하여 n개를 선택하는 경우의 수  ❓ 각 위치마다 모음을 중복하여 선택 가능(aa, oo, .. 가능) ❓문제 예시에서 'ae'가 나왔으면 'ea'는 같다고 취급함을 알려줍니다.2. 식 표현 : [식2] 이 문제에서는 입력으로 주어지는 길이 n, 모음 5개를 선택..

Problemhttps://leetcode.com/problems/all-possible-full-binary-trees/ Soln개의 노드를 가지는 가능한 모든 완전 이진트리(Full Binary Tree)를 생성하는 문제 Dynamic Programming 동적 프로그래밍동적 프로그래밍 DP == 동적 계획법문제를 작은 하위 문제로 나누고결과 저장➡ 동일 하위 문제에 대한 중복 계산 피하기중복되는 하위 문제큰 문제를 해결하기 위해 동일한 하위 문제를 여러번 해결해야 하는 경우, 중복되는 계산을 피하기 위해 사용문제의 최적 해결 방법이 그 하위 문제들의 최적 해결 방법으로 구성될 수 있는 경우Memoization이미 계산한 하위 문제의 결과를 저장해두고 필요할 때마다 결과를 사용하는 방식주로 재귀를 사..

Problemhttps://leetcode.com/problems/container-with-most-water/ Sol가장 많은 물을 담을 수 있는 컨테이너를 만들고 그 양을 찾는 문제 Greedy Algorithm ? Two-pointer ? two-pointer 접근법포인터를 배열의 처음과 끝에 둡니다.포인터가 양끝에서 시작하여 중앙으로 이동하면서 현재 가능한 최대 면적을 유지합니다.현재 가능한 최대 면적을 유지한다는 점에서 탐욕스러운 greedy algorithm 중 하나로 불리는 것 같습니다. 해결 방법👀 컨테이너의 너비를 최대로 시작하여 점점 좁히는 형식으로 접근하였습니다. 1. 시작과 끝에서 점점 좁히기 : 시작점에 left 포인터, 끝 점에 right 포인터 설정2. 면적 구하기 : ri..