프로그래머스 데브코스 Day 04를 듣고 정리한 내용입니다.

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

실무에서 중요하게 생각하는 3가지! : 이 3가지가 밸런스 있게 잡힌 사람은 무조건적으로 뽑는 경향이 있다.

• 기초 코딩 능력 : 코딩능력과 논리적인 사고 능력 (문제 해결 능력)
  • 어려운일을 해내는 회사는 특정 프레임워크나 라이브러리에 정통한 사람을 찾지 않는다. 소프트웨어 세상의 문제는 계속해서 달라지고 변하기 때문에 새로운 기술을 빠르게 습득하고 활용할 수 있는 사람을 찾는다. 기초 코딩 능력이 중요한 이유이다.
• 전문 분야 지식 : 프론트, 백엔드, 딥러닝등 특화된 지식
• 기본 CS 지식 : 운영체제, 네트웤, 소프트웨어구조등 학문적인 지식

문제 해결 능력의 핵심

• 논리적 사고
• 전산화 능력 : 현실에 있는 것을 컴퓨터 세계(소프트웨어)로 구성하는 능력, 컴퓨터적인 사고력 필요
• 엣지 케이스 탐색 : 예외사항을 얼마나 잘 찾는가

자료구조의 종류

선형구조

• 배열
• 연결 리스트
• 스택
• 큐

비선형 구조

• 트리
• 그래프

완벽한 자료구조는 없다!

특정 상황에서 유용한 자료구조와 덜 유용한 자료구조가 존재할 뿐이다.
상황에 맞게 적절한 자료구조를 선택하자.

시간 복잡도

프로그램의 성능을 정확히 파악하는 것은 불가능하다.
그러기 때문에 상대적인 표기법을 사용해 비교를 하게 된다.
이러한 표기법을 Big O 표기법 이라 한다.

Big O 표기법의 성능 비교

$O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)$

위의 성능을 다른 이름으로 말 하자면 차례대로
상수시간, 로그시간, 성형시간, 선형로그시간, 2차시간, 지수시간, 팩토리얼시간

JS에서 실제 성능을 측정하는 방법

Date 객체를 이용한다.

const start = new Date().getTime();

// ...

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

배열

연관된 데이터를 연속적인 형태로 구성된 구조를 가진다.
배열에 포함된 원소는 순서대로 번호(index)가 붙는다.

배열의 특징

• 고정된 크기를 가지며 일반적으로 동적으로 크기를 늘릴 수 없다.
  • 자바스크립트처럼 대부분의 스크립트 언어는 동적으로 크기가 증감되도록 만들어져 있다.
• 원하는 원소의 index를 알고 있다면 O(1)로 원소를 찾을 수 있다.
• 원소를 삭제하면 해당 index에 빈자리가 생긴다.

배열 중간의 요소를 삭제하거나, 추가하면 선형시간이 소모된다.

연결 리스트

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

연결 리스트의 특징

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

배열과의 차이

• 메모리 차이
  • 배열은 순차적인 데이터가 들어가며, 메모리의 주소를 연속적으로 사용한다.
  • 연결리스트는 순차적이지 않고 각 데이터가 흩어져 있다. 흩어져 있는 데이터의 위치를 알기 위해 포인터를 사용해 각 영역을 참조한다.
• 배열 요소 삭제
  • 배열은 요소를 추가하거나 삭제 할때 선형시간이 소모 된다.
  • 연결리스트는 요소를 추가하거나 삭제 할때 상수시간이 소모 된다.