조각모음

그리디 알고리즘 패스트 캠퍼스 코딩 테스트 강좌 내 잔재미코딩 님의 부분을 참고했습니다. 정의 Greedy algorithm 혹은 탐욕 알고리즘 최적의 해에 가까운 값을 구하기 위해 사용된다. 여러 경우 중 하나를 결정해야 할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구한다. 예제 1 지불해야하는 값이 4720원일 때, 1원, 50원, 100원, 500원 동전을 이용하여 지불하되, 가장 적은 수의 동전을 사용하시오. 접근 가장 가치가 큰 동전부터 사용해야 가장 적은 수의 동전을 사용하게 된다. // 사용 가능한 동전을 담은 배열 const coins = [1, 50, 100, 500]; // @params : cost - 지불해야할 금액 // @params : ..

자바스크립트 string, number 간단하게 형변환하기 Sting()이나 parseInt() 등을 사용하지 않고 간단하게 형변환하기 // 숫자 -> 문자열 const num1 = 123456; const str1 = num2 + ""; // "123456" // 문자열 -> 숫자 const str2 = "123456"; const num2 = +str; // 123456 const num3 = str/1; // 123456 const num4 = -str; // -123456 const num5 = str/-1; // -123456

분할 정복과 고급정렬 분할 정복 문제를 나눌 수 없을 때까지 나누어 각각을 풀고 다시 합병하여 문제의 답을 얻는 알고리즘 하향식 접근법으로 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식 일반적으로 재귀함수로 구현된다. 문제를 잘게 쪼갤 때 부분 문제들은 서로 중복되지 않는다. 병합 정렬, 퀵 정렬 등 고급 정렬 1) 병합정렬 리스트를 절반으로 계속해서 자른다. 더이상 나눌 수 없을 만큼 나뉘었다면, 값을 비교 후 정렬해가며 병합한다. 리스트를 계속해서 나누는 함수와 나뉜 리스트를 정렬하며 합치는 함수를 만든다. 구현 // 병합 정렬 const mergeSort = arr => { // 재귀함수 종료 조건 if (arr.length leftIndex && right.length >..

패스트캠퍼스 코딩테스트 강좌의 잔재미코딩 님 부분을 참고하였습니다. 동적 계획법 (Dynamic Programming)과 분할 정복(Divide and Conquer) 동적 계획법 통상 DP라고 많이 부른다. 상향식 접근법으로 가장 최하위 해답을 구한 뒤 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 입력 크기가 작은 부분 문제들을 해결한 후, 해당 문제의 해를 활용하여 보다 큰 크기의 부분 문제를 해결하여 최종적으로 전체 문제를 해결하는 알고리즘 문제를 잘게 쪼갤 때 부분 문제는 중복되어 재활용된다. 예) 피보나치 수열 Memoization 기법을 사용한다. 프로그램 실행 시 이전에 계산한 값을 저장하고 재활용하여 전체 실행 속도를 빠르게 하는 기술 분할 정복 문제를 나눌 수 없을 때..