알고리즘 공부 일지 1

시간 복잡도 

---

시간 복잡도의 유형

• 빅-오메가( Ω(n) ) : 최선일 때의 연산 횟수를 나타낸 표기법 
• 빅-세타( Θ(n) ) : 보통일 때의 연산 횟수를 나타낸 표기법 
• 빅-오( O(n) ) : 최악일 때의 연산 횟수를 나타낸 표기법 

 

연산 횟수 계산 방법

• 연산 횟수 = 알고리즘 시간 복잡도 X 데이터의 크기

알고리즘 적합성 평가

ex) 데이터의 최대 크기(n)가 1,000,000 이고 시간이 2초(2억 2,000,000,000) 일때

• 버블 정렬(n2 ,n제곱) = (1,000,000)2 = 1,000,000,000,000 > 200,000,000   ==> 부적합 알고리즘
• 병합 정렬(nlogn) = 1,000,000log(1,000,000) = 약 2,000,000 < 200,000,000 ==> 적합 알고르짐

 

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

 

 

디버깅

---

 - 자료형은 처음부터 long형으로 선언하자. (자료형 범위 오류 대부분을 예방해준다)

(팩토리얼, 경우의 수, 순열, DP에서 만약 음수가 나온다면 long인지 int인지 꼭 확인하기)

 

 

 

 

자료구조

---

배열과 리스트

- 두 자료구조의 특징을 정확하게 이해하고 문제가 요구하는 조건에 따라 적절하게 선택해 사용하는것이 중요하다

 

배열

• 연속 공간에 값이 채워져 있는 형태의 자료구조
• 인덱스를 통해 값에 바로 접근할 수 있다.
• 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다.
• 배열의 크기는 선언할 때 지정할 수 있으며, 한번 선언하면 크기를 늘리거나 줄일 수 없다.
• 코딩테스트에서 가장 많이 사용

 

리스트

• Head 퐁인터로부터 순서대로 접근해야한다. 접근 속도가 느리다
• 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다
• 선언할 때 크기를 별도로 지정하지 않아도 된다. 변하기 쉬운 데이터를 다룰 때 적절하다

 

---

구간 합 (투 포인터 )

- 구간합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.

 

합배열

S[i] = A[0] + A[1] + A[2] + ... A[i-1] + A[i] // A[0]부터 A[I]까지의 합

합배열 S를 만드는 공식 

S[I] = S[i-1] + A[i]

 

구간 합을 구하는 공식

S[ j ] - S[i -1]

 

ex) 1940, 2018

- 정렬을 해야하거나 정렬이 되서 나온다면, 90프로 투 포인터 사용

 

 

슬라이딩 윈도우 알고리즘

2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결합니다.

투 포인터 알고리즘과 매우 비슷하다

 

 

 

 

스택과 큐

---

스택과 큐는 배열에서 발전된 형태의 자료구조입니다.

 

스택

스택은 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조입니다. 

스택은 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에 효과적이므로 알아두는게 좋습니다.

 

• push : top 위치에 새로운 데이터를 삽입하는 연산
• pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• peek: top 위치에 현재 있는 데이터를 단순 확인하는 연산

 

큐

큐는 삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조입니다. 양방향에서 삽입과 삭제가 이뤄집니다.

큐는 너비 우선 탐색(BFS)에서 자주 사용합니다

• rear: 큐에서 가장 끝 데이터를 가리키는 영역
• front: 큐에서 가장 앞에 데이터를 가리키는 영역
• add: rear 부분에 새로운 데이터를 삽입하는 연산
• poll:front 부분에 있는 데이터를 삭제하고 확인하는 연산
• peak: 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산