[TIL004]

<1> 코딩테스트 문제 유형 파악하기

입력값 제한에 따른 분류

1. 100이하 : 완전탐색, 백트래킹

2. 10,000 이하

• 최대 O(n^2), 문제에 따라 O(n^2 log n)까지
• n*n 2차원 리스트를 모두 순회해야하는 문제가 많음

3. 1,000,000 이하

• 최대 O(n log n)
• 힙, 우선순위 큐
• 정렬
• 동적 계획법
• 위상 정렬
• 다익스트라 알고리즘

4. 100,000,000 이하

• 최대 O(n)
• 동적 계획법
• 그리디

5. 그 이상

• 최대 O(log n)
• 이진탐색

문제 유형

• 입력값이 작은 문제

  • 완전탐색
  • 백 트래킹

• 지도가 주어지고 채워진 영역을 찾아야하는 경우

  • BFS, DFS
  • FloodFill, 전염병 문제, 치즈 문제

• 그래프 그림

  • 최단 거리 찾기: BFS, DFS, 다익스트라
  • 최소 신장 트리(최소 비용 문제): 크루스칼, 프림 알고리즘
  • 위상 정렬: 순서, 차례 관련

• 특정 조건을 만족하는 최대/최소값

  • 파라메트릭 서치(결정 문제)

• 실시간으로 정렬이 이루어져야하는 경우

  • 우선순위 큐, 힙

• DP 문제

  • 시간이 오래걸리면 안 되고, 특별한 알고리즘을 사용하지 않을 때
  1. 문제를 따라 먼저 초기값을 적는다
  2. 초기값을 포함해 모든 상태값을 적는다
  3. 현재 상태를 통해 다음 값을 구할 수 있는지 판단한다
  4. 혹은, 이전 상태들을 통해 현재 값을 구할 수 있는지 판단한다

• 문자열이 주어지는 경우

  • 구현력 (알고리즘 딱히 필요없음)

• 현재 상황에서 최적의 선택

  • 그리디

엣지케이스

• 입력 값이 굉장히 작은/큰 경우
• 입력 값의 범위가 넓은 경우
• 음수 입력 허용시, 음수만 받는 경우
• 리스트 입력 시, 값이 없거나 하나만 있는 경우
• 기타: 그래프에서 사이클이 발생하는 경우, 길찾기에서 지그재그, 부동소수점 오차

<2> 이터레이터/이터러블

정의

이터러블(iterable) : 이터레이터를 리턴하는 [Symbol.iterator]()를 가진 값
이터레이터(iterator) : { value, done} 을 리턴하는 next()를 가진 값
이터러블/이터레이터 프로토콜 : 이터러블을 for...of, 전개 연산자 등과 함께 동작하도록 한 규약

등장 배경

ES6에서 배열 등을 순회할 때 사용하는, for...of 가 추가
이를 통해 내부 순회를 돌 수 있는 속성이 이터러블

이전 문법과의 차이점

for...i++은 배열만 순회 가능하지만,
for...of는 배열, 객체, 그리고 ES6에서 추가된 Map, Set 객체도 순회가 가능하다.

/// array
const arr = [1, 2, 3];
for (const a of arr) log(a); //1, 2, 3
for (let i = 0; i < arr.length; i++) log(arr[i]); // 1, 2, 3

// set
const set = new Set([1, 2, 3]);
for (const a of set) log(a); // 1, 2, 3
for (let i = 0; i < set.length; i++) log(set[i]); // undefined

//map
const map = new Map([
  ["a", 1],
  ["b", 2],
  ["c", 3],
]);
for (const a of map) log(a); // ["a", 1], ["b", 2], ["c", 3],
for (let i = 0; i < map.length; i++) log(map[i]); // undefined

사용자 정의 이터러블 예시

const iterable = {
  [Symbol.iterator]() {
    let i = 3;
    return {
      next() {
        return 1 == 0 ? { done: true } : { value: i--, done: false };
      },
      //well-formed 조건
      [Symbol.iterator]() {
        return this;
      },
    };
  },
};
let iterator = iterable[Symbol.iterator]();

• well-formed iterable/iterator
  자기자신을 반환하는 Symbol.iterator 메서드를 가지고 있을 때.
  자기자신의 상태를 기억.
  반복 진행상황 기억 가능.

제너레이터

이터레이터이자 이터러블을 생성하는 함수

특징

• 함수 앞에 *을 붙임
• yield를 통해 몇 번의 next를 도출할지를 설정 가능
• return값 할당 가능 (순회 시 포함x, 완료시 반환)

  function* gen() {
    yield 1;
    yield 2;
    yield 3;
    return 100;
  }

이터레이터, 이터러블, 제너레이터 처음 들어본 개념이다.
ES6에서 for...of 문법이 생긴건 알고 있었지만, 기존과 차이를 몰라 익숙했던 for...i++문법을 애용했는데 앞으로 새로운 문법을 사용하는 연습을 해야겠다.
객체 키-밸류 값 받아올 때도 Object.keys() 쓰곤 했는데 이거 쓰면 훨씬 나아지겠지.
이번 기회에 아직 낯설기만 한 Map, Set 오브젝트를 스터디 주제로 다뤄볼까 생각 중이다.