[워밍업 클럽 3기] CS 1주차 - 발자국

자료구조

데이터가 어떤 구조로 저장되고, 어떻게 사용되는지 나타냄

가장 단순한 자료구조 변수

• 숫자나 문자열 저장을 위해 변수 사용

• 저장한 숫자, 문자열 접근을 위해 변수 참조

• 사용 방법 단순

배열

• 숫자, 문자열 등 연속적으로 저장

• 해당 숫자, 문자열 접근을 위해 인덱스를 이용하여 참조

   

알고리즘

어떤 문제를 해결하기 위한 확실한 방법

• 알고리즘은 자료구조에 따라 많은 영향을 받음(e.g. 자료구조 성적 평균 구하기)

• 같은 자료구조에 대해서도 여러 알고리즘이 존재

• 프로그램 개발 시

  • 어떻게 저장 및 사용할 것인지 자료구조 선택 → 데이터를 가공할 알고리즘 사용

  • 적절한 자료구조 선택, 적절한 알고리즘 사용을 할 줄 알아야 한다.

  ---

  더 좋은 알고리즘은 무엇인가? → 사용자에 따라 다를 것이다.

• 메모리를 더 적게 사용하고 싶은 사용자

  • 메모리 사용을 적게하는 알고리즘

• 속도를 우선으로 하는 사용자

  • 메모리 사용량이 많아도, 빠른 알고리즘

• 일반적으로 알고리즘 속도를 성능의 척도로 사용 → 시간복잡도!

   

시간복잡도

• 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간

• 같은 알고리즘이라도 컴퓨터 성능에 따라 처리 시간 상이
  → 알고리즘 평가 시 시간 측정이 아닌 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행 시간을 예측

   

  → 반복문이 가장 많은 영향!

   

Big-Ω: 최선의 경우 (한 번에 찾음)

Big-O: 최악의 경우 (배열의 길이만큼)

Big-Θ: 평균 (배열 길이의 중간)

Big-O: 최악의 경우 (O(n))

• 선형시간 알고리즘 O(n)

  • 데이터가 증가할 수록 계산량 증가

• 상수시간 알고리즘 O(1)

  • 입력 크기 상관 없이 상수 시간 소요

  • 계산량이 한번일 필요가 없음

빅오 표기법은 성능을 정확하게 측정하진 못한다.