MJ 복습 블로그

저번 시간까지는 선형회귀의 가설을 H(x) = Wx + b 의 1차식 형태로 세워서 살펴보았다. 또한 이때 해당하는 Cost function과 그 cost를 최소화시키는 Gradient Descent Algorithm에 대해서 알아보았다. 만약 변수가 x 하나가 아니고 여러개가 되면 어떻게 될까? 예를 들어, 3개의 시험을 본다면 3개의 변수를 가지게 된다. H(x)의 가설 식을 다시 세워보자. H(x)를 구했으면 저번 시간에 배운 MSE loss function을 통해 cost 식을 세워볼 수 있다. 여기까지가 변수가 여러개일 때 선형회귀의 기본적인 틀이다. 만약 무수히 많은 변수가 있다면 우리는 가설 식을 일자로 쭉 써봐야할까? 이때 Matrix, 행렬을 이용할 수 있다. Matrix를 쓸 때 보통 ..

문제 이해제목에서부터 알 수 있듯이 이 문제는 최소 스패닝 트리 (Minimum Spanning Tree)를 찾는 문제이다.  먼저 트리이기 때문에 순환이 없는 그래프의 한 종류이다. 그 중 '최소'라는 것은 간선들의 가중치 합이 최소가 되어야 한다는 의미이다. 몇 가지 예상을 해보자면 우리에게 주어지는 그래프는 연결 그래프 일 것이다. 상식적으로 비연결 그래프에서 MST를 찾으라는 것 자체가 말이 안되기 때문이다.  하지만 그 안에는 순환하는 부분이 존재할 수 있을 것이다(모든 그래프가 트리가 아니기 때문). MST 유형을 몰랐을 때는 BFS, DFS 등의 방향으로 생각하며 도대체 어떻게 풀어야하나 많은 고민을 했던 것 같다. 문제 자체가 MST 기본을 연습하는 문제이기에 알고리즘만 ..

유니온 파인드 알고리즘은 대표적인 그래프 알고리즘이다. 두 노드가 같은 집합에 있는지 확인할 때 유용하게 이용된다. 유니온 파인드의 대표적인 연산에는 두 노드를 합치는 Union 연산, 루트 노드를 찾는 Find 연산이 있다. 추상적으로 생각했을 때는 트리 구조로 생각할 수 있다. 유니온 파인드는 그림으로 이해하는 것이 편리했다. 다른 블로그의 이해하기 쉬운 그림이 보여서 가져왔다.이 예시로 좀 더 구체적으로 살펴보자.   유니온 파인드 알고리즘을 위해서는 먼저 원하는 노드 수 만큼의 리스트를 만들고, 각 노드에 대해 초깃값으로 각각의 노드 번호를 부여한다. 위의 그림을 해석하자면 각각의 노드가 각자 다른 집합에 속하고 있는 상태로 해석할 수 있다.   1. Union 연산   만약 위의 그림과 같이 1..

거스름돈 문제와 앞선 ATM문제를 풀다보니 이 문제를 읽었을 때는 그리디 문제라는 것이 눈에 보였다.  문제 이해강호가 손님을 입장시킬 때 팁을 받는다. 손님들이 생각하고 있는 팁의 금액이 주어진다. 하지만 이 팁을 다 받을 수 있는 것이 아니다. 최종적으로 받는 팁 = 원래 생각하던 팁 - (손님의 입장 등수 - 1) 즉 원래 생각하던 팁은 주어져 있기 때문에 우리가 바꿀 수 있는 것은 "손님의 등수" 라는 것을 쉽게 알 수 있다. 문제의 출력으로 원하는 것은 강호가 받을 수 있는 팁의 최댓값이다. 손님의 등수를 기준으로 매 순간 최선의 선택을 해야한다는 것을 알 수 있다.  해설내가 가장 먼저 떠올렸던 방법은 ATM에서 이용했던 방법이다. 처음부터 공식이 ..

들어가기 앞서학기 중에 전공과목을 병행하느라 포스팅을 거의 하지 못했다. 방학을 맞아 그동안 풀었던 문제들을 복습해보고 새롭게 푸는 문제들을 포스팅 할 계획이다. 저번학기 자료구조를 수강하며 더 많은 알고리즘을 접할 수 있던 것이 좋은 경험이 되었다.  ATM문제는 그리디 알고리즘에서 기초가 되는 문제이다.  그리디 알고리즘이란 이름에서도 알 수 있듯이 탐욕스러운 알고리즘이다. 즉, 지금 당장 우리가 하는 최선의 선택이 전체로 봤을 때도 최선의 선택인 경우 그리디 알고리즘을 이용할 수 있다. 여기서 내가 어렵게 느꼈던 점은 지금 당장의 선택이 이후 결과에 영향을 미치는 상황일 때 최선의 선택이 보장 될 수 있느냐였다. 이것이 그리디 문제가 어려운 이유이고, 앞으로 다양한 문제를 풀어보며 ..

