알고리즘 : 여러가지 지시 사항을 나열 한 것
- (ex) 패스파인더(pathfinder) 알고리즘 - 지도 길 찾기,
- (ex) 압축(compression) 알고리즘 - 이미지 압축 알고리즘 ( 손상과 용량 고려 )
자료구조 : 데이터를 목적에 맞게 효율적으로 보관하는 것
- 어떻게 보관하는 가에 따라 속도에 영향을 끼친다.
- (ex) '데이터 크기 기준'으로 한 자료구조, '검색을 위한 인덱스 기준'으로 한 자료구조, '생성 시간 기준'으로 한 자료구조

배열은 데이터를 램에 연속으로 이어 붙인 형태의 자료구조다. 배열의 시작 주소와 길이를 이미 알고 있다. 읽기(read), 검색(search), 추가(add), 삭제(delete) 과정에서의 시간 복잡도(time complexity)에 집중해야 한다.

시간 복잡도 : 프로그램의 작업 속도를 측정하는 방법이다.
- 실제 시간을 재는 것이 아니라 작업 과정에서 얼마나 많은 단계를 거치는지를 측정한다.

읽기(read) : 연속으로 놓인 데이터이고, 시작 주소와 길이를 알기 때문에 인덱스만 기입하면 된다.
- 즉, 한 번만 돌리는 1단계 알고리즘으로 굉장히 빠르다.
검색(search) : 모든 데이터를 하나씩 까봐야 하기 때문에 빠르지 않다. ( 선행 검색을 해야 한다. )
추가(add) : 중간에 삽입할 경우 뒤에 있는 모든 데이터가 한 칸 씩 밀려나야 한다.
- '새 배열 만들기 => 복사하기 => 추가하기' 로 단계가 많아 매우 느리다.
삭제(delete) : 중간에 데이터를 삭제할 경우 뒤쪽의 모든 데이터를 끌어 당겨야 한다.
- 마찬가지로 매우 느리다.

알고리즘으로 작업을 완료할 때까지 걸리는 절차 수 N을 이용해 O(N), O(로그N)과 같은 형태로 만드는 표기법이다.

[ 예시1-1 ] 배열의 첫 번째 데이터를 출력하는 코드

def print_first(arr):
    print(arr[0])

배열의 길이와 상관없이 함수는 딱 1번ㄴ 실행하고 끝난다. ( 첫 번째 데이터 출력이기 때문이다. )
이 함수의 시간 복잡도는 O(1)이다.
- '상수 시간(constant time) 내에 실행된다.'라고도 말한다. ( 상수 시간이란 실행 횟수가 고정으로 정해진 것을 말한다. )

[ 예시1-2 ] 배열의 첫 번째 데이터를 2번 출력하는 코드


def print_first(arr):
    print(arr[0])
    print(arr[0])

[ 예시 2-1 ] 배열의 모든 데이터를 출력하는 코드


def print_all(arr):
    for n in arr:
        print(n)

[ 예시 2-2 ] 배열의 모든 데이터를 중첩 반복문으로 출력하는 코드


def print_twice(arr):
    for n in arr:
        for x in arr:
            print(x, n)

이차 시간(quaratic time) : 중첩 반복문이 일 때 사용하는 시간 복잡도이다.
배열의 길이가 길어질수록 작업 속돈는 제곱배로 느려진다.
- Big-O로 나타내면 O(N제곱)이다. 제곱 배수(N x N)를 그대로 표현한 것이다.

오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요

궁금한 내용이 있거나, 잘 이해되지 않는 내용이 있다면 적어보세요.

inalee님의 TIL
(https://nomadcoders.co/community/thread/8256)
- 깔끔한 정리와 자체적으로 찾아보신 자료들이 도움이 되었습니다.
hailey님의 노션 TIL (https://hailey-lim.notion.site/Assignment-03-Day3-230219-3e62dfa0d84e441c870504b5ace48ea0)
- 자신의 고민 흔적들이 상세하게 알 수 있어서 도움이 되었다.
taerin13님의 TIL
(https://nomadcoders.co/community/thread/8260)
- inalee님과 마찬가지로 깔끔한 정리와 상세한 설명이 도움이 되었다.

2 comments