오늘 배운 내용

1. 자료구조 & 알고리즘 중요한 이유
2. 자료구조 & 알고리즘의 종류
3. 시간복잡도
4. 배열
5. 연결리스트
6. 스택
7. 올바른 괄호 사용 및 괄호 문제 풀이

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

자료구조는 단순구조 -> 정수, 실수, 문자열, 논리 , 선형 구조 -> 배열, 연결리스트, 스택, 큐, 비선형 구조 -> 트리, 그래프 로 이루어져있다.

선형구조

한 원소 뒤에 하나의 원소 만이 존재하는 형태. 자료들이 선형으로 나열되어 있는 구조.

배열의 특징

• 고정된 크기를 가지고 동적으로 크기를 늘릴 수 없다.
  • 자바스크립트처럼 대부분의 스크립트 언어는 동적으로 크기가 증감될 수 있다.
• 원하는 원소의 index를 알면 O(1)로 원소를 찾음.
• 원소를 삭제하면 해당 index에 빈자리가 생김.

배열의 요소 삭제

삭제 후 순서를 맞추려면 최악의 경우 O(n)이 소요.

배열의 요소 추가

추가 후 순서를 맞추려면 최악의 경우 O(n)이 소요.

연결리스트 특징

연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조. 각 요소는 노드라고 부르고 데이터 영역과 포인터 영역으로 구성

• 메모리가 허용하는 한 요소를 제한없이 추가 가능
• 탐색은 O(n) thdy
• 요소 추가하거나 제거할 때는 O(1) thdy
• Singly Linked List, Doubly Linked List, Circular Linked List가 존재.

Singly Linked List

Head에서 Tail까지 단방향으로 이어지는 연결리스트로 가장 단순한 형태의 연결리스트이다.

Doubly Linked List

양방향으로 이어지는 연결 리스트. Singly Linked Lis보다 자료 구조의 크기가 조금 더 크다.

배열과 연결리스트의 차이점

비선형 구조

원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기 적절.

특정 문제를 효율적이고 빠르게 해결하는 것이 궁극적인 목표. 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 말한다.

그렇다면 자료구조와 알고리즘은 왜 중요할까?

실무에서 중요하게 생각하는 3가지

1. 기초 코딩 능력 - 논리적 사고 중요
2. 전문 분야 지식
3. 기본 CS 지식

문제 해결 능력에서 중요한 3가지

1. 논리적 사고
2. 전산화 능력
3. 엣지 케이스 탐색

빅오 표기법

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

빅오 표기법엔 4가지 법칙이 존재한다

1. 계수 법칙
2. 덧셈 법칙
3. 곱셈 법칙
4. 다항 법칙

자바스크립트에서 성능을 확인하는 방법

Date 객체 이용

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

~~~~~~
  
const end = new Date().getTime();
console.log(end - start);

Doubly Linked List 기반 Circular Linked List

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
        this.pre = null;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    // 탐색하기
    find(data) {
        let curNode = this.tail;
        
        // 원하는 데이터를 찾을 때까지 무한 반복
        while (curNode.value !== data) {
            // 예외 처리 부분
            if (curNode.pre === this.tail) return false;
            curNode = curNode.pre
        }

        // 찾고자하는 데이터 리턴
        return curNode;
    }

    // 데이터 추가
    append(newData) {
        const newNode = new Node(newData);
        // 연결리스트가 비어있을 경우 새로 들어온 데이터가 head이자 tail
        if (this.head === null) {
            this.head = newNode;
            this.tail = newNode;
        } else { 
          // 리스트를 tail 쪽으로 계속 생성해 나가 tail이 head를 바라보게 하면 무한루프에 빠짐
          // 무한루프에 빠지지 않게 하기 위해 head의 pre가 tail을 바라보게 설정
            this.head.pre = newNode;
            this.tail.next = newNode;
            newNode.pre = this.tail;
            this.tail = newNode;
        }

        // 개수 증가
        this.length ++;
    }

    // 데이터 중간 삽입
    insert(node, newData) {
        // 예외 처리
        if (node === false) return console.log("찾으려는 데이터를 찾지 못해 데이터를 삽입할 수 없습니다.");

        const newNode = new Node(newData);
        // 새로 들어온 노드가 이전 노드의 다음 노드를 가리키고
        newNode.next = node.next;
        // 새로 들어온 노드는 이전 노드를 가리키고
        newNode.pre = node;
        // 다음 노드는 새로 들어온 노드를 가리키고
        newNode.next.pre = newNode;
        // 이전 노드는 새로 들어온 노드를 가리킨다
        node.next = newNode;

        // 개수 증가
        this.length ++;
    }
    
    // 데이터 삭제 (데이터 삭제를 위해 데이터 탐색부터 하는 로직 시간복잡도 O(n))
    remove(data) {
        let preNode = this.tail;
        // 원하는 데이터 찾을때까지 무한 반복
        while (preNode.pre.value !== data) {
            // 예외 처리 부분
            if (preNode.pre.pre === this.tail) return console.log("삭제하려는 데이터를 찾을 수 없습니다.");
            preNode = preNode.pre
        }
        // 찾고자하는 데이터를 찾았으면 현재 데이터가 찾은 데이터의 다음 데이터를 가리키게 만듬 -> 추후 JS의 가비지 컬렉터에 의해 사용되지 않는 찾은 데이터는 사라지게 됨.
        if (preNode.pre !== null) {
            preNode.pre = preNode.pre.pre;
            preNode.pre.next = preNode; 
            // 개수 감소
            this.length --;
        }
    }

    dispaly() {
        let curNode = this.head;
        let displayString = "[";
        while (curNode !== null) {
            displayString += `${curNode.value}, `;
            curNode = curNode.next;
        }

        displayString = displayString.substr(0, displayString.length - 2);
        displayString += "]";
        console.log(displayString);
    }

    size() {
        console.log(this.length);
    }
}

const linkedList = new DoublyLinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);
linkedList.append(5);
linkedList.dispaly();

linkedList.remove(10);
linkedList.insert(linkedList.find(100), 200)
linkedList.dispaly();
linkedList.remove(200);
linkedList.dispaly();
linkedList.size();

실행 결과

[1, 2, 3, 4, 5]
삭제하려는 데이터를 찾을 수 없습니다.
찾으려는 데이터를 찾지 못해 데이터를 삽입할 수 없습니다.
[1, 2, 3, 4, 5]
삭제하려는 데이터를 찾을 수 없습니다.
[1, 2, 3, 4, 5]
5

function solution(s){
    let stack = [];
    
    for (let bracket of s) {
        // 열린 괄호일 때 stack에 삽입
        if (bracket === "(") stack.push("(");
        else {
            // 닫힌 괄호일 때 스택의 길이가 0이면 올바른 괄호가 나올 수 없으므로 false 리턴
            if (stack.length === 0) return false;
            // 스택의 길이가 1 이상이면 pop
            else stack.pop();
        }
    };
	// 열린 괄호가 남아 있으면 false 그렇지 않으면 true
    return stack.length > 0 ? false : true;
};

느낀점

오늘은 대부분 알았던 내용이라 어렵진 않았지만, 연결리스트를 직접 구현해본지 너무 오래돼서 다시 구현하는데 시간이 좀 오래걸렸다. 기본부터 다시 열심히하자!