viamemine

📍 퀵 정렬: 분할정복방법론N 개의 값이 있고, 특정 값(pivot) 이상/미만으로 분류pivot을 중심으로 왼쪽에는 더 작은 숫자들, 오른쪽에는 더 큰 숫자들이 오도록 만들어준다.시간복잡도: 평균적으로 O(NlogN) / 최악의 경우 O(N^2)병합 정렬은 정확히 logN회 분할이 되지만, 퀵 정렬은 평균적으로 logN회 분할 수행퀵 정렬의 성능은 pivot을 무엇으로 잡느냐에 따라 결정됨pivot은 맨 왼쪽, 맨 오른쪽, 가운데 값 중 중앙값을 선택  💬 python 코드 n 개의 원소가 주어졌을 때, 퀵 정렬을 이용해 n 개의 숫자를 오름차순으로 정렬n = int(input())arr = list(map(int, input().split()))# arr = [17, 21, 15, 29, 81, ..

📍 병합 정렬: 반으로 나눠서 정렬하는, 더 빠른 정렬1) 배열의 길이가 1개가 될 때까지 재귀적으로 쪼개기 → O(logN)2) 쪼갠 배열을 합쳐가며 정렬된 배열로 만들기 → O(N)분할 정복 (Divide and Conquer)시간복잡도: O(NlogN)   💬 python 코드 n 개의 원소가 주어졌을 때, 병합 정렬을 이용해 n 개의 숫자를 오름차순으로 정렬 n = int(input())arr = list(map(int, input().split()))merged_arr = [0] * ndef merge(low, mid, high): i = low; j = mid + 1 k = low while i

📍 기수 정렬: 값을 비교하지 않는 특이한 정렬맨 뒤에 있는 자릿수부터 정렬, 점점 앞으로 이동하며 각 자릿수를 정렬시간복잡도: O(kn)k는 자릿수 각각의 데이터에 대해 매 자릿수마다 분류작업을 하기 때문에, 분류작업이 k번 반복됨  💬 python 코드function radix_sort(arr, k) for pos = k - 1 ... pos >= 0: set arr_new = [10][] for i = 0 ... i

📍 삽입 정렬: 앞에서부터 순서대로 보면서, 앞에 있는 모든 원소가 정렬되어 있다는 가정 하에서 현재 원소의 위치를 적절하게 집어넣는 정렬시간복잡도: O(N^2)n 개의 원소에 대해 값 삽입을 수행하는데, 2번째 원소의 경우에는 최대 1개의 원소를 이동해야 하고, 3번째 원소의 경우에는 최대 2개의 원소를 이동해야 하며, n번째 원소까지 삽입하는 경우에는 최대 n-1개의 원소가 이동해야 함  💬 python 코드n 개의 원소가 주어졌을 때, 삽입 정렬을 이용해 n 개의 숫자를 오름차순으로 정렬n = int(input())arr = list(map(int, input().split()))for i in range(1, n): key = arr[i] j = i-1 while j >..

📍 선택 정렬: 앞에서 부터 정렬하는, 일상적인 방법의 알고리즘전체 값 중 가장 작은 값을 찾고, 해당 값을 맨 첫 번째에 배치함첫 번째 값을 제외하고 가장 작은 값을 찾아 두 번째에 배치함 두 번째, 세 번째, ... , n-1 번째 값을 제외하고 가장 작은 값을 찾아 정해진 위치에 배치함시간 복잡도: O(N^2)n-1, n-2, ..., 2, 1번의 비교 연산을 수행해야 하기 때문에, n(n-1)/2번의 연산 필요함 💬 python 코드n 개의 원소가 주어졌을 때, 선택 정렬을 이용해 n 개의 숫자를 오름차순으로 정렬n = int(input())arr = list(map(int, input().split()))for i in range(n-1): min_idx = i for j in r..

