Time Complexity: O(N)
Space Complexity: O(N)
값을 index로 접근

Python

1
2
3
4
5
6
7

A.append, A.pop # O(1) 평균
A.insert, A.remove # O(n) Worst Case
A.index, A.count # O(n) Worst Case
A.pop() # 평균 O(1)
A.pop(2) # O(n) Worst Case
# 평균 O(1) Hashtable

list 리스트: 용량 자동조절(dynamic array)

1
2
3
4
5

import sys
A = []                  # 빈 리스트
print(sys.getsizeof(A)) # 28bytes
A.append(10)            # A = [10]
print(sys.getsizeof(A)) # 44bytes

list class:
capacity: 용량
n: 현재 저장된 값의 개수

1
2
3
4
5
6
7
8
9
10
11
12
13

A.append(X):
if A.n < A.capacity:
  A[n] = x
  A.n = n + 1
else: A.n == A.capacity
B = A.capacity*2 #A.capacity*2 크기의 리스트 새로 할당
for i in range(n):
  B[i] = A[i] # O(n)
del A
A = B
A[n] = x
A.n = n+1

A[0] = 2를 넣으면
A[0]의 주소가 2가 저장되어있는 주소를 가르킴
A[0]+1을 하면 A[0] = 3이 됨
그러면 3이 저장되어있는 새로운 주소를 가르킴

1
2
3
4
5
6
7
8
9
10
11
12
13
14

list.append(값)
append: 맨 뒤에 값 추가

list.pop()
pop: 맨뒤의 값을 지우고 리턴
pop(index): A[index]를 제거하고 리턴

list.insert(index, value)
list[index]에 value를 삽입

list.remove(value): list에서 value제거

list.index(value), list.count(value)

JavaScript

• push, pop, unshift, shift
• concat
• indexOf, lastIndexOf, includes

-join
-split

-splice: 배열자체를 변형
-slice(start, end) : end exclusive하다

Array 배열

• map, forEach, filter, find, findIndex, reduce, every, some 등 내장 iteration 메소드를 활용한다.
• map : array → array
• forEach: array 한개씩 순회하여 콜백 호출
• filter: 필터링
• find: 한개 찾아 반환
• findIndex: 한개 찾아 인덱스 반환
• reduce: array → single value
• reduceRight: 배열거꾸로 부터 누적
• every: 모두 만족하면 true 값을 반환
• some: 한개라도 만족하면 true 값을 반환

한국외대 신찬수 교수님 자료구조와알고리즘

자료구조(Data Structure), 알고리즘(Algoritm)

자료: data -> [저장공간(memory) + 읽기,쓰기,삽입,삭제,탐색(연산)] => 구조
알고리즘: data (유한한 횟수의 연산들) 입력-> 정답 출력

자료구조 (예:) 1. 변수(variable) 2.배열(array), 리스트(list)
알고리즘 (예:) 100개의 정수: 리스트 A:입력 -> 오름차순 정렬:출력

1
2
3
4
5
6
7
8
9
10
11
12

a = 5 # 쓰기 연산
print(a) # 읽기 연산

A = [3, -1, 5, 7]
'''
접근: 원소의 index
읽기, 쓰기: A[3]
삽입: A.append(9) # 맨 끝에 추가,
      A.insert(0, 100) # 0번째 idx에 100 값 추가
삭제: A.pop() # 가장 마지막 제거,
      A.pop(2) # 2번쨰 idx 값 제거
'''

인류 최초의 알고리즘

ac, 페르시아, Algebra 수학자 Al-khwarizmi
-> Algorismus + Arithmos => [Algorithm]

최대공약수(GCD)계산 알고리즘 by Euclid

1
2
3
4
5

def gcd(a, b):
    while a!=0 and b!=0:
        if a>b: a = a-b
        else: b = b-a
    return a+b

date: 2022-09-20 23:26:03
Big O notation
Big Ω notation/ Big θ notation
Big O notation

시간 복잡도(점근적 실행 시간, asymptotic runtime)

• O(big-O): 시간의 상한
  배열의 모든 값을 출력하는 알고리즘은 O(N)으로 표현할 수 있지만
  O(N^3),O(N^2),O(2^N)도 옳은 표현이다.
  다시 말하자면 알고리즘의 수행 시간은 적어도 이들 중 하나보다 빠르기만 하면 된다.

• Ω (big-Omega): 시간의 하한
  배열의 모든 값을 출력하는 알고리즘은 Ω(N) 뿐만 아니라 Ω(logN) 혹은 Ω(1)로도 표현할 수 있다.결국, 해당 알고리즘은 Ω 수행 시간보다 빠를 수 없게 된다.

• θ (big-theta): 딱 맞는 수행 시간
  θ는 O와 Ω 둘 다 의미한다. 즉, 어떤 알고리즘의 수행시간이 O(N)이면서 Ω(N)이라면, 이 알고리즘의 수행 시간을 θ(N)로 표현할 수 있다.

공간 복잡도

• 사용하는 스택 공간 또는 공간 복잡도 계산에 포함된다.
• 함수들이 호출 스택에 동시에 존재하지 않으면 계산에 포함되지 않는다.

1. 상수항은 무시하라
   O(N) = O(2N)
2. 지배적이지 않은 항은 무시하라
   O(N^2) = O(N^2 + N)
3. 여러 부분으로 이루어진 알고리즘: 덧셈 vs 곱셈

• O(A+B)
  만약 알고리즘이 “A 일을 모두 끝마친 후에 B일을 수행하라”의 형태라면 A와 B의 수행 시간을 더해야 한다.
• O(A*B)
  만약 알고리즘이 “A 일을 할 떄마다 B 일을 수행하라”의 형태라면 A와 B의 수행시간을 곱해야 한다.