공부 기록일지📚

[문제 설명]: 부서별로 물품을 구매하는데 필요한 금액을 담은 배열 d와 전체 예산 budget을 매개변수로 준다. 전체 예산은 정해져있고 모든 부서의 물품을 구매해줄 수는 없으며 최대한 많은 부서의 물품을 구매해 줄 수 있도록 해야 한다. [제한 사항] 전체 부서의 개수는 1이상 100이하 => i = 0; d.length array.sort() 를 활용하여 오름차순 ..

최대 공약수(Greatest Common Divisor) & 최소 공배수(Largest Common Multiple) 최대 공약수(GCD) 정수인 두 수의 공약수 중 가장 큰 수 즉, 두 수를 동시에 나눌 수 있는 수 중에 가장 큰 수 Math.min(a,b)를 활용해 둘 중에 작은 수의 범위를 넘어가지 않게하여 불필요한 연산 제거 최소 공배수(LCM) 정수인 두 수의 공배수 중 가장 작은 수 즉, 두 수를 곱한 값을 최대 공약수로 나눈 수 (a * b / a와b의 최대 공약수) 두 수의 최대 공약수만 알아도 최소 공배수를 구할 수 있다. 최적화 하는 알고리즘: 유클리드 호제법 {관련 내용 정리 요망} 내 풀이 { function solution(n, m) { let gcd = 1; let lcm; //..

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

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

오늘 푼 5가지 문제는 숫자, 문자열 데이터를 골라내서 가공하는 문제였다. [푼 문제 목록] 숨어있는 숫자의 덧셈 순서쌍의 개수 문자열안에 문자열 자릿수 더하기 모음 제거 각각의 요소를 조작해야 할 경우, 매개변수로 들어온 값이 string일 때에는 주로 배열로 변환해서 배열 내장 메서드를 활용한다. String.prototype.split() 문자열을 한 char 단위로 쪼개고싶을 때에는 .split("") 을 해주면 된다. split(구분자) 구분자가 공백이 될수도 있고 ""아무것도 없는 따옴표를 넣어주면 apple -> a,p,p,l,e로 쪼개준다. 새배열을 반환하는 것은 아니므로 변수에 담아줘야 한다. 내 경우는, 숫자로 들어온 매개변수 n값을 toString()을 통해 형변환 시켜준 뒤 ... ..

이전에 배웠던 정렬알고리즘 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개 요소가 있는 배열이 될 때까지 분할)한다. 그리고 가장 작은 요소끼리 정렬하며 합친다...