[코딩 면접을 위해 꼭 알아둬야 하는 알고리즘 패턴 8가지와 문제 유형] 코딩 면접에 자주 출제되는 문제를 푸는데 도움 되는 알고리즘 패턴 14가지 중 6가지 소개합니다. 아티클에 나오지는 않았지만 자주 출제되었던 문제에 사용되는 2가지 패턴도 함께 공유합니다. 1️⃣ Breadth-First-Search Queue를 사용해서 트리나 그래프 전체에 있는 노드를 탐색하는 알고리즘입니다. 트리 레벨 탐색에 자주 사용되는 패턴입니다. 트리 너비 우선 탐색 알고리즘 문제 유형 * Binary tree level order traversal * Zig-zag traversal 📌 너비 우선 탐색 알고리즘의 경우 코드가 비슷합니다. 문제에 따라 큰 뼈대에서 조금씩 변형하는 경우가 많아서 트리와 크래프 BFS 코드를 어떻게 작성하는지 알아두면 문제 풀때 알고리즘 코드 짜는 것이 훨씬 수월할 수 있습니다. 📌 그래프 너비 우선 탐색 알고리즘 파이썬 코드 https://www.educative.io/answers/how-to-implement-a-breadth-first-search-in-python 📌 그래프 너비 우선 탐색 알고리즘 쉽게 설명해주는 영상 + 예시 문제 https://www.youtube.com/watch?v=tWVWeAqZ0WU&t=1787s 2️⃣ Depth-First-Search 깊이 우선 탐색은 recursion이나 stack을 사용해서 트리나 그레프를 탐색하는데 사용됩니다. 문제 접근 방식에따라 recursion 또는 stack을 사용합니다. 트리 깊이 우선 탐색 알고리즘 문제 유형 * Sum of path numbers * All paths for a sum 📌 깊이 우선 탐색 알고리즘의 경우 코드가 비슷합니다. 문제에 따라 큰 뼈대에서 조금씩 변형하는 경우가 많아서 트리와 크래프 DFS 코드를 어떻게 작성하는지 알아두면 문제 풀때 알고리즘 코드 짜는 것이 훨씬 수월할 수 있습니다. 📌 그래프 깊이 우선 탐색 알고리즘 파이썬 코드 https://www.educative.io/answers/how-to-implement-depth-first-search-in-python 📌 그래프 깊이 우선 탐색 알고리즘 쉽게 설명해주는 영상 + 예시 문제 https://www.youtube.com/watch?v=tWVWeAqZ0WU&t=1787s 3️⃣ Sliding Window 슬라이딩 윈도우 패턴은 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 요소를 이용합니다. 슬라이딩 윈도우 문제 유형 * Maximum sum subarray of size “K” * Longest substring with “K” distinct characters * String anagrams (애너그램) 4️⃣ Fast & Slow Pointers 두 포인터를 사용하는데, 한 포인트는 느리게 이동하며 나머지 한 포이트는 빠르게 이동하는 알고리즘입니다. 두 포인터는 정렬된 배열의 각 요소를 비교해야 하는 경우에 유용합니다 Fast & Slow Pointers 문제 유형 * 3Sum * 백스페이스가 들어간 스트링 비교하기 5️⃣ Merge Intervals Interval 중 시작과 끝이 겹치는 구간이 있는 것을 하나로 병합하는 알고리즘 패턴입니다. Merge Interval 알고리즘 * Intervals intersection * Maximum CPU load 6️⃣ Binary Search 오름차순으로 정렬된 리스트에서 특정 값을 효과적으로 찾을 때 사용되는 알고리즘입니다. 여기서 중요한 점은 "정렬된 리스트"에서 탐색한다는 것! 🚨아티클에 나오지 않았지만 자주 출체되는 알고리즘 패턴🚨 현재까지 실면접과 모의 면접 합해서 100 군대 넘게 본 것 같은데, 아티클에 소개된 BFS와 DFS 문제가 가장 많이 출제되었던 것 같습니다. 이 두가지 알고리즘이 그래프와 트리에 어떻게 사용되는지 잘 숙지하는 것도 중요하지만 다이나믹 프로그래밍과 백트래킹 문제도 자주 출제되었던 것 같습니다. 1️⃣ Dynamic Programming 다이나믹 프로그래밍 문제를 사용해야하는 문제 유형이 있는데, 패턴을 파악해도 코드로 쓰는 것이 어려운 경우가 많습니다. 📌 다이나믹 프로그래밍 알고리즘 공부 관련 글은 지난번 포스팅을 참고해 주세요. https://careerly.co.kr/comments/60463 2️⃣ Backtracking 모든 경우의 수를 전부 고려하는 알고리즘입니다. Combination을 모두 찾는 문제는 Backtracking을 사용해서 풀어야 하는 경우가 대부분이며, dynamic programming처럼 알고리즘의 효율성에 중점을 둔 패턴은 아닙니다. 📌 백트래킹 알고리즘을 아주 쉽게 설명해주는 영상 추천합니다. https://www.youtube.com/watch?v=DKCbsiDBN6c 🪴 함께 읽으면 좋은 글: [알고리즘 문제 풀기 공부하는 법] https://careerly.co.kr/comments/60668 [해외 취업 "이것" 하나로 준비하기 - 무료 템플릿] https://careerly.co.kr/comments/59046