시간 복잡도
입력값과 연산 수행 시간의 상관관계를 나타내는 측정 도구.
알고리즘에서는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.
- 시간 복잡도 유형
- 빅 오메가 : 최선일 때의 연산 횟수를 나타낸 표기법
- 빅 세타 : 보통일 때의 연산 횟수를 나타낸 표기법
- 빅 오 : 최악일 때의 연산 횟수를 나타낸 표기법
( 주로 빅오 표기법을 사용한다. )
빅오 표기법
시간제한에 따른 알고리즘 설계
500 O(N³)
2,000 O(N²)
100,000 O(NlogN)
10,000,000 O(N)문제를 해석하기 전에 조건을 먼저 보고, 사용할 알고리즘을 먼저 분석하는 경우도 있다.
구간 합
- 구간 합의 핵심 이론
구간 함 알고리즘을 활용하려면 먼저 합 배열을 구해야한다.
// 합 배열 S
S[i] = A[0] + A[1] + ... + A[i] // A[0] 부터 A[i] 까지의 합// 합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]// 구간 합을 구하는 공식
S[j] - S[i-1] // i에서 j까지 구간 합Deque
- 큐의 양쪽으로 엘리먼트의 삽입과 삭제를 수행할 수 있는 자료구조를 의미
- 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택(Stack)으로 사용할 수도 있고,
큐(Queue)로도 사용할 수 있다. - https://soft.plusblog.co.kr/24
스택과 큐
- 스택
삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조 (LIFO)
후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.
// 스택 용어
- 위치
-- top : 삽입과 삭제가 일어나는 위치를 뜻한다.
- 연산
-- push : top 위치에 새로운 데이터를 삽입하는 연산이다.
-- pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
-- peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산이다.- 큐
삽입과 삭제 연산이 선입선출로 이뤄지는 자료구조 (FIFO)
스택과 다르게 먼저 들어온 데이터가 먼저 나가며, 삽입과 삭제가 양방향에서 이뤄진다.
// 큐 용어
- rear : 큐에서 가장 끝 데이터를 가리키는 영역이다.
- front : 큐에서 가장 앞의 데이터를 가리키는 영역이다.
- add : rear 부분에 새로운 데이터를 삽입하는 연산이다.
- poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
- peek : 큐의 맨 앞에 있는 데이터를 확인할 때 사용하는 연산이다.정렬
- 버블(bubble) : 데이터의 인접요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식
- 선택(selection) : 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식
- 삽입(insertion) : 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식
- 퀵(quick) : pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식
- 병합(merge) : 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식
- 기수(radix) : 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식
// 버블 정렬 과정
1. 비교 연산이 필요한 루프 범위를 설정한다.
2. 인접한 데이터 값을 비교한다.
3. swap 조건에 부합하면 swap 연산을 수행한다.
4. 루프 범위가 끝날 때까지 2-3번을 반복한다.
5. 정렬 영역을 설정한다. 다음 루프를 실행할 떄는 이 영역을 제외한다.
6. 비교 대상이 없을 때까지 1-5를 반복한다.// 선택 정렬 과정
1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.
2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다.
3. 가장 앞에 있는 데이터의 위치를 변경해 남은 정렬 부분의 범위를 축소한다.
4. 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때 까지 반복한다.
Developer