+노마드 코더니꼴라스, 배지현 :: IT 5분 잡학사전 (3)

• 알고리즘
  • 컴퓨터에게 내리는 지시사항을 나열한 것
  • ex) 패스파인더 알고리즘(최단 경로 길 찾기), 압축 알고리즘(이미지 손상은 줄이고 용량 줄이기. png,jpg도 이걸로 만든 파일)
  • 검색 알고리즘
    • 선형 검색 알고리즘 (linear search) - 맨 처음부터 검색
    • 이진 검색 알고리즘 (binary search) - 데이터 정렬이 되어있어야 사용(12345,54321 이런식으로) , 중앙값을 이용해 절반씩 배제하기, y = log x
  • 정렬 알고리즘
    • 버블 정렬: 1칸씩 밀면서 좌우 비교해서 교환하는 게  한 사이클, 시간복잡도는 O(N²)
    • 선택 정렬: 전체 데이터에서 가장 작거나 큰 데이터의 위치를 따로 기억하는 방식, 시간복잡도는  O(N²)이지만 자리를 바꾸는 연산은 사이클당 1번으로 버블보다는 효율적.
    • 삽입 정렬: 앞의 데이터를 보고 교환이 아니라 밀어 넣어서 배치. 시간복잡도는  O(N²)
    • 시간복잡도가 같은 것은 단순히 측정했을 때, 알고리즘은 초기 데이터 상태에 따라 처리 속도가 달라지기 때문에 시간 복잡도가 같아도 평균적으로 빠른 알고리즘이 있을 수 있다.
• 자료구조
  • 자료 = 데이터, 쓰기 좋게 찾기 좋게 데이터를 정리 보관해야 하는 방식
  • 데이터 크기 기준, 검색을 위한 인덱스 기준, 생성 시간 기준 등 있음
  • 배열 Array
  • 스택과 큐는 상상 속 개념인 추상 자료구조(abstract data type,ADT)- 규칙만 부여하면 된다.
  • 스택
    • 위에서부터 데이터를 쌓고 위에서부터 뺸다.
    • LIFO(Last In First Out) 마지막에 들어간 것이 처음 나온다.
    • 웹 브라우저의 뒤로가기 버튼, 되돌리기 단축키 Ctrl+Z
  • 큐
    • 위로 데이터를 쌓고 아래부터 데이터를 뺀다.
    • FIFO(First In First Out) 먼저 들어간 것이 먼저 나온다. 선입선출, Queue Up(줄을 서다)->먼저 줄을 서면 버스 먼저 탄다.
    • 쇼핑몰 주문 처리 시스템
•  시간복잡도
  • 프로그램의 작업 속도가 얼마나 빠른지 측정하는 방법
  • 배열에서 특정 값을 검색하는 시간, 특정 값을 특정 위치에 추가하는 시간 같은 것인데 실제 시간이 아닌 작업을 거치는 단계가 얼마나 많은지
  • 알고리즘으로 작업을 완료할 때까지 걸리는 절차 수 N을 이용해 O(N), O(log N)로 표현: Big O 표기법
  • 선형 검색 알고리즘의 시간 복잡도는 배열의 길이가 N이면 최대 검색 횟수는 N = O(N)
  • 시간복잡도가 O(1)이면 상수시간내에 실행된다. 상수 시간: 이미 실행 횟수가 고정으로 정해진 것
  • Big-O는 실행 단계에 영향을 주는 요소만 보기에 배열 길이와 상관없이 실행 횟수만 본다. 그래서 print(arr[0]) 코드가 한번 쓰여도 두번 쓰여도 시간 복잡도는 O(1)
  • for..in을 통해 배열의 모든 데이터를 출력하면 시간 복잡도는 O(N)
  • 중첩 반복문을 사용했을 때는 이차시간으로 인해 시간 복잡도는 O(N*N) = O(N²)
•   메모리
  • 비휘발성 메모리 - 컴퓨터 하드 드라이브 같은 것
  • 휘발성 메모리 - RAM (프로그램의 변수,함수 저장)
• 해시 테이블
  • 키와 값을 짝지어 모은 것으로 데이터를 쉽게 정리할 수 있게 해준다.
  • 일반적인 검색 시나리오로 볼 때 시간 복잡도는 O(1), 어떤 값을 찾더라도, 데이터 추가 삭제 시에도 O(1)
  • 배열에 '해시함수'라는 것이 있고 해시 함수가 검색할 때 쓰는 키를 숫자인 인덱스로 바꿔주는 역할을 한다. 
  • 해시 함수
    • 특정 입력 데이터에서 고정 길이의 출력값(해시값)을 내는 함수.
    • 동일한 입력값에 대해 동일한 출력값을 가진다 - 1:1 대응 관계
    • 입력값이 조금만 바뀌어도 출력값은 완전히 다르다. - 무작위성
    • 한쪽으로만 설계된 함수라 거꾸로 입력한다고 원래 값이 나오지 않는다.
    • 위 세가지 특징으로 비밀번호 시스템 구현할 때 유용하다.
    • 레인보우 테이블(해시 함수가 변경한 값을 원래의 값과 연결한 표)의 보안이 중요하다.
    • -> 레인보우 + 솔트(아주 작은 무작위 테스트) :레인보우 테이블만으로 원래 비밀번호를 찾을 수 없음.
  • 두 개의 입력값에 동일한 출력값을 내는 상황을 '해시 충돌'이라 한다.대처 방법 중에는 같은 인덱스에 또 다른 배열을 넣는 방법이 있다. 이런 경우 시간 복잡도가 O(1)은 아님.
• 클린 코드 쓰는 법
  1. 의미 있는 변수, 함수의 이름을 사용하기
  2. 함수는 1가지의 역할만 가지도록 하고 역할을 알 수 있도록 함수 이름을 동사로 짓기
  3. 지나치게 많은 매개변수 쓰지 말기.불가피할 때는 configuration Object 방식을 사용

     function makeProduct({productId,name,price,color,size}){ }
     
     makeProduct({
     	productId: 1,
         name: 'chair',
         price: 42000,
         color: 'red',
         size: '42*42*60'
     })​

  4. Boolean값을 인자로 보내지 말기 : 참과 거짓에 2가지 일을 처리한다면 가독성이 안 좋아지고 책임도 모호해진다. 함수는 1가지의 역할만 가지는 것이 가장 좋기에 boolean값을 return하는 함수를 인자로 보내지 않도록 해야 한다.
  5. 혼자만 아는 축약어 쓰지 않기