공부 기록일지📚

단일 연결 리스트와 JS의 배열의 가장 큰 차이는 index유무이다. 연결 리스트는 단순히 포인터로 연결된 노드의 집합이며 index를 가지고 있지 않아 특정 값에 접근하는데 적합하지 않다. 배열의 경우 index를 가지고 있어 특정 값을 읽어오는 것에 능하다. 메모리 상에 연속적으로 저장되어있는 특정을 갖기 때문이다. 데이터 탐색에는 배열이 용이하고 추가와 삭제의 경우는 연결리스트가 용이하다. 배열(Array) 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어있는 자료구조 메모리 상에 연속적으로 저장되어있는 특징 index를 통한 접근 용이(임의 접근 가능) 배열의 크기는 처음 생성할 때 정하며 이후에는 변경 불가-> 배열은 정적(static)인 자료구조 연결 리스트(linked list) 동적인 ..

class(클래스)? : 객체를 만들기 위한 프로퍼티와 메서드가 명시된 청사진 이 청사진에 기반한 객체들을 인스턴스화할 수 있다. 엄밀히 말하자면 JS는 실제로 클래스를 지원하지 않는다.(JS에 이미 존재하는 프로토타입 기반 상속자들을 구문적으로 눈속임한 syntatical sugar이다.) -> 진정한 OOP는 지원하지 않음 프로토타입 기반 상속자 혹은 프로토타이핑으로 불리는 무엇인가를 이용하는 것 new 키워드를 통해 생성되거나 인스턴스화 된다. 생성자 함수는 클래스가 인스턴스화 할 때 동작하는 특별한 함수이다. 클래스를 왜 배워야할까🤔? 앞으로 수 많은 자료 구조들을 클래스(ES2015최신 문법)로 구현할 것이기 때문이다. 1. class syntax (문법) class Student { const..

이전에 배웠던 정렬알고리즘 5개는 기본적으로 comparison sorts(비교 정렬)이다. 배열의 요소를 하나 하나 비교하면서 정렬했던 것이기 때문이다.(e.g. 두 요소의 크기를 비교해서 어느 위치로 옮기고 하는 작업) 아래는 기존에 배웠던 정렬 알고리즘의 평균 시간 복잡도(big O표현)이다. bubble sort - O(n^2) Insetion sort - O(n^2) selection sort - O(n^2) quick sort - O(n log (n)) merge sort - O(n log (n)) 결과를 보면 알 수 있겠지만 최대 효율이나도 n log n이 한계이다. 여기서 어떻게 더 발전할 수 있을까? -> 비교를 통해 정렬하는 sort 알고리즘 외에 다른 유형의 sort 알고리즘이 존재한..

Quick Sort (퀵 정렬) : 퀵 정렬은 합병 정렬과 같은 가정으로 작동한다. 재귀를 통해 해결하기 가장 쉬운 방식 중 하나다. 합병 정렬처럼 0또는 1개의 정렬된 요소를 배열로 쪼갠다. 피벗(pivot) 포인트라 부르는 단일 요소를 선택하여 수행한다. 예시로 첫번째에 위치하는 5를 피벗으로 골랐다면 5를 기준으로 왼쪽 오른쪽 섹션을 나누게 된다. 그리고 왼쪽 섹션에서 새로운 피벗을 고른다. 이 과정을 반복해준다. *피벗 포인트로 선택된 요소는 어찌됐든 정렬된 데이터가 된다.(e.g.)5를 선택했다면 5를 기준으로 작은 값 큰 값을 나누기 때문이다.) 1-1. Pivot Helper - 파티션 or 피봇이라 부른다. -> 같은 의미 - 배열이 주어지면 요소를 피벗 포인트로 지정하여 배열 속 요소를 ..

이전에 배웠던 3가지 기초 sorting 알고리즘은 소규모의 데이터(e.g.)20개의 요소가 담긴 배열..)에 적합하다. 큰 데이터를 정렬할 때에는 이전 기초 정렬알고리즘보다 더 효율적인 알고리즘이 존재한다. faster sorts 합병 정렬(merge), 퀵 정렬(quick), 지수 정렬(radix)에 대해서 배워보자 시간복잡도를 O(n^2)에서O(n log n)으로 바꿀 수 있다. Merge Sort (합병 정렬) - merging and sorting 의 조합, 정확히 말하자면 분할, 정렬, 합병 모두가 일어난다. 데이터 배열이 있다고 했을 때 해당 배열이 가장 작은 요소를 갖도록 분할(정렬된 배열이 0개나 1개 요소가 있는 배열이 될 때까지 분할)한다. 그리고 가장 작은 요소끼리 정렬하며 합친다...

Insertion sort (삽입 정렬) 삽입 정렬은 버블 정렬 및 선택 정렬과 꽤 비슷하다. 기초 sort 알고리즘으로 이 3가지가 묶임 몇 가지 주요 차이점이 있고, 사실상 삽입 정렬이 더 유리한 지점이 있다. 삽입 정렬이 잘 작동하는 상황이 존재한다는 소리 -> 거의 정렬된 데이터에 새로운 데이터가 들어올 때 상황 예시: 라이브 & 스트리밍 방식으로 들어온 데이터를 즉시 입력해야 하는 상황, 데이터가 들어와서 계속 재정렬하고 실행중인 정렬을 유지하여 최신 상태로 두어야 할 상황 2. 삽입 정렬의 동작 방식 이 정렬은 배열의 과반을 점차적으로 만들어 정렬을 구축하며, 과반은 항상 정렬되어 있다. 따라서 하나씩 이동하거나, 한 번에 가장 큰 요소를 찾거나 한 번에 가장 작은 요소를 찾는 대신 각 요소를..

Selection Sort (선택정렬) -버블 정렬과 비슷하지만, 큰 값을 배열 끝에 위치시키는 대신 작은 값을 한 번에 하나씩 위치에 배열한다. 버블 정렬과 마찬가지로 처음부터 끝까지 움직이지만, 실제 정렬된 데이터는 처음부터 누적되고 있다. 첫 요소와 모든 요소를 비교 후, 비교 대상 중 최솟값을 찾아 마지막 swap을 통해 첫 요소와 최소값인 요소의 자리를 바꾼다(만일 첫번째 요소가 비교를 전부 끝냈을 때 최솟값이라면 자리를 이동하지 않는다-> noSwap). 버블 정렬 만들기 tip 우선 최솟값을 담을 변수를 만들어준다. 최솟값의 초기값은 첫번째 요소의 값으로 설정할 수 있다. 저장하려는 변수 값은 최소값이 담긴 요소의 인덱스이다. 모든 단일 항복들에 대해 반복할 필요는 없다. 실제로 해야할 것은..

1. What is sorting? 간단히 설명하자면 정렬 알고리즘이란 컬렉션(e.g. 배열)의 항목을 재배열하는 과정을 의미한다. e.g.) 문자열을 하나 고른 후에 문자열 내의 각 문자를 정렬하는 것 정렬 알고리즘의 대표적인 종류들만해도 15가지가 넘는다. 인설션 소트(insertion), 퀵 소트(quick), 버블 소트(bubble), 머지 소트(merge), 힙 소트(heap), 기수 소트(radix sort) 셸 소트(shell)등등.. 여러가지 접근 방법이 존재한다. 2. 왜 배워야 할까? 정렬(sorting)이 프로그래밍에서 정말 흔하게 사용되기 때문이다. JS, 루비, 파이썬의 내장 정렬 메서드를 사용하고 있더라도, 거기에 어떤 알고리즘이 사용되는 지를 이해하는 것이 중요하다. 데이터를 ..