JavaScript 알고리즘 & 자료구조 마스터클래스 1

Big O 표기법

O(1) - 상수 시간

• 입력 크기와 관계없이 항상 같은 시간이 걸림
• 예: 배열의 인덱스 접근, 객체의 키 접근

O(log n) - 로그 시간

• 입력이 증가할 때 실행 시간이 로그함수처럼 증가
• 예: 이진 검색

O(n) - 선형 시간

• 입력 크기에 비례하여 실행 시간이 증가
• 예: 단일 반복문

O(n log n) - 선형 로그 시간

• 대부분의 효율적인 정렬 알고리즘이 이에 해당
• 예: 퀵소트, 머지소트

O(n²) - 이차 시간

• 입력 크기의 제곱에 비례하여 실행 시간이 증가
• 예: 이중 반복문

O(2ⁿ) - 지수 시간

• 입력이 증가할 때마다 실행 시간이 2배씩 증가
• 예: 재귀 피보나치

O(n!) - 팩토리얼 시간

• 가장 비효율적인 시간 복잡도
• 예: 외판원 문제의 무차별 대입 해법

Big O 시간 복잡도

function addUpTo1(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

function addUpTo2(n) {
  return (n * (n + 1)) / 2;
}

Big O 표현식의 단순화

• 배열(인덱스 기준) 또는 객체(키 기준)의 요소에 접근하는 것은 O(1)과 같이 일정하다.
• 루프는 n만큼의 복잡도를 가지며 O(n)과 같다. 중첩문의 경우 O(n²)이다.
• 알고리즘의 성능을 비교할 때는 가장 큰 차수의 항이 결정적인 역할을 한다.
  • O(n^2 + n^3)의 경우 O(n^3)으로 단순화 할 수 있다.

공간 복잡도

• boolean, undefined, number, null은 불변의 공간이다.
  • 입력의 크기와 상관없이 똑같은 공간을 가진다.
• 문자열은 O(n)의 공간 복잡도를 가진다.
  • 50자의 문자열인 경우 1자의 문자열 보다 50배의 더 많은 공간을 차지하게 된다.
• 배열과 객체는 O(n)의 공간 복잡도를 가진다.

시간 복잡도와 공간 복잡도의 차이

• 시간 복잡도는 알고리즘이 실행되는데 걸리는 시간 또는 연산의 횟수를 나타낸다.
  • 입력값이 증가할 때 실행 시간이 어떻게 증가하는지 측정한다
• 공간 복잡도는 알고리즘이 실행될 때 필요한 추가적인 메모리 공간을 나타낸다.
  • 입력값이 증가할 때 추가 메모리 사용량이 어떻게 증가하는지 측정한다.

객체의 Big O

• 입력, 삭제, 접근은 O(1)의 시간을 가진다.
• 검색은 O(n)의 시간을 가진다.

배열의 Big O

• 입력
  • push의 경우(마지막에 넣는 경우) O(1)의 시간을 가진다.
  • 맨 앞에 추가하는 경우 O(n)의 시간을 가진다. (배열의 길이 n에 따라 index를 변경해야 한다.)
• 삭제
  • pop의 경우(마지막을 제거하는 경우) O(1)의 시간을 가진다.
  • 맨 앞을 제거하는 경우 O(n)의 시간을 가진다. (배열의 길이 n에 따라 index를 변경해야 한다.)
• 검색은 O(n)의 시간을 가진다.
• 접근은 O(1)의 시간을 가진다.

문제의 이해

문제를 내 방식대로 다시 설명할 수 있나요?

• 문제를 자신의 언어로 다시 표현해보세요.
• 다른 사람에게 설명하듯이 정리해보세요.
• 핵심 요구사항을 파악하세요.

문제에 들어가는 입력값들은 무엇인가요?

• 파라미터의 종류와 개수는 무엇인가요?
• 입력값의 데이터 타입은 무엇인가요?
• 입력값의 범위나 크기는 어떻게 되나요?

문제의 해결책에서 나와야 하는 출력값은 무엇인가요?

• 어떤 형태의 결과를 반환해야 하나요?
• 출력값의 데이터 타입은 무엇인가요?
• 예상되는 결과값의 형식은 어떠한가요?

입력값들로부터 출력값을 결정할 수 있나요?

• 주어진 입력값으로 문제를 해결하기에 충분한가요?
• 추가적인 정보가 필요한가요?
• edge case(경계 조건)는 어떻게 처리해야 하나요?
• 이 단계에서 완벽한 답을 할 수 없더라도, 고민해보는 것이 중요합니다.

문제의 일부인 중요한 데이터들을 어떻게 라벨링해야 할까요?

• 사용할 변수들의 이름을 어떻게 정할까요?
• 데이터의 구조를 어떻게 조직화할까요?
• 핵심 정보들을 어떻게 체계적으로 관리할까요?

세부 분석

• 문제의 요구사항을 주석으로 먼저 작성하여 단계별로 정리한다.
• 각 단계에서 필요한 로직을 의사코드(pseudocode)로 표현한다.
• 예상되는 edge case들을 미리 파악하고 처리 방법을 계획한다.
• 필요한 헬퍼 함수나 유틸리티 함수들을 미리 식별한다.

이러한 세부 분석 과정을 통해

• 복잡한 문제를 작은 단위로 분해할 수 있다.
• 구현 전에 발생할 수 있는 문제점들을 미리 파악할 수 있다.
• 더 체계적이고 효율적인 코드를 작성할 수 있다.

되돌아보기

리팩토링

1. 코드 가독성 개선

   • 변수와 함수명이 명확한가?
   • 코드의 들여쓰기와 포맷팅이 일관적인가?
   • 복잡한 로직에 대한 주석이 충분한가?

2. 성능 최적화

   • 시간 복잡도를 개선할 여지가 있는가?
   • 공간 복잡도를 줄일 수 있는 방법이 있는가?
   • 불필요한 연산이나 반복문이 있는가?

3. 코드 구조 개선

   • 중복된 코드를 제거할 수 있는가?
   • 함수나 모듈로 분리할 수 있는 부분이 있는가?
   • 더 적절한 자료구조를 사용할 수 있는가?

리팩토링 접근 방법

1. 점진적 개선

   • 한 번에 한 가지 측면만 개선하기
   • 각 변경 사항 후 테스트 수행하기
   • 성능 측정을 통한 개선 효과 확인하기

2. 코드 재사용성

   • 유틸리티 함수 추출하기
   • 공통 로직 모듈화하기
   • 확장 가능한 구조로 개선하기

3. 에러 처리 보완

   • 예외 상황 처리 로직 추가하기
   • 에러 메시지 명확하게 작성하기
   • 디버깅을 위한 로깅 개선하기