동적 프로그래밍 패턴과 문제 해결 기법

### 코딩 면접을 위한 동적 프로그래밍 및 주요 알고리즘 패턴 마스터하기
* 📚 동적 프로그래밍(DP)은 최적화 문제를 더 작은 하위 문제로 나누어 해결하는 중요한 기법으로, **최장 증가 수열, 부분 집합 합, 행렬 연쇄 곱셈**과 같은 패턴을 사용하는 경우가 많습니다.
* 🔗 DP 패턴에 대해 더 깊이 이해하고자 하는 분들을 위해 최근 블로그 게시물에서 **20가지 동적 프로그래밍 패턴**에 대해 설명하고 관련 **LeetCode 문제에 대한 링크**를 제공합니다.
* 📝 blog.algomaster에 있는 이 블로그는 격주로 **코딩, 데이터 구조, 알고리즘, 시스템 설계 및 인터뷰 준비에 대한 인사이트**를 제공하여 학습자에게 유용한 자료가 됩니다.
* 🔍 수정된 이진 검색 패턴은 **거의 정렬된 배열이나 중복이 있는 배열**을 검색할 때 유용하며, 문제 해결의 효율성을 높여줍니다.
* 📏 두 개의 포인터 접근 방식은 **포인터가 만날 때까지 양쪽 끝의 문자를 비교**하여 문자열의 팔린드롬 검사를 간소화하여 시간 복잡성을 크게 줄입니다.
* 🌊 슬라이딩 윈도우 패턴은 특정 기준을 충족하는 서브어레이 또는 서브스트링을 찾는 데 도움이 되며, **크기 K의 서브어레이의 최대 합 구하기**와 같은 문제에 대해 **O(n*K)에서 O(n)까지의 솔루션을 최적화**합니다.
* 🔄 역추적은 **모든 잠재적인 솔루션 경로를 탐색**하는 강력한 기술로, **순열을 생성하거나 스도쿠와 같은 퍼즐을 푸는** 등의 문제에 적용할 수 있습니다.
* 💡 이러한 패턴을 익히면 **Amazon, Google과 같은 유수 기업의 면접에 대비**할 수 있을 뿐만 아니라 다양한 코딩 과제를 효율적으로 해결할 수 있는 도구를 갖추게 됩니다.

동적 프로그래밍 패턴을 마스터하면 문제 해결자가 다양한 코딩 과제를 효율적으로 해결할 수 있습니다.

Having solved more than 1500 lead code problems, if there is one thing I have learned, it is this: lead code is less about the number of problems you have solved and more about how many patterns you know. Because learning patterns allows you to solve a wide variety of problems in less time and helps you quickly identify the right approach to a problem you have never seen before. In this video, I will walk you through the 15 most important patterns I learned that made my lead code journey a lot less painful. And the best part is, these patterns actually came up in most of the interviews, including at companies like Amazon and Google. For each pattern, I will explain when to use it, walk through an example, and list lead code problems you can practice to learn them better. First off, we have the prefix sum pattern. This pattern is commonly used for problems where you need to query the sum of elements in a subarray. Imagine you are given an array, and you need to find the sum of all elements between indexes I and J. If you have just one query, you can simply loop

through the array in linear time to find the sum, but if you have multiple such queries, it can take up to order of n * m time complexity, where m is the number of queries and N is the length of the array. To make such queries faster, you can create a prefix sum array, where the value at index I is the sum of all elements from the start up to index I in the given array. Now you can answer some queries in O(1) time using the formula sum from I to J is equal to P of J minus P of I - 1. This is the main idea behind the prefix sum pattern. One thing to remember is that you don't always need a new array for prefix sums; sometimes you can use the input array itself and avoid using extra space. Here are some LeetCode problems you can practice using this pattern. Next one is the two pointers pattern. In the two-pointer approach, we use two variables and move them towards each other or away from each other based on the problem. For example, let's say you are given a string and you need to check

whether it's a palindrome. A string is a palindrome if it's the same when the order of characters is reversed. To solve this problem using the two pointers approach, use one pointer to iterate from the beginning and the other from the end. At each step, compare the values at both pointers. If they don't match, the string is not a palindrome; return false. If they match, move the pointers closer. Keep doing this until the pointers meet. The two pointers pattern can reduce the time complexity for many problems from order of L^2 to order of n, so make sure to practice it well. There are a few LeetCode problems to get better at this pattern. Let's slide into our next pattern: sliding window. This pattern helps us find subarrays or substrings that meet a specific criteria. Let's understand it with an example. Suppose you're given an array and you need to find the subarray of size K with the maximum sum. Let's say K is three. A brute force approach is to consider all the subarrays of size three using a nested

