알고리즘 공부 일지 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 ==> 적합 알고르짐
시간 복잡도 도출 기준
- 상수는 시간 복잡도 계산에서 제외한다.
- 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.
디버깅
- 자료형은 처음부터 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)에 있는 데이터를 확인할 때 사용하는 연산