지난 시간 Sorting Algorithms이 무엇인지 그 중에서도 Bubble Sort에 대해서 알아보았다. 👉 Link - Sroting Algorithms + Bubble Sort 선택 정렬 알고리즘(Selection Sort Algorithm) 데이터 배열을 내림차순 혹은 오름차순으로 나열하는 과정에서 사용되는 정렬 알고리즘 중 하나로 데이터 배열에서 가장 작은 데이터를 선택하여 앞으로 보내는 정렬이다. 정렬 과정을 보면 첫 시작 값에서 시작하여 모든 데이터를 최소값을 찾은 뒤 교환한다. 교환된 최소값은 정렬이 된 것이며 다음 값에서 시작하여 다시 최소값을 찾아서 교환하기를 반복한다. 간단한 원리이다. bubble 정렬과 마찬가지로 swap이 발생한다. 선택 정렬의 의사코드를 살펴보자. 의사코드 ..
정렬 알고리즘(Sorting Algorithm)은 무엇일까? 정렬 알고리즘은 컬랙션(배열과 같은)의 아이템들을 어떤 종류의 순서로 재배열하는 과정이다. 목록이나 트리 같은 데이터 구조의 정렬 등 다양하지만 배열에 초점을 두고 살펴보자. 여기서 핵심은 뭘 어떻게 비교해서 정렬하는지는 중요하지 않다. 오름차순이든, 내림차순이든, 순자를 기준으로 하든 상관없다. 👉정렬 알고리즘 애니메이션 정렬 알고리즘을 배워야 하는 이유는? 정렬은 흔히 발생하기에 이것들이 어떻게 동작하는지 이해하는 것은 중요하다. 데이터들을 정렬하는 방법은 많고 각 알고리즘에는 장단점이 있기에 상황에 맞는 알고리즘을 사용해야한다. 정렬은 다양한 접근법을 제공하고 비판적 사고가 필요한 아주 좋은 도전과제이자 문제이다. 1. 버블 정렬(Bubb..
목표 Searching Algorithm이 무엇인가 배열의 선형 검색(linear search) 정렬된 배열의 이진 검색(binary search) 나이브(navie) 문자열 검색 알고리즘, KMP 문자열 검색 알고리즘 선형 검색 알고리즘(linear search algorithm) 선형 검색은 데이터가 모인 집합(배열, 링크드리스트 등)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘이다. 데이터를 정렬하거나 따로 건드릴 필요가 없고, 난이도가 쉬운 편이나, 데이터의 양이 많아지면 검색에 소요되는 시간도 비례하여 많아지고, 하나씩 일일이 비교하기 때문에 비효율적이라는 단점이 있다. JavaScript는 선형 검색 기능을 가지고 있다. indexOf includes find fi..
💡학습 전 보기 - 재귀 함수 등 정리 목표 재귀의 정의와 재귀 사용 방법 정의 재귀 함수의 두 가지 필수 구성 요소 이해 호출 스택을 시각화하여 재귀 함수를 더 잘 디버그하고 이해하기 헬퍼 메소드 재귀(helper method recursion)와 순수 재귀(pure recursion) 재귀를 한번에 이해하는 것은 쉽지 않다. 지속적인 반복으로 자신의 것으로 만들자. 재귀(recursion)란? 자기 자신을 호출하는 프로세스 즉, 자기 자신을 호출하는 함수를 의미한다. 재귀를 알아야하는 이유는 무엇일까? 재귀는 어디서든 사용된다. JSON.parse / JSON.stringify document.getElementById and DOM traversal algorithms Object traversal..
Sliding Wind 한 위치에서 다른 위치로 배열 또는 숫자가 될 수 있는 창을 만드는 것을 의미한다. 특정 조건에 따라 창이 증가하거나 닫힌다. (새 창이 생성됨) 배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용하다. 예시를 들어보자. maxSubarraySum 함수는 정수 배열과 n이라는 숫자를 받아들인다. 함수는 배열에서 연속되는 n개의 요소의 최대 합계를 계산해야 한다. 순수한 해결책 function maxSubarraySum(arr, num) { if(num > arr.length) { return null; } let max = -Infinity; for(let i = 0; i < arr.length - num + 1; ..
Multiple Pointers: 다중 포인터 (공식 이름은 아님) 인텍스나 위치에 해당하는 포인터 또는 값을 만든 다음에 특정 조건에 따라 중간 지점에서부터 시작 지점, 끝 지점 또는 양쪽 지점을 향해 이동시키는 것이다. 공간 복잡성을 최소화하면서 문제를 해결하는데에 매우 효율적이다. 포인터는 배열이나 문자열의 특정 위치를 가리키는 것이다. 예시 1: sumZero함수 입력 값: 오름차순으로 정렬된 정수 배열 출력 값: 합계가 0인 첫 번째 쌍. 쌍이 없을 경우 0으로 합한 값 또는 undefined sumZero([-3,-2,-1,0,1,2,3]) // [-3,3] sumZero([-2,0,1,3]) // undefined sumZero([1,2,3]) // undefined 순진한 해결책 funct..
Frequency Counters Pattern 빈도 카운터 패턴은 공식적인 이름은 아니다. 이 패턴은 자바스크립트의 객체를 사용해서 다양한 값과 빈도를 수집한다. 이 패턴은 알고리즘과 프로젝트에 있는 여러 데이터와 입력값이 서로 비슷한 값으로 구성되어 있는지, 값이 다른 값에 포함되는지 여부를 비교하거나, 데이터를 입력값이나 두 개 이상의 빈도 혹은 특정하게 발생하는 빈도와 비교할 때 유용하다. 이 패턴은 중첩 루프나 배열/문자열이 있는 O(N^2) 연산의 필요성을 피할 수 있다. 예시를 살펴보자. 2개의 배열을 허용하는 same함수를 작성하고 배열의 모든 값이 두 번째 배열에서 제곱한 해당 값을 가지면 참을 반환한다. 값의 빈도는 같아야 한다. same([1,2,3], [4,1,9]) // true ..
알고리즘(Algorithm): 특정 작업을 달성하기 위한 과정이나 일련의 단계 문제를 해결하기 위해 수행해야 하는 일련의 수학적 단계, 특정 광고를 사용자에게 제안하는 페이스북이나 구글의 알고리즘이라고 할 수 있다. 우리는 왜 알고리즘을 필요로 할까? 프로그래밍에서 수행하는 거의 모든 작업에는 일종의 알고리즘이 포함되므로 문제를 해결할 방법을 마련할 수 있도록 결정을 해야 한다. 어떻게 발전해나가야 할까? 1. Devise a plan for solving problems. 문제 해결을 위한 계획을 수립하라. 문제에 접근하는 방법, 문제를 세분화하기 위한 전략, 방향을 잡기 위한 몇 가지 단계 2. Master common problem solving patterns. 일반적인 문제 해결 패턴을 파악하라..
