TIL 221109 회고

8일 차 회고

• 수학적 개념 필수

알고리즘 강의시작

알고리즘 강의를 듣기 시작했다. 일단 문제를 풀지 못하는 것은 당연하고
문제 자체를 이해 못하는 경우가 생겨 버렸다.
중학교 이후로 수학을 포기... 해서 수학적인 개념이 없어 문제 먼저 이해 할수 가 없었다. 멘붕..
아래는 오늘 하루 들은 강의의 개념을 조금 정리해 보았다.

알고리즘😂

시간복잡도

입력값과 문제를 해결하는 데 걸리는 시간과 상관관계를 말한다.
입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇배로 늘어나는지 보는 것이다.

1. for문 ## array의 길이만큼 연산이 실행된다 (N번)
2. 비교연산, 대입 연산 은 각 1번씩 실행한다.
3. 따라서 상수는 신경쓰지 말고 N의 지수를 먼저 비교 하면된다.

## N * N
for num in number: 			#array 길이 만큼 실행 (N)
	for i in number:		#array 길이 만큼 실행 (N)
    	if num > max_nume:	#비교연산 1번
        
## 2N + 1
max_num = array[0] 			#연산 1번 실행
for num in array:			#array 길이 만큼 실행 (N)
	if num > max_num:		#비교연산 1번
    	max_num = num		#대입연산 1번

공간복잡도

입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다.
입력값이 2배로 늘어났을 때 문제를 해결하는데 걸리는 공간은 몇 배로 늘어 나는지 확인한다.

1. 알고리즘의 성능은 공간에 의해 결정 되지 않는다. 따라서 공간복잡도 보다, 시간 복잡도의 더 신경을 써야한다.

점근 표기법

알고리즘의 "효율성" 을 평가하는 방법.
어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법
알고리즘은 거의 빅오 표기법으로 분석한다.
입력값이 최선의 경우일 가능성은 굉장히 적을 수 있고, 최악의 경우를 대비 해야 하기 때문이다.

• 점근 표기법의 종류

1. 빅오 : 최악의 성능이 나올 때 어느 정도의 연산량의 걸릴 것인지 O(N)
2. 빅 오메가 : 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지. O(1)

어레이와 링크드리스트 🚃

어레이(배열)

• 배열은 정해진 데이터의 공간이다. 정해지면 바꿀 수 없다.
• 배열은 즉시접근이 가능하다. 상수 시간 내에 접근할수 있다. ex)arry[0]
• 배열은 중간 삽입/삭제 하려면 모든 원소가 움직여야 한다. 배열의 길이 만큼 옮겨야 하므로 O(N)의 시간복잡도를 가진다.
• 원소를 새로 추가하려면 새로운 공간을 할당해야 하므로 비효율적인 자료구조이다.

링크드리스트 (Linked List)

• 리스트는 크기가 정해지지 않은 데이터 공간이다.
• 리스트는 특정 원소에 접근하려면 연결 고리를 따라 탐색해야 한다.
  최악의 경우 모두 탐색해야 하므로 O(N)의 시간복잡도를 가진다.
• 리스트는 원소를 중간에 삽입/삭제 하기위에서 앞 뒤의 포인터만 변경하면 된다.O(1)의 시간복잡도 안에 할 수 있다.