정리 노트

이 포스트는 국민대학교 소프트웨어학부 '알고리즘' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! Backtracking이란? Backtracking(백 트래킹)은 해답을 구할 수 없는 경우가 나온 경우, 더 진행하는 것을 포기하고 이전 상태로 되돌아가서 다른 경우를 찾는 방법을 말합니다. 흔히 생각할 수 있는 예시가 '미로 찾기'입니다. 미로를 빠져나가는 방법들 중에서 가장 많이 알려진 방법이 '우수법' 입니다. 오른손으로 한쪽 벽을 짚으면서 걸으면 무조건 미로를 빠져나갈 수 있는 방법입니다. https://youtu.be/YS4ng_vKr7o?t=89 우수법으로 나아가는 과정이 백트래킹과 같다고 생각이 됩니다. 위와 같은 ..

이 포스트는 국민대학교 소프트웨어학부 '알고리즘' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 동적 계획법 동적 계획법은 분할 정복 기법으로 문제를 해결하는 방식과 유사합니다. 분할 정복 기법에 대해 모르시는 분들은 제가 저번에 적은 포스트를 참고하셔도 됩니다. 2022.10.17 - [개념 정리/알고리즘] - 분할 정복 기법(Divide & Conquer) 동적 계획법도 하나의 문제를 여러 작은 문제들로 나눈 다음, 각 문제들의 해답을 이용해서 원래 문제의 답을 구합니다. 분할 정복 기법과의 차이점은 여러 작은 문제들의 연관성입니다. 예를 들어, 병합 정렬이나 퀵 정렬을 구현할 때 나눠지는 배열들은 서로 상관이 없습니다...

이 글은 제가 저번에 적은 글에 이어서 작성하는 글입니다. 그러니 이전 글을 읽고 이 글을 읽어주시기 바랍니다. 2022.10.22 - [개념 정리/알고리즘] - 퀵 정렬(Quick Sort) (with Lomuto) 두 번째 Partiton 방법 이번에 소개하는 partition 방법은 Hoare가 제시한 방법입니다.(사실 퀵 정렬 알고리즘을 제안한 사람이 Hoare입니다.) 이번 partition도 pivot 값을 배열의 가장 왼쪽 값으로 정하고 시작합니다. i와 j의 초기값은 각각 -1, 배열의 길이로 배열의 양 끝을 지정하는 인덱스입니다. 먼저 i의 값을 하나 증가시키고 i번째 원소가 pivot값보다 작으면 다시 i값을 늘려줍니다. 이 과정을 배열의 i번째 값이 pivot보다 크거나 같을 때까지 ..

이 글은 Divide & Conquer에 대해 기본적인 내용을 알고 계신다는 가정 하에 작성되었습니다. 따라서 분할 정복 기법에 대해 잘 모르시는 분들은 제가 저번에 썼던 글을 참고하셔도 됩니다. 2022.10.17 - [개념 정리/알고리즘] - 분할 정복 기법(Divide & Conquer) 퀵 정렬 이름 그대로 빠르게 정렬하는 알고리즘입니다. 퀵 정렬도 분할 정복 기법 방식으로 설명할 수 있습니다. Divide: 배열의 원소들 중 임의의 원소 하나를 기준(pivot)으로 정하고 기준보다 작은 원소들의 그룹과 큰 원소들의 그룹으로 나눕니다. Conquer: 기준점을 중심으로 나누어진 두 그룹을 recursive 하게 quick sort를 수행합니다. 이 설명에서는 'combine' 과정이 빠져있습니다...

이번 포스트는 병합 정렬에 대한 두 번째 글입니다. 그러니 병합 정렬에 대해 잘 모르시는 분은 제가 저번에 적었던 글을 참고하셔도 됩니다. 2022.10.20 - [개념 정리/알고리즘] - 병합 정렬(Merge Sort) 병합 정렬 과정 다시 보기 병합 정렬을 간단하게 얘기하면 배열을 반씩 나누고 나눠진 배열들을 정렬시킨 후 정렬된 두 배열을 다시 하나의 배열로 합치는 정렬 알고리즘이었습니다. 이 과정을 Divide & Conquer의 시각에 맞춰서 보면 세 단계로 나눌 수 있었고 각각 Divide, Conquer, Combine(Merge)로 볼 수 있었습니다. 이번에는 병합 정렬 과정을 Top-down, Bottom-up 방식으로 나눠서 보겠습니다. Top-down: 하나의 커다란 문제를 여러 개의 ..

이 글은 Divide & Conquer(분할 정복 기법)을 알고 계신다는 가정 하에 작성되었습니다. 분할 정복에 대한 글은 제가 저번에 쓴 글을 참고하셔도 됩니다. 2022.10.17 - [개념 정리/알고리즘] - 분할 정복 기법(Divide & Conquer) 병합 정렬(Merge Sort) 병합 정렬을 하는 과정을 분할 정복 기법을 사용해서 설명할 수 있습니다. 전체 배열을 반씩 나눕니다(Divide). 이 과정은 재귀적으로 진행됩니다. 반씩 나눈 배열들을 정렬합니다(Conquer). 정렬한 배열들을 다시 하나로 합칩니다(Combine). 여기서의 base case는 배열의 길이가 1인 경우입니다. 배열의 길이가 1이면 이 자체로 정렬이 되어있기 때문에 배열의 길이가 1이면 반씩 나누는 것을 그만둡니..

이 포스트는 국민대학교 소프트웨어학부 '컴퓨터 비전' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 질문과 오류 지적은 매우 환영합니다! Gradient Descent(경사 하강) 손실 함수를 MSE Loss(오차 제곱의 평균), f라고 하고, 변경해야 할 값을 w라고 할 때 $$ w = w - \alpha * \frac{\partial f} {\partial w} $$의 식을 통해서 고쳐 나갑니다. MSE 손실 함수(아래 식에서의 'f')는 dataset의 모든 값들을 보고 오차를 계산합니다. $$ f(w) = \frac{1} {N} \sum_{i = 1}^{n} g^{(i)}(y(x^{(i)}, w), t^{(i)}) \quad \text{(} x^{..

이 포스트는 국민대학교 소프트웨어학부 '알고리즘' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다! 문제 해결 과정 분할(Divide): 문제를 2개 이상의 같은 형식의 작은 문제들로 나눕니다. 정복(Conquer): 나눠진 작은 문제들은 재귀적으로 해결합니다. 나눠서 문제를 해결할 필요가 없을 때까지 계속 분할해 나갑니다. 통합(Combine): 풀어낸 작은 문제들의 해답들을 합쳐서 원래 문제의 해답으로 만듭니다. 위에 적은 과정이 주로 분할 정복 기법을 사용해 문제를 풀어나가는 과정입니다. 정복 과정에서 문제들을 재귀적으로 해결해 나가기 때문에 재귀를 이용해서 구현하게 됩니다. 따라서 재귀에 대해 어느 정도 아셔야 합니다. ..