백트래킹

• 모든 경우의 수를 탐색하는 알고리즘
• DFS나 BFS를 이용할 수 있음
• 가지치기(Pruning): 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것 ⇒ 백트래킹의 핵심!
  • 효율성을 결정하는 부분
• JS는 재귀 효율이 좋지 않기 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋음
• 탐색에서 순환(Cycle)이 발생할 가능성이 있다면 BFS를 이용하는 것이 좋음

구현 과정

• 먼저 모든 경우의 수를 찾을 수 있도록 코딩
• 문제에서 특정한 조건을 만족하는 것만 탐색하고 나머지는 탐색하지 않도록 조건문을 작성 ⇒ 절대로 답이 될 수 없는 것은 탐색을 종료

동적계획법(Dynamic Programming, DP)

• 작은 문제부터 해결하면서 점점 범위를 넓혀가 큰 문제를 해결하는 방식
• 특정 알고리즘이 아닌 문제 해결 방식을 의미함
• Dynamic Programming이지만 Dynamic하지 않고 Programming과도 관련이 없음 ⇒ 단지 멋있어 보여서 지은 이름이다…
• 메모리를 많이 사용하는 대신 빠른 성능
• 두 가지 방법론이 있음
  • 메모이제이션(Memoization)
  • 타뷸레이션(Tabulation)

메모이제이션

• 하향식 접근법
• 작은 문제들의 결과를 저장해두었다가 필요할 때 꺼내쓰는 방식(동적 계획법에서 작은 문제들의 결과는 항상 같음)

타뷸레이션

• 상향식 접근법
• 필요한 값들을 미리 계산해두는 것
  • 메모이제이션은 필요할 때 계산한다면 타뷸레이션은 미리 계산해둔 값을 꺼내쓰는 방식
• 실제 업무에서는 타뷸레이션을 많이 사용하지만 코딩 테스트에서는 메모이제이션을 많이 사용함

동적 계획법 문제 접근법

• 동적 계획법 유형은 키워드만으로 동적 계획법 문제임을 알기 어려움
• 문제 유형을 알 수 없으면 다음을 확인해야함
  • 가장 작은 문제로 정의할 수 있는가?
  • 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙이 있는가?
  • 위의 두가지가 가능하다면 동적 계획법 문제로 볼 수 있음

간결하고 가독성 좋은 코드 작성법

• 변수, 함수의 이름을 적절하게 선언
• 중복 코드 제거
• 함수형 프로그래밍을 이용하기 → map, filter, reduce와 같은 고차함수 이용
• 일관성을 잘 유지하기 → 조금 더러워도 일관성있는 코드가 좋음
  • var과 let 혼용하지 않기
  • snake_case와 camelCase를 혼용하지 않기
  • 변수명, 함수명을 줄임말과 전체 작성을 혼용하지 않기

코딩테스트 입출력 제한

• 입력이 100 이하인 경우
  • 완전 탐색
  • 백트래킹
• 입력이 10,000 이하인 경우
  • 최대 O(n^2) 이내로 끝내야함
  • 문제에 따라 O(n^2 log n)까지 가능
  • n*n 2차원 리스트를 모두 순회해야하는 문제가 많음
• 입력이 최대 1,000,000 이하인 경우
  • 최대 O(n log n)으로 끝내야하는 문제
  • 힙, 우선순위 큐
  • 정렬
  • 동적 계획법(DP)
  • 위상 정렬
  • 다익스트라 알고리즘
• 입력이 100,000,000 이하인 경우
  • 최대 O(n)으로 끝내야하는 문제
  • 동적 계획법
  • 그리디
• 그 이상인 경우 → 거의 출제되지 않음
  • 최대 O(log n)으로 끝내야하는 경우가 많음
  • 이진탐색

문제 유형

