Q&A 14주차

1. b) dynamic programming (bottom-up 방식)

2. negative-weight cycle이 존재한다면, 대각성분들 중에 음수가 등장할 것이다. (대각 성분 확인하기!)

   • 플로이드 워셜 알고리즘에서 D(0) → 0은 중간에 거치는 노드가 0개일 때를 의미(초기상태)
   • D(k) : k를 도착노드로 하는 경우 + k에서 출발하는 경우 들에 대해서 생각해서 k라는 노드를 거쳐가도록 했을때의 가중치의 최소합을 D(k) 테이블에 갱신함
   • k의 최대값이 4라고 했을 때 예시!

   

   • 노란색으로 칠해진 부분에 대해서 확인을 하고 노란색 부분 제외한 나머지 부분을 갱신해주는 것임! 확인한 노란색부분 갱신 x

3. d) -3

4. DFS, BFS가 더 낫다. (traversal-based algorithms is better)

   • n-1 : connected
   • n * n-1 / 2 : undirected fully connected
   • n * n-1 : directed fully connected
   • 셋 중에 위로 올라갈수록 sparse, 아래로 내려갈수록 dense
   • 플로이드 워셜 시간복잡도 : O(N^3) ← n*n matrix가 n번 반복됨
     • O(n^3) = O(|V|^3)
   • DFS, BFS 시간 복잡도 : O(n+m) = O(|V| + |e|)
   • 플로이드 워셜에서는 sparse할수록 matrix에 0값이 많아지는데 플로이드 워셜에서 0값을 읽는 것 자체가 시간복잡도 면에서 손해를 일으키기에 DFS, BFS가 더 낫다.
     • BFS, DFS = Θ(n^2) / 플로이드 워셜 = Θ(n^3)

5. 플로이드 워셜 알고리즘 적용해봐라!

6. maximum flow : 23

   • maximum flow는 물을 옮긴다고 생각했을 때, 얼마나 많은 양의 물(유량, flow)을 옮길 수 있나? Q&A 6.1~6.3의 과정을 잘 봐두자.
   • s→t로 물을 보낼 수 있는 경로(처음엔 가장 많은 노드를 지나는 경로, 경로는 BFS, DFS로 찾는다.)를 찾은 후, 그 경로에서 가장 작은 가중치를 가진 값만큼만 물을 옮길 수 있음 → 지나온 경로에서 그 만큼의 값을 빼서 갱신해주면 된다.

7. while문(3번줄) + 4번줄은 Maxflow 횟수만큼 DFS, BFS 반복해야 됌 나머지는 다 O(E)

   • 전체 시복 : O(maximumflow*(V+E)) (DFS,BFS O(V+E))

8. network 앞 뒤로 상상의 s, t노드 1개씩을 있다고 가정하고 상상의 s노드, t노드와 연결된 노드들의 엣지의 가중치를 ∞로 설정하고 푼다.

27강 Machine Learning Algorithms

• Machine Learning

  • 왜 사용하는가?

    • 손글씨, 얼굴 인식과 같은 경우에 문제를 해결하는 프로그램을 작성하는 것은 굉장히 어렵다.
    • 손으로 프로그램을 작성하는 대신 주어진 입력에 대한 올바른 출력을 지정하는 예시를 얻을 수 있다.
      • 머신 러닝은 이러한 예시들을 사용하여 작업을 하는 프로그램을 만든다.

  • 언제 사용하는가?

    • 화성을 탐색, 얼굴, 손글씨 인식, 사용자의 생체정보, 책/영화 추천 등등에 사용 됌
    • 많고 다양한 이용가능한 데이터가 있고, 계산적인 과정과 공간이 싸다.
    • 경쟁 이점

    

  • 머신러닝이란 무엇일까?

    • 데이터로부터 학습, 히든패턴을 파악, 명시적인 프로그래밍이 아니다.
    • Domain Knowledge : 미래에 굉장히 중요해질것

    

    • 톰 미셀은 머신러닝은 자동적으로 경험으로부터 성능을 향상시킬 수 있다고 말했다.

  • 비지도학습/지도학습

    • 지도학습 : 레이블링된(정답이 적혀져있는) 데이터를 통해서 function을 유추하는 방식

      • 데이터를 모델을 통해 학습시키고 반복을 통해 성능을 향상시켜 predicting(testing)한다!

      

      • 지도학습의 적용
        • 패턴을 인식하는 것(손글씨 얼굴인식)
        • 예측하는 것(주가, 환율 예측)

    • 비지도학습 : 레이블링되지 않은 데이터를 통해서 히든 패턴이나 규칙을 찾는 방식

      • clustering을 주로 사용한다. → 유사한 데이터들을 묶어서 다른 클러스터(비교적 다른) 데이터들과 구분한다.

      

      • 비지도학습의 적용
        • 클러스터링(소셜 네트워크, 의학적 사진을 보고 진단내리기, 이미지 인식)
        • 차원 축소(데이터 압축)

• Deep Learning

  • 머신러닝보다 더 많은 양의 데이터를 처리가능하다.

    • medical, sport, network 주로 이분야에서 딥러닝 많이 사용

  • Input layer 1개, Hidden layers(여러개), output layer 1개로 구성

    • hidden layer가 1개보다 많다면 deep하다는 용어를 사용하고, 그러한 네트워크를 deep(shallow) neural networks라고 부른다.

    

  • 뉴런의 값은 이전 layer의 뉴런에 영향을 받아 계산된다.

  

  • 딥러닝 모델의 종류
    • Feedforward neural networks → independent variables
    • Convolutional neural networks CNN → 이미지 분류에 사용
    • Recurrent neural networks RNN → 시계열자료 예측에 사용
    • Transformer → natural language processing에 사용
    • Autoencoder → noise reduction
    • Generative adversarial networks → image 생성에 사용
  • 딥러닝의 적용

    • 가상 도우미 virtual assistants

      • siri, 구글 어시스턴트

    • Natural Language Processing

      • 정보 추출, 언어 변환, 질문답변 등등..

      

    • Healthcare

      • 건강 진단, 정신건강 챗봇 등등

    • Self-Driving Cars

      • 자율주행 자동차

    • Entertainment

      • 유튜브 알고리즘, 흑백 사진 컬러화, ai 얼굴 만들기 등등

    • Sports

      • AI 심판, 경기 분석, 경기 예측

    • Network Mobility Prediction

      • 5g, 6g 등등 네트워크를 통한 통신
  • 이러한 딥러닝의 적용 사례들은 딥러닝으로 성능을 엄청나게 향상시킬 수 있다는 것을 증명해준다!

28강 Machine Learning Algorithms

• 머신러닝 알고리즘 2가지
• Multiplicative-Weights Algorithms 곱셈 가중치 알고리즘