알고리즘

[다이나믹프로그래밍] DP - JS, Python

다이나믹 프로그래밍 큰 문제를 작게 나누고 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하려는 알고리즘 기법 다이나믹 프로그래밍을 사용할 수 있는 경우 1. 최적 부분 구조(큰 문제를 작은 문제로 나눌 수 있다) 2. 중복되는 부분 문제(동일한 작은 문제를 반복적으로 해결 (최적화)) 위의 두 조건이 모두 충족할 경우 다미나믹 프로그래밍을 사용할 수 있다 (점화식 사용) 다이나믹 프로그래밍 최적화의 핵심 각 작은 문제는 한 번만 풀어야 한다 Optimal Substructure를 만족하기 때문에 같은 문제는 구현 때마다 정답이 같다 정답을 한 번 구했으면 어딘가에 메모해 놓는다 메모하는 것을 코드에서는 배열로 구현할 수 있다 메모한다고 해서 memoization 용어를 쓴다 다이나믹 프로그래밍의 ..

[JavaScript] 알고리즘에 쓰이는 문법 (판별)

판별 match() 인자에 포함된 문자를 찾으면 이를 반환(Array로) 일치하는게 없으면 null반환 1. 일반 문자열 if (str.match('red') === 'red') { console.log('Okay'); } 2. 정규표현식 let new_id = 'hello' new_id.match(/^[a-z]$/) //['hello'] var test = 'love you. love me. love everything!' var regExp = /love/gi; test2 = test.match(regExp); ['love', 'love', 'love'] // test2변수에 배열로 모든 love 텍스트가 저장됨 var str = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijkl..

[JavaScript] 알고리즘에 쓰이는 문법 (중복, 포함여부)

중복제거 Set < indexOf < includes순으로 시간 오래걸림 indexOf() 배열에서 지정된 요소 찾을 수 있는 첫번째 인덱스를 반환 존재하지 않으면 -1 if(answer.indexOf(numbers[i]+numbers[j])===-1){ answer.push(numbers[i]+numbers[j]) } Set() 자료형에 관계 없이 원시 값과 객체 참조 모두 유일한 값을 저장할 수 있음 const temp = [] for (let i = 0; i < numbers.length; i++) { for (let j = i + 1; j < numbers.length; j++) { temp.push(numbers[i] + numbers[j]) } } const answer = [...new Se..

[JavaScript] 알고리즘에 쓰이는 문법 (배열초기화)

new Array 초기화 할 값의 길이를 정할 수 있음 prices = [1,2,3,4,5] answer = new Array(prices.length) >>[ ] Array.from 초기화할 범위와 값을 정할 수 있다 const arr = Array.from({length: 5}, (v, i) => i); // i(index) 1씩 증가 console.log(arr); // => Array(5) [0, 1, 2, 3, 4] console.log(arr[0]); // => 0 console.log(arr.length); // => 5 /* 콜백함수의 첫번째 매개변수, v 생략시 undefined 반환 */ const arr = Array.from({length: 5}, (i) => i); console...