[TIL] 20250325화 (자바스크립트의 배열, 연결리스트, 완전탐색(모의고사), reduce와 filter의 시간복잡도 계산)

2025-03-25

1) 자바스크립트의 배열

`for...of`는 배열의 반복에서 사용되고,
`for...in`은 객체의 반복에서 사용된다.

 

`unshift`, `shift` (배열의 맨앞)

`pop`, `push` (배열의 맨뒤)

 

`Array(5).fill(0)` ➡ 5개의 원소가 들어있는 배열을 모두 0으로 초기화 ex) [ 0, 0, 0, 0, 0 ]

 

인파 자바스크립트 배열 → 자바스크립트에서 제공하는 배열의 특징을 잘 정리해 놓은 블로그

 

2 ) 자바스크립트 반복문

🔹 문자열 반복

문자열을 반복할 때는 for, split + map/forEach, for...of 등을 사용할 수 있다.

1. for문 이용

const str = "hello";
for (let i = 0; i < str.length; i++) {
  console.log(str[i]);
}

2. split 후 map 또는 forEach 이용

문자열을 배열로 변환한 후 map이나 forEach를 사용할 수도 있다.

const str = "hello";
str.split("").forEach(char => console.log(char));

3. for...of 사용

const str = "hello";
for (const char of str) {
  console.log(char);
}

---

🔹 배열 반복

배열을 순회할 때 사용할 수 있는 반복문이 많다.

1. map 사용 (새로운 배열 반환)

const arr = [1, 2, 3];
const doubled = arr.map(num => num * 2);
console.log(doubled); // [2, 4, 6]

2. forEach 사용 (반환값 없음)

const arr = [1, 2, 3];
arr.forEach(num => console.log(num));

3. for...of 사용

const arr = [1, 2, 3];
for (const num of arr) {
  console.log(num);
}

---

🔹 객체 반복

객체의 키(key), 값(value), 키-값 쌍을 반복하는 방법이 있다.

1. Object.keys(obj) → 키(key) 반복

const obj = { a: 1, b: 2, c: 3 };
Object.keys(obj).forEach(key => console.log(key));
// 출력: a, b, c

2. Object.values(obj) → 값(value) 반복

const obj = { a: 1, b: 2, c: 3 };
Object.values(obj).forEach(value => console.log(value));
// 출력: 1, 2, 3

3. Object.entries(obj) → 키와 값 둘 다 반복

const obj = { a: 1, b: 2, c: 3 };
Object.entries(obj).forEach(([key, value]) => {
  console.log(`${key}: ${value}`);
});
// 출력: a: 1, b: 2, c: 3

 

 

3) 바킹독 알고리즘 배열 읽음, 링크드 리스트 읽는 중

자바스크립트로 `linked list` 구현

https://www.freecodecamp.org/korean/news/implementing-a-linked-list-in-javascript/

자바스크립트로 연결 리스트를 구현하는 방법

 

 

4) 프로그래머스 Lv1. 완전탐색 - 모의고사 문제 품

function solution(answers) {
    var answer = Array(3).fill(0);
    let su1 = [1, 2, 3, 4, 5];
    let su2 = [2, 1, 2, 3, 2, 4, 2, 5];
    let su3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    
    for(let i = 0; i < answers.length; i++) {
        if(answers[i] === su1[i % su1.length]) {
            answer[0]++;
        } 
        if(answers[i] === su2[i % su2.length]) {
            answer[1]++;
        } 
        if(answers[i] === su3[i % su3.length]) {
            answer[2]++;
        }
    }
    
    // 제일 많이 맞춘 사람 구하기
    let max = Math.max(...answer);
    let final = answer.reduce((indexes, num, i) => {
        if (num === max) indexes.push(i + 1);
        return indexes;
    }, []);
    
    return final.sort((a, b) => a-b);
}

📌 총 시간 복잡도 정리

단계	연산 횟수	시간 복잡도
점수 계산 (for 루프)	≈ 3 × N	O(N)
Math.max(...answer)	1	O(1)
reduce()로 인덱스 찾기	≤ 3	O(1)
sort() (최대 3개 정렬)	≤ 3 log 3	O(1)

📢 최종 시간 복잡도:
🔹 O(N) + O(1) + O(1) + O(1) = O(N)
즉, 이 알고리즘은 O(N) 으로 동작하며, N = 10,000일 때에도 효율적이다.

 

프로그래머스 인기 답안 중, 가장 첫번째 답안인`filter`을 3번 사용한 답안은 for문을 3번 돌리는 것과 유사한 시간복잡도를 가진다. 따라서, 시간 복잡도 측면에서 효율적이지는 않다.

 

추가적으로 `filter`, `reduce`의 시간복잡도에 대해 궁금증이 생겨 조사해 보았다.

🔍 JavaScript `filter()`와 `reduce()`의 시간 복잡도

✅ 1. `filter()`의 시간 복잡도

const result = array.filter((element) => condition);

• filter()는 배열의 각 요소에 대해 주어진 조건을 검사해야 함.
• 즉, N개의 요소를 가진 배열이라면 N번 반복하며 조건을 체크.
• 시간 복잡도:
  • 최악의 경우: O(N) (배열의 모든 요소를 검사해야 함)
  • 최상의 경우: O(N) (여전히 모든 요소를 확인해야 함)

예제

const arr = [1, 2, 3, 4, 5];
const filtered = arr.filter(num => num % 2 === 0); // O(N)

👉 결론: `filter()`는 기본적으로 O(N)

---

✅ 2. `reduce()`의 시간 복잡도

const result = array.reduce((acc, element) => {
    return operation;
}, initialValue);

• reduce()는 배열을 처음부터 끝까지 한 번 순회하며 누적 연산을 수행.
• N개의 요소에 대해 반복 1번 + 연산 수행 → 총 N번 실행
• 시간 복잡도:
  • 일반적인 경우: O(N)
  • 단, `reduce()` 내부에서 추가적인 `map()`, `filter()` 등 O(N) 연산을 호출하면 O(N²)로 증가할 수 있음

예제

const sum = arr.reduce((acc, num) => acc + num, 0); // O(N)

👉 결론: `reduce()`도 기본적으로 O(N)

---

🚀 최종 정리

메서드	시간 복잡도	설명
filter()	O(N)	각 요소를 조건과 비교하며 새 배열 생성
reduce()	O(N)	배열을 한 번 순회하면서 누적 연산 수행

🔥 추가적인 최적화 팁

• `filter()`는 새로운 배열을 반환하기 때문에, 메모리를 절약하려면 for 문을 고려
• `reduce()` 내부에서 추가적인 반복문 (`map()`, `filter()`, `forEach()`)를 사용하면 성능 저하 가능

👉 따라서, N이 크다면 for 문을 고려하는 것이 가장 빠른 해결책! 🚀