배열

push, pop은 O(1) shift, unshift은 O(n)

• 알고리즘 해결방법

1. 문제 해결을 위한 계획 수립
2. 일반적인 문제 해결 패턴을 파악

• 계획 수립 - 방향이나 기본적 개념을 알고 있다는 것을 보여줄 수 있다

• 리팩토링 질문 can you check the result?

can you derive the result differently? 문제에 대한 해결책이 하나만 있는 경우는 드물기 때문에 이런 질문이 가능 can you understand it at a glance? can you use the result or method for some other problem? can you improve the performance of your solution? can you think of other ways to refactor? how habe other people solved this problem?

루프는 중첩 루프보다 개별 루프가 훨씬 효율적 ex: 개별루프 2개와 이중루프의 경우, 1000개의 작업을 수행하게 되면 2000 vs 10^6

슬라이드 윈도우 배열에서 n개의 연속된 수의 합을 구하는 경우 매번 루프를 도는 대신, 첫째값과 마지막값만 참조함

탐색

선형 탐색

• 배열은 정렬되어 있어야 함
• 빅오 O(n)

이진 탐색

• 배열은 정렬되어 있어야 함
• 배열을 둘로 나누고, 위아래로 탐색
• 빅오 O(logn)

재귀

• 중단점이 필요

• 중단점 > 실행코드 > 재귀호출

• 종료 조건이 없으면 스택에 계속해서 함수를 추가하게 됨

스택이 넘침

• 잘못된 값을 반환하거나, 애초에 반환하지 않는 것

종료 조건을 제대로 설정했지만, 위와 같은 경우에 종료 조건에 도달하지 못함 ex : 재귀 호출을 하는 과정에서 값을 감소시켜야 하는데, 이에 대한 로직이 빠진 경우

헬퍼 매소드 재귀

일종의 결과를 컴파일할 때 흔히 사용되는 패턴으로, 결과는 보통 배열이나 배열과 비슷한 다른 형태 데이터 구조이다.

• 재귀 호출을 하는 과정에서 배열 등의 자료 구조나 변수 등이 초기화되는 문제를 해결해줌

• 재귀적이지 않은 함수가 재귀적인 내부 함수를 호출하는 패턴

• 배열을 사용하고 헬퍼 메소드 없이 순수 재귀 솔루션을 작성하는 경우, 배열을 복사하는 slice, spread 연산자(operator), concat 같은 메서드를 사용해 배열을 변경하지 않을 수 있다.

검색 알고리즘

선형 검색

• 배열의 처음부터 끝까지 탐색하는 방법
• 빅오 O(n)

이진 검색

• 정렬된 배열의 중간값과 탐색 대상을 비교해가며, 배열을 계속해서 절반씩 탐색하는 방법
• 빅오 O(log n)

나이브(naive) 문자열 검색

• 탐색 범위와 탐색 대상을 이중 루프를 사용해 순회하면서, 탐색 대상이 범위 안에 있다면 count를 늘리는 방식

정렬 알고리즘

기본 내장 JS 정렬

• array.sort() sort()에 함수를 인자값으로 주어 배열을 정렬하는 방법

function numberCompare(num1, num2) {
 return num1 + num2;
}

[ 6, 4, 15, 10 ].sort(numberCompare);
// [ 4, 6, 10, 15 ]

위 코드에서 numberCompare() 함수를 sort()의 인자값으로 주어 배열을 오름차순으로 정리하였습니다.

버블, 선택, 삽입

• 버블, 선택, 삽입 모두 2차 평균 시간 복잡도를 갖습니다.
• 즉각적인 직관성이 떨어집니다.
• 아주 작은 데이터에서 잘 작동합니다.

버블 정렬

배열의 끝에 가장 큰 값을 쌓아가며 순회하는 방법 마지막에는 정렬되지 않은 값들 중 가장 큰 값이 쌓이기 때문에, 순회를 할 때마다 순회하는 범위가 줄어듭니다.

