코딩 패턴: 코딩 인터뷰 준비를 위한 더 스마트한 접근 방식

코딩 인터뷰를 준비하는 것은 개발자가 새로운 자료를 검토하고 배우는 데 몇 주를 소비하는 경우가 많기 때문에 정말 어려운 일이 될 수 있습니다.

사실, 대부분의 개발자는 코딩 인터뷰에 대한 준비가 완전히 되어 있지 않다고 생각합니다. 개발자가 LeetCode에서 문제를 해결하는 데 몇 주를 소비하고도 여전히 준비가 되지 않았다고 느끼는 것은 드문 일이 아닙니다. 분명히 이 접근법에는 문제가 있습니다.

전통적인 코딩 인터뷰 준비와 관련된 몇 가지 문제를 자세히 살펴보겠습니다.

전통적인 인터뷰 준비의 함정

전통적인 인터뷰 준비에서 가장 흔한 함정 중 하나는 "연마" 관행입니다. 이 접근 방식에는 명확한 계획이나 전략 없이 가능한 한 많은 LeetCode 문제를 해결하는 것이 포함됩니다. 이는 생산적인 전략처럼 보일 수 있지만 몇 가지 단점이 있습니다.

체계적인 접근 방식 없이 문제를 해결하면 자신의 약점을 인식하지 못할 수도 있습니다. 연구에 대한 의도적인 계획은 없습니다. 목표는 단순히 가능한 한 많은 문제를 해결하는 것입니다. 결과적으로, 많은 것을 배웠다고 느낄 수도 있지만, 지식에 상당한 격차가 있을 수 있습니다.

더욱이 이것의 문제는 본질적으로 다양한 문제에 대한 해결책을 암기하는 것과 관련이 있다는 것입니다. 수백 가지 코딩 문제에 대한 해결책을 기억하려는 시도는 면접관이 이전에 접했던 것과 조금이라도 다른 질문을 제시할 때 효과적이지 않습니다. 이로 인해 다양한 문제를 처리할 준비가 되어 있지 않다는 느낌이 들 수 있습니다.

이 전략의 마지막 문제는 장기적으로 더 많은 스트레스와 두통을 유발한다는 것입니다. 직업을 바꾸고 싶을 때마다 몇 주간 똑같은 벼락치기 공부를 해야 한다면, 매번 어려움을 겪게 될 것입니다. 당신은 이전과 같은 문제를 다시 배우고 해결하는 데 몇 주를 보낼 것입니다.

이러한 과제를 감안할 때 더 나은 방법이 있어야 합니다.

더 나은 방법: 코딩 패턴 수용

그렇다면 코딩 인터뷰 준비에 더 효과적이고 지속 가능한 접근 방식이 있을까요? 그 답은 코딩 패턴을 이해하고 활용하는 데 있습니다.

저는 코딩 인터뷰를 준비할 때 문제의 기본 패턴을 파악하는 것을 우선시합니다. Two-Pointers , Sliding Window , Modified Binary Search , Topological Sort 등과 같은 기술을 포함하는 이러한 패턴은 광범위한 코딩 문제를 해결하기 위한 다양하고 강력한 프레임워크를 제공합니다. 해결책을 암기하는 것에서 검증된 문제 해결 기술로 강조점이 바뀌었습니다.

코딩 패턴에 집중하면 인터뷰 준비를 대폭 간소화하여 더욱 효율적으로 만들 수 있습니다.

기억하세요. 더 열심히 준비하는 것이 아니라 더 현명하게 준비하세요.

뭘 기대 할까?

이번 글에서는 제가 정리한 상위 15개 코딩 패턴 코딩 질문에 대답하려면 알아야 할 사항입니다. 각 패턴이 무엇인지, 어떻게 작동하는지 분석하겠습니다. 패턴을 식별하는 데 도움이 되는 주요 지표를 공유하고, 마지막으로 템플릿 코드로 상세한 그래픽을 제공하여 이해를 강화하는 데 도움을 줍니다.

이 기사에서 많은 내용을 다루고 있지만 더 심층적인 교육, 설명 및 코딩 연습을 원한다면 Techinterviews.io에서 종합 코딩 인터뷰 준비 과정을 확인하세요 . 우리는 또한 데이터 구조 , 행동 인터뷰 , 심지어 급여 협상 과 같은 중요한 주제도 다룹니다.

이제 이러한 코딩 패턴을 살펴보겠습니다.

1. 연결리스트 반전

연결 목록 반전에는 연결 목록의 포인터 방향을 변경하여 요소의 순서를 바꾸는 작업이 포함됩니다. 이는 데이터 구조의 기본 작업이며 종종 노드 참조를 주의 깊게 조작해야 합니다.

이는 연결된 목록을 처리할 때 유용하며 제약 조건은 이를 제자리에서 반전시키는 것입니다.

연결된 목록을 제자리에 되돌리는 프로세스는 다음과 같습니다.

1. 세 가지 변수( current , Previous 및 next ) 를 정의하는 것부터 시작하세요. 연결된 리스트의 선두를 현재로 설정하고, 이전과 다음을 None으로 초기화합니다.

2. 현재 변수가 None 이 아닌 동안 다음을 수행하십시오.

   1. 다음 노드를 임시 변수에 저장합니다.
   2. 현재 노드의 포인터를 반전하여 이전 노드를 가리킵니다.
   3. 이전 노드를 현재 노드로 업데이트하고 현재 노드를 다음 노드로 업데이트합니다.

3. 마지막으로, 역방향 목록의 헤드를 도달한 마지막 노드로 설정합니다. 이는 이전 변수에 저장됩니다.

주요 지표:

• 연결리스트의 요소 순서를 반대로 바꿔야 합니다.
• 문제는 연결된 목록에서 회문을 확인하는 것과 관련됩니다.
• 목록 내의 특정 하위 목록에 있는 요소의 순서를 반대로 바꾸고 싶습니다.

템플릿 코드:

파이썬

 def reverse_linked_list(head): curr = head prev = None while curr: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev

