[프로그래머스 FE 데브코스/TIL] DAY4 2023.06.06 화

오늘은 자료구조와 알고리즘에 대해 배웠어요.
데이터 = 음식 재료, 자료구조 = 도구, 알고리즘 = 레시피, 소프트웨어 = 요리, 개발자 = 요리사와 같이 요리에 비유해 주시니까 확 이해가 가더라고요!
정리해볼 내용은 시간 복잡도와 자료구조 중 선형구조인 배열과 연결 리스트에 대한 내용입니다.
단일 연결 리스트를 코드로 구현하는 연습을 하라고 하셨는데 구현 코드가 class로 짜여 있더라고요..
class와 친하지가 않아서 class도 같이 공부해 봐야겠어요! 🥸

 

✔️ 시간 복잡도

• 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도입니다. 
• 빅오표기법 Big-O notation을 주로 사용합니다. 
  • 빠름 ↔ 느림
  • O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n) < O(n!)
  • 상수시간 < 로그시간 < 선형시간 < 선형로그시간 < 이차시간 < 지수시간 < 팩토리얼 시간
  • ⭐️ 두 가지만 기억하자!
    • 상수항은 무시!
    • 가장 큰 항 외엔 무시!

✔️ 알고리즘

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

 

✔️ 자료구조

• 메모리를 효율적으로 사용하며 빠르게 안정적으로 데이터를 처리하는 것이 궁 즉 적인 목표로 상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있다.
  • → 상황에 따라 맞는 자료구조가 다릅니다!

 

자료구조

✔️ 배열 Array

• 순차 리스트입니다. 
• 고정된 크기를 가지며 일반적으로 동적으로 크기를 늘릴 수 없어요.
• 배열 요소를 추가하거나 삭제할 때  O(n)이 소요됩니다.
• 탐색 시 index를 알고 있다면 O(1)로 원소를 찾을 수 있습니다. 

 

✔️ 연결 리스트 Linked List

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

 

단일 연결 리스트

• 요소를 추가하거나 제거할 때 O(1)이 소요됩니다. 
• 요소를 탐색할 때 O(n)이 소요됩니다.

 

배열과 연결 리스트의 메모리 차이는❓
배열은 메모리에 순차적으로 들어가지만 연결 리스트는 순차적이지 않고 각 데이터가 퍼져 있어요.
포인터를 사용하여 각 영역을 참조하게 됩니다. 

연결 리스트는 다시 단일 연결 리스트, 이중 연결 리스트, 환형 연결 리스트로 나눌 수 있습니다❗️

연결 리스트 분류

• 단일 연결 리스트 Singly Linked List
  • 가장 단순한 형태의 연결 리스트입니다. 
  • Head(가장 첫 번째 요소)에서 tail(가장 마지막 요소)까지 단방향으로 이어지는 연결 리스트입니다. 
  • 요소 찾기
    • 헤드부터 포인터를 따라가며 하나씩 찾아보는 수밖에 없습니다. 
    • O(n) 선형 시간이 소요됩니다.
  • 요소 추가
    • O(1) 상수 시간만 소요됩니다. 
    • ⭐️ 하지만 추가를 위한 탐색을 하지 않도록 코드를 주의해서 작성해야 합니다!
  • 요소 삭제
    • O(1) 상수 시간만 소요 됩니다.

 

• 이중 연결 리스트 Doubly Linked List
  • 단일 연결 리스트와 다르게 각 노드에 포인터가 2개 존재합니다.
    • 자료구조가 단일 연결 리스트 보다 좀 더 커요. 
  • 요소 추가와 삭제
    • O(1) 상수 시간만 소요 됩니다.

 

• 환형 연결 리스트 circular Linked List
  • 단일 혹은 이중 연결 리스트에서 Tail이 Head로 연결되는 연결 리스트입니다. 
    • 중간에서 탐색을 시작하더라도 한 바퀴를 전부 탐색할 수 있습니다. 
  • 메모리를 아껴 쓸 수 있다는 장점이 있어요.
  • 원형 큐 등을 만들 때도 사용합니다. 

 

✔️ 단일 연결 리스트를 자바스크립트로 구현하기 

