Dev On The Coffee Dev On The Coffee

# 문제 내 풀이 # 내 풀이 - 시간 복잡도 O(N²) def solution(phone_book): for i in range(len(phone_book)): for j in range(i + 1, len(phone_book)): min_len = min(len(phone_book[i]), len(phone_book[j])) if phone_book[j][:min_len] == phone_book[i][:min_len]: return False return True 지향할 답안 # 모범 답안 - 시간 복잡도 O(NlogN) def solution(phoneBook): phoneBook = sorted(phoneBook) for p1, p2 in zip(phoneBook, phoneBook[1:]): ..

# 최단 경로 알고리즘 (Shortest Path Algorithm) 최단 경로 알고리즘(Shortest Path Algorithm)이란 가장 짧은 경로를 찾는 알고리즘을 말한다. 최단 경로를 찾는 것은 여러가지 상황이 존재할 수 있는데, 대표적으로 (1) 한 지점에서 다른 한 지점까지의 최단 경로를 찾는 상황 (2) 한 지점에서 다른 모든 지점까지의 최단 경로를 찾는 상황 (3) 모든 지점에서 다른 모든 지점까지의 최단 경로를 찾는 상황을 생각해 볼 수 있다. 최단 경로 알고리즘은 일반적으로 그래프 자료구조를 기반으로 해 진행된다. 각 지점은 노드(Node)로 나타내고, 지점 사이를 연결하는 도로는 간선(Edge)으로 표현한다. 예를 들어, 노드는 도시, 마을, 국가 등으로, 간선은 도로, 통로 등으로..

# RNN (Recurrent Neural Network) Data는 여러가지 종류가 존재하는데, 그 중 Sequential data의 처리는 기존의 Neural Net이나 CNN으로 해결할 수 없다. Sequential data란 순서에 의미가 있어서 순서가 달리지면 의미가 손상되는 데이터를 말한다. Sequential data에는 음성 인식에서의 소리 신호, 세계 기온 변화 추이와 사례가 있는데, 특히 언어의 경우 문장은 하나의 단어뿐만 아니라 그 앞뒤의 단어들까지 고려해야 이해가 가능하다. 이러한 Sequential data를 처리하는 기법으로 RNN(Recurrent Neural Network)이 사용된다. RNN에서는 입력으로 계산한 값이 그 다음 것에 영향을 주도록 구조화한다. 위 그림에서 입..

# CNN (Convolutional Neural Network) CNN의 시작은 고양이의 시각 인식에 관한 연구에서 비롯됐다. 고양이가 어떤 사진을 인식할 때, 각 뉴런이 각각 자신이 맡은 사진의 특정 부분에만 활성화되는 것이 확인되었고, 컴퓨터의 이미지 인식에도 같은 방식을 적용하는 시도가 이뤄졌다. CNN은 Convolutional Layer와 ReLU, Pooling 계층의 반복적 조합으로 구성되며 끝에는 Fully Connected Layer로 결과를 분류한다. 실제로 CNN을 동작시킬 때, 행렬의 크기 단위로 설정한 filter를 사용해 전체 이미지를 부분으로 쪼개어 처리한다. 위 그림의 예는 3개의 RGB 컬러로 구성된 32 pixel X 32 pixel 이미지를 5 X 5 X 3의 크기를 ..

# Overfitting 문제 뉴럴 넷의 가중치 변수를 많이 생성하고, 레이어를 깊게 쌓을수록 해당 모델은 training data에 오버피팅될 가능성이 높다. 오버 피팅을 해결하기 위해서 1. training data를 더욱 늘리거나 2. feature(x 변수)를 줄이거나 (이 방법은 굳이 사용하지 않아도 괜찮다.) 3. Regularization(정규화)를 진행해 모델의 하이퍼플레인(선)을 보다 평탄하게 해주는 방법이 있다. (= 가중치에 너무 큰 값을 배정하지 않게 하자!) # 드롭아웃 (Dropout) 그러나 뉴럴넷 모델이 복잡해지면 정규화만으로 오버피팅에 대응하기 어려워지는데, 이 때 Dropout 기법이 사용된다. Dropout: A Simple Way to Prevent Neural Net..

# 가중치 초기화 (Weight initialization) 1. Zero initialization Geoffrey Hinton 교수가 찾아낸 Neural Network가 제대로 동작하지 않는 이유들 중 하나는 가중치 초기화의 문제이다. 예를들어, 극단적으로 가중치를 0으로 초기화하면 backpropagation으로 구한 x에 대한 f(x)의 기울기 값이 0이 되어 기울기가 소실되는 현상이 발생한다. 이 경우 학습이 원활하게 이뤄지지 않기 때문에, 가중치 초기화의 첫번째 유의점은 'w를 모두 0으로 설정하지 말자.'이다. 2. RBM을 이용한 initialization 가중치를 어떻게 설정해야할 지에 대한 문제는 깊이 들어갈수록 어려워졌는데, Hinton 교수는 A Fast Learning Algori..

# Backpropagation에서 나타나는 Vanishing gradient 문제 모델의 층을 많이 쌓을수록 보다 다양한 문제를 풀 수 있지만, backpropagation을 하며 input이 output에 미치는 영향을 알아볼 때 chain rule을 통해 얻은 미분값이 너무 작아져 학습이 잘 안되는 문제가 생긴다. 위와 같이 곱셈에 대한 오차역전파를 구할 때 x에 대한 g(x)의 미분 값은 y가 되는데, y는 시그모이드 함수를 통과한 출력 값이라 범위가 0~1 사이로 고정된다. 만일 x = -10이어서 y가 0에 근접한 수를 갖게 된다면, x에 대한 f(x)의 미분값은 g(x)에 대한 f(x)의 미분값 곱하기 y이기 때문에 0에 근접한 값을 갖게 된다. 이러한 과정을 계속 반복해 더욱 0에 가까운 ..

# XOR 문제 XOR 문제는 두 변수 x1, x2가 같다면 False를, 다르다면 True를 반환하는 문제이다. 많은 Neural Network 연구자들이 이 문제를 해결하기 위해 애썼지만, 이 문제는 하나의 유닛으로는 해결할 수 없다는 것이 수학적으로 증명될 정도로 해결하기 어려웠고 'Neural Network는 안된다'는 인식이 강해졌다. 이후 여러 개의 유닛을 사용하면 XOR 문제를 해결할 수 있음이 알려졌지만 어떻게 매개변수 w, b를 학습할 수 있을지에 대해 다시 한번 장벽에 부딪혔다. 하지만, 결국 Neural Network는 XOR 문제를 극복해냈는데 지금부터 어떻게 이것이 구현됐는지 살펴보고자 한다. # Neural Network로 XOR 문제 해결하기 1. Forward Propagat..