for Loop and pick the one with the maximum sum, but since the adjust server is overlap, there is a lot of repetitive calculation leading to a Time complexity of order of n * K. Because optimize this using sliding window approach, we start by initializing a window containing the sum of first three elements, and as we iterate through the array, we subtract the leftmost item, add new item's value to the window, and update the result. This reduces time complexity from order of n * K to order of n since we are only using a single for Loop to iterate through the array. There are some lead code problems to practice this approach. Next pattern is a variant of the two pointers pattern called fast and slow pointers. This pattern helps solve problems related to linked lists and arrays which involves finding Cycles. It works by moving two pointers at different speeds. Let's understand this with a real-world example. Imagine a circular track with two Runners A and B. Runner A moves faster than Runner B. Since the track is circular, Runner A will eventually pass

Runner V, this is the idea behind fast and slow pointers. Using this approach, you can check if a linked list contains a cycle. Start by placing both slow and fast pointers at the head of the linked list. Move the slow pointer one node at a time and the fast pointer two nodes at a time. If there is a cycle, they will eventually meet. This pattern can also find the middle node of a linked list in one pass. When the fast pointer reaches the end, the slow pointer will be at the middle of the linked list. To get better at this pattern, you can practice these lead code problems. The next pattern on the list is linked list in-place reversal. Many linked list problems ask you to change its nodes and pointers in some way. The trick is to do it in-place without using extra space. That's where this pattern can help. Let's look at an example where you need to reverse a linked list. A simple approach is to copy the linked list values into an array and then update the linked list by traversing the array in reverse.

but this isn't the most optimal approach since it needs extra space equal to the size of the link list and requires multiple passes through the link list. Can we do it in one pass and without extra space? Yes, we can use three pointers: previous, current, and next. Set previous to none and current to the head of the link list. Use a while loop to go through the list until current is none. In each loop, set next to the next node of the current, reverse the current node's pointer to point to previous, move previous to current, and current to next. At the end of the loop, previous will point to the new head of the reversed link list. You can use this technique for any problem that asks you to rearrange the links between nodes of a link list. Here are some lead code problems to practice this pattern. The next pattern is monotonic stack. This pattern uses a stack to find the next greater or next smaller element in an array. Let's look at an example. Given an array, find the next greater element for each item. If there isn't one,

output minus one a br. Force approach is to use a nested for loop to check all the elements to the right of each item until you find a bigger one, but this can take up to order of n square time. We can solve it in O of n time by using a stack. Here is what the algorithm looks like: use a stack to track indices of elements for which we haven't found the next greater element yet. Initialize the result array with minus 1s for each element. Check if it's greater than the element at the top of the stack. If it is, pop from the stack and set the result for that index to the current element. Push the current element onto the stack. During the whole process, we keep the stack elements in the decreasing order, but for finding the next smaller element, keep them in increasing order. Here are some lead quote problems to practice this pattern. Next is the top K elements pattern. This pattern helps you find the K largest, smallest, or most frequent elements in a data set. Imagine you have an array and you need to find three.

largest elements. A simple approach is to sort this array in descending order and take the first three elements, but sorting takes O(n log n) time. Can we avoid sorting the array? Yes, by using a min-heap. By using a min-heap, we can keep track of the three largest elements as we loop through this array. Since inserting and popping elements in a heap takes logarithmic time, it reduces the time complexity from O(n log n) to O(n log k). We start by putting the first three elements into a min-heap. After that, for every element, we compare it with the top heap element. If the current array element is greater, we pop the top element from the heap and push the new element at the end. The heap will contain three largest elements. If the problem asks you to find K largest elements, use a min-heap, but for K smallest problems, use a max-heap. There is another algorithm called quick select that can solve top K elements problems with an average time complexity of O(n), but it's more complex. I will cover it in a future video if you'd like.

me to make detailed videos on each of these patterns and cover multiple examples. Let me know in the comments and make sure to subscribe so that you don't miss my new videos. Here are some problems to practice the top key elements pattern. Next is the overlapping intervals pattern. This pattern is useful for problems involving intervals or ranges that may overlap. Here are a few problem types where you can apply this pattern: merging intervals, given a collection of intervals, merge all overlapping intervals into one interval; intersection, find the intersection between two sets of intervals; insert interval, add a new interval to a list of non-overlapping intervals; and problems like finding the minimum number of meeting rooms needed for overlapping meeting times. Let's understand one of the examples where you are given a list of intervals and you need to merge all overlapping intervals. Here is an approach to solve this problem: start by sorting the intervals by the start time, create an empty list called MZ to store the merged intervals, read through the intervals, and check if it overlaps with the last interval in the MZ list. If it

