2022/07/17 4

문제 해결 패턴 - Multiple Pointers

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

Algorithm 2022.07.17

문제 해결 패턴 - Frequency Counters

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

Algorithm 2022.07.17

문제 해결 패턴 종류

개선하는 법 (문제를 해결하는 법) 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 알고리즘 & 자료구조 마스터클래스 강의를 듣고 정리 및 메모한 내용입니다. 오역 및 오개념이 있을 수 있으니 바로잡기 위해 문제가 있는..

Algorithm 2022.07.17

문제 해결 5단계 - 복습하고 재구성하기

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

Algorithm 2022.07.17