꼬비.com

목표 - 재귀가 무엇이며, 어떻게 유용한지를 정의 - 재귀 함수(Recursive function) 작성의 두 가지 핵심 구성 요소를 이해 - Call Stack 이라는 것에 대한 학습 - Call Stack과 Recursive function 의 관계 재귀함수란 무엇인가? 재귀함수는 자기 자신을 호출하는 절차이다. Recursion이 사용되고 있는 곳 - JSON.parse / JSON.stringify - document.getElementById & DOM traversal algorithms - Object traversal (객체 순회) 재귀 함수 작성에서 두 가지 핵심 구성 요소 - 종료 조건 (재귀가 멈추는 시점을 정해줘야한다.) - 다른 입력값 (매번 다른 데이터를 가지고 함수를 호출해야 ..

function sameFrequency(a, b) { // good luck. Add any arguments you deem necessary. const dicA = {}; for (const digit of a.toString()) { dicA[digit] = dicA[digit] + 1 || 1; } for (const digit of b.toString()) { if (isNaN(dicA[digit]) || dicA[digit] < 0) return false; dicA[digit] = dicA[digit] - 1; if (dicA[digit] < 0) { return false; } } return true; } // Udemy Solution function sameFrequency(num..

Divide and Conquer (분할 정복) 알고리즘 주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리할 때 사용한다. Lenear Search (선형 탐색) Lenear Search 는 정렬된 자료를 왼쪽부터 오른쪽으로 차례대로 탐색하는 알고리즘이다. Binary Search (이진 탐색) Binary Search 는 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘이다. (단, 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다. Binary Search는 큰 데이터셋을 취해 작은 하위 데이터셋으로 분할하고 다른 부분은 무시한다. 이는 곧 Divide and Conquer (분할정복) 의 일종으로 볼 수 있다. 본 내용은 작성자가 (Udemy) JavaScri..

Sliding Window(슬라이딩 윈도우) 배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용하다. 전자는 중첩된 루프문으로 배열에 숫자가 백만개 있을 경우 1,000,000 * 1,000,000 번 반복해야 하는 문제가 있다. 후자의 경우 루프를 배열에 한 번만 적용하여 O(n)으로 해결할 수 있다. 이것이 슬라이딩 윈도우 function maxSubarraySum(arr, num) { if (arr.length < num) return null; let tempMaxNum = 0; let maxNum = 0; for (let idx = 0; idx < num; idx++) { tempMaxNum += arr[idx]; } // tem..

Multiple Pointers도 실제로 다중 포인터라고 불리지 않음. (공식 이름도 없음) 이 패턴은 인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 중간지점에서부터 시작 지점이나 끝 지점이나 양쪽 지점을 향해 이동시키는 것이다. 문제 1. 합계가 0인 첫번째 쌍을 찾는 함수를 구현하자. (문제 1은 양쪽 지점에서 시작하여 반대편 지점으로 이동하면서 해결하는 방법을 사용하였다.) // My Solution validAnagram("", ""); // true validAnagram("aaz", "zza"); // false validAnagram("anagram", "nagaram"); // true validAnagram("rat", "car"); // false) // false..

Frequency Counters 는 실제로 빈도 카운터라고 불리지 않음. (공식 이름도 없음) 이 패턴은 보통 js의 객체를 사용해서 다양한 값과 빈도를 수집한다. Tip : 가능한 중첩된 루프는 사용하지 않는 것이 좋다. 두 개의 루프가 두 개의 중첩된 개별 루프보다 훨씬 낫다. (n^2 < n) Frequency Counters는 보통 객체를 사용한다. 배열이나 문자열의 내용을 분석하여 비교할때는 두 개의 배열을 객체로 세분화하여 각 배열의 요소들을 분류한 다음 각 배열을 비교하는 것이 좋다. 둘 다 같은 결과를 내지만 시간복잡도 측면에서 봤을때는 후자가 훨씬 성능이 좋다. 전자는 for문 안에서 indexOf을 사용하여 O(n^2) 이 되지만, 후자는 for문을 3번 반복하여 3n. 즉 O(n) ..

개선하는 법 (문제를 해결하는 법) 1. Devise a plan for solving problems. (문제 해결을 위한 계획 수립) 2. Master common problem solving patterns. (일반적인 문제 해결 패턴 마스터) 문제 해결 패턴 종류 - Frequency Counter - Multiple Pointers - Sliding Window - Divide and Conquer - Dynamic Programming - Greedy Algorithms - Backtracking - ... 본 내용은 작성자가 (Udemy) JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 듣고 정리 및 메모한 내용입니다. 오역 및 오개념이 있을 수 있으니 바로잡기 위해 문제가 있는..

재구성(Refactoring) 할때 생각할 수 있는 질문 - 결과를 확인할 수 있는가? - 결과를 다른 방식으로 도출할 수 있는가? - 한눈에 보고 이해할 수 있는가? - 결과나 방법을 다른 문제해도 적용할 수 있는가? - 해결책의 성능을 향상시킬 수 있는가? - 재구성할 수 있는 다른 방법을 생각할 수 있는가? - 다른 사람들은 이 문제를 어떻게 해결하는지? 결과나 방법을 다른 문제해도 적용할 수 있는가? 문제를 해결함으로써 얻을 수 있는 큰 이점 중 하나는 직감을 발달시켜 다른 문제를 해결할 수 있는 직관력을 길러준다는 것이다. 따라서 해결책을 작성할 때마다 잠시 멈추고 이 해결책이나 이 문제가 이전에 접했던 다른 문제와의 유사점이 있는지 자문해 보는 것이 좋다. 해결책의 성능을 향상시킬 수 있는가?..

단위 검사는 더 작은 기능에 대해 무엇인가가 어떻게 작동해야 하는지 그 틀을 잡는 데 사용된다. 문제 해결 2단계 - 구체적 예시 보기 1단계 - 간단한 예시로 시작하기 (Start with Simple Examples) 2단계 - 더 복잡한 예시들로 진행하기 (Progress to More Complex Examples) 3단계 - 빈 값을 입력하면 어떻게 될지 생각해보기 (Explore Examples with Empty Inputs) 4단계 - 유효하지 않은 값을 입력하면 어떻게 될지 생각해보기 (Explore Examples with Invalid Inputs) 문제 해결 3단계 - 문제를 세분화하기 밟아야 할 단계들을 명확하게 작성해보자 (해결책의 기본적인 구성 요소만이라도) -> 코드를 실제로..

알고리즘의 핵심은 어떤 작업을 달성하기 위한 일련의 단계이다. 알고리즘 문제 향상 방법 1. 문제 해결을 위한 계획을 수립 -> 이는 기술적인 문제면서도 아니기도 하지만 문제에 접근하는 방법으로, 문제를 세분화하기 위한 전략에 더 가깝다. (방향을 잡기 위한 몇가지 단계) 2. 일반적인 문제 해결 패턴을 파악 -> 많은 알고리즘과 면접에서의 문제들을 여러 범주로 나눌 수 있는데 일부 범주를 식별할 수 있는 경우에는 코드에 수행할 수 있는 몇가지 단계를 통해 얻을 수 있는 알고리즘이나 과제를 해결하는데 도움이 될 몇가지 조합법을 파악하고 공부하는 것을 뜻한다. 문제 해결 순서? 1단계 - 문제를 이해하는 것 2단계 - 구체적인 예시를 경험해보는 것 3단계 - 문제를 세분화 하는 것 4단계 - 문제를 해결하..