💡 강의에서 강사님께서 function 키워드로 된 생성자 함수가 아닌 클래스로 구현을 해주셨더라고요. 클래스로 구현하는 게 평소에 어렵게 느껴져서 피해왔는데 이번 기회에 한번 정리해 보려 합니다.

 

🔗  클래스 class

• 클래스는 새로운 방식의 객체 생성 메커니즘이라고 생각하면 편합니다!
• 클래스는 class 키워드를 사용하여 정의합니다. 

 

//클래스 선언문
class Person {}

 

• 클래스는 함수로 평가됩니다. 
• 클래스는 인스턴스를 생성하기 위한 생성자 함수입니다. 
  • new 연산자와 함께 호출되어 인스턴스를 생성합니다. 

 

class Person {}

//인스턴스 생성
const me = new Person();
console.log(me) // Person {}

 

• 클래스 몸체에서 정의할 수 있는 메서드는 constructor(생성자), 프로토타입 메서드, 정적 메서드 세 가지가 있습니다. 
  • function 키워드를 생략한 메서드 축약 표현을 사용합니다. 

 

• constructor
  • constructor는 인스턴스를 생성하고 초기화하기 위한 특수한 메서드입니다. 
  • constructor는 생략할 수 있습니다. 
    • 생략해도 빈 constructor가 암묵적으로 정의되고 constructor를 생략한 클래스는 빈 constructor에 의해 빈 객체를 생성합니다. 

 

• constructor는 별도의 반환문(return)을 갖지 않아야 합니다. 
  • new 연산자와 함께 클래스가 호출되면 생성자 함수와 동일하게 암묵적으로 this, 즉 인스턴스를 반환하기 때문입니다. 
  • this = 인스턴스

 

class Person {
	//생성자
    constructor(name) {
    	//인스턴스 생성 및 인수로 인스턴스 초기화
        //인스턴스 프로퍼티 추가
    	this.name = name;
    }
}

//인스턴스 프로퍼티 추가
const me = new Person()

 

• 프로토타입 메서드
  • 클래스 몸체에서 정의한 메서드는 생성자 함수에 의한 객체 생성 방식과는 다르게 클래스의 prototype 프로퍼티에 메서드를 추가하지 않아도 기본적으로 프로토타입 메서드가 됩니다. 

 

class person {
	//생성자 
    constructor(name) {
    	//인스턴스 생성 및 초기화 
        this.name = name;
    }
    
    //프로토타입 메서드
    sayHi() {
    	console.log(`Hi! My name is ${this.name}`);
    }
}

const me = new Person('Lee');

//프로토타입 메서드는 인스턴스를 이용해 호출 합니다. 
me.sayHi(); // Hi! My name is Lee

 

• 정적 메서드
  • 인스턴스를 생성하지 않아도 호출할 수 있는 메서드를 말합니다. 
  • 클래스로 호출합니다. 

 

class person {
	//생성자
	constructor(name) {
    	//인스턴스 생성 및 초기화 
        this.name = name;
    }
    
    //정적 메서드
    static sayHi() {
    	console.log('Hi!');
    }
}

Person.sayHi(); // Hi!

 

💡 정적 메서드와 프로토타입 메서드의 차이 정리

1. 자신이 속해있는 프로토타입 체인이 다르다. 
2. 정적 메서드는 클래스로 호출하고 프로토타입 메서드는 인스턴스로 호출한다. 
3. 정적 메서드는 인스턴스 프로퍼티를 참조할 수 없지만 프로토타입 메서드는 인스턴스 프로퍼티를 참조할 수 있다. 

인스턴스 프로퍼티를 참조해야 한다면 정적 메서드 대신 프로토타입 메서드를 사용해야 한다. 

 

• 정적 메서드 추가 예제

class Square {
	//정적 메서드
    static area(width, height) {
    	return width * height;
    }
}

console.log(Square.area(10, 10)); //100

 

• 프로토타입 메서드 추가 예제

class Square {
	constructor(width, height) {
    	this.width = width;
        this.height = height;
    }
    
    //프로토타입 메서드
    area() {
    	return this.width * this.height;
    }
}

const square = new Square(10, 10);
console.log(square.area()) // 100

 

읽어주셔서 감사합니다!

😎