FrontEnd/Javascript

TIL | JavaScript 주요 문법 (3) | 데브코스 5기 Day3

제이드Jade 2023. 9. 22. 19:29

자료구조&알고리즘

  • 자료구조+알고리즘 = 프로그램
  • 자료구조
    • 메모리, 속도, 안정성 쪽으로 상황에 따라 유용한 특정 구조
    • ex. 스택, 큐, 그래프, 트리
  • 알고리즘
    • 일련의 절차와 방법을 공식화한 형태
    • ex. 이진, 최단 탐색

 

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

실무에 중요한 세가지

1. 기초 코딩 능력

  • 자료구조, 알고리즘을 공부해야 함
  • 문제 해결 능력! == 일머리
    • 논리적 사고 : 현상을 추론 후 구조화 하여 해답을 찾는 능력
    • 전산화 능력 : 현실 -> 컴퓨터로 구현
    • 엣지 케이스 탐색 : 예외사항 찾기

2. 전문 분야 (나같은 경우는 FE)

3. 기본 CS 지식

  • 업무상 발생하는 예외사항에 대응 할 수 있음

 

자료구조의 종류

  • 자료구조의 목적 : 전산화를 위한 것임
  • 자료구조의 구분
    • 단순구조 
      • 정수, 실수, 문자열, 논리
    • 선형구조
      • 한 원소 뒤에 하나의 원소만 존재함 
      • 배열, 연결리스트, 스택, 큐
    • 비선형구조
      • 원소간 다대다 관계
      • 계층형, 망형
      • 트리, 그래프
  • 자료구조에 좋고 나쁨은 없다. 특정 상황에 따라 적절한 자료구조를 선택해야한다.

 

시간 복잡도

  • 프로그램의 성능을 정확히 하는 것은 불가능
    • 입력크기, 하드웨어/운영체제 성능 등에 따라 달라짐
    • 이에 대응하기 위해 Big-O 표기법을 사용함
  • 시간 복잡도(Big-O)의 크기
    • ... < O(n^2) < O(2^n) < O(n!)
    • 우리네 코테에서 O(n^3) 이상의 시간 복잡도는 없다고 보면 됨
  • Big-O 표기법의 특징
    1. 합/곱의 법칙 : Big-O 끼리는 합/곱할 수 있다.
    2. 계수법칙 : n이 무한으로 갈수록 n의 계수는 의미가 없다.
      • but, k가 클수록 "실제 "성능에는 영향을 미칠 수 있다.
    3. 다항법칙 : 다항식처럼 제일 높은 계수를 채택한다.
  • 점근적 표기법으로 인해 계수와 상수는 복잡도에 영향을 주지 않는다.
  • JS에서 성능을 측정하는 방법
    • Date 객체를 이용해서 연산후 Date - 연산전 Date로 경과된 시간을 측정한다.

 

배열

=순차리스트

배열의 특징

고정된 크기

  • but, 스크립트 언어(JS 등)는 동적으로 크기가 증감 됨
  1. 요소에 접근은 idx로 => O(1)
  2. 삭제시 공백을 채우거나, 원소 사이에 추가를 하려면 뒤의 원소들을 한칸씩 이동해야 한다. => O(n)
    • 추가/삭제 반복이 많음 -> 배열 적합 x
    • 탐색이 많음 -> 배열 적합 o

JS의 배열

  • 생성
    1. []
    2. fill
    3. from
  • 추가
    • push : O(1)
  • splice
    • 추가 : (idx,0,값) => O(n)
    • 삭제 : (idx,1) => O(n)
  • 특이점
    • 배열은 해쉬/맵과 유사 => 숫자 외의 자료형이 key가 될 수 있음 (because 배열의 자료형==객체)
    • length가 내부적으로 관리됨 => key가 숫자 외의 자료형인 원소는 length에 영향 x

 

연결 리스트

  • 각 요소를 포인터로 연결, 관리
  • 노드 = 데이터+포인터
  • 요소를 제한 없이 추가 가능 (JS는 배열도 그럼 ㅇㅇ)
  • 탐색 : O(n), (탐색 제외한)추가/제거 : O(1)
  • 요소(노드)가 메모리의 곳곳에 퍼져있어서 포인터로 관리 (cf. 배열 : 순차적으로 존재)
  • 유형
    • singly : 단방향
      • 찾기 : 순차적으로 확인
      • 추가 : (이전 노드만 가리키고 있다고 가정) 새 노드의 다음 등록 -> 이전 노드의 다음 수정
      • 삭제 : (이전 노드만 가리키고 있다고 가정) 이전 노드의 다음 수정 -> 삭제 노드 ㅂㅇ (garbage collector가 알아서 노드 삭제)
      • 추가/삭제 시 이전/다음의 순서 변경 불가능
    • doubly : 양방향
      • 추가 : (이전 노드만 가리키고 있다고 가정)현재 노드의 이전/다음 등록 -> 다음 노드의 이전 수정 -> 이전노드의 다음 수정
      • 삭제 : 이전노드의 다음 수정 -> 다음 노드의 이전 수정 -> 삭제할 노드 ㅂㅇ
      • 이전/다음의 순서를 바꿀 수 있음
    • circular
      • 순회하는 연결리스트
      • tail이 head로 연결됨
      • 메모리를 아낄 수 있음
      • 원형 큐에 사용됨
  • JS로 Singly, Doubly, Circular Linked List 구현해보기
더보기
JS로 Singly, Doubly, Circular Linked List 구현해보기

 

스택

  • LIFO
  • ex) 스택 메모리 : 함수 안의 지역변수, 매개변수가 저장되는 메모리 영역
    • 함수 호출 시 (지역변수, 반환 주소 값, 매개변수) 세트가 스택에 push되고 함수가 끝나면 pop된다.
  • 구현
    • 배열로 구현
      • js에서 사용. push/pop
    • 연결리스트로 구현
      • 언제나 유동적이므로 배열이 유동적이지 않은 C,Java에서 사용하는 방법
      • head를 top으로 둔다

 

 

 

 

 

 

 

저작자표시 비영리 변경금지 (새창열림)