overlaps mge the intervals by updating the end time of the last interval in M if it doesn't overlap at the current interval to the m list to get better at this pattern try solving these lead code problems next is modifies binary search pattern modifies binary search pattern is a variant of the standard binary search algorithm used to solve problems where the array isn't perfectly salted like searching in a nearly salted array searching in a rotated salted array searching in a list with unknown length searching in Array with duplicates finding the first or last occurrence of an element finding the square root of a number or finding a peak element for example if we are given a rotated salted array and we need to search for an element we can perform binary search with an additional check to determine which half of the array is salted within check if the target is within the range of the sorted half if it is we sech that half otherwise we search the other half here are some problems to practice this approach next pattern is binary tree.

traversal binary trees are all about traversing it in a specific order. The four popular ways to traverse the binary tree are pre-order, in-order, post-order, and level-order. Implementing pre-order, in-order, and post-order traversal algorithms in code is pretty easy if you use recursion, but the iterative version is a bit more complex and requires using stack data structures. Level-order traversal is useful when you want to explore the nodes level by level, starting from the root node. It is usually implemented using a queue data structure. Whenever you are given a tree problem, think about which traversal order fits the best. For example, to retrieve the values of a binary search tree in sorted order, use in-order traversal. To create a copy of the tree and the problems involving tree serialization, use pre-order traversal. When you want to process child nodes before the parent, like when deleting a tree, use post-order traversal. And when you need to explore all nodes at the current level before moving on to the next, use level-order traversal. Here are the problems you can solve to learn.

these traversal algorithms. The next one is depth-first search or DFS. It is used to explore all paths or branches in graphs or trees to solve problems like finding a path between two nodes, checking if a graph contains a cycle, finding the topological order in a directed graph, and counting the number of connected components in a graph. DFS can be implemented recursively or iteratively using a stack. Here is a generic approach to solve DFS-related problems: choose a starting point, keep track of visited nodes to avoid cycles, perform the required operation on the current node, explore unvisited neighbors, and continue until all required nodes are visited. Here are some lead code problems you can practice to learn this pattern. The next pattern is a related one called breadth-first search or BFS. BFS is a traversal technique that explores nodes level by level in a tree or graph. It is very useful for problems like finding the shortest path between two nodes in an unweighted graph, printing all nodes of a tree level by level, finding all connected components in a graph, and finding the sorted transformation.

sequence from one word to another to implement BFS. We can use a queue. Here is a generic approach to solve BFS problems: add the starting node to the queue, set up a visited set or array to track processed nodes, continue while the queue is not empty, dequeue a node and process it, and enqueue unvisited neighbors, add processed nodes to the visited set, continue until the queue is empty. Here are some LeetCode problems you can practice using this approach. Next up is the Matrix traversal pattern. Most Matrix traversal problems can be seen as graph problems. In a graph, you have nodes and edges. In a matrix, which is usually a 2D array, your nodes are the cells from where you can reach to adjacent cells horizontally, vertically, or diagonally, depending on the problem. The best part is you can use most of the graph algorithms like DFS and BFS to solve Matrix-related problems like finding the shortest path in a grid. Let's understand this pattern using the island count problem. You're given a 2D binary grid where one is land and zero

is water. You need to return the number of islands. An island is formed by connecting adjacent lands horizontally or vertically. You can either use DFS or BFS to solve this problem. Let's do DFS for this one. Here is the general idea: iterate through each cell in the grid. If you find a land cell, we have found a new island. Explore this island using DFS, marking all connected land cells as visited. Increment our island count. Continue until we have checked all cells. Here are the lead quid problems you can practice using this approach. Next pattern is backtracking. Backtracking is a powerful technique used to solve problems that involve exploring all potential solution paths and backtracking the paths that do not lead to a valid solution. Some of the problems you can solve using this approach are: generate all possible permutations or combinations of a given set of elements, solve puzzles like Sudoku or N-Queen problem, find all possible paths from a start point to an endpoint in a graph or a maze, generate all valid parentheses of a given length. Let's say you are

given an array of integers, and you need to generate all possible subsets. We can use the backtracking approach to solve this problem. We start with an empty subset and index zero. For each element, we have two choices: include it or not. After making a choice, we recurse to the next element. Once we have considered all elements, we backtrack to explore other possibilities. To get better at backtracking, you can practice these problems. Lastly, dynamic programming, also called DP, is a powerful technique used for solving optimization problems by breaking them down into smaller subproblems and restoring their solutions to avoid repetitive work. It is particularly useful for problems with overlapping subproblems and optimal substructure properties, like problems where you need to maximize or minimize a certain value and counting problems where you need to count the number of ways to achieve a certain goal. Dynamic programming is a big and challenging topic for coding interviews, but learning common patterns can make it a lot easier. Here are some of the common DP patterns you should know about: Fibonacci numbers, 0/1 knapsack, longest common subsequence.

