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

😉 헷갈렸던 & 몰랐던 부분들만 정리하는 나만의 TIL
😯 모든 강의 내용은 적지 않아요!

오늘의 소감은?
너무 유익한 수업이었다.
특히 Big-O 표기법을 대략적으로만 알고 있었는데 정말 차근차근 들여다볼 수 있는 좋은 기회였다.

또한 역시 코드 작성은 너무나도 재밌다.
이론 공부만 하다가 코드 작성하니 환기되는 기분이었다..

DoublyLinkedList 구현하는데 조금 애를 먹었다. 😣
자꾸 순회 구조가 생겨서 [Circular *n]이 출력되는.. 나의 못난이 코드

코딩 테스트 대비 문제만 풀다가, 이렇게 근본적인 자료구조 문제를 푸는 것도 오랜만인데 초심으로 돌아간 기분이었다.
기초가 탄탄해야 앞으로 나아가기 쉽다! 꼭 기억하자.

[1] 자료구조와 알고리즘

자료구조란 무엇일까요? 말 그대로 특정한 자료의 구조입니다.

이는 메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 목표입니다.

알고리즘이란 무엇일까요?

정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 말합니다.

이는 특정 문제를 효율적이고 빠르게 해결하는 것이 궁극적인 목표입니다.

[1-1] 자료구조의 종류

경우에 따라서는 4개로 나눌 수 있지만, 크게 3가지로 나눌 수 있습니다.

• 단순 구조
  • 정수
  • 실수
  • 문자열
  • 논리
• 선형 구조
  • 배열
  • 연결리스트
  • 스택
  • 큐
• 비선형 구조
  • 트리
  • 그래프

[1-2] 선형 구조

자료구조의 종류 중 하나인 선형 구조에 대해 알아보도록 하겠습니다.

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

[1-3] 비선형 구조

비선형 구조란, 원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절합니다.

선형 구조와는 다르게 원소가 여러 개의 원소와 관계를 가질 수 있습니다.

😊 완벽한 자료구조는 없습니다. >

더 좋고 더 나쁜 자료구조는 없습니다.
특정 상황에서 유용한 자료구조와 덜 유용한 자료구조가 있을 뿐입니다.
우리는 상황에 맞게 적절한 자료구조를 선택해서 사용하면 됩니다.

[2] 시간 복잡도

시간 복잡도를 나타내기 위한 방법의 하나인 Big-O notation에 대해 알아보도록 하겠습니다.

(상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수)

선형시간(O(n))은 일반적인 반복문을 돌 만큼

로그시간(O(log n))은 입력받은 n에 로그를 씌운 만큼 루프를 돌게 됩니다.

