자료구조 & 알고리즘(1) (시간 복잡도, 배열, 연결 리스트, 스택)

✔️자료구조와 알고리즘이 중요한 이유

자료구조와 알고리즘이란 무엇일까?

요리에 비유하면 이해하기 쉽다!

떡, 어묵, 소시지 같은 재료는 데이터

칼, 프라이팬 등의 도구는 자료구조

레시피는 알고리즘이 된다.  

완성된 요리는 소프트웨어 요리를 먹는 손님은 소프트웨어 이용자이다~🍴

 

자료구조 

메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 목표로 특정 구조를 이룬다.

상황에 맞는 자료구조 선택은 필수!

ex) stack, queue, graph, tree

 

알고리즘 

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

ex) Binary Search, Shortest Path

 

이러한 자료구조와 알고리즘은 왜 중요할까?

실무에서 중요한 3가지

• 기초 코딩 능력(문제 해결 능력) 👈자료구조와 알고리즘 공부를 통해 능력 up!
• 전문 분야 지식
• 기본 cs지식

문제 해결 능력

• 논리적 사고 
• 전산화 능력
• 엣지 케이스 능력

---

✔️자료구조의 종류

목표: 메모리를 효율적으로 사용 👉 빠르고 안정적으로 데이터를 처리하기

 

현실에 존재하는 영화 예매를 컴퓨터로 어떻게 옮긴 걸까?

    영화를 검색한다. -> Trie

    고객이 많을 경우 줄을 선다. -> Queue

    좌석을 선택한다.  -> HashTable

이와 같이 자료구조는 일차원인 컴퓨터 메모리를 현실에 대응되도록 구조를 만든 것!

선형구조

• 자료들이 선형으로 나열되어 있는 구조
• ex) 배열, 연결리스트, 스택, 큐

비션형 구조

• 원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절
• ex) 그래프, 트리

 

---

 

✔️시간복잡도⭐

프로그램의 성능을 정확히 파악하는 것은? 불가능...

그렇다면 성능을 상대적으로 표현하자 해서 나온 것이 빅오 표기법!

 

빅오표기법(Big-O notation)

• O(n)

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

• 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){
    	//...
    }
}

• O(n^2)

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

※ 코테에서는 O(n^3)은 넘는 경우는 거의 없다.

 

빅오 표기법의 4가지 법칙

• 계수 법칙 : n이 무한에 가까울수록 계수의 크기는 의미가 없음
• 합의 법칙 : 빅오끼리 더해질 수 있음
• 곱의 법칙 :  빅오끼리 곱해질 수 있음
• 다항 법칙 

기억해야 할 2가지!

1. 상수항은 무시하자

for (let i =0; i<n*6;i+=1){
	//...
} //계수 무시 -> O(n)

2. 가장 큰 항 외엔 무시하자

for (let i = 0;i < n;i += 1){
	//...
}
for (let i = 0;i < n;i += 1){
	for (let j = 0;j < n;j += 1){
		//...
	}
}//작은 항 무시 -> O(n^2)

성능 측정 방법 

Date 객체 이용해 로직 작동 시간 측정

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

 

---

✔️배열, 순차 리스트

배열 : 

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

특징 : 

• 고정된 크기를 가짐 -> 동적으로 크기 늘릴 수 없다.
• 단, 자바스크립트와 같은 스크립트 언어는 동적으로 크기가 증감된다. 
• 원하는 원소의 index를 통해 O(1)로 원소를 찾을 수 있다. 
• 원소를 삭제하면 해당 index는 빈자리가 된다.

배열 요소 삭제, 배열 요소 추가 -> O(n) 걸림 👉추가와 삭제에 배열은 비추천! 배열은 탐색에 유리

 

+자바스크립트 배열의 특이점 

자바스크립트의 배열은 동적이다!

index에 숫자가 아닌 논리값, 문자열도 들어갈 수 있다! (숫자 외의 값은 문자열로 자동 변환)

자바스크립트의 배열이 근본적으로 객체 타입 이기 때 (object와의 차이 : length가 내부적으로 관리된다)

 

---

✔️연결 리스트

연결 리스트 :

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

각 요소는 노드라고 부름, 첫 번째 요소는 헤더

 

특징 : 

• 메모리가 허용하는 한 요소를 제한 없이 추가할 수 있다. 
• 탐색 : O(n) 소요
• 요소를 추가하거나 제거할 때는 O(1) 소요
• ex) Singly Linked List, Doubly Linked LIst, Circular LInked List 

배열과 차이점 : 

• 메모리 차이
• 삭제 & 추가 시간 복잡도 차

배열	O(n)
연결 리스트	O(1)

 

singly Linked List(단일 연결 리스트)

Head에서 Tail까지 단반향으로 이어지는 연결 리스트 (가장 단순한 연결 리스트)

-요소 찾기(O(n))

-요소 추가(O(1))

-요소 삭제(O(1))

 

Doubly Linked LIst

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

-요소 찾기(O(n))

-요소 추가(O(1))

-요소 삭제(O(1))

 

Circular Linked List

SIngly 혹은 Doubley Linked List에서 Tail이 Head로 연결되는 연결 리스트 

메모리 아껴 쓸 수 있다! 원형 큐를 만들 때 사용된다!

---

 

✔️스택

스택: last in First Out이라는 개념을 가진 선형 자료구조 

표현 방법 

-배열로 표현하기 Push() , Pop() 사용

-Linked List로 표현하기 

 

예제) 올바른 괄호 

[프로그래머스][JavaScript]올바른 괄호