알고리즘- 문제를 해결하기 위해 수행해야 하는 절차나 방법 APS (Algorithm Problem Solving)알고리즘 문제 풀이 알고리즘의 필요성예를 들어, 1부터 100까지의 합을 구하는 문제를 생각해 보자문제를 푸는 방식에 따라 작업량이나 소요시간 등이 달라질 수 있다 고려 사항1) 정확성 : 얼마나 정확하게 동작하는가2) 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가3) 메모리 사용량 : 얼마나 적은 메모리를 사용하는가4) 단순성 : 다른 사람이 이해하기 쉬운가5) 최적성 : 더 이상 개선할 여지없이 최적화되었는가 알고리즘을 표현하는 두 가지 방법1) 의사코드 2)순서도시간복잡도 알고리즘의 효율성을 평가하는 지표중 하나실제 수행 시간이나 실행되는 명령문의 개수를 계산 빅오 표기법- ..
분할 정복 패턴주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리한다.(연결리스트나 트리가 될 수 있다.) 값을 찾기 위해 배열의 왼쪽에서 시작하여 오른쪽 끝까지 이동하는 것보다는배열을 작은 조각으로 세분화하여 각 조각들을 어디로 이동시킬지 결정하는 작업을 하겠다.즉! 큰 데이터 덩어리를 작은 조각으로 나누는것 예시탐색 알고리즘의 대표적인 예로, 정렬된 숫자 배열을 이용하는 방법이 있다.배열은 반드시 정렬된 상태여야 한다. 주어진 search 함수는 특정 값을 입력으로 받아, 그 값이 배열에서 위치한 인덱스를 반환한다.search([1,2,3,4,5,6],4) // 3 function search(arr, val) { for (let i = 0; i o(n)의 시간복잡도이다. 이 구조를 선형 탐색이..
기준점 간 이동 배열 패턴배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용하다. sliding window 접근법창문을 하나 만들어야 한다. 창문은 단일변수, 하위배열, 또는 필요한 경우 다른 문자열도 될 수 있다. 조건에 따라 창문을 이동시키며, 시작 위치에서 시작하면 보통 왼쪽에서 오른쪽으로 이동한다. 오른쪽에서 왼쪽으로 이동도 가능하고 가운데 위치에서 시작할 수 있다. 그러나 보통 창문을 왼쪽, 즉 요소의 시작 위치 또는 배열이나 문자열의 시작 위치에서 끝나는 위치로 이동한다. 규모가 큰 데이터셋에서 데이터의 하위 집합을 추척하는 문제에 유용하다.예시 문제정수의 배열과 n이라는 수를 받아들이는 maxSubarraySum이라는 함수..
빈도수 세기 패턴객체나 Set을 활용하여 값의 빈도나 횟수를 저장하는 방식이렇게 하면 중첩 반복문 없이도 시간 복잡도 O(N^2)를 피할 수 있다. 문제 두 개의 배열을 입력받는 same이라는 함수를 작성이 함수는 첫 번째 배열의 각 값이 두 번째 배열에서 제곱된 값으로 존재하는 경우에 true를 반환해야 합니다.값의 빈도도 동일해야 합니다.same([1,2,3], [4,1,9]) // truesame([1,2,3], [1,9]) // falsesame([1,2,1], [4,4,1]) // false (must be same frequency)내가 풀은 방법더보기function same(arr1, arr2) { // 배열 오름차순 정렬 arr1.sort((a, b) => a - b); arr2.so..
빅오표기법빅오표기법는 대략적으로 숫자를 세는 것이다. 입력된 내용이 늘어날 수록 알고리즘에 실행 시간이 어떻게 변하는지 설명해주는 방식이다. 어떤 function의 입력 값이 늘어나는 것과 function 실행 시간이 변하는 관계를 의미한다.알고리즘의 성능 평가를 하기 위해서 사용하드웨어의 영향을 받지 않는다. 즉, 입력의 크기와 실행시간의 관계를 의미(f(n)=n) | n의 값이 커질수록 실행시간도 늘어난다.(f(n)=n*n | 실행시간이 n의 제곱일 수도 있다. f(n) = 1 | n이 커져도 실행 시간에는 아무런 영향을 받지 않기에 항상 상수일 수 있다. (간단하게 표현하기 위해 1로 표시)f(n)이 완전이 다를 수도 있다. 빅오 표기법의 필요성여러가지 코드를 일반적으로 서로 비교하고 성능을 평가..
