본문 바로가기

Study/Algorithm & Data structure

(6)
sort algorithm(1) +) sorting 알고리즘을 시각화 한 사이트 bubble sort(sinking sort) Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed bubbleSort([5, 4, 1, 3, 2]) // [1, 2, 3, 4, 5] 최대값을 찾아 배열을 오른쪽 => 왼쪽 순으로 정렬한다. [5, 4, 1, 3, 2]의 배열을 bubble sort를 ..
recursion call stack 대부분의 프로그래밍 언어에는 함수의 호출 순서를 저장하는 자료 구조(data structure)가 구현되어있다. js에서 이는 call stack으로 불리며, 소스 코드에서 함수를 호출할 때 마다 stack에 그 정보가 쌓이고, 맨 꼭대기(top)에 쌓여있는 함수 호출 정보가 가장 먼저 삭제된다(pop). 재귀 함수를 호출하게 되면, 이 함수의 호출이 중단될 때 까지 call stack에 같은 재귀 함수가 여러개 쌓이게 된다. 그렇다면 재귀 함수란 무엇일까? what is recursion? a process(function) that call themselves from within their own code. +) 재귀함수는 거의 모든 곳에 존재하며, JSON.stringify, ..
problem solving patterns(2) 1. frequency counter pattern 예제 문제1 same([1, 2, 3, 3], [9, 4, 1, 9]) // true same([1, 2, 3, 3], [9, 4, 1]) // false 1. write a function called "same", which accepts 2 arrays. 2. the function should return "ture" if every value in the array has it's corresponding value squared in the second array. 3. the frequency of values must be the same. 문제 풀이한 방법 const squared = [1, 9, 25, 25] getFrequencyOf..
problem solving patterns intro 문제를 해결하는 방법은 아래의 5 가지로 나누어 볼 수 있다. => 참고 도서) "how to slove it" by Georhe Polya 문제 이해하기(understad the problem) 구체적인 예제 살펴보기(explore concrete example) 세부적으로 분석하기(analyze) 문제 해결하기/단순화하기(solve/simplify) 재검토하기(look back and refactor) understand the problem 문제를 확실히 이해한 후에, 코드를 작성하는 것이 중요하다. 문제를 나만의 언어로 다시 정의할 수 있는가? input은 어떤 형태여야 하는가? 어떤 output을 반환해야 하는가? input을 이용해서 output을 결정할 수 있는가? 즉, outpu..
performance of array & object object 객체는 순서(unordered)가 없고, key - value 쌍으로 이루어진 데이터의 집합이다. 따라서 순서에 관계 없는 데이터를 보관할 때 사용하면 좋다. 뿐만 아니라, 빠르게 데이터에 접근하거나 데이터를 추가/삭제 할 때에도 유용하다. 이 때 빠르다는 것은 상수의 시간 복잡도(O of constants)를 갖는다는 것을 의미한다. let harry = { fullName: 'harry styles', age: 28, favoriteNumbers: [1, 2, 3, 4], } insertion => O(1) removal => O(1) access => key를 이용해 value에 접근하는 것을 의미, O(1) searching => 어떤 value가 객체에 존재하는지 확인하는 것을 의미..
BigO Notation intro big o 표기법은 같은 문제를 해결하는 여러 방법, 즉 여러 알고리즘 중 어떤 것이 더 나은지 판단할 수 있는 기준이 된다. 어떤 알고리즘이 더 낫다고 이야기하는 것은 상황에 따라 다르지만, 빠른 속도와 적은 메모리 사용량이 보편적인 기준이다. +) 속도나 메모리 사용량 뿐만 아니라 코드의 가독성, 간편한 유지보수 가능성 등이 더 나은 코드를 판별하는 기준이 될 수 있다. time complexiry | how long to execute the function? perfomance.now 이용하기 예를 들어 문자열을 input으로 받고, 그 문자열을 거꾸로 뒤집은 값을 반환하는 함수를 만든다고 해 보자. 이 함수를 구현해내는 방법은 아래의 두가지 외에도 많을 것이다. 둘 중 어떤 함수가 더..