JS

 function reverseLinkedList(head) { let curr = head; let prev = null; while (curr) { const nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

자바

 public ListNode reverseLinkedList(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

2. 수정된 이진 검색

수정된 이진 검색은 다양한 문제를 해결하기 위해 고전적인 이진 검색 알고리즘을 적용합니다. 변형에는 요소의 첫 번째/마지막 발생 찾기 또는 회전된 배열 검색이 포함됩니다. 중간점과 조건을 주의 깊게 처리해야 합니다.

정렬된 배열, 연결 목록 또는 행렬이 제공되면 수정된 이진 검색을 사용해 보세요.

정렬된 데이터 구조에 이 패턴을 적용하는 방법은 다음과 같습니다.

1. 시작 위치와 끝 위치 사이의 중간점을 식별하여 시작합니다. 잠재적인 정수 오버플로를 방지하려면 middle = start + (end - start) / 2 같이 중간을 계산하는 것이 더 안전합니다.
2. 키가 중간 인덱스의 요소와 일치하는지 확인하세요. 그렇다면 중간 인덱스를 결과로 반환합니다.
3. 키가 중간 인덱스의 요소와 일치하지 않으면 다음 단계로 진행하세요.
4. 키가 인덱스 middle 에 있는 요소보다 작은지 여부를 평가합니다. 그렇다면 끝을 중간 - 1 로 업데이트하여 검색 범위를 좁히세요.
5. 반대로, 키가 인덱스 middle 에 있는 요소보다 큰 경우 start를 middle + 1 로 업데이트하여 검색 범위를 조정하세요.

주요 지표:

• 정렬된 데이터 구조로 작업하고 있습니다.
• 특정 요소, 경계 또는 피벗점을 효율적으로 찾아야 합니다.
• 문제는 회전 정렬 배열 검색과 관련됩니다.

템플릿 코드:

파이썬

 def binary_search(arr: List[int], target: int) -> int: left, right = 0, len(arr) - 1 first_true_index = -1 # Perform binary search until left and right pointers meet while left <= right: mid = (left + right) // 2 if feasible(mid): # If the condition is true at mid index, update first_true_index first_true_index = mid right = mid - 1 else: # If the condition is false at mid index, narrow down the search space left = mid + 1 return first_true_index

JS

 function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; let firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { const mid = Math.floor((left + right) / 2); if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

자바

 public int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; int firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { int mid = left + (right - left) / 2; if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

3. 두 개의 포인터

두 포인터 기술에는 쌍이나 하위 배열과 관련된 문제에 자주 사용되는 데이터 구조(일반적으로 배열 또는 연결 목록)를 순회하는 두 개의 포인터를 유지하는 작업이 포함됩니다. 서로 다른 위치의 요소를 비교해야 하는 문제에 최적화됩니다.

이 기술의 장점은 단순성과 효율성에 있습니다. 특히 처음에 하나의 포인터만 사용할 수 있는 배열이나 문자열과 같은 선형 데이터 구조를 처리할 때 더욱 그렇습니다. 두 개의 포인터를 사용하면 중복 작업을 방지하고 런타임 효율성을 크게 향상시켜 잠재적으로 O(n^2) 에서 O(n) 으로 줄일 수 있습니다.

"두 포인터" 패턴은 각각 특정 시나리오에 맞게 조정된 여러 변형을 포함합니다. 이러한 변형에는 동일한 방향 , 반대 방향 및 "빠른 및 느린" 이라는 고유한 방법이 포함됩니다. 이 방법은 데이터 구조를 통해 서로 다른 속도로 이동하는 두 개의 포인터를 포함하는 "거북이와 토끼" 기술이라고도 하며 특히 감지에 유용합니다. 사이클.

여러 포인터를 사용하여 데이터 구조를 탐색하는 경우 접근 방식을 "두 포인터" 패턴을 따르는 것으로 분류할 수 있습니다.

주요 지표:

• 서로 다른 위치에 있는 요소를 비교하거나 조작해야 합니다.
• 문제는 정렬된 배열에서 요소 쌍을 검색해야 합니다.
• 정렬된 배열에서 중복 항목을 효율적으로 제거하려고 합니다.
• 선형 데이터 구조(배열, 문자열 또는 연결된 목록)를 처리하고 2차 시간 복잡도( O(n^2) 무차별 솔루션)에 직면할 때 두 포인터 사용을 고려하십시오.

템플릿 코드:

"반대 방향" 변형을 위한 템플릿

파이썬

 def two_pointers_opposite(arr): left = 0 right = len(arr) - 1 ans = 0 while left < right: # Perform logic using the left and right pointers if CONDITION: left += 1 else: right -= 1 return ans

JS

 function twoPointersOpposite(arr) { let left = 0; let right = arr.length - 1; let ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

자바

 public int twoPointersOpposite(int[] arr) { int left = 0; int right = arr.length - 1; int ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

4. 슬라이딩 윈도우

슬라이딩 윈도우 기술에는 배열, 문자열 또는 연결된 목록과 같은 선형 데이터 구조에 대한 동적 윈도우를 유지하는 작업이 포함됩니다. 창의 크기는 구체적인 구현에 따라 달라질 수 있으며, 고정된 값으로 설정할 수도 있습니다. 이 창의 주요 목적은 특정 기준을 충족하는 데이터를 지속적으로 모니터링하고 캡처하여 하위 배열 또는 하위 문자열 문제를 효율적으로 해결하는 데 특히 유용하게 만드는 것입니다.

이 패턴은 창 내에서 개별 데이터를 쉽게 추적하기 위해 해시 맵을 활용하는 경우가 많습니다. 그러나 이 접근 방식은 O(n) 의 시공간 복잡성을 초래할 수 있다는 점에 유의하는 것이 중요합니다.

주요 지표:

• 연속 또는 비연속 하위 배열이나 하위 문자열을 분석해야 합니다.
• 문제는 더 큰 데이터 세트 내에서 가변 길이 시퀀스를 추적하는 것과 관련됩니다.
• 고정 길이의 최대 합계 하위 배열을 찾고 싶습니다.
• 문제 입력은 배열, 연결 리스트, 문자열과 같은 선형 데이터 구조입니다.

템플릿 코드:

파이썬

 def slidingWindow(nums): # Initialize necessary variables left = 0 window = [] # Initialize the window ans = 0 # Initialize the answer variable for right in range(len(nums)): window.append(nums[right]) # Expand the window to the right while invalid(window): # Condition to shrink the window from the left until it is valid again window.pop(0) # Remove the left element from the window left += 1 ans = max(ans, len(window)) # Update the answer, can vary on your implementation return ans

JS

 function slidingWindow(nums) { let left = 0; const window = []; // Initialize the window let ans = 0; // Initialize the answer variable for (let right = 0; right < nums.length; right++) { window.push(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.shift(); // Remove the left element from the window left++; } ans = Math.max(ans, window.length); // Update the answer , can vary on your implementation } return ans; }

자바

 public static int slidingWindow(int[] nums) { int left = 0; List<Integer> window = new ArrayList<>(); // Initialize the window int ans = 0; // Initialize the answer variable for (int right = 0; right < nums.length; right++) { window.add(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.remove(0); // Remove the left element from the window left++; } ans = Math.max(ans, window.size()); // Update the answer , can vary on your implementation } return ans; }

5. 상위 K 요소

이 패턴에는 컬렉션에서 K개의 가장 크거나 가장 작은 요소를 찾는 작업이 포함되며, 종종 힙이나 우선 순위 큐와 같은 데이터 구조를 사용하여 구현됩니다. 값이나 빈도를 기준으로 요소의 하위 집합을 선택하는 데 유용합니다.

주어진 데이터 세트 내에서 가장 빈번하거나, 가장 작거나, 상위 'K' 요소를 찾으라는 요청을 받을 때마다 이 패턴 사용을 고려할 수 있습니다.

작동 방식은 간단합니다.

1. 최소 또는 최대 힙에 'K' 요소를 삽입합니다(구현에 따라 다름).
2. 힙에 추가할 때마다 자주/가장 작은/상위 'K' 요소가 항상 유지되도록 조정해야 합니다.

이 접근 방식의 장점은 효율성에 있습니다. 힙 자체가 자연스럽게 필요한 순서를 유지하므로 정렬 알고리즘에 의존할 필요가 없습니다.

주요 지표:

• 컬렉션에서 K개의 가장 큰 요소 또는 가장 작은 요소를 식별해야 합니다.
• 문제에는 특정 기준에 따른 순위 요소가 필요합니다.
• 데이터 세트에서 상위 K개의 자주 사용되는 요소를 찾으려고 합니다.

템플릿 코드:

파이썬

 import heapq def top_k_elements(arr, k): heap = [] for num in arr: # Define your own criteria and logic to push elements onto the heap # For example, if you want to find the top k largest elements, push (-num, num) onto the heap heapq.heappush(heap, (-CRITERIA, num)) if len(heap) > k: heapq.heappop(heap) return [num for _, num in heap]

JS

 function topKElements(arr, k) { const minHeap = []; for (const num of arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k smallest elements, push num onto the heap minHeap.push(CRITERIA); if (minHeap.length > k) { minHeap.sort((a, b) => a - b).shift(); } } return minHeap.sort((a, b) => a - b); }

자바

 import java.util.*; public List<Integer> topKElements(int[] arr, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(a -> -CRITERIA)); for (int num : arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k largest elements, push -num onto the heap heap.offer(-CRITERIA); if (heap.size() > k) { heap.poll(); } } List<Integer> topK = new ArrayList<>(); while (!heap.isEmpty()) { topK.add(-heap.poll()); } Collections.reverse(topK); return topK; }

6. 두 개의 힙

두 개의 힙은 두 개의 힙(최대 힙과 최소 힙)을 활용하여 데이터 세트에서 중앙값 찾기와 같은 특정 문제를 최적화합니다. 이 패턴은 균형 잡힌 구조를 유지하는 데 특히 유용합니다.

작동 방식은 다음과 같습니다.

1. 두 개의 힙을 활용합니다. 최대 힙은 가장 큰 요소를 식별하고 최소 힙은 가장 작은 요소를 찾습니다.
2. 숫자 중 가장 큰 숫자를 찾는 것을 목표로 숫자의 전반부로 Max Heap을 채웁니다.
3. Min Heap을 숫자의 후반부로 채워 이 부분에서 가장 작은 숫자를 찾아냅니다.
4. 현재 숫자 집합의 중앙값은 두 힙의 최상위 요소를 검사하여 언제든지 계산할 수 있습니다.

주요 지표:

• 효율적인 중앙값 찾기를 위해서는 균형 잡힌 구조를 유지해야 합니다.
• 문제는 동적 중앙값으로 슬라이딩 윈도우 문제를 처리하는 것과 관련이 있습니다.
• 값을 기준으로 컬렉션의 요소 우선순위를 지정하려고 합니다.

템플릿 코드:

파이썬

 import heapq class TwoHeaps: def __init__(self): self.min_heap = [] # Right heap to store larger half self.max_heap = [] # Left heap to store smaller half def add_num(self, num): if not self.max_heap or num <= -self.max_heap[0]: heapq.heappush(self.max_heap, -num) else: heapq.heappush(self.min_heap, num) # Balance the heaps if necessary if len(self.max_heap) > len(self.min_heap) + 1: heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) elif len(self.min_heap) > len(self.max_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) def find_median(self): if len(self.max_heap) == len(self.min_heap): return (-self.max_heap[0] + self.min_heap[0]) / 2.0 else: return -self.max_heap[0] # Usage: two_heaps = TwoHeaps() two_heaps.add_num(1) two_heaps.add_num(2) median = two_heaps.find_median() print("Median:", median)

JS

 class TwoHeaps { constructor() { this.minHeap = []; // Right heap to store larger half this.maxHeap = []; // Left heap to store smaller half } addNumber(num) { if (this.maxHeap.length === 0 || num <= -this.maxHeap[0]) { this.maxHeap.push(-num); } else { this.minHeap.push(num); } // Balance the heaps if necessary if (this.maxHeap.length > this.minHeap.length + 1) { this.minHeap.push(-this.maxHeap.shift()); } else if (this.minHeap.length > this.maxHeap.length) { this.maxHeap.push(-this.minHeap.shift()); } } findMedian() { if (this.maxHeap.length === this.minHeap.length) { return (-this.maxHeap[0] + this.minHeap[0]) / 2; } else { return -this.maxHeap[0]; } } } // Usage: const twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); const median = twoHeaps.findMedian(); console.log("Median:", median);

자바

 import java.util.*; class TwoHeaps { private PriorityQueue<Integer> minHeap; // Right heap to store larger half private PriorityQueue<Integer> maxHeap; // Left heap to store smaller half public TwoHeaps() { minHeap = new PriorityQueue<>(); maxHeap = new PriorityQueue<>(Collections.reverseOrder()); } public void addNumber(int num) { if (maxHeap.isEmpty() || num <= -maxHeap.peek()) { maxHeap.offer(-num); } else { minHeap.offer(num); } // Balance the heaps if necessary if (maxHeap.size() > minHeap.size() + 1) { minHeap.offer(-maxHeap.poll()); } else if (minHeap.size() > maxHeap.size()) { maxHeap.offer(-minHeap.poll()); } } public double findMedian() { if (maxHeap.size() == minHeap.size()) { return (-maxHeap.peek() + minHeap.peek()) / 2.0; } else { return -maxHeap.peek(); } } } // Usage: TwoHeaps twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); double median = twoHeaps.findMedian(); System.out.println("Median: " + median);

7. 단조로운 스택

단조적(Monotonic) - (함수나 양의) 변화가 전혀 줄어들지 않거나 증가하지 않는 방식으로 변하는 것입니다.

단조 스택은 비증가 또는 비감소 순서로 요소 스택을 유지하며 배열에서 가장 가까운 작은/큰 요소를 찾는 데 자주 사용됩니다. 특정 문제를 최적화하기 위한 강력한 도구입니다.

순서는 엄격합니다. 스택의 맨 위에 있는 요소보다 작거나 큰 요소를 만날 때마다 추가하려는 요소가 가장 작은(또는 가장 큰) 요소가 될 때까지 단조 스택에서 팝해야 합니다. 그들을.

주요 지표:

• 증가하지 않거나 감소하지 않는 순서로 요소를 유지해야 합니다.
• 문제는 가장 가까운 작거나 큰 요소를 찾는 것과 관련이 있습니다.
• 순서를 유지하면서 스택 기반 작업을 최적화하려고 합니다.

템플릿 코드:

파이썬

 def monotonic_stack(items): stack = [] for item in items: # Adjust the condition for comparisons to suit your needs while stack and stack[-1] <= item: stack.pop() # Do something with the popped item here stack.append(item)

JS

 function monotonicStack(items) { const stack = []; for (const item of items) { // Adjust the condition for comparisons to suit your needs while (stack.length > 0 && stack[stack.length - 1] <= item) { stack.pop(); // Do something with the popped item here } stack.push(item); } return stack; }

자바

 import java.util.*; public static int[] monotonicStack(int[] items) { Deque<Integer> stack = new ArrayDeque<>(); for (int item : items) { // Adjust the condition for comparisons to suit your needs while (!stack.isEmpty() && stack.peekLast() <= item) { stack.pollLast(); // Do something with the popped item here } stack.offerLast(item); } int[] result = new int[stack.size()]; int i = stack.size() - 1; while (!stack.isEmpty()) { result[i--] = stack.pollLast(); } return result; }

8. 깊이 우선 검색

DFS 또는 깊이 우선 검색은 역 추적하기 전에 분기를 따라 최대한 깊이 탐색하는 순회 방법입니다. 이는 트리 및 그래프와 관련된 문제, 특히 순회 및 검색 작업에 널리 적용됩니다.

트리에서 DFS를 수행하려면 루트에서 시작해야 합니다. 그런 다음 아래 단계를 따르십시오.

1. 일반적으로 왼쪽 에서 오른쪽 으로 하위 노드를 방문하여 현재 노드를 탐색합니다.
2. DFS 프로세스를 각 하위 노드에 반복적으로 적용하여 트리에 더 깊이 들어갑니다.
3. 모든 하위 노드를 방문한 후 상위 노드로 역추적합니다 .
4. 트리의 모든 노드를 방문할 때까지 현재 노드의 방문하지 않은 각 하위 항목에 대해 1-3단계를 반복합니다 .

그래프에서 DFS와의 차이점: 트리 DFS와 그래프 DFS의 주요 차이점은 주기가 있다는 것입니다. 트리에는 정의상 순환이 없으므로 트리 DFS는 각 노드가 정확히 한 번만 방문하도록 보장하고 전체 트리를 탐색할 때 자연스럽게 종료됩니다. 대조적으로, 그래프 DFS는 그래프 내의 순환 구조를 처리하기 위해 추가 조치를 통합해야 합니다. 한 주기에서 노드를 무기한 재방문하는 것을 방지하려면 그래프 DFS에는 방문한 노드를 표시 하고 역추적을 적절하게 처리하는 것과 같은 메커니즘이 필요합니다. 이러한 차이로 인해 사이클이 있을 때 무한 루프가 발생할 가능성이 있기 때문에 그래프 DFS가 트리 DFS보다 더 복잡해집니다.

주요 지표:

• 트리 구조를 다루고 있으며 특정 순회 순서를 탐색해야 합니다.
• 문제는 경로 찾기, 깊이 계산 또는 선순/순서/후순 순회 수행과 관련됩니다.
• 두 노드 사이에 경로가 존재하는지 확인하려고 합니다.

템플릿 코드:

파이썬

 def dfs(root, target): if root is None: # Base case: Check if the current node is None return None if root.val == target: # Base case: Check if the current node value matches the target return root left = dfs(root.left, target) # Recursively search the left subtree if left is not None: # If the target is found in the left subtree, return the result return left return dfs(root.right, target) # Recursively search the right subtree

JS

 function dfs(root, target) { if (root === null) { // Base case: Check if the current node is null return null; } if (root.val === target) { // Base case: Check if the current node value matches the target return root; } let left = dfs(root.left, target); // Recursively search the left subtree if (left !== null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

자바

 public TreeNode dfs(TreeNode root, int target) { if (root == null) { // Base case: Check if the current node is null return null; } if (root.val == target) { // Base case: Check if the current node value matches the target return root; } TreeNode left = dfs(root.left, target); // Recursively search the left subtree if (left != null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

9. 너비 우선 검색

BFS는 다음 레벨로 이동하기 전에 현재 깊이의 모든 노드를 탐색하는 트리 및 그래프의 순회 기술입니다.

트리에서 BFS를 수행하려면 루트에서 시작해야 합니다. 그런 다음 아래 단계를 따르십시오.

1. 방문할 노드를 추적하기 위해 빈 대기열 데이터 구조를 초기화합니다.

2. 루트 노드를 대기열에 넣습니다 .

3. 대기열이 빌 때까지 루프를 입력합니다.

   1. 대기열 앞쪽에 있는 노드를 대기열에서 제거합니다.
   2. 대기열에서 제거된 노드를 처리합니다(예: 노드를 방문하거나 일부 작업을 수행).
   3. 노드의 모든 자식(있는 경우)을 대기열에 넣습니다.

4. 대기열이 빌 때까지 3a-3c단계를 반복합니다 .

5. BFS 순회는 트리의 모든 노드를 왼쪽에서 오른쪽으로 수준별 방식으로 방문하면 완료됩니다.

본질적으로 트리의 BFS는 루트에서 시작하여 다음 레벨로 진행하기 전에 자식 노드로 이동하여 레벨별로 노드를 탐색합니다. 이렇게 하면 다음 레벨로 이동하기 전에 각 레벨의 노드를 방문할 수 있으므로 비가중 트리에서 최단 경로를 찾거나 레벨별로 트리 레벨을 탐색하는 등의 작업에 특히 유용합니다.

그래프에서 BFS와의 차이점: DFS와 유사하게 Graph BFS는 노드 간 주기 및 다중 경로의 존재에 적응합니다. 방문 노드 표시 및 특수 종료 조건과 같은 메커니즘을 사용하여 그래프 내의 복잡한 관계 네트워크를 효율적으로 탐색합니다.

주요 지표:

• 레벨별로 트리 레벨을 탐색해야 합니다.
• 문제는 비가중 그래프에서 최단 경로를 찾는 것과 관련이 있습니다.
• 너비 우선 방식으로 트리나 그래프를 탐색하려고 합니다.

템플릿 코드:

파이썬

 from collections import deque def bfs(root): # Create a queue and initialize it with the root node queue = deque([root]) # Perform breadth-first search until the queue is empty while len(queue) > 0: # Dequeue the front node from the queue node = queue.popleft() # Process the current node for child in node.children: if is_goal(child): # If the goal condition is satisfied, return the child node return FOUND(child) # Enqueue the child node to explore it in the next iterations queue.append(child) # Return NOT_FOUND if the goal is not reached return NOT_FOUND

JS

 function bfs(root) { const queue = []; // Create a queue and initialize it with the root node queue.push(root); while (queue.length > 0) { // Perform breadth-first search until the queue is empty const node = queue.shift(); // Dequeue the front node from the queue for (const child of node.children) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return `FOUND ${child}`; } queue.push(child); // Enqueue the child node to explore it in the next iterations } } return 'NOT_FOUND'; // Return NOT_FOUND if the goal is not reached }

자바

 import java.util.LinkedList; import java.util.Queue; public String bfs(Node root) { Queue<Node> queue = new LinkedList<>(); // Create a queue and initialize it with the root node queue.offer(root); while (!queue.isEmpty()) { // Perform breadth-first search until the queue is empty Node node = queue.poll(); // Dequeue the front node from the queue for (Node child : node.getChildren()) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return "FOUND(child)"; } queue.offer(child); // Enqueue the child node to explore it in the next iterations } } return "NOT_FOUND"; // Return NOT_FOUND if the goal is not reached }

10. Union Find(Disjoint-Set 유니온)

DSU(Disjoint Set Union) 라고도 알려진 Union-Find 데이터 구조는 서로소 집합 또는 연결된 구성 요소와 관련된 문제를 효율적으로 관리하고 해결하는 데 사용됩니다. 집합을 병합하고(union) 요소가 속한 집합을 결정하는(찾기) 작업을 제공합니다. Union-Find는 일반적으로 Kruskal의 최소 스패닝 트리 및 그래프의 순환 감지와 같은 알고리즘에 사용됩니다.

Union Find는 다음과 같이 구현됩니다.

1. 초기화: 각각 별도의 분리된 집합으로 간주되는 요소 컬렉션으로 시작합니다. 각 세트에 고유한 대표(종종 요소 자체)를 할당합니다.
2. 합집합 연산: 두 세트를 병합하려면 합집합 연산을 수행합니다. 한 세트의 대표를 선택하고(종종 순위나 크기와 같은 일부 기준을 기반으로 함) 이를 다른 세트 대표의 상위로 만듭니다. 이는 두 세트를 효과적으로 연결합니다.
3. 찾기 작업: 요소가 속한 집합을 결정해야 할 경우 찾기 작업을 사용하세요. 문제의 요소부터 시작하여 트리를 위쪽으로 탐색하여 해당 집합의 루트 노드(대표)를 찾습니다. 경로를 따라 있는 요소가 루트를 직접 가리키도록 함으로써 향후 찾기 작업을 최적화하기 위해 경로 압축 기술을 여기에 적용할 수 있습니다.
4. 주기 감지: Union-Find는 그래프에서 주기를 감지하는 데 자주 사용됩니다. 합집합 연산을 수행할 때 두 요소가 모두 동일한 세트에 속하면(즉, 동일한 대표를 가짐) 노드 사이에 간선을 추가하면 그래프에 순환이 생성된다는 것을 나타냅니다.
5. 최적화: 순위별 통합 및 경로 압축과 같은 Union-Find 작업의 효율성을 향상시키기 위해 다양한 최적화 기술을 적용할 수 있습니다.

템플릿 코드:

파이썬

 class UnionFind: def __init__(self): self.id = {} def find(self, x): y = self.id.get(x, x) if y != x: self.id[x] = y = self.find(y) return y def union(self, x, y): self.id[self.find(x)] = self.find(y)

JS

 class UnionFind { constructor() { this.id = {}; } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @returns The root parent of the element. */ find(x) { let y = this.id[x] || x; if (y !== x) { this.id[x] = y = this.find(y); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ union(x, y) { this.id[this.find(x)] = this.find(y); } }

자바

 import java.util.*; class UnionFind { private Map<String, String> id; public UnionFind() { id = new HashMap<>(); } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @return The root parent of the element. */ public String find(String x) { String y = id.getOrDefault(x, x); if (!y.equals(x)) { id.put(x, find(y)); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ public void union(String x, String y) { id.put(find(x), find(y)); } }

11. 토폴로지 정렬

방향성 비순환 그래프(DAG)는 방향성 순환이 없는 방향성 그래프입니다.

토폴로지 정렬은 방향성 비순환 그래프( DAG )의 노드를 선형 순서로 배열하는 알고리즘으로, 각 노드는 후속 노드 앞에 표시됩니다. 이는 종속성 예약, 코드 컴파일, 다양한 애플리케이션의 작업 우선 순위 분석과 같은 작업에 매우 중요합니다.

다음은 토폴로지 정렬의 단계별 분석입니다.

1. 초기화: 종속성이 있는 작업이나 노드를 나타내는 방향성 비순환 그래프( DAG )로 시작합니다. 정렬된 노드를 보유하기 위해 대기열을 초기화합니다.

2. 차수 계산: 그래프의 각 노드에 대한 차수(들어오는 모서리 수)를 계산합니다. 진입차수가 0인 노드는 종속성이 없으며 위상 정렬의 시작점으로 적합합니다.

3. 초기 대기열 채우기: 진입 차수가 0인 모든 노드를 대기열에 넣습니다. 이러한 노드를 먼저 처리할 수 있습니다.

4. 토폴로지 정렬 루프: 큐가 비어 있지 않은 동안 다음 단계를 수행하십시오.

   1. 대기열의 앞쪽에서 노드를 제거합니다.
   2. 노드를 처리합니다(예: 정렬된 목록에 추가).
   3. 각 노드의 이웃(이 노드가 가리키는 노드)에 대해 해당 차수를 1씩 감소시킵니다.
   4. 감소의 결과로 이웃의 차수가 0이 되면 이를 대기열에 넣습니다.

5. 완료: 토폴로지 정렬 루프가 완료되면 큐는 비어 있고 정렬된 목록에는 유효한 토폴로지 순서로 모든 노드가 포함됩니다.

6. 사이클 감지: 토폴로지 정렬 프로세스 중 어느 시점에서든 큐에 0차수가 남아 있는 노드가 없으면 그래프에 사이클이 있음을 나타내므로 토폴로지 정렬이 불가능해집니다.

토폴로지 정렬의 결과는 종속성을 존중하는 노드의 선형 순서이므로 작업을 예약하거나 다양한 애플리케이션에서 실행 순서를 분석하는 데 적합합니다.

주요 지표:

• 문제는 종속성이 있는 작업을 예약하거나 주문하는 것과 관련이 있습니다.
• 방향성 비순환 그래프(DAG)를 사용하고 있습니다.
• 작업은 종속성을 준수하면서 특정 순서로 실행되어야 합니다.

템플릿 코드:

파이썬

 from collections import deque def find_indegree(graph): # Calculate the indegree of each node in the graph indegree = {node: 0 for node in graph} for node in graph: for neighbor in graph[node]: indegree[neighbor] += 1 return indegree def topological_sort(graph): result = [] queue = deque() indegree = find_indegree(graph) # Add nodes with 0 indegree to the queue for node in indegree: if indegree[node] == 0: queue.append(node) while queue: node = queue.popleft() result.append(node) # Update the indegree of neighboring nodes for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) # If all nodes are visited, return the result if len(graph) == len(result): return result else: return None

JS

 /** * Finds the indegree of each node in the graph. * @param {object} graph - The input graph. * @returns {object} - The indegree of each node. */ function findIndegree(graph) { const indegree = {}; for (const node in graph) { indegree[node] = 0; } for (const node in graph) { for (const neighbor of graph[node]) { indegree[neighbor]++; } } return indegree; } /** * Performs topological sorting on the given graph. * @param {object} graph - The input graph. * @returns {array|null} - The sorted nodes in topological order or null if a cycle is detected. */ function topologicalSort(graph) { const result = []; const queue = []; const indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (const node in indegree) { if (indegree[node] === 0) { queue.push(node); } } while (queue.length > 0) { const node = queue.shift(); result.push(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (const neighbor of graph[node]) { indegree[neighbor]--; if (indegree[neighbor] === 0) { queue.push(neighbor); } } } // Check if all nodes have been visited (no cycles) if (Object.keys(graph).length === result.length) { return result; } else { return null; } }

자바

 import java.util.*; /** * Finds the indegree of each node in the graph. * @param graph - The input graph. * @return The indegree of each node. */ public Map<String, Integer> findIndegree(Map<String, List<String>> graph) { Map<String, Integer> indegree = new HashMap<>(); for (String node : graph.keySet()) { indegree.put(node, 0); } for (String node : graph.keySet()) { for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.getOrDefault(neighbor, 0) + 1); } } return indegree; } /** * Performs topological sorting on the given graph. * @param graph - The input graph. * @return The sorted nodes in topological order or null if a cycle is detected. */ public List<String> topologicalSort(Map<String, List<String>> graph) { List<String> result = new ArrayList<>(); Queue<String> queue = new LinkedList<>(); Map<String, Integer> indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (String node : indegree.keySet()) { if (indegree.get(node) == 0) { queue.offer(node); } } while (!queue.isEmpty()) { String node = queue.poll(); result.add(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.get(neighbor) - 1); if (indegree.get(neighbor) == 0) { queue.offer(neighbor); } } } // Check if all nodes have been visited (no cycles) if (graph.size() == result.size()) { return result; } else { return null; } }

12. 시도(접두사-트리)

Trie 는 효율적인 문자열 일치 및 단어 저장에 사용되는 트리형 데이터 구조입니다. 공통 접두사가 있는 문자열을 저장하고 검색해야 하는 문제에 탁월합니다.

Trie를 구현하는 방법은 다음과 같습니다.

1. 초기화: 일반적으로 연관된 문자가 없는 루트 노드로 구성된 빈 Trie로 시작합니다.

2. 삽입: Trie에 단어를 삽입하려면 루트 노드에서 시작하여 한 번에 한 문자씩 트리 아래로 이동합니다. 단어의 각 문자에 대해 다음을 수행합니다.

   1. 해당 문자를 가진 하위 노드가 현재 노드 아래에 존재하는지 확인하십시오.
   2. 그렇다면 하위 노드로 이동합니다.
   3. 그렇지 않은 경우 해당 캐릭터로 새 하위 노드를 만들고 해당 노드로 이동합니다.

3. 단어 완성: Trie에 단어가 존재하는지 확인하려면 삽입과 유사한 방식으로 단어를 순회합니다. 단어의 각 문자가 현재 노드의 하위 노드에 해당하는지 확인하십시오. 순회가 단어 끝에 도달하고 마지막 문자 노드에 유효한 끝 표시(예: 부울 플래그)가 있는 경우 해당 단어는 Trie에 존재합니다.

4. 접두어 검색: Trie는 접두어 검색에 탁월합니다. 주어진 접두사가 있는 모든 단어를 찾으려면 루트 노드에서 순회를 시작하고 접두사의 문자를 따라 트리 아래로 이동합니다. 접두사의 마지막 문자에 도달하면 해당 노드에서 깊이 우선 검색(DFS)을 수행하여 동일한 접두사를 공유하는 모든 단어를 찾을 수 있습니다.

5. 삭제: Trie에서 단어를 삭제하려면 해당 단어를 검색하세요. 단어 끝에 도달하면 끝 표시를 제거합니다(있는 경우). 노드에 다른 하위 노드가 없으면 단어를 나타내는 Trie의 전체 분기를 안전하게 제거할 수 있습니다.

특히 대규모 어휘의 경우 시도는 메모리 집약적일 수 있습니다. 메모리를 최적화하기 위해 압축(예: 각 노드의 문자 배열 대신 맵 사용) 및 정리(후손이 없는 노드 제거)와 같은 기술을 적용할 수 있습니다.

시도는 효율적인 문자열 일치, 자동 완성 제안, 맞춤법 검사기 및 공통 접두사가 있는 단어 색인화에 특히 유용합니다. 트리형 구조에서 공유 접두사가 있는 단어나 문자열을 저장하고 검색하는 빠르고 공간 효율적인 방법을 제공합니다.

주요 지표:

• 문자열을 다루고 있으며 효율적인 문자열 일치가 필요합니다.
• 문제에는 자동 완성 제안, 맞춤법 검사기 또는 공통 접두사가 있는 단어 검색이 포함됩니다.
• 단어를 효율적으로 저장하고 검색하고 싶습니다.

템플릿 코드:

파이썬

 class TrieNode: def __init__(self, value): self.value = value self.children = {} def insert(self, s, idx): # idx: index of the current character in s if idx != len(s): self.children.setdefault(s[idx], TrieNode(s[idx])) self.children.get(s[idx]).insert(s, idx + 1)

JS

 class TrieNode { constructor(value) { this.value = value; this.children = {}; } insert(s, idx) { // idx: index of the current character in s if (idx !== s.length) { if (!this.children[s[idx]]) { this.children[s[idx]] = new TrieNode(s[idx]); } this.children[s[idx]].insert(s, idx + 1); } } }

자바

 import java.util.*; class TrieNode { char value; Map<Character, TrieNode> children; TrieNode(char value) { this.value = value; this.children = new HashMap<>(); } void insert(String s, int idx) { // idx: index of the current character in s if (idx != s.length()) { char c = s.charAt(idx); if (!children.containsKey(c)) { children.put(c, new TrieNode(c)); } children.get(c).insert(s, idx + 1); } } }

13. 동적 프로그래밍

동적 프로그래밍은 컴퓨터 과학 및 수학에서 광범위하고 복잡한 문제를 효율적으로 해결하는 데 사용되는 강력한 문제 해결 기술입니다. 문제를 더 간단한 하위 문제로 나눌 수 있고 이러한 하위 문제에 대한 솔루션을 결합하여 전체 문제를 해결할 수 있는 경우 특히 유용합니다.

주요 특징과 작동 방식은 다음과 같습니다.

최적의 하부 구조:

• 이 특성은 더 큰 문제에 대한 최적의 솔루션이 더 작은 하위 문제에 대한 최적의 솔루션으로 구성될 수 있다는 특성을 나타냅니다.
• 즉, DP 문제는 문제에 대한 최적의 솔루션이 해당 하위 문제의 최적 솔루션에 의존하는 재귀적 구조를 나타냅니다.
• 예를 들어, 그래프의 두 점 사이의 최단 경로를 찾는 경우 두 중간 점 사이의 최단 경로도 최적이어야 합니다.

겹치는 하위 문제:

• 계산 중에 동일한 하위 문제를 여러 번 해결하면 중복되는 하위 문제가 발생하여 작업이 중복됩니다.
• 동적 프로그래밍은 하위 문제에 대한 솔루션을 데이터 구조(종종 테이블 또는 메모 배열)에 저장하여 재계산을 방지함으로써 이 문제를 해결하는 것을 목표로 합니다.
• 하위 문제 솔루션을 저장하고 재사용하면 알고리즘의 시간 복잡성이 크게 줄어듭니다.

동적 프로그래밍 작동 방식:

1. 하위 문제 식별: DP를 사용하여 문제를 해결하는 첫 번째 단계는 하위 문제를 식별하는 것입니다. 문제를 해결되면 주요 문제 해결에 기여할 수 있는 더 작고 관리 가능한 하위 문제로 세분화합니다.
2. 재귀적 솔루션: 더 작은 하위 문제에 대한 솔루션 측면에서 더 큰 문제의 솔루션을 표현하는 재귀 솔루션을 개발합니다. 이 재귀적 공식은 최적의 하위 구조를 포착합니다.
3. 메모 또는 표 작성: 중복되는 하위 문제를 해결하기 위해 다음 두 가지 일반적인 기술 중에서 선택할 수 있습니다.
   • 메모: 하위 문제의 결과를 계산할 때 데이터 구조(일반적으로 배열 또는 해시 테이블)에 저장합니다. 하위 문제가 다시 발생하면 다시 계산하는 대신 스토리지에서 솔루션을 검색하세요. 이는 하향식 접근 방식이라고도 합니다.
   • 표 작성: 상향식 방식으로 하위 문제에 대한 솔루션을 저장하기 위해 표(종종 2D 배열)를 만듭니다. 가장 작은 하위 문제를 해결하는 것부터 시작하여 점진적으로 주요 문제를 해결하세요.
4. 최적해: 모든 하위 문제가 해결되면 문제의 재귀 구조에 따라 하위 문제의 솔루션을 결합하여 주요 문제에 대한 솔루션을 얻을 수 있습니다.

동적 프로그래밍은 그래프에서 최단 경로 찾기, 자원 할당 최적화, 조합 계산, 배낭 문제 해결 등을 포함하여 광범위한 문제에 적용됩니다. 복잡한 문제를 더 간단한 부분으로 나누고 중복 계산을 피함으로써 솔루션을 최적화하는 능력은 알고리즘 설계 및 최적화의 기본 기술이 됩니다.

중요 개념: 상향식 접근 방식, 하향식, 메모, 표 작성

주요 지표:

• 문제는 더 작은 중첩 하위 문제로 나눌 수 있습니다.
• 하위 문제에 대한 솔루션을 저장하고 재사용하여 최적화할 필요가 있습니다.
• 최적화 또는 계산과 관련된 문제를 해결하고 싶습니다.

템플릿 코드:

하향식 메모용 템플릿은 동적 프로그래밍을 구현하는 여러 방법 중 하나입니다.

파이썬

 def top_down_memo(arr): def dp(state): # Base case(s): Define your own base case(s) for the problem if base_case: return 0 # Check if the state has already been memoized if state in memo: return memo[state] # Calculate the result using recurrence relation and memoize it result = recurrence_relation(state) memo[state] = result return result memo = {} # Memoization table to store calculated results return dp(initial_state)

JS

 function topDownMemo(arr) { function dp(state) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.has(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it const result = recurrenceRelation(state); memo.set(state, result); return result; } const memo = new Map(); // Memoization map to store calculated results return dp(initialState); }

자바

 import java.util.HashMap; import java.util.Map; public int topDownMemo(int[] arr) { Map<StateType, Integer> memo = new HashMap<>(); // Memoization map to store calculated results return dp(initialState, memo); } private int dp(StateType state, Map<StateType, Integer> memo) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.containsKey(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it int result = recurrenceRelation(state); memo.put(state, result); return result; }

14. 역추적

역추적은 다양한 가능성을 시도하고 해결책이 나오지 않으면 취소하여 문제를 점진적으로 해결하는 일반적인 알고리즘 기술입니다. 철저한 검색이 필요할 때 사용됩니다.

역추적 작동 방식에 대한 자세한 내용은 다음과 같습니다.

1. 문제 공간 탐색: 역추적은 한 번에 하나씩 솔루션을 점진적으로 구축하여 문제 공간을 탐색합니다. 각 단계에서 결정을 내리고 앞으로 나아갑니다.
2. 재귀적 구조: 역추적에는 재귀가 포함되는 경우가 많습니다. 초기 부분 솔루션으로 시작하여 이를 확장할 수 있는 모든 가능한 방법을 탐색합니다. 이 프로세스는 완전한 솔루션을 찾거나 유효한 솔루션이 존재하지 않는다는 것이 명백해질 때까지 반복적으로 계속됩니다.
3. 결정 지점: 각 단계에는 알고리즘이 사용 가능한 옵션 중에서 선택해야 하는 결정 지점이 있습니다. 이러한 선택은 탐색 프로세스의 분기로 이어집니다.
4. 솔루션 검증: 선택 후 알고리즘은 현재 부분 솔루션이 유효한지 확인합니다. 유효하면 알고리즘은 다음 단계로 진행됩니다. 그렇지 않은 경우 이전 선택을 취소하고 다른 옵션을 탐색하여 되돌아갑니다.
5. 종료 조건: 다음 두 조건 중 하나가 충족될 때까지 역추적이 계속됩니다.
   • 유효한 솔루션이 발견되면 알고리즘이 중지되고 솔루션이 반환됩니다.
   • 유효한 솔루션이 존재하지 않는다고 판단되면 알고리즘은 이전 결정 지점으로 역추적하여 다양한 옵션을 탐색합니다.
6. 가지치기: 검색을 최적화하기 위해 역추적에는 가지치기 전략이 포함되는 경우가 많습니다. 가지치기에는 유효하지 않은 솔루션으로 이어지는 경로 탐색을 방지하여 검색 공간을 크게 줄이는 작업이 포함됩니다.

역추적의 응용:

역추적은 다음을 포함한 다양한 문제 영역에서 사용됩니다.

• Sudoku 및 N-Queens와 같은 퍼즐을 해결합니다.
• 순열 및 조합 생성.
• 그래프와 트리에서 경로를 검색합니다.
• 제약조건 만족 문제(예: 여행하는 외판원 문제)
• 게임 플레이 알고리즘(예: 체스 AI)

주요 지표:

• 문제는 여러 가능성을 점진적으로 탐색하는 것과 관련이 있습니다.
• 다양한 옵션을 시도해야 하는 결정 지점이나 제약 조건이 있습니다.
• 철저한 검색을 통해 가능한 모든 솔루션을 찾거나 특정 조건을 충족해야 합니다.

템플릿 코드:

파이썬

 def backtrack(curr, OTHER_ARGUMENTS...): if BASE_CASE: # Modify the answer according to the problem's requirements return ans = 0 for ITERATE_OVER_INPUT: # Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS...) # Undo the modification of the current state (backtrack) return ans

JS

 function backtrack(curr, ...OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } let ans = 0; for (let i = 0; i < ITERATE_OVER_INPUT.length; i++) { const item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, ...OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

자바

 public int backtrack(StateType curr, OtherArgumentType... OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } int ans = 0; for (int i = 0; i < ITERATE_OVER_INPUT.length; i++) { ItemType item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

15. 병합 간격

간격 병합에는 겹치거나 인접한 간격을 통합 세트로 결합하는 작업이 포함되며, 시간 간격 또는 일정과 관련된 문제에 자주 사용됩니다. 간격 기반 작업을 단순화합니다.

다음은 병합 간격이 작동하는 방식을 자세히 살펴보겠습니다.

1. 간격 표현: 간격은 일반적으로 시작점 과 끝점 의 쌍으로 표시됩니다(예: [start, end] ).
2. 정렬: 간격을 효율적으로 병합하려면 시작점을 기준으로 간격을 정렬하는 것부터 시작하세요. 이렇게 하면 정렬된 목록에서 겹치거나 인접한 간격이 인접해 있습니다.
3. 병합 프로세스: 병합된 간격을 보관하기 위해 빈 목록을 초기화합니다. 그런 다음 정렬된 간격을 하나씩 반복합니다.
   • 현재 간격이 이전 간격과 겹치지 않으면 병합된 간격 목록에 추가합니다.
   • 겹치는 부분이 있는 경우 현재 및 이전 간격을 모두 포함하도록 이전 병합 간격의 끝점을 업데이트하여 효과적으로 병합합니다.
4. 완료: 모든 간격을 처리한 후 병합된 간격 목록에는 겹치지 않는 통합 간격이 포함됩니다.

병합 간격의 적용:

병합 간격은 일반적으로 다음과 같은 경우에 사용됩니다.

• 일정 관리 및 시간 관리 애플리케이션.
• 캘린더 시스템에서 중복 이벤트 감지.
• 데이터베이스 쿼리와 같은 간격 기반 데이터 분석.
• 자원 할당 및 회의 일정과 관련된 문제를 해결합니다.

이 기술은 겹치는 간격을 병합하여 간격 기반 작업을 단순화하고 다양한 애플리케이션에서 효율성을 향상시킵니다.

주요 지표:

• 간격 또는 시간 기반 데이터를 다루고 있습니다.
• 문제는 겹치거나 인접한 간격을 병합하는 것과 관련됩니다.
• 간격 기반 작업을 단순화하거나 이벤트 일정을 최적화하려고 합니다.

템플릿 코드:

파이썬

 def merge_intervals(intervals): # 1. Sort the intervals based on their start values. intervals.sort(key=lambda x: x[0]) # 2. Initialize an empty list to store merged intervals. merged_intervals = [] # 3. Iterate through the sorted intervals. for interval in intervals: # 4. If the merged_intervals list is empty or the current interval does not overlap with the last merged interval: if not merged_intervals or interval[0] > merged_intervals[-1][1]: merged_intervals.append(interval) else: # 5. If the current interval overlaps with the last merged interval, merge them. merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1]) # 6. Return the merged_intervals list. return merged_intervals

JS

 function mergeIntervals(intervals) { // 1. Sort the intervals based on their start values. intervals.sort((a, b) => a[0] - b[0]); // 2. Initialize an empty array to store merged intervals. const mergedIntervals = []; // 3. Iterate through the sorted intervals. for (const interval of intervals) { // 4. If the mergedIntervals array is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.length === 0 || interval[0] > mergedIntervals[mergedIntervals.length - 1][1]) { mergedIntervals.push(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals[mergedIntervals.length - 1][1] = Math.max(mergedIntervals[mergedIntervals.length - 1][1], interval[1]); } } // 6. Return the mergedIntervals array. return mergedIntervals; }

자바

 public class MergeIntervals { public int[][] merge(int[][] intervals) { // 1. Sort the intervals based on their start values. Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 2. Create a list to store merged intervals. List<int[]> mergedIntervals = new ArrayList<>(); // 3. Iterate through the sorted intervals. for (int[] interval : intervals) { // 4. If the mergedIntervals list is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.isEmpty() || interval[0] > mergedIntervals.get(mergedIntervals.size() - 1)[1]) { mergedIntervals.add(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals.get(mergedIntervals.size() - 1)[1] = Math.max(mergedIntervals.get(mergedIntervals.size() - 1)[1], interval[1]); } } // 6. Convert the list to an array and return it. return mergedIntervals.toArray(new int[mergedIntervals.size()][]); } }

더 자세히 알고 싶으십니까?

이러한 패턴에 대해 자세히 알아보고 다음 코딩 인터뷰에서 이를 보다 효과적으로 구현할 수 있는 방법을 알아보려면 지금 techinterviews.io를 확인하세요! 우리는 데이터 구조 , 알고리즘 , 행동 인터뷰 , 심지어 급여 협상 과 같은 주제를 다루는 다음 코딩 인터뷰를 준비할 수 있도록 포괄적인 커리큘럼을 제공합니다. 연습할 수 있는 코딩 작업 공간도 내장되어 있습니다.

오늘 $30 할인된 프로모션 코드 TECH30을 사용하여 코딩 인터뷰 준비를 강화하세요!