- 발행일
코딩 테스트 개요 및 문제 풀이를 위한 자바스크립트 문법 02
코딩 테스트 개요 및 문제 풀이를 위한 자바스크립트 문법 02
이 글은 네이버 블로그에 2024년 2월 4일에 올렸던 것을 그대로 옮겨온 것입니다.
자료구조 개요
자료구조는 다수의 자료를 담기 위한 구조이다.
데이터의 수가 많아질수록 효율적인 자료구조가 필요하다.
자료구조의 필요성에 대해서 이해할 필요가 있다.
선형 구조
선형 자료구조는 하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조다.
데이터가 일직선 상으로 연결
배열
연결리스트
스택
큐
비선형 구조
하나의 데이터 뒤에 다른 데이터가 여러개 올 수 있다.
데이터가 일직선 상으로 연결 될 필요가 없다.
트리
그래프
시간 복잡도 : 연산횟수
공간복잡도 : 메모리의 양
배열
가장 기본적인 자료 구조
여러개의 변수를 담는 공간으로 이해
배열은 인덱스가 존재하며, 인덱스는 0부터 시작한다.
특정한 인덱스에 직접적으로 접근 가능
컴퓨터의 메인 메모리에서 배열의 공간은 연속적으로 할당 된다.
장점 : 캐시 히트 가능성이 높으며 조회가 빠르다.
단점 : 배열의 크기를 미리 지정해야하는 것이 일반적이므로 데이터 추가 및 삭제에 한계가 있다.
연결 리스트
연결 리스트는 컴퓨터의 메인 메모리상에서 주소가 연속적이지 않다.
리스트의 크기는 동적으로 변경 가능
포인터를 통해 다음 데이터의 위치를 가리킨다는 점에서 삽입과 삭제가 간편하다.
특정 번째의 원소를 검색할때는 앞에서 원소를 찾아야하기 때문에 데이터 검색 속도가 느리다.
배열 혹은 스택이 기능이 필요할때는 자바스크립트의 배열
큐의 기능을 제공하지는 못한다.
동적 배열
push 메서드를 통해 배열의 가장 뒤쪽에 새로운 원소를 추가할 수 있다.
concat 메서드를 통해 여러개의 배열을 이어 붙여서 합친 결과를 반환한다.
slice(left,right) 메서드를 통해 특정 구간의 원소를 꺼낸 배열을 반환한다.
indexOf 메서드를 통해 특정한 값을 가지는 원소의 첫번째 인덱스를 반환한다.
연결리스트
연결 리스트는 각 노드가 한줄로 연결 되어 있는 자료구조다.
각 노드는 데이터, 포인터 형태를 가진다.
포인터 : 다음 노드의 메모리 주소를 가리키는 목적으로 사용된다.
연결성 : 각 노드의 포인터는 다음 혹은 이전 노드를 가리킨다.
-> 스택, 큐
연결리스트 vs 배열
연결 리스트와 배열을 비교하여 장단점을 이해할 필요
특정 위치의 데이터를 삭제 할때, 일반적인 배열에서는 시간 필요 N
하지만 연결리스트는 단순히 끊어주면 된다.
따라서 삭제할 위치를 정확하게 알고 있으면 시간이 소요 1
스택 : 먼저 들어온 데이터가 나중에 나가는 자료구조
새로운 원소를 삽입할 때는 마지막 위치에 삽입
새로운 원소를 삭제 할때는 마지막 원소가 삭제
스택 연산법?
삽입 : 스택에 원소를 삽입하는 연산
추출 : 스택에서 원소를 추출하는 연산
최상위 원소 : 스택의 최상위 원소를 확인하는 연산
empty : 스택이 비어 있는지 확인하는 연산
배열 자료형
push 메서드를 통해 마지막 위치에 원소를 삽입하며, 시간 복잡도 1
pop 메서드를 통해 마지막 위치에 원소를 추출하며 , 시간 복잡도 1
연결 리스트로 스택 구현하기
스택을 연결 리스트로 구현하면, 삽입과 삭제가 1로 보장
연결 리스트로 구현할 때는 머리를 가리키는 하나의 개 포인터만 가진다.
머리 : 남아 있는 원소 중에 가장 마지막에 들어 온 데이터를 가리키는 포인터
삽입 : 머리 위치에 데이터를 넣는다.
삭제 : 머리 위치에 데이터를 꺼낸다.
큐는 먼저 삽입된 데이터가 먼저 추출되는 자료구조다.
큐를 연결 리스트로 구현하면, 삽입과 삭제에 있어서 1을 보장
연결 리스트로 구현할때는 머리와 꼬리 두개의 포인터
머리 : 남아 있는 원소 중에 가장 먼저 들어온 데이터를 가리킴
꼬리 : 남아 있는 원소 중에 가장 마지막에 들어 온 데이터를 가리키는 포인터
다수의 데이터를 삽입 및 삭제 할때 측정
단순히 배열 자료형보다는 연결리스트가 압승
자바스크립트에서는 Dictionary 자료 형으로 큐를 구현
그래프
그래프는 사물을 정점과 간선으로 나타내기 위한 도구다.
그래프는 두가지 방식으로 구현 할 수 있다.
인접 행렬 : 2차원 배열을 사용하는 방식
인접 리스트 : 연결 리스트를 이용하는 방식
인접 행렬은 그래프를 2차원 배열로 표현한다.
모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프
모든 간산에 가중치가 없는 그래프를 무가중치 그래프
모든 간선이 방향을 가지는 그래프를 방향 그래프라고 한다.
모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.
방향 가중치 그래프가 주어졌을때 연결되어 있는 상황을 인접 행렬로 출력 할 수 있다.
인접 행렬
모든 정점들의 연결 여부를 저장해 공간 요구
공간 효율성이 떨어지지만 두 노드의 연결 여부를 확인
인접 리스트 연결된 간선의 정보만을 저장
공간 효율성이 우수하지만 여부를 위한 시간 필요
최단 경로 알고리즘
각각 근처의 노드와 연결 되어 있는 경우가 많아서 간선 개수가 적어 인접 리스트가 유리
