엘리스 코드 챌린지라는 대회가 있어 예선에 참여하게 되었다. 코딩 교육 플랫폼 엘리스에서 제공하는 알고리즘 대회로, 예선은 2주간 평일에 매일 강의와 문제가 하나씩 나오는 방식이였다. 밑은 강의들을 리마인드겸 정리한 내용이다.
1일차
시간복잡도의 계산
각 언어마다 속도가 다르지만 보정이 들어가므로 1억번당 1초로 보면 된다.
2일차
GCD(최대공약수)
유클리드 호제법 O(root(N))
LCM(최소공배수)
GCD * LCM = 두 수의 곱을 이용, 즉 GCD로 구함.
소수 판별
- 소수는 1을 포함하지 않는다.
- 만약 하나만 판별한다면? GCD가 1인 수가 소수
- 만약 일정 범위의 소수를 판별한다면(1~N)? 에라토스테네스의 체 O(Nlog(logN))
3일차
문자열
회문(Palindrome) : 문자열에서 중간을 기준으로 문자들이 대칭인 문자열. [ex) level] 단순히 for문으로 문자를 검사해주면 됌.
올바른 괄호 문자열(Valid Parenthesis String) : 괄호가 올바른지 확인하는 문제 주로 스택을 활용해 구현
분할정복(Divide and Conquer)
Divide -> 큰 문제를 작은 문제로 분할 base case를 잘 설정해 일정 이상 분할되는 것을 막아줘야함
Conquer -> 작은 문제의 답을 모아, 큰 문제의 답을 구함
(재귀로 구현 가능)
백트래킹(Backtracking)
답이 될 수 없는 경우 탐색 대상에서 제외하며 효율적으로 답을 구하는 알고리즘
가지치기(Pruning)을 통해 연산량을 줄여줌, 단 정확한 시간 복잡도를 구하기 어려움
(재귀로 구현 가능)
4일차
재귀함수
함수 내부에서 자기 자신을 호출하는 함수
base case를 잘 잡는 것이 중요
정렬
자바는 java7 이전까지 병합 정렬 이후 팀 정렬
Tim Sort?
전체를 작은 덩어리로 잘라 각각의 덩어리를 Insertion sort로 정렬한 뒤 Merge sort하면 좀 더 빠르지 않을까 하는 것이 기본적인 아이디어이다. O(NlogN)
5일차
DFS(깊이우선탐색)
stack이나 재귀로 구현
주로 트리 탐색에 활용
6일차
BFS
큐를 활용해 구현
주로 최단거리측정시 사용(단 가중치가 동일해야함)
다익스트라
간선의 가중치가 모두 양수일때 사용
우선순위 큐를 활용해서 구현
특정 노드로부터 다른 노드들 까지의 최단거리를 구할 수 있음.
그리디 알고리즘
O(ElogV)
7일차
DP
이전의 계산한 값을 재사용하여 하나의 문제를 한번만 풀게 하는 알고리즘 패러다임.
Divide & Conquer과 비슷하지만 중간 결과를 저장하여 효율성을 높인다는 것에서 차이.
이전 계산값을 메모리에 저장해 반복 작업을 줄이는 것이 핵심
조건
- Overlapping Subproblem (겹치는 작은 문제) : 어떤한 문제가 여러개의 동일한 하위 문제로 쪼갤 수 있어야 함
- Optimal Substructure (최적 부분 구조) : 문제의 정답을 작은 문제의 정답에서 구할 수 있어야 함
종류
- Top Down Dp: 가장 큰 문제부터 시작해 작은 문제를 푸는 방법 (주로 재귀를 활용하며 메모이제이션을 활용)
- Bottom Up Dp: 작은 문제에서 시작해 큰 문제를 해결하는 방식 (주로 반복문으로 해결 점화식과 base case가 필요 -> tabulation)
팁
그리디 알고리즘이 최적 부분 구조 조건을 만족하지 못해 사용하지 못할때 사용해볼 수 있는 전략.
8일차
생략 DP가 동일하게 나옴
9일차
서로소 집합
서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합(분리집합)
유니온 파인드
용도: 서로 다른 원소가 같은 집합에 속해있는지 아닌지 판별할때 사용, 사이클 판정
크루스칼 알고리즘의 베이스가 됌.
-
find(x)
두번째가 메모이제이션을 활용한 기법으로 추천됌.(경로 압축) 시간복잡도는 O(a(N)) 아커만 함수
-
merge(x, y)
단지 해당 구현에는 없지만 전체 노드 원소개수가 큰쪽을 부모로 원소 개수가 작은 집합을 자식으로 둬야 시간복잡도가 작아진다.
만약 x == y라면 사이클이 발생하는 경우이다. (원래 분리집합이 아닌 경우)
전체 N개의 원소에 대해서 유니온 파인드를 진행한다면?
O(N a(N)) -> 약 O(N)
10일차
강의없음
