[DAY-4] JS 주요문법 (3)

박민우·2023년 6월 6일

TIL devcourse 프로그래머스 프론트엔드

✏️ TIL

목록 보기

4/6

💡 오늘부터는 자료구조와 알고리즘에 대한 내용이다. 자바스크립트로 코딩테스트를 준비하기로 결정한 만큼, JS로 자료구조를 다루고 알고리즘을 짜는 것에 익숙해지자 !

[1] - 자료구조와 알고리즘이 중요한 이유

요리할 때의

재료 + 도구 + 레시피 => 음식

개발할 때의

데이터 + 자료구조 + 알고리즘 => 프로그램

우리가 라면을 끓일 때 칼을 쓰지는 않는 것처럼

요리를 할 때에는 재료에 따른 도구 사용 이 정말 중요하다 !

이처럼, 프로그램을 만들 때에도 데이터에 맞는 자료구조 를 활용해야 한다 !

찰떡 비유 ㄷㄷ👍🏻

[2] - 자료구조의 종류

📌 자료구조

메모리를 효율적으로 사용 하며 빠르고 안정적으로 데이터를 처리 하는 것이 궁극적인 목표로, 상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있다.

그렇다,,,

자료구조는 현실의 문제를 해결하기 위해, 일차원인 컴퓨터 메모리를 현실에 대응되도록 여러가지 구조를 만든 것이다 ! 이를 통해 더욱 메모리를 효율적으로 사용하고, 빠르고 안정적으로 데이터를 처리할 수 있다.

그냥 어찌저찌 작동만 되게 구현하는 코더가 되고 싶지 않으면, 효율적인 코드를 위해서는 자료구조는 꼭 알아야 한다 🤐

자료구조의 종류

자료구조

단순구조
- 정수
- 실수
- 문자열
- 논리
- 선형 구조 => 각 데이터는 앞뒤의 데이터들과만 연관 관계를 갖는다.
- 배열
- 연결 리스트
- 스택
- 큐
비선형 구조 => 데이터 간 다대다 연관 관계를 가질 수 있다.
- 트리
- 그래프

[3] - 시간 복잡도

우리는 프로그램의 성능을 정확히 알 수 있을까 ?

=> 입력 크기, 하드웨어 성능, 비동기 로직 등등,,, 고려할게 너무 많다

=> 불가능

=> 대략적인 성능을 비교하기 위한 상대적인 표기법을 사용하기로 약속함

📌 Big-O notation

O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n) < O(n!)

선형 시간 O(n)

for(let i=0;i<n;i++){
    /// ..
}

로그 시간 O(log n)

for(let i=1; i<=n; i*=2){
    /// ..
}

선형 지수 시간 O(n log n)

for(let i=0; i<n; i +=1){
    for(let j=1;j<=n;j*=2){
    /// ..
    }
}

2차 시간 O(n2)

for(let i=0; i<n; i +=1){
    for(let j=0; j<n; j +=1){
    /// ..
    }
}

Big-O 표기법은 점근적 표기법 을 따른다

점근적 표기법

함수의 증감 추세를 비교하는 방법

Big-O notation의 특징

상수항은 무시해도 된다
가장 큰 항 외에는 무시해도 된다

코드의 실제 성능을 측정하기 위해서 JS의 Date 객체를 이용할 수 있다.

const start = new Date().getTime();

// ...

const end = new Date().getTime();
console.log(end - start);
// 시작 시간 - 끝 시간 => 로직이 걸린 시간

[4] - 배열

배열

연관된 데이터들을 연속적인 형태로 구성된 자료구조

보통 스크립트 언어는 동적으로 배열의 크기가 증감되도록 만들어져 있다.

배열의 특징

탐색 시, O(1)의 시간복잡도가 소요
배열 요소의 추가와 삭제 시, O(n)의 시간 복잡도가 소요

=> 추가와 삭제보다는 탐색 연산이 필요할 때 배열을 사용하는 것이 권장된다
JS의 Array는 HashMap에 가깝다

=> index가 숫자가 아닌 문자열도 가능

=> JS의 Array가 근본적으로 object 이기 때문.

[5] - 연결 리스트

