1. 알고리즘 공부 시작
이번 주는 본격적으로 알고리즘 공부를 시작했다. 내가 이번 주에 알게 된 알고리즘들을 유형별로 정리하려 한다.
어떤 알고리즘으로 풀어야할까
- 알고리즘의 선택의 기준이 되는 시간 복잡도
코딩 테스트의 핵심 중 하나는 문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것이다.
처음에 알고리즘을 잘못 선택하면 아무리 코드를 잘 자려고 노력해도 좋은 결과를 거두기 어렵다.
문제를 본격적으로 풀어보기 전에 시간 복잡도를 활용할 줄 알아야한다.
일반적으로 알고리즘의 수행시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다.
예를 들어 버블 정렬은 O(n^2)의 시간 복잡도를 갖고 있고 병합 정렬은 O(nlogn)의 시간 복잡도를 가진다.
수 정렬 문제가 나왔을 때 N의 갯수가 최대 1,000,000이라고 하자.
시간 제한이 2초면 2억 번 이하의 연산 횟수로 문제를 풀어야한단 것이다.
연산횟수 계산 방법
- 연산횟수 = 알고리즘 시간 복잡도 * 데이터의 크기
버블 정렬은 1,000,000^2 > 200,000,000 - > 부적합
병합 정렬은 1,000,000log(1,000,000) < 200,000,000 - > 적합
이렇게 시간 복잡도를 분석하여 적합 알고리즘을 찾는 것이 중요하다.
시간 복잡도 도출 기준
- 상수는 시간 복잡도 계산에서 제외
- 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.
배열과 리스트
배열
: 메모리의 연속 공간에 값이 채워져있는 형태의 자료구조, 인덱스를 통해 값 참조 가능, 구조가 간단하여 많이 쓰임
리스트
: 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조, 파이썬의 링크드 리스트랑 똑같다. 동적 배열
둘의 차이
: 배열은 인덱스를 통해 조희가 빠르다. 리스트는 포인터를 통해 데이터의 삽입, 삭제가 빠르다.
리스트는 포인터를 저장할 공간이 필요하므로 배열보다 자료구조가 복잡하다.
구간합
합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 특수한 목적의 알고리즘이다. 코테 사용 빈도가 높다.
합 배열 S의 정의
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]
합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]
구간 합을 구하는 공식
S[j] - S[i-1] -> i에서 j까지의 구간 합
투 포인터
2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.
투 포인터는 출발 시작이 같을 수도, 양 끝에서 올 수도 있다.
투 포인터 이동 원칙
시작지점이 같을 때
- sum > N : sum = sum - start_index; start_index++;
- sum < N: end_index++; sum = sum + end_index;
- sum == N: end_index++; sum = sum + end_index; count++;
양 끝에서 출발할 때
- A[i] + A[j] > M: j++;
- A[i] + A[j] < M: i++;
- A[i] + A[j] == M: i++; j--; count++;
슬라이딩 윈도우
슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하여 문제를 해결한다.
투 포인터 알고리즘과 매우 비슷하다.
*자세한 내용은 문제를 볼 것
스택
스택은 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조이다.
후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징을 가지고 있다.
스택은 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아 두어야 한다.
스택용어
위치
- top: 삽입과 삭제가 일어나는 위치를 뜻한다.
연산
- push: top 위치에 새로운 데이터를 삽입하는 연산이다.
- pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
- peek: top 위치에 현재 있는 데이터를 단순 확인하는 연산이다.
큐
큐는 삽입과 삭제 연산이 선입선출로 이뤄지는 자료구조이다.
스택과 다르게 먼저 들어온 데이터가 먼저 나간다.
그래서 삽입과 삭제가 양방향에서 이뤄진다.
스택용어
- rear: 큐에서 가장 끝 데이터를 가리키는 영역이다.
- front: 큐에서 가장 앞의 데이터를 삽입하는 영역이다.
- add: rear 부분에서 개로운 데이터를 삽입하는 연산이다.
- poll: front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
- peek: 큐의 맨 앞(front)에 있는 데이터를 확인하는 연산이다.
***우선선위 큐도 존재한다.
우선순위 큐는 값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다.***