longest increasing subsequence, subset sum, and matrix chain multiplication, and these are the lead quote problems you can solve to learn these patterns. If you want to learn more about DP patterns, check out my recent blog article where I talk about 20 dynamic programming patterns and include links to lead code problems for each pattern. Links are in the description. You can also find links to other patterns and lead code questions that I mentioned in this video in the description. You can subscribe to my blog at blog.algomaster, where I post twice a week about topics related to coding, DSA, system design, and interviews. If you want to know what else is required to master DSA apart from learning patterns, do check out this video. See you there.

LeetCode was HARD until I Learned these 15 Patterns

Ashish Pratap Singh

배열 합계 쿼리를 효율적으로 처리하고 가장 큰 요소 찾기

접두사 합계 배열을 사용하면 다중 합계 쿼리의 시간 복잡도를 쿼리당 O(n * m)에서 O(1)로 줄일 수 있습니다.

2포인터 접근 방식과 min-heap은 배열에서 가장 큰 요소를 효율적으로 추적하여 시간 복잡성을 O(n 로그 n)에서 O(n 로그 k)로 줄일 수 있습니다.

가장 큰 요소 K개를 찾으려면 최소 힙을 사용하고, 가장 작은 요소 K개를 찾으려면 최대 힙을 사용합니다.

코딩에서 다음 더 큰 요소와 핵심 패턴을 효율적으로 찾기

스택은 인덱스를 추적하고 감소하는 순서를 유지함으로써 배열에서 다음으로 큰 요소를 O(n) 시간 내에 찾는 데 사용할 수 있습니다.

상위 K 요소 패턴은 데이터 세트에서 가장 크거나, 가장 작거나, 가장 빈번한 요소를 식별하는 데 도움이 됩니다.

접두사 합계 및 이진 트리 탐색과 같은 일반적인 패턴을 학습하는 것은 다양한 코딩 문제를 효율적으로 해결하는 데 매우 중요합니다.

간격 및 연결된 목록 문제 해결을 위한 패턴

겹치는 간격 패턴은 간격 병합 및 교차점 찾기와 같이 겹칠 수 있는 범위와 관련된 문제에 유용합니다.

겹치는 간격을 병합하는 최적의 방법은 세 개의 포인터를 사용하여 추가 공간 없이 한 번에 목록을 가로지르는 것입니다.

단조로운 스택 패턴은 배열에서 다음으로 크거나 작은 요소를 찾는 데 도움이 되므로 이러한 문제에 대한 효율적인 해결책을 제공합니다.

그리드에 있는 섬의 수는 연결된 육지 셀을 방문한 것으로 표시하여 DFS를 사용하여 찾을 수 있습니다.

백트래킹은 모든 솔루션 경로를 탐색하는 강력한 기술로 순열, 스도쿠, 미로 탐색과 같은 문제에 유용합니다.

빠르고 느린 포인터 패턴은 연결된 목록에서 주기를 감지하고 중간 노드를 찾을 수 있으며, 연결된 목록의 제자리 반전은 추가 공간 없이 노드와 포인터를 변경하는 데 도움이 됩니다.

역추적 및 동적 프로그래밍으로 부분집합 생성 및 문제 해결하기

역추적을 사용하면 각 요소를 포함하거나 제외하도록 선택함으로써 배열의 가능한 모든 하위 집합을 생성할 수 있습니다.

동적 프로그래밍은 최적화 문제를 더 작은 하위 문제로 나누고 반복적인 작업을 피함으로써 문제를 해결하는 강력한 기법입니다.

일반적인 DP 패턴에는 피보나치수, 0/1 냅색, 최장공통수열 등이 있으며, DFS 및 BFS와 같은 그래프 알고리즘은 행렬 탐색과 트리 또는 그래프에서 노드 탐색에 사용할 수 있습니다.

동적 프로그래밍 패턴 및 문제 해결

최장 증가 수열, 부분집합 합, 행렬 연쇄 곱셈과 같은 동적 프로그래밍 패턴은 다양한 문제를 푸는 데 핵심적인 역할을 합니다.

이 블로그에서는 20가지 동적 프로그래밍 패턴에 대한 인사이트를 관련 LeetCode 문제에 대한 링크와 함께 제공합니다.

수정된 이진 검색 및 두 포인터와 같은 다른 패턴도 응용 및 연습 문제와 함께 설명합니다.