알고리즘강의-20230531

1. 시간 복잡도

: 문제를 해결하는데 걸리는 시간과 입력의 함수 관계 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것
입력값과 연산 수행 시간의 상관관계

(1) O(1)
(2) O(log n)
(3) O(n)

예)
입력: array의 원소 갯수 = N
실행시간 : array의 원소 갯수 Xarray의 원소 갯수만큼 비교 연산

• Big-O(빅오)표기법

• 프로그램의 수행성능을 최악의 경우를 가정하여 정량화 하는 방법
  ** 노드는 무한루프가 걸리는 순간 죽음
  -> 여기서 최선, 최악의 경우는

• 시간 복잡도를 알지 못하면 내가 알고리즘을 고안해도 이방법이 정말로 유용한지 판단하지 힘듬

** 서비스의 기본 소양
(1) 느리면 안됨
(2) 다운타임이 생기면 안됨

2. 공간 복잡도

: 문제를 해결하는데에 대한 공간과의 상관관계 N개의 입력이 주어지면 공간을 얼마나 쓰는지 나타냄

• 공간도 최적화를 선호
• 코드를 최적화를 해서 비용 및 공간을 절감
• 지나치게 공간을 헤프게 쓰는 것에 대해 주의!

3. 알고리즘에서 자주 쓰이는 자료구조

• 배열
• 링크드리스트

1. 배열
   왜 0부터 시작할까? -> 메모리관리가 쉬워지고 램에 주소를 할당할 때 편해서

• 프로그래밍을 할 때 가장 많이 쓰는 자료

• 연관된 데이터를 하나의 변수에 그룹핑 해서 관리하는것이 핵심

• 하나의 변수에 여러정보를 담을 수 있거 반복문과 결합하면 많은 정보도 효율적으로 처리

조회:
1. O(1)의 조회시간을 가진다는 매우 큰 장점을 가짐
-> 무조건 한번에 상수적으로 값을 조회 인덳그값을 받으면 해당하는 배열의 값을 바로 리턴

삽입과 삭제:
1. 배열 끝에서 추가 및 삭제는 O(1)
2. 배열 끝이 아닌 다른곳에서 원소를 삽입 혹은 삭제할 경우 n(0)이다.
-> 삽입을 할 자리를 비워 밀고 삽입, 중간에서 삭제하고 당겨야해서

정렬:
1. 정렬의 경우엔 어

검색:
1. 일반적으로 O(N) 첫원소부터 끝까지 봐야되니까
2. 정렬이 되어있느 ㄴ배열이면 O(log N) <- log가 뭐임

3. 링크드리스트

: 유동적으로 연결고리를 떼었다가 붙였다가 할 수 있는 자료 구조를 뜻한다. 링크드리스트에서 요소를 '노드'라고 한다.
맨 앞의 노드를 '헤드' 맨 뒤의 노드를 '테일'이라고 한다.

• 포인터: 현재 노드가 가리키는 것을 포인터라고 칭한다.

배열이 빠르게 값을 갖고 오는 것이 장점
링크드리스트는 원소의 삽입/삭제가 장점