📍 버블 정렬: 가장 단순한 정렬 알고리즘 첫번째와 두번째 값을 비교하고, 두번째와 세번째 값을 비교하고, ..., n-1번째와 n번째 값을 비교한다. 순서가 맞지 않은 값을 서로 교환하고, 정렬이 될 때까지 반복한다.비효율적인 알고리즘시간복잡도: O(N^2)ex) 5, 4, 3, 2, 1이라는 데이터가 존재한다고 가정할 때 한 바퀴 돌면 4, 3, 2, 1, 5로 정렬됨두 바퀴 돌면 3, 2, 1, 4, 5로 정렬됨N개의 숫자가 N-1 바퀴 돌아야 함 ( 나머지 한 개는 자연스럽게 정렬되기 때문에 고려하지 않아도 됨) 💬 python 코드 n 개의 원소가 주어졌을 때, 버블 정렬을 이용해 n개의 숫자를 오름차순으로 정렬n = int(input())arr = list(map(int, input().s..

batch size는 그저 모든 데이터를 한 번에 학습하기에는 학습량이 너무 많기 떄문에 속도 측면으로 데이터를 쪼개어 학습한다고만 생각할 수 있다. 하지만 loss 수렴 측면에서도 batch size가 중요한 역할을 한다. batch size 작으면 learning rate도 작게 batch size 크면 learning rate도 크게 .... 1. Learning rate가 클 때, Learning rate가 크면, 한 번의 step에서 파라미터 학습이 크게 진행되기 때문에 보폭이 커진다. 보폭이 크기 때문에 조금 더 빨리 수렴이 가능하고, 그만큼 local minimum에 빠질 위험이 적다. 하지만 너무 크면, Loss가 전혀 줄지 않을 수도 있다. 수렴하지 않는 것이다. 2. Learning r..

개와 고양이 이미지를 분류하는 task를 수행한다고 할 때, 이미 학습된 pre-trained model을 불러와서 사전학습된 모델의 파라미터를 적용하는 transfer learning을 수행한다. 이 과정에서 개와 고양이에 대한 binary classification만 하면 되므로 불러온 모델이 현재 task에 좀 더 집중하도록 fine-tuning을 해주는 것이다. 새로운 데이터로 한 번 더 가중치(사전학습된 모델의 파라미터)를 조정해주는 것이다. 💥 Transfer Learning과 Fine-tuning의 개념 두 개의 용어가 혼동될 수 있지만, transfer learning과 fine-tuning을 같은 개념으로 이해해도 무방하다. 큰 데이터로 사전학습된 backbone 모델을 통해 featur..

A Survey of Vision-Language Pre-Trained Models 📍 Summary Pre-training은 처음에 computer vision에서 유용하다고 밝혀졌는데, Transformer와 BERT의 등장 이후 NLP에서도 만연하게 사용되었다. 이는 Transformer가 long range dependency를 model하는 강력한 능력 덕분에 Pretrained Language Models (PLM)의 backbone이 되었다. 이후, vision과 language modalities를 모두 model하는 Vision-Language Pre-Trained Models이 연구되었다. 📍 VL-PTM의 3단계 1. image와 text의 의미를 유지한 채 latent represe..

문제 잘못된 풀이 n = int(input()) dp = [0] * n dp[0] = 1 dp[1] = 2 for i in range(2, n): dp[i] = dp[i-1] + dp[i-2] print(dp[n-1] % 10007) 해당 문제는 다이나믹 프로그래밍으로 해결할 수 있다. 2*1일 때, 1 / 2*2일 때, 2 / 2*3일 때, 3 / 2*4일 때, 5 / 2*5일 때, 8 으로, dp[i] = dp[i-1] + dp[i-2]를 만족한다. 하지만 해당 풀이는 dp의 사이즈를 n으로 지정하면서 런타임 오류(IndexError)가 발생하였다. 올바른 풀이 n = int(input()) dp = [0] * 1000 dp[0] = 1 dp[1] = 2 for i in range(2, n): dp[..