• 빅오 일반적인 경우 O(n^2) 그러나 데이터가 거의 정렬되어 있거나, 이미 정렬이 끝난 상태에서는 선형 시간에 더 가깝습니다. O(n)

선택 정렬

• 버블 정렬과 비슷하지만, 큰 값을 배열 끝에 쌓는 대신, 배열을 순회하며 최소값을 한 번에 하나씩 위치에 배열합니다.
• 빅오 배열의 길이가 길어질 경우 O(n^2)

삽입 정렬

• 배열의 과반을 점차적으로 만들어 정렬을 구축하며, 과반은 항상 정렬되어 있습니다.
• 첫 번째 값을 정렬된 배열로 간주하고, 두 번째 값부터 비교해가며 배열 안의 올바른 위치에 넣습니다.
• 배열의 길이가 길어질 경우 O(n^2)

합병 정렬

• 배열을 작게 나눈 다음, 정렬을 하며 배열을 합병합니다.

1. 모두를 작은 요소로 나눕니다.
2. 합병 함수를 사용해 합칩니다.(전체 배열로 돌아갈 때까지)

• 빅오 최적 케이스, 평균 케이스, 최악 케이스가 O(n log n)으로 모두 같습니다. 배열을 나누는 과정이 log n, 합병할 때 각 분할을 O(n)번 비교

빠른 정렬

• 배열을 돌면서, 요소 하나씩 올바른 인덱스에 위치시키는 방법입니다.

1. Pivot Helper Pivot보다 작은 값은 모두 왼쪽으로, 큰 값을 오른쪽으로 이동시킵니다.

Pivot Helper 를 사용해서 하나씩 올바른 인덱스에 위치시켜 정렬합니다.

• 빅오 최적의 케이스와 평균은 O(n log n), 최악의 케이스는 O(n^2) - 이미 정렬된 배열

기수 정렬

비교 알고리즘이 아닌 정렬 알고리즘 이진수를 사용 숫자 크기에 대한 정보를 자릿수로 인코딩한다는 사실을 이용합니다 첫 번째 자리수부터 값을 비교해서, 배열에서 가장 큰 숫자의 자리수까지 비교하여 정렬합니다.

• 빅오 최상, 평균, 최악의 경우 o(nK) : n = 정렬할 항목 수나 정수의 수 / k = 이러한 수의 길이

자료 구조

class

사전에 정의된 속성 및 메소드들을 이용해 객체를 생성하기 위한 도구

단일 연결 리스트

시작 노드(0인덱스를 가지고 있는 노드)가 다음 노드를 가리키고, 마지막 노드는 null을 가리키고 있습니다.

• 장점 : 삽입과 제거의 과정이 쉽습니다.

• 단점 : 각 노드가 인덱스를 가지고 있지 않기 때문에, 특정 인덱스에 해당하는 대상을 찾기 위해서는 head node부터 차례로 대상을 찾는 작업이 필요합니다.

• 메서드

1. push 리스트의 마지막에 연결 노드를 추가합니다.
2. pop 리스트의 마지막 연결 노드를 제거하고, 이를 return합니다.
3. shift 리스트의 head 노드를 제거하고, 이를 return합니다.
4. unshift 리스트의 head 노드 앞에 새로운 연결 노드를 추가합니다.
5. get 인덱스 혹은 위치를 의미하는 숫자를 인자로 받아, 해당 위치에 있는 노드를 return합니다.
6. set 위치 혹은 인덱스와, 해당 인덱스에 위치한 노드를 업데이트할 값 등 두 개의 인자를 받아 해당 인덱스의 노드를 업데이트합니다.
7. insert 인덱스와 인자를 받아, 해당 인덱스에 입력받은 인자를 추가합니다.
8. remove 인덱스를 인자로 받아, 해당 인덱스에 있는 노드를 제거하고 앞뒤 노드를 재연결합니다.
9. reverse 연결 리스트의 연결 순서를 뒤집습니다.

• 빅오

1. Insertion - O(1)
2. Removal - O(1) or O(n) : 인덱스의 값에 따라 다름
3. Searching - O(n)
4. Access - O(n)

이중 연결 리스트