자료구조 & 알고리즘 (1)

자료구조

자료구조(Data Structure)를 배워야 하는 이유

• 데이터의 형태와 쓰임에 가장 적합한 자료구조를 쓰는것이 매우 중요
  • 컴퓨터의 자원은 한정적임 === 아무리 좋은 하드웨어를 사용하더라도 무제한이 되는건 아님
    • 제한된 제약조건 내에 정확한 결과를 내야함
• 적합하지 않은 자료구조를 사용했을 때
  • 느린 시스템
  • 트래픽이 몰렸을 때 펑🤯🤯🤯🤯

결론 : 어떤 자료구조를 사용하는게 효율적인가, 자료구조의 동작원리를 아는것이 나중에 발생할 수 있는 문제를 예측할 수 있음

알고리즘

좋은 소프트웨어 란?

• 효율적이어야 함
  • 적은 자원 사용
  • 빠른 실행 시간
• 적은 비용으로 개발하고 유지보수할 수 있어야 함

알고리즘이란

• 어떤 문제가 주어졌을 때, 문제를 풀기위한 동작들의 절차
  • ex ) 라면 끓이는 법, 집에서 학교 가는 법, 네이버에 들어가는 법

알고리즘의 조건

• 입력 - 출력
• 완전성과 명확성
  • 수행 단계와 순서가 완전하고 명확하게 명세 되어야 함
  • 순수하게 알고리즘이 지시하는 대로 실행하기만 하면 의도한 결과가 나와야 함
• 유한성
  • n번의 명령어를 수행한 후 반드시 종료되어야 함
    • 무할루프를 돌면 안됨

공간 복잡도

• 데이터 관리에 필요한 공간
• 데이터 양의 변화에 따른 공간의 변화
• 예상 소요 공간 측정
• 컴퓨터 사양이 높아짐으로 써 별로 중요하지 않게 됨

시간 복잡도

• 데이터 처리에 소요되는 시간 체크
• 데이터 양의 변화에 따른 소요시간의 변화 체크
• 예상 처리 시간을 측정
  • 수만개 혹은 수 억개의 데이터를 처리해야 한다면?
• 지연 장애가 발생했을 때 왜 발생했는지 찾을 수 있는 근거
• big-O 표기법
  • O(1)

    • 입력 데이터 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘

    • ex) 배열, Hash

      function O_1_algorithm(arr, index) {
        return arr[index];
      }

  • O(log n)

    • 데이터가 커질수록 단계 수가 늘어나므로 이진탐색은 O(1)이라 표현할 수 없음
      검색하고 있는 배열의 원소 수보다 단계 수가 훨씬 적으므로 O(N)이라 표현할 수도 없음

    • ex) 이진탐색

      function O_log_n_algorithm(n) {
        let a = b = 0;
        while (a < n) {
      		b += 1
      		a = a * 2
        }
        return b;
      }

  • O(n)

    • 입력 데이터의 크기에 비례해서 시간이 소요되는 알고리즘

    • for문

      function O_n_algorithm(n) {
        for (let i = 0; i < n.length; i++) {
          // do something
        }
      }

  • O(n²)

    • 입력 데이터의 제곱에 비례해서 시간이 소요되는 알고리즘

    • 중첩 for문

      function O_quadratic_algorithm(n) {
        for (let i = 0; i < n; i++) {
          for (let j = 0; j < n; j++) {
            // do something
          }
        }
      }