📌 연결리스트

각 요소를 포인터로 연결하여 관리하는 선형 자료구조
배열과는 다르게 추가와 삭제가 반복되는 로직에 적합하다

연결리스트의 특징

탐색은 O(n)이 소요된다.
요소를 추가하거나 제거할 때는 O(1)이 소요된다.

배열과의 차이점

메모리 차이
- 배열은 순차적인 데이터가 들어가기 때문에 메모리의 영역을 연속적으로 사용
- 연결 리스트는 연속적이지 않은 메모리 사용 => 각 메모리를 참조하기 위해 포인터 사용
시간 복잡도
- 요소 탐색 : 배열은 O(1), 연결리스트는 O(n)
- 요소 추가/삭제 : 배열은 O(n), 연결 리스트는 O(1)

📌 Singly Linked List

Head에서 Tail까지 단방향으로 이어지는 연결리스트

Singly Linked List의 핵심 로직

요소 찾기

Head 포인터부터 시작해 내가 찾는 요소인지 계속 확인하면서 포인터를 따라가야 함 => O(n)
요소 추가

1 => 2 => 4 => 5 => .... 이런 구조일 때, 2와 4 사이에 3을 추가하고 싶다면
1. 3의 포인터 영역이 4를 가리키도록
2. 2의 포인터 영역이 3을 가리키도록만 해주면 됨 !
=> O(1) (대신, 추가하고 싶은 위치의 포인터를 알고 있다고 가정했을 때)
요소 삭제

1 => 2 => 4 => 5 => ... 구조일 때, 2를 삭제한다면 ?
1. 1의 포인터 영역이 4를 가리키도록 바꿔준다.
이때, 삭제된 노드 2는 나중에 garbage collector에 의해서 메모리가 해제된다.

📌 Doubly Linked List

양방향으로 이어지는 연결리스트로

이전 노드를 가리키는 포인터 next
다음 노드를 가리키는 포인터 prev 를 가지고 있음

Doubly Linked List의 핵심 로직

요소 찾기

Head 포인터부터 시작해 내가 찾는 요소인지 계속 확인하면서 포인터를 따라가야 함 => O(n)
요소 추가

1 <=> 2 <=> 4 <=> 5 <=> .... 이런 구조일 때, 2와 4 사이에 3을 추가하고 싶다면
1. 3의 next가 4를 가리키도록
  
  4의 prev가 3을 가리키도록
2. 2의 next가 3을 가리키도록
  
  3의 prev가 2를 가리키도록
=> O(1) (대신, 추가하고 싶은 위치의 포인터를 알고있다고 가정했을 때)
요소 삭제

1 <=> 2 <=> 4 <=> 5 <=> ... 구조일 때, 2를 삭제한다면 ?
1. 1의 next가 4를 가리키도록
2. 4의 prev가 1을 가리키도록
3. 2 노드 삭제

📌 Circular Linked List

SLL 혹은 DLL 에서 Tail이 HEAD로 연결되는 리스트

[6] - 스택

LIFO의 구조를 가지는 자료구조 !

스택 메모리

스택 자료구조를 이용하는 가장 대표적인 예시는 스택 메모리이다.

스택 메모리는 함수가 호출되며 생성되는 지역변수, 매개변수가 저장되는 메모리 영역

스택을 코드로 표현하는 2가지 방법

Array로 표현하기

push, pop 으로 구현

JS에서는 보통 array로 사용함
Linked List로 구현하기

✏️ Stack 실습 문제 풀이

< 프로그래머스 85579번 올바른 괄호 >

내 풀이

function solution(s){
    let stack = [];
    
    for(let word of s){
        if(word === '('){
            stack.push(1);
        }
        else{
            if(stack.length === 0)
                return false;
            stack.pop();
        }    
    }
    
    return (stack.length === 0) ? true : false; 
}

solution

const stack = []; 로 선언해 주기 => 그래도 배열의 요소 변경 가능
마지막 줄 return (stack.length === 0) ;로 줄일 수 있음

참고 및 출처

박민우

꾸준히, 깊게

이전 포스트

[DAY-3] JS 주요문법 (2)

다음 포스트