🧩 자료구조/알고리즘

패스트캠퍼스 네카라쿠배1기 자료구조/알고리즘 정리
https://github.com/ai-creatv/algorithm_nklcb1

자료구조란?

자료구조 정의

• 자료(Data)
  • 현실 세계로부터 수집한 사실(측정값)이나 개념의 값 또는 이들의 집합
  • cf) 정보(Information) : 특정용도로 사용하기 위해 처리/가공한 것
  • 값을 모아놓은 것이 자료, 가공하면 정보!
    정보에는 사람의 가치관이 들어가있다.
    예를 들어 평균을 구할때 아웃라이어를 제외하기 위해 상/하위 3명을 제외한다면,
    이런 기준에는 가치관이 적용된다.
• 자료구조(Data Structure)
  • 자료 값의 모임, 자료 간의 관계, 자료에 적용할 수 있는 함수나 명령을 의미
  • ex) 부자의 모근자료 데이터 모음, 부자 관계, 예외 데이터 삭제시 어떻게 처리할 것인지 동작이 있는 것.

자료구조 특징

• 효율성 (Efficiency)
  더 좋은 점이 있다.
• 추상화 (Abstraction)
  삭제 명령시 노드를 삭제한다만 추상화하여 대화하기 편해짐
  어떻게 구현해야하는지 하나하나 명시하지 않음
• 재사용성 (Reusability)
  = 범용적으로 작성해야 한다.
  특정한 상황에만 사용할 수 있다면 자료구조라고 인정받기 어려움.

자료구조 종류

• 선형 자료구조
  • 배열리스트, 연결리스트, 스택, 큐
  • 자료가 선형(1차)로 연결된 경우
• 비선형 자료구조
  • 트리, 그래프
  • 선형으로 연결되지 않은 모든 자료구조

자료구조 필요성

• 자료구조의 선택(자료를 어떻게 저장할지)에 따라, 프로그램에 영향을 준다.
  • 필요한 자료에 효율적으로 빠르게 접근할 수 있게 한다.
  • 자료의 중복을 최소화하여 저장장치를 효율적으로 사용할 수 있게 한다.
  • 자료구조별로 적절한 알고리즘을 기계적으로 적용할 수 있다.
• 다만, 만능(자료접근의 효율성과 저장공간의 효율성을 동시에 만족)인 자료구조는 없다. 각 상황에 따라 최적인 자료구조를 찾아서 적용해야 한다.

알고리즘이란?

알고리즘 정의

• 문제를 해결하기 위한 여러 동작들의 모임
• cf) 문제를 더 쉽게 만들거나, 답에 근사한 값을 얻는 것은 method

알고리즘 조건

• 입력 (Input)
  외부에서 제공되는 자료가 존재한다.
  입력이 없다면 출력도 정해져 있는 것.
• 출력 (output)
  적어도 2가지 이상의 다른 결과를 출력해야 한다.
  항상 똑같은 값을 출력하면 안된다.
• 명확성 (Definiteness)
  수행과정은 명확한 명령어로 구성되어 있어야 한다.(코드로 작성할 수 있을만큼)
  ↔ 자료구조 추상화
• 유한성 (Finiteness)
  유한한 시간안에 종료되어야 한다.
  출력하는데 무한한 시간이 걸리면 안됨
• 효과성 (Effectiveness)
  데이터 적을 경우, 손으로 써가면서 따라할 수 있을 정도로
  단순/명료/명백 해야한다.

알고리즘 필요성

• 서비스의 규모가 커져도, 동일한 퍼포먼스를 내기위해
  십만명과 백만건 아이템 사이의 관계를 다루려면
  100,000 * 1,000,000 = 100,000,000,000개(천억, 100기가)의 관계를 다뤄야함
  naive한 방식으로는 이러한 데이터를 실시간으로 다룰 수 없다.
• 컴퓨터 연산 속도와 비용
  연산은 비용이다! 더 좋은 알고리즘으로 연산 속도를 개선할 경우,
  더 낮은 서버 spec으로도 동일한 서비스 제공 가능하고
  더 짧은 시간 서버를 임대할 수 있다.
  (클라우드 서버의 비용은 실제로 임대한 서버의 spec과 시간에 비례한다)