• 입력 값이 작은 문제 → 높은 확률로 완전 탐색 혹은 백트래킹 문제
• 지도가 주어지고 채워진 영역을 찾아야하는 경우 → 높은 확률로 BFS, DFS 문제
• 그래프 그림이 있는 경우
  • 최단 거리 찾기, 최소 신장 트리, 위상 정렬 중 한 가지를 사용해야할 확률이 높음
  • 최단 거리 찾기: 문제에 “가장 빠른 길”, “최단 거리”, “x비용 내로 갈 수 잇는 길” 같은 키워드
  • 최소 신장 트리: “가장 저렴한 방법으로 모든 경로 연결”, “가장 저렴하게 연결” 같은 키워드 ⇒ 크루스칼, 프림 알고리즘 사용
  • 위상 정렬: “순서”, “차례” 같은 키워드
• X라는 조건을 만족하는 가장 최대/최소값을 찾아라 → 높은 확률로 결정 문제, 파라메트릭 서치 이용
• 실시간으로 정렬이 이루어져야 하는 경우 - 높은 확률로 우선순위 큐 혹은 힙을 사용하는 문제
• DP 문제
  • 완전 탐색처럼 시간이 오래걸리면 안되는데 특별한 알고리즘을 사용하는 문제가 아닐 경우 높은 확률로 DP 문제
  • 유형을 판단하기 힘든 경우 DP처럼 풀 수 있는지 생각해봐야함
    1. 문제를 따라 초기값을 작성
    2. 초기값을 포함해 모든 상태값을 작성
    3. 현재 상태를 통해 다음 값을 구할 수 있는지 판단
    4. 혹은 이전 상태들을 통해 현재 값을 구할 수 있는지 판단
    5. 식을 만들 수 있다면 DP 문제임
• 문자열이 주어지는 경우 → 구현력 문제인 경우가 많음
• 현재 상황에서 가장 최적인 선택을 해야하는 경우 → “가장 많은 선택을 할 수 있는”, “가장 작은/큰” 등의 키워드가 들어가면 그리디 문제일 확률이 높음

엣지케이스 찾는 법

• 엣지케이스: 일반적인 테스트 케이스와는 다른, 주로 특수한 상황이나 극단적인 입력값을 가지는 테스트 케이스를 말함
• 엣지케이스의 종류
  • 입력 값의 크기가 굉장히 작은 케이스
  • 입력 값의 크기가 굉장히 큰 케이스
  • 입력 값의 범위가 넓은 케이스
  • 음수 입력이 허용된 경우 음수만 입력받는 케이스
  • 리스트를 입력 받을 때 값이 없거나 하나만 있는 케이스
  • 그래프에서 사이클이 발생하는 경우
  • 길찾기 문제에서 지그재그로 움직일 경우
  • 부동소수점 오차

JS 코드 트릭

배열 생성으로 루프 제거

• 일반적인 범위 루프 방법

let sum = 0;
for (let i = 1; i < 5; i += 1) {
	sum += i;
}
// sum = 15

• 함수형 프로그래밍 방식으로 범위 루프 작성

const sum = Array
  .from(new Array(5), (_, k) => k+1)
  .reduce((acc, cur) => acc + cur, 0);
// sum = 15

배열 내 같은 요소 제거

• Set을 사용

const fruits = ['apple', 'banana', 'apple', 'banana', 'melon'];
const uniqueFruitsWithArrayFrom = Array.from(new Set(fruits));
const uniqueFruitsWithSpread = [...new Set(fruits)];

console.log(uniqueFruitsWithArrayFrom); // [ 'apple', 'banana', 'melon' ]
console.log(uniqueFruitsWithSpread); // [ 'apple', 'banana', 'melon' ]

객체 생성시 키 생략하기

• 객체를 생성할 때 프로퍼티 키를 변수 이름으로 생략할 수 있음

const name = 'GunWoo';
const FullName = 'HongGunWoo';
const person = {
  name,
  FullName
}
console.log(person); // { name: 'GunWoo', FullName: 'HongGunWoo' }

동적 속성 이름

• ES6에 추가된 기능으로 객체의 키를 동적으로 생성 가능

