1. Understand the problem

  • 문제를 자신의 방식으로 다시 말할 수 있는지?
  • 문제에 들어가는 입력 데이터는 무엇인지?
  • 해결책에서 얻을 수 있는 결과는 무엇인지?
  • 문제를 해결할 충분한 정보를 가지고 있는지?
  • 함수나 변수 등의 이름은 어떻게 정할 것인가?

2. Explore examples

  • 간단한 예제로 시작하기
  • 더 복잡한 예제 진행하기
  • 빈 입력값을 가진 예제로 테스트하기
  • 잘못된 입력값을 가진 예제로 테스트하기

3. Break it down

  • 수행해야 할 단계를 명시적으로 기록하기

4. Solve or Simplify

  • 문제를 해결하거나 더 간단한 문제 해결하기

5. Look back and Refactor

  • 결과를 확인할 수 있는지?
  • 결과를 다르게 할 수 있는지?
  • 한번에 코드를 이해할 수 있는지?
  • 다른 문제에서도 결과값이나 함수를 사용할 수 있는지?
  • 수행 시간이 적절한지?
  • 다른 방법으로 문제를 해결할 수 있는지?
  • 다른 사람들은 이 문제를 어떻게 풀었는지?

What does better mean?

1. Faster?

2. Less memory-intensive?

3. More readable?

 

The Problem with Time

1. Different machines will record different times

2. The same machine will record different times

 

다른 performance 측정법

Counting Operations이 있지만 연산자를 세는 방법은

힘들고 시간이 오래 걸린다.

 

Big O 정의

간단한 연산들은 컴퓨터가 최대 f(n)번 해야한다면 알고리즘은 O(f(n))이다.

f(n)은 상수형, 선형 등 형태가 다양하다.

 

1. f(n)이 2n일 때 상수는 무시되고 O(n)이 된다.

2. f(n)의 최고차항만 남긴다.

 

O(1)

O(n)과 같이 보이지만 i가 10 이후부터 연산 개수가 증가하지 않기 때문에 O(1)이다!!

function logAtMost10(n) {
  for (var i = 1; i <= Math.min(n, 10); i++) {
    console.log(i);
  }
}

 

Space Complexity

boolean, number, undefined, null은 상수이다.

String 공간 복잡도는 O(n)이다.

참조형은 일반적으로 O(n)이고 n은 배열 길이나 object key 개수이다.

+ Recent posts