모든 강의내용은 김성훈 교수님의 ‘모두를 위한 딥러닝’을 기반으로 한다. 저번 시간에는 cost function 중 결과값과 예측값의 오차를 제곱하는 MSE loss function을 배웠다. lec03에서는 이 cost를 어떻게 최소화 할 수 있는지를 알아본다. 이전에는 weight과 cost 두 가지의 변수를 가지는 hypothesis 배웠다. 하지만 이번 강의에서는 cost 최소화를 위해 hypothesis를 bias가 없는 형태로 단순화하여 배운다. 이전에 배웠던 데이터를 이용해본다. 위의 단순화된 가설을 이용하여 W=0, W=1, W=2 일 때 각각의 cost를 구해보자. 영상에는 나와있지 않지만 W=2일 때도 계산을 해보면 cost = 4.67이 된다. x축을 W, y축을 cost로 두고 그래..

모든 강의내용은 김성훈 교수님의 ‘모두를 위한 딥러닝’을 기반으로 한다. In statistics, linear regression is a statistical model which estimates the linear relationship between a scalar response and one or more explanatory variables (also known as dependent and independent variables). 위에 나와있는 글은 Wikipedia에 나와있는 선형회귀의 정의이다. 즉 쉽게 말하면 일종의 확률 모델인 것이다. 그 확률을 예측 하기 위하여 주어진 값들 사이에서 선형 관계를 찾아내고, weight과 bias를 도출하여 모델을 만든다. 굉장히 단순한 개념을..

모든 강의내용은 김성훈 교수님의 ‘모두를 위한 딥러닝’을 기반으로 한다. 첫 강의는 머신러닝의 기본적인 개념과 용어와 관련된 강의이다. 머신러닝의 등장 배경은 사람이 모든 조건을 코딩하는 것에 점차 한계점을 느낌에 있었다. 개념에서 볼 수 있듯이, 컴퓨터에게 직접 프로그래밍 할 수 있는 능력을 부여하는 것이다. 크게 정답을 알려주고 학습시키는 “지도학습(Supervised Learning)"과 정답을 알려주지 않은 채로 학습하는 ”비지도학습(Unsupervised Learning)"으로 구분한다. 이외에도 강화학습이라는 것도 존재하지만 이 강의에서는 다루지 않는다. 머신러닝이 문제해결을 위해 사용되는 대표적인 분야들에는 ‘이미지 라벨링’, ‘스팸 이메일 필터’, ‘다양한 점수 예측’ 등이 있다. 위의 예..

이번 문제는 paragraph 에 들어온 문자열 중 가장 많이 등장한 '단어'를 골라내는 문제이다. 대신 banned 리스트에 있는 단어들은 제외하고 따지는 것이 조건이다.(조건에도 쓰여있지만 banned 리스트에는 0개부터 100개까지의 단어가 들어올 수 있다) 입력에는 문자 뿐만 아니라 기호들도 섞여 있다는 것과답을 출력할 때 lowercase로 출력해야한다는 것을 기억해야한다.답은 '유일'하다는 조건이 있으므로 중복 답에 대해서는 고려하지 않아도 된다.  알고리즘을 풀 때 예외 케이스를 생각하는 것이 중요한데, 이런 문자열 혹은 리스트 입력을 받는 문제에서는 무한한 문자열/리스트비어있는 문자열/리스트(혹은 한개, 두개로 구성되어 있는)위 두 가지의 케이스를 주의해서 문제를 풀어..

이 문제는 로그 파일의 재정렬 이라는 문제이다. 문제 제목부터 어려워 보이지만 그저 리스트 속의 문자열을 파일로 볼 때, 문자파일과 숫자파일을 규칙에 맞게 정렬하면 되는 문제이다. 문제 조건:문자열의 제일 앞 단어는 Identifier(식별자)이다.문자로 구성된 문자파일은 모두 소문자로 구성된다.숫자 파일은 정수로 구성된다. 재배열 규칙:문자파일은 숫자파일보다 항상 앞에 온다.문자파일은 사전 순으로 재배열한다.식별자는 순서에 영향을 끼치지 않지만, 문자가 동일한 경우는 식별자의 순서로 배열한다.숫자파일은 입력 순서 그대로 배열한다.결국 복잡한 기준들을 모두 만족하는 정렬을 잘 해야한다...그렇다면 가장 큰 기준부터 세부적인 기준으로 들어가며 정렬하는 것이 바람직 할 것이다..