const nameKey = 'name';
const emailKey = 'email';
const person = {
  [nameKey]: 'GunWoo',
  [emailKey]: 'test@test.com'
};
console.log(person); // { name: 'GunWoo', email: 'test@test.com' }

!! 연산자를 사용하여 Boolean 값을 바꾸기

• !! 연산자를 통해 0, null, 빈 문자열, ndefined, NaN을 false로 그 외에는 true로 변경할 수 있음

function check(variable) {
  if (!!variable) {
    console.log(variable);
  } else {
    console.log('false');
  }
}
check(0); // false
check(null); // false
check(''); // false
check(undefined); // false
check(NaN); // false

check('Good'); // Good
check(5); // 5
check(3.1); // 3.1

CSS란?

• css : Cascading Style Sheets cascading: ‘위에서 아래로 흐르는’, 선택자에 적용된 많은 스타일 중에 어떤 스타일로 브로우저에 표현할지 결정해주는 원리를 의미한다.
  

CSS 선택자 종류

• *: 전체 선택
• type(태그 이름): 태그 선택
• id( # ): id 선택
• class( . ): 클래스 선택
• state( : ): 상태에 따라 변경 가능
• attribute( [ ] ): 해당 속성값 선택
• 자식( > ): 특정 요소의 자식요소를 선택(ex. ul > li ⇒ ul 요소의 자식인 모든 li를 선택)
• 후손(공백): 특정 요소의 모든 하위 요소를 선택(ex. div p ⇒ div 요소의 모든 p를 선택

id와 class의 차이점

• 유일성(Uniqueness)
  • id는 문서 내에서 유일한 식별자로 사용되어야함 → 동일한 id를 여러 요소에 할당할 수 없음
  • class는 여러 요소에 동일한 class를 할당할 수 있음 → 여러 요소를 그룹화하고 스타일을 일괄적으로 적용하는 데 유용함
• 우선순위(Priority)
  • id 선택자의 우선순위는 class 선택자보다 높음 →id는 class보다 더 특정하고 구체적인 스타일을 적용하고자 할 때 유용함
• 재사용성(Reusablility)
  • id는 고유성을 가져야 하므로 특정 요소에 한 번만 사용함 → 해당 요소에 대한 스타일을 재사용할 수 없음
  • class는 여러 요소에 동일한 class를 할당할 수 있으므로 스타일의 재사용성이 높음
• JavaScript 접근성
  • id는 JS에서 요소를 식별하고 조작하는 데 사용
  • class도 JS에서 사용할 수 있지만, id보다는 한정적인 용도로 사용됨
    • JS에서 class를 선택하여 해당 클래스를 가진 모든 요소에 스타일을 적용하거나 조작하는 경우
    • 이벤트 핸들러를 일괄적으로 적용하는 경우
    • 그룹화된 동작을 수행하는 경우

동일한 id가 여러개 있다면?

• 동일한 id를 가진 여러 요소에 대해 어떤 요소의 스타일이 적용될지 예측할 수 없음
• CSS는 id 선택자에 매칭되는 첫 번째 요소에 스타일을 적용하고 나머지 동일한 id를 가진 요소는 무시함

DOM(Document Object Model)

• 브라우저가 웹 문서를 이해할 수 있도록 구성한 것으로 html 모든 요소들과의 관계를 부자관계로 표현된 트리 구조로 구성한 것
• 트리 구성 노드
  • 문서 노드: 최상위 노드로 DOM 트리의 시작점
  • 요소 노드: HTML태그 그 자체를 나타냄, HTML 문서 구조를 그대로 표현함
  • 속성 노드: 요소 노드에 붙어있는 노드(자식 노드 X)로 태그에 정의되어있는 속성을 말함
  • 텍스트 노드: 요소의 텍스트를 표현하며 자식 노드를 가질 수 없어 DOM 트리의 단말 노드가 됨
• DOM의 각 요소는 프로토타입 객체로 정의되어 있음

JS로 DOM 선택하기

• getElementById: DOM Tree에서 요소 노드를 id로 찾음, 제일 먼저 찾은 요소 하나를 반환
• getElementByClassName: DOM Tree에서 요소 노드를 class로 찾음, 일치하는 모든 요소를 반환
• getElementByTagName: DOM Tree에서 요소 노드를 태그 이름으로 찾음, 일치하는 모든 요소를 반환
• querySelector: DOM Tree에서 요소 노드를 CSS Selector 문법으로 찾음. 제일 먼저 찾은 요소 하나를 반환
• querySelectorAll: DOM Tree에서 요소 노드를 CSS Selector 문법으로 찾음. 일치하는 모든 요소를 반환
• window.[id]: id가 있는 요소는 window 객체를 통해 찾을 수 있음, 여러 개라면 리스트로 반환

DOM 탐색 방법

• parentNode: 선택한 요소 노드의 부모 노드를 불러옴
• firstElementNode: 선택한 요소 노드의 자식 요소 노드 중 첫 번째를 불러옴, 없을 경우 null 반환
• chilren: 선택한 요소 노드의 자식 요소 노드를 불러옴, 없을 경우 빈 배열 반환
• nextElementSibiling: 선택한 요소 노드의 다음 형제 요소 노드를 불러옴, 없을 경우 null 반환
• previousElementSibiling: 선택한 요소 노드의 이전 형제 요소 노드를 불러옴, 없을 경우 null 반환

DOM 조작 방법

• class 접근: 선택한 요소 노드에서 className과 classList로 요소의 class 속성을 불러오고 변경할 수 있음
• hasAttribute: 선택한 요소 노드에서 속성을 가지고 있는지 확인
• getAttribute: 선택한 요소 노드에서 속성의 값을 반환, 없을 경우 null 반환
• setAttribute: 선택한 요소 노드에서 속성을 정의
• removeAttribute: 선택한 요소 노드에서 속성을 제거
• textContent: 선택한 요소 노드에서 텍스트 노드에 접근, 변경 가능
• innerHTML: 선택한 요소 노드 내부 HTML을 수정 → XSS 위험이 있음
• createElement: 요소 노드를 태그 이름으로 생성할 수 있음
• appendChild: 선택한 요소 노드 마지막 자식 요소로 추가
• removeChild: 선택한 요소 노드 자식 노드 중 해당하는 요소를 제거

document.createDocumentFragment

• 비어있는 DocumentFragment 객체를 생성하는 메서드
• DocumentFragment는 메모리에 존재하는 가상의 문서 조각으로 실제 DOM에 직접 추가되지 않고 메모리 상에서 조작할 수 있음
• DocumentFragment를 사용하면 여러 DOM 요소를 생성하고 조작하는 작업을 효율적으로 수행할 수 있음
• DOM 요소를 동적으로 생성하여 DocumentFragment에 추가하고 나중에 한 번에 실제 DOM에 추가할 수 있음 → DocumentFragment를 사용하여 여러 요소를 조작하는 동안 불필요한 리플로우나 리레이아웃 계산이 발생하지 않아 성능 향상에 도움이 됨
• 예시 코드

  const fragment = document.createDocumentFragment();
  
  for (let i = 0; i < 5; i++) {
    const div = document.createElement('div');
    div.textContent = `div ${i}`;
    fragment.appendChild(div);
  }
  
  // 실제 DOM에 추가
  document.body.appendChild(fragment);

Virtual DOM

• 실제 DOM Tree를 JS 객체로 만든 것으로 필요한 정보만을 담아 만들어짐
• 이벤트나 DOM이 수정되는 한 틱 내에 Virtual DOM에서 바뀌는 부분만 수정한 후 렌더링하면 브라우저 렌더링 프로세스 과정이 줄어들게 됨
• Virtual DOM는 유지보수가 용이한 애플리케이션을 만들도록 도와주고 대부분의 유스케이스에서 DOM보다 충분히 빠를 뿐이지 Virtual DOM이 DOM보다 빠른 것은 아니다.