JS코테입문

시간 복잡도 O(n) 유추 방법

입력값 크기 기준

• 입력 크기(n)가 1,000,000(백만) 이하일 때 O(n) 가능성이 높음
• 1초 제한시간에 약 1억 번의 연산이 가능한 점을 고려

문제 유형별 특징

• 배열을 한 번만 순회하는 문제
• 투 포인터나 슬라이딩 윈도우 활용 문제
• 해시맵을 이용한 탐색 문제

코드 패턴

// 단일 순회
for (let i = 0; i < n; i++) {
    // 작업 수행
}

// 투 포인터
let left = 0, right = 0;
while (right < n) {
    // 작업 수행
}

// 해시맵 활용
const map = new Map();
for (let item of array) {
    // 맵 조작
}

문제 설명 키워드

• "순서대로"
• "연속된"
• "차례대로"
• "한 번의 순회로"
• "모든 원소를 한 번씩"

주의사항

• 중첩 반복문 사용 시 O(n²)가 됨
• 정렬이 필요한 경우 O(n log n)으로 변경됨
• 재귀 호출 시 호출 횟수를 고려해야 함

결론: 입력 크기, 문제 유형, 코드 패턴, 키워드를 종합적으로 분석하여 O(n) 시간 복잡도 여부를 판단.

Citations:
[1] https://pplx-res.cloudinary.com/image/upload/v1729659556/user_uploads/mxiysslxn/image.jpg
[2] https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/
[3] https://sam-repository.tistory.com/20
[4] https://easy-code-yo.tistory.com/13

---

문제 예시: 배열에서 가장 많이 등장하는 숫자 찾기

function findMostFrequent(arr) {
    // 해시맵(객체) 생성
    const numCount = {};
    let maxCount = 0;
    let mostFrequent = arr[0];

    // O(n): 배열을 한 번만 순회
    for (const num of arr) {
        // 숫자의 등장 횟수를 카운트
        numCount[num] = (numCount[num] || 0) + 1;
        
        // 최대 등장 횟수 갱신
        if (numCount[num] > maxCount) {
            maxCount = numCount[num];
            mostFrequent = num;
        }
    }

    return mostFrequent;
}

// 테스트
const numbers = [1, 2, 3, 2, 2, 4, 2, 3];
console.log(findMostFrequent(numbers)); // 출력: 2

O(n) 시간 복잡도 도출 과정

1. 문제 조건 분석

• 배열의 모든 요소를 한 번씩 확인 필요.
• 추가 배열 순회나 중첩 반복문 불필요.
• 해시맵을 통한 상수 시간 접근.

2. 최적화 포인트

• 단일 for 루프 사용.
• 객체를 활용한 O(1) 시간 접근.
• 불필요한 정렬이나 이중 반복 제거.

3. 공간 복잡도

• O(n) 공간 사용: 해시맵 저장용.
• 추가 메모리로 시간 복잡도 개선.

시간 복잡도 분석

1. 루프 연산: O(n)
2. 객체 접근: O(1)
3. 최종 시간 복잡도: O(n)

결론: 해시맵을 활용한 단일 순회로 O(n) 시간 복잡도 달성.

Citations:
[1] https://pplx-res.cloudinary.com/image/upload/v1729659556/user_uploads/mxiysslxn/image.jpg

---

선택 정렬 구현 코드

선택 정렬은 배열을 반복하면서 가장 작은 요소를 선택해 앞쪽으로 이동시키는 방식이다.

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

const exampleArray = [64, 25, 12, 22, 11];
console.log(selectionSort(exampleArray)); // [11, 12, 22, 25, 64]

reduce 메서드 예제

reduce는 배열의 각 요소에 대해 누적 계산을 수행하고 단일 값을 반환한다.

const numbers = [1, 2, 3, 4, 5];

// 합계 계산
const sum = numbers.reduce((accumulator, currentValue) => accumulator + currentValue, 0);
console.log(sum); // 15

// 중복 제거
const ageGroup = [18, 21, 1, 1, 51, 18];
const uniqueAgeGroup = ageGroup.reduce((accumulator, currentValue) => {
  if (!accumulator.includes(currentValue)) {
    accumulator.push(currentValue);
  }
  return accumulator;
}, []);
console.log(uniqueAgeGroup); // [18, 21, 1, 51]

결론: O(n) 시간 복잡도는 효율적인 알고리즘 설계의 기본이며, 선택 정렬과 reduce 메서드는 이를 이해하는 데 유용한 도구이다.

Citations:
[1] https://pplx-res.cloudinary.com/image/upload/v1729659556/user_uploads/mxiysslxn/image.jpg
[2] https://www.programiz.com/javascript/library/array/reduce
[3] https://blog.chulgil.me/algorithm/
[4] https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/
[5] https://developercc.tistory.com/1
[6] https://www.freecodecamp.org/news/javascript-reduce-method-code-examples/