자료구조와 알고리즘

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

비선형구조: 원소간 다대다 관계를 가지는 구조.

시간복잡도

1. 배열(순차리스트)

배열(순차리스트)는 요소를 삭제/삽입하는 데에 부적절하다. 탐색할 때에 좋은 자료구조.

2. 연결리스트

연결리스트를 설명하는 좋은 블로그!
https://overcome-the-limits.tistory.com/16

• 연결리스트의 구조를 이미지로 설명하고 있음
• 연결리스트의 종류를 장단점과 함께 설명함
• 배열과 연결리스트의 차이점이 기재되어 있음
• JS로 연결리스트를 구현하는 것에 앞서, Abstract Data Type을 자세히 설명함
• JS로 연결리스트를 구현하는 코드에 주석이 상세함.
• 참고에 기재해 둔 책/글들이 유용함

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

메모리가 허용하는 한 요소를 제한없이 추가할 수 있다.

(1) SinglyLinkedList

SinglyLinkedList 구현 코드

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  find(value) {
    let currNode = this.head;
    while (currNode.value !== value) {
      currNode = currNode.next;
    }
    return currNode;
  }

  append(newValue) {
    const newNode = new Node(newValue);
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  insert(node, newValue) {
    const newNode = new Node(newValue);
    newNode.next = node.next;
    node.next = newNode;
  }

  remove(value) {
    let prevNode = this.head;
    while (prevNode.next.value !== value) {
      prevNode = prevNode.next;
    }

    if (prevNode.next !== null) {
      prevNode.next = prevNode.next.next;
    }
  }

  display() {
    let currNode = this.head;
    let displayString = "[";
    while (currNode !== null) {
      displayString += `${currNode.value}, `;
      currNode = currNode.next;
    }
    displayString = displayString.substr(0, displayString.length - 2);
    displayString += "]";
    console.log(displayString);
  }
}

const linkedList = new SinglyLinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(5);
linkedList.display();
console.log(linkedList.find(3));
linkedList.remove(3);
linkedList.display();
linkedList.insert(linkedList.find(2), 10);
linkedList.display();

size 메서드 추가하기

size() {
    let currNode = this.head;
    let cnt = 0;
    while (currNode !== null) {
      cnt++;
      currNode = currNode.next;
    }
    console.log("Size of Singly Linked List is", cnt);
}

모든 예외를 찾아 수정하기

find(value) {
    let currNode = this.head;
    while (currNode.value !== value) {
      currNode = currNode.next;
      //1. 찾는 value가 없을 때
      if (currNode.next === null) {
        return `There is not ${value}`;
      }
    }
    return currNode;
}
insert(node, newValue) {
    //2. 추가하려는 value가 find메서드의 결과값이고, 이것이 null값일 때
    if (node === null) {
      return `There is not ${node}`;
    }
    const newNode = new Node(newValue);
    newNode.next = node.next;
    node.next = newNode;
}
remove(value) {
    let prevNode = this.head;
    //3. 리스트가 비어 있을 때
    if (prevNode === null) {
      return "LinkedList is empty";
    }
    //4. 리스트의 헤드를 삭제할 때
    if (prevNode.value === value) {
      this.head = prevNode.next;
      return;
    }
	//5. 삭제하려는 value가 없을 때
    while (prevNode.next.value !== value) {
      prevNode = prevNode.next;
      if (prevNode.next === null) {
        return `There is not ${value}`;
      }
    }
    if (prevNode.next !== null) {
      prevNode.next = prevNode.next.next;
    }
}
display() {
    let currNode = this.head;
    //6. 리스트가 비어 있을 때
    if (currNode === null) {
      return "LinkedList is empty";
    }
    let displayString = "[";
    while (currNode !== null) {
      displayString += `${currNode.value}, `;
      currNode = currNode.next;
    }
    displayString = displayString.slice(0, -2);
    displayString += "]";
    console.log(displayString);
}

(2) DoublyLinkedList

추후 추가 예정

(3) CircularLinkedList

추후 추가 예정

3. 스택

데이터를 한 줄로 쌓아서 탑을 쌓는 듯한 형태의 자료구조. 스택의 맨 위에 데이터를 추가하는 것을 push라고 하고, 맨 위의 데이터를 하나씩 제거하는 것을 pop이라고 한다. LIFO 형태

실습과제

• 첫번째 시도 코드 아이디어와 결과
  쉽군... 배열에 문자열을 하나씩 넣다가 ')'를 만나면 배열에서 요소를 pop해줘야겠어. 최종적으로 배열의 길이가 0이라면 올바른 괄호겠군! 쏘2지

function solution(s){
    let arr=[];
    for(let i=0; i<s.length; i++){
        if(s[i]===")"){
            arr.pop();
        } else {
            arr.push(s[i]);
        }
    }
    return arr.length===0 ? true : false ;
}

???????

• 두번째 시도 코드 아이디어와 결과
  아... 배열 마지막 문자가 "("이어야만 pop해야 유효하네...

function solution(s){
    let arr=[];
    for(let i=0; i<s.length; i++){
        if(s[i]===")" && arr[arr.length-1]==="("){
            arr.pop();
        } else {
            arr.push(s[i]);
        }
    }
    return arr.length===0 ? true : false ;
}

통과

강사님 코드