[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 문을 고려하는 것이 가장 빠른 해결책! 🚀