이분 탐색이란, 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 때까지 탐색하는 알고리즘이다. 1. 이분 탐색의 조건 반드시 오름차순으로 정렬된 상태에서 시작해야 한다. 2. 이분 탐색 알고리즘 시간복잡도: O(logN) 반복문과 재귀 두 가지 방법을 사용할 수 있다. 자료를 오름차순으로 정렬한다. 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다. mid 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2번과 3번을 반복한다. ⓐ target이 mid 값 보다 작으면 end를 mid 왼쪽 값으로 바꿔준다. (절반의 왼쪽 탐색) ⓑ target이 mid 값 보다 크면 start를 mi..
가장 긴 증가하는 부분 수열 알고리즘 이란, 왼쪽에서 오른쪽 방향으로 탐색할 때 오름차순으로 증가하는 부분 수열 중 가장 길이가 긴 부분 수열을 찾는 알고리즘이다. 0 1 2 3 4 5 6 10 40 20 50 30 40 60 위의 리스트에서 증가하는 부분 수열은 {10,40,50,60}, {10,20,50,60}, {10,20,30,40,60}, {40, 50, 60} 이 있다. 여기서 가장 긴 증가하는 부분 수열은 {10,20,30,40,60}이며, 부분 수열의 길이는 5가 된다. LIS 알고리즘은 두 가지 방법으로 구성될 수 있다. DP 활용 방법 이분탐색 활용 방법 1. LIS 알고리즘 (DP 활용) 시간복잡도: O(N**2) 1.1. DP 초기화 DP에는 부분 수열의 길이가 담기기 때문에 DP는..
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 누적합
- 코딩테스트실력진단
- python
- Prefix sum
- greedy
- dfs
- lis
- 트랜스포머
- 수학
- 알고리즘
- Algorithm
- 백준
- 코딩테스트
- 구현
- 이분탐색
- DP
- BFS
- 코드트리
- 그리디
- Look-ahead Mask
- MySQL
- Transformer
- pytorch
- padding mask
- 분리집합
- COLAB
- disjoint set
- FastAPI
- 파이썬
- boj