자바스크립트로 자료구조 공부하기

데이터 구조와 알고리즘 개요

1. 자바스크립트의 데이터 구조

• 데이터 구조는 프로그램에서 데이터를 저장, 구성, 조작하는 방식
• 데이터 구조는 대량의 데이터를 효율적이고 효과적으로 관리할 수 있는 방법 제공
• 간단한 일상 업무부터 복잡한 과학 및 엔지니어링 문제까지 다양한 애플리케이션에 사용
• ex) 배열, 연결 리스트, 스택, 큐, 트리, 그래프, 해시 테이블 등

a. 배열

• 배열은 객체모음을 선형 순서로 저장하는 방법을 제공
• 배열은 메모리에 연속적인 데이터 블록으로 저장되는 데이터 항목의 모음
• 배열의 요소는 모든 데이터 타입이 될 수 있음
• 메모리에 빠르게 액세스하고 조작할 수 있는 데이터 리스트 저장에 자주 사용
• ex) 이름 리스트, 일련의 숫자값, 이미지 픽셀 등

b. 객체

• 복잡한 데이터 구조를 저장하는데 사용
• 키가 고유해야하며 키 참조를 통해서만 액세스가 가능

c. 집합

• 집한은 고유한 요소의 모음
• 배열과 유사하게 작동하지만 고유한 값만 포함
• 자바스크립트에서 집합을 만들려면 Set() 생성자 사용
• 집합은 배열과 같은 데이터 컬렉션에서 중복을 제거할 때 유용

let mySet = new Set([1,2,3,4,4])

console.log(mySet) //Set {1,2,3,4}

d. 연결리스트

• 연결리스트는 일련의 노드로 구성된 데이터 구조
• 노드에는 데이터 값과 시퀀스의 다음 노드에 대한 참조(또는 포인터) 포함
• 연결리스트는 크기가 커지거나 작아질 수 있는 동적 데이터 구조를 표현하는데 자주 사용
• 큐나 스택과 같이 지속적인 삽입 또는 삭제 작업이 필요한 애플리케이션에서 사용

e. 스택

• 스택은 요소 모음을 저장하는 데이터 구조, 스택의 맨 위에서 요소가 추가되고 제거 됨
• 스택에 마지막으로 추가된 요소가 가장 먼저 제거되는 후입선출 원칙
• 재귀함수 호출, 실행 취소 작업, 접두사에서 접미사로의 변환 알고리즘을 구현하는데 자주 사용됨

f. 큐

• 큐는 요소 모음을 저장하는 데이터 구조
• 선입선출 원칙 : 요소는 큐의 뒤쪽에 추가되고 큐의 앞쪽에서 제거됨
• 시뮬레이션, 모델링, 프로세스 스케줄링 알고리즘 구현에 자주 사용

g. 트리

• 트리는 에지 또는 분기로 연결된 노드로 구성된 계층적 데이터 구조
• 시각화 및 조작하기 쉬운 방식으로 요소간의 관계를 표현하는데 사용
• ex) 머신러닝 알고리즘에 사용되는 패밀리 트리, 디렉토리 구조, 의사 결정 트리 등
• 트리는 깊이 우선 탐색, 너비 우선 탐색과 같은 다양한 검색 및 탐색 알고리즘 구현에 사용

h. 그래프

• 그래프는 정점(=노드)과 정점 쌍을 연결하는 에지의 집합
• 소셜 네트워크, 교통망, 컴퓨터 네트워크와 같은 복잡한 관계를 모델링하는데 사용
• 그래프는 방향성 또는 비방향성, 가중치 또는 비가중치를 가질 수 있음
• 두 정점 사이의 최단 경로를 찾거나 그래프의 연결성을 결정하는 등 여러가지 유용한 연산을 제공할 수 있음

i. 해시 테이블

• 해시 테이블은 해시 함수를 사용하여 키를 배열의 인덱스에 매핑함으로써 데이터에 빠르게 액세스할 수 있도록 하는 데이터 구조
• 해시 테이블은 연관 배열을 구현하는데 사용되며 키-값 쌍으로 데이터 저장하고 검색할 수 있는 방법 제공
• 장점 : 삽입, 삭제, 검색과 같은 작업에 대해 상수 시간(O(1)) 액세스를 제공
• 단점 : 두개의 키가 동일한 인덱스에 매핑되는 충돌 발생 가능성 있고 데이터 손실, 손상 방지 위해 특별한 처리 필요

 

2. 자바스크립트의 알고리즘

알고리즘

• 알고리즘은 특정문제 해결하거나 특정 작업 수행하는 프로세스 또는 절차
• 자바스크립트에서 알고리즘은 개발 프로세스의 필수적인 부분
• 데이터 구조를 조작하고 해당 데이터에 대해 검색, 정렬, 분석 등 다양한 작업 수행에 사용
• 기본적인 수학, 논리 연산 수행하는 간단한 루틴부터 복잡한 자연 현상을 시뮬레이션하거나 대규모 데이터 세트를 분석하는 복잡한 모델도 있음

복잡도 분석

• 복잡도 분석은 컴퓨터 과학에서 알고리즘과 데이터 구조의 효율성과 확장성을 분석하는데 사용되는 기법
• 입력 데이터의 크기에 따라 계산에 필요한 시간과 공간 측정이 포함됨
• 특정 알고리즘이나 구조의 성능 특성을 파악하고 주어진 문제에 적합한 솔루션을 선택하는데 사용

Big O 표기법

• Big O 표기법은 입력 크기가 무한대에 가까워질 때 함수의 제한 동작을 설명하는데 사용되는 수학적 표기법
• 컴퓨터 과학에서는 알고리즘과 데이터 구조의 시간 및 공간 복잡도를 설명하는데 일반적으로 사용됨
• 일반적으로 함수의 성장률에 대한 상한으로 표현되며 계산을 실행하는데 필요한 시간이나 공간의 양에 대한 최악의 시나리오를 나타냄

a. 검색 알고리즘

• 검색 알고리즘은 데이터 구조 내에서 특정 값 검색
• ex) 배열에서 요소 검색하고 해당 인덱스를 반환하는 선형 검색

b. 정렬 알고리즘

• 정렬 알고리즘은 특정 기준에 따라 값을 특정 순서로 정렬

c. 그래프 알고리즘

• 그래프 알고리즘은 상호 연결된 데이터 세트 또는 그래프와 관련된 문제를 해결하는데 사용
  • 경로 계획, 네트워크 최적화, 클러스터링과 같은 문제를 해결하는데 사용되므로 최신 프로그래밍에 필수적
• 다익스트라 알고리즘
  • 우선순위 큐를 사용해 그래프에서 두 노드 사이의 최단 경로를 찾는 다익스트라 알고리즘이 가장 일반적
  • 우선순위 큐는 알고리즘이 비용이 가장 낮은 노드를 검사하여 최단 경로를 빨리 찾을 수 있도록 하기 위해 사용

 

3. 연습문제

a. 숫자 배열을 받아 배열의 최대값을 반환하는 함수를 작성하세요.

 

 

b. 문자열을 받아 문자열의 역을 반환하는 함수를 작성하세요.

 

 

c. 숫자 배열을 받아 짝수만 있는 새 배열을 반환하는 함수를 작성하세요.

 

 

 

 

 

 

자료구조와 알고리즘 책을 정리한 내용입니다!!