선형 로그시간((O(n log n))과 이차 시간(O(n^2))은 단순히 두 시간을 곱한 값이 각각의 시간이 됩니다. (선형 _ 로그 / 선형 _ 선형)

보통의 코딩 테스트에서는 적어도 O(n^3) 이상의 시간이 걸리면 안 되는 문제들이 출제됩니다.

[2-1] Big-O 표기법 법칙

• 계수법칙

상수 k가 0보다 클 때, f(n) - O(g(n))이면 kf(n) = O(g(n))이다.

따라서 단순한 반복문의 n이 얼마든, n이 무한에 가까울수록 k의 크기는 의미가 없으므로 똑같이 O(n)으로 표기합니다.

• 합의 법칙

f(n) = O(h(n))이고 g(n) = O(p(n))이면 f(n) + g(n) = O(h(n)) + O(p(n))이다. (더해질 수 있다.)

두 개의 각 반복문이 있을 때, i의 범위가 하나는 n까지고 하나는 m까지라 하면 두 루프를 합쳐 O(n+m)로 표기할 수 있습니다.

• 곱의 법칙

f(n) = O(h(n))이고 g(n) = O(p(n))이면 f(n) _ g(n) = O(h(n)) _ O(p(n))이다. (곱해질 수 있다.)

두 개의 각 반복문이 중첩되어 있을 때, i가 n까지고 j도 n까지라 하면 두 루프를 곱해 O(n^2)로 표기할 수 있습니다.

• 다항 법칙

f(n)이 k차 다항식이면 f(n)은 O(n^k)이다.

하나의 반복문에서 i가 n _ n _ n까지라 하면 O(n^3)으로 표기할 수 있습니다.

😊 Big-O 표기법 포인트

1. 상수항 무시
2. 가장 큰 항 외에 무시
3. JS에서 성능(소요 시간)을 알기 위해서는 Date객체를 이용할 수 있습니다.

[3] 배열 (순차 리스트, Array)

배열은 연관된 데이터를 연속적인 형태로 구성된 구조를 가지며, index를 가집니다.

배열은 추가/ 삭제가 반복되는 작업보다, 탐색에 유리한 자료구조입니다.

[3-1] 배열의 특징

• 고정된 크기를 가지며 일반적으론 동적으로 크기를 늘릴 수 없습니다.

→ 하지만 자바스크립트처럼 대부분의 스크립트 언어(python, Ruby …)는 동적으로 크기가 증감되도록 만들어져 있습니다.

• 원하는 원소의 index를 알고 있다면 O(1)(상수시간)로 원소를 찾을 수 있습니다.
• 원소를 삭제하면 해당 index에 빈자리가 생깁니다.

[3-2] JS 배열

JS의 Array는 HashMap에 가깝습니다. (근본적으로 객체 타입에 가깝습니다.)

또한 index가 number가 아니어도 괜찮습니다.

arr["string"] = 10;
arr[false] = 0;

배열의 key값 추가도 가능하며, 자동으로 문자열로 변환되어 key가 생성됩니다.

😊 이런 식의 사용은 추천하지 않지만, 알아두면 좋습니다.

[4] 연결 리스트 (Linked List)

연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조입니다.

각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성됩니다.

[4-1] 연결 리스트 특징

연결 리스트의 특징은 배열과 상반되어 있습니다.

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

[4-2] 배열과 차이첨

• 메모리 차이

배열은 순차적인 데이터가 들어가기 때문에 메모리의 영역을 연속적으로 사용

연결 리스트는 연속적이지 않은 메모리 사용 → 각 메모리를 참조하기 위해 포인터 사용

• 시간 복잡도

요소 추가/삭제 : 배열은 O(n), 연결 리스트는 O(1)

[+] 과제 코드

• 과제 1-1 - size 메소드 만들기

// method
size() {
	let curNode = this.head;
	let count = 0;
	while(curNode !== null){
		curNode = curNode.next;
		count += 1;
	}

	console.log('size :',count);
}

// console
linkedList.size(); // 4 ([1, 2, 10, 5]일 경우)

• 과제 1-2 - 예외처리 하기

(1) find method, remove method : 해당 요소가 없을 경우

(2) insert method : find를 사용했는데, 해당 요소가 없을 경우

// find method
find(val) {
	let curNode = this.head;
	try{
		while (curNode.val !== val){
			curNode = curNode.next;
		}
	} catch(error) {
		console.log("find : 존재하지 않는 값입니다.");
		return false;
	}
	return curNode;
}

// remove method
remove(val) {
	let preNode = this.head;
	while(preNode.next.val !== val) {
		preNode = preNode.next;

		if (preNode.next === null){
			console.log("remove : 존재하지 않는 값입니다.")
			return false;
		}
	}

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

// insert method
insert(node, newVal){
	if (node === false) {
		console.log("insert : 잘못된 위치입니다.");
		return false;
	}
	const newNode = new Node(newVal);
	newNode.next = node.next;
	node.next = newNode;
}

// console
linkedList.remove(3);
linkedList.insert(linkedList.find(10), 10); // [1, 2, 5]일 경우

// remove : 해당 요소가 없습니다.
// find : 존재하지 않는 값입니다.
// insert : 잘못된 위치입니다.

(3) display method : 비어있는 배열 출력 시 ‘[’ 생략되는 이슈

//display method
display() {
	let curNode = this.head;
	let displayString = "[";
	while (curNode !== null) {
		displayString += `${curNode.val}, `;
		curNode  = curNode.next;
	}
	displayString = displayString.substr(0, displayString.length - 2);

	if (displayString === ""){
		displayString += "[";
	}

	displayString += "]"
	console.log(displayString);
}

// answer
const linkedList = new SingleLinkedList();
linkedList.size(); // 0
linkedList.display(); // []

😅 분명히 더 있을 것 같은데.. 계속 고민해보자

• 과제 2 - DoublyLinkedList 구현

우선 DoublyLinkedList는 앞과 뒷부분을 다 연결해놓기 때문에 (양방향) 앞부분 insert, 뒷부분 insert가 가능합니다.

코드가 너무 길어 핵심적인 부분만 첨부했습니다.

// Node class
class Node {
	constructor(val){
		this.val = val;
		this.previous = null;
		this.next = null;
	}
}

// insertNext method
insertNext(node, newVal){
	if (node === false) {
		console.log("insert : 잘못된 위치입니다.");
		return false;
	}
	const newNode = new Node(newVal);
	newNode.next = node.next;
	node.next.previous = newNode;
	node.next = newNode;
	newNode.previous = node;
}

// insertPrevious method
insertPrevious(node, newVal){
	if (node === false) {
		console.log("insert : 잘못된 위치입니다.");
		return false;
	}
	const newNode = new Node(newVal);
	newNode.previous = node.previous;
	node.previous.next = newNode;
	node.previous = newNode;
	newNode.next = node;
}

// console (append 생략)
linkedList.display(); // [1, 2, 5]
linkedList.insertNext(linkedList.find(1), 10);
linkedList.display(); // [1, 10, 2, 5]
linkedList.insertPrevious(linkedList.find(2), 7);
linkedList.display(); // [1, 10, 7, 2, 5]

1 뒷부분에 추가되고 2 앞부분에 잘 추가되는 것을 확인할 수 있습니다.

• 과제 3 - CircularLinkedList 구현

마지막 요소의 next가 다시 첫 번째 요소로 연결되는 CircularLinkedList 구조를 구현해봅시다.

코드가 너무 길고 변경사항이 별로 없으므로 append 함수만 첨부합니다.

// append method
append(newVal) {
	const newNode = new Node(newVal);
	if (this.head === null){
		this.head = newNode;
		this.tail = newNode;
		newNode.next = this.head; // next 순회
	}
	else {
		this.tail.next = newNode;
		this.tail = newNode;
		newNode.next = this.head;// next 순회
	}

	console.log(newNode);
}

// 이외의 메소드의 curNode === null 조건을 모두 this.head로 바꿔주면 된다.
// if문 밖으로 동일한 코드를 빼주면 되지만, 원리 이해의 목적으로 중복 작성했다.

5의 값을 가진 5 요소의 next가 첫번째 요소인 1 node로 잘 연결된 것을 확인할 수 있습니다.

새로 만든 size method와 find 역시 밑의 제약조건을 사용해서 제대로 결과가 출력되도록 했습니다.

if (curNode === this.head){
	break
}

[5] 스택 (Stack)

LIFO 개념을 가진 선형 자료구조입니다.

대표적으로 Call Stack을 생각할 수 있습니다.

Stack은 배열의 push, pop과 연결 리스트로도 표현할 수 있습니다.

[6] 실습 코드

function solution(s) {
  s_arr = s.split("");
  let arr = [];

  for (item of s_arr) {
    if (item === "(") {
      arr.push(item);
    } else {
      if (arr.length === 0) {
        return false;
      }
      arr.pop();
    }
  }

  if (arr.length >= 1) {
    return false;
  }

  return true;
}

짝 맞추는 문제는 stack을 이용하면 편하다.
나름 솔루션과 비슷하게 풀어서 기분이 좋아요 😋

---

출처

프로그래머스

https://noahlogs.tistory.com/27