집밖은 위험해

슬라이딩 윈도우란?

- 고정 크기의 윈도우(마스크, 영역)을 이동하면서 윈도우 내 데이터를 이용하는 알고리즘

- 네트워크 호스트 간 패킷 흐름을 제어하기 위해서 고안됨.

네트워크와 서버 간의 연결 과정 3 way handshake

- 3 way handshake : 클라이언트와 서버간 연결 과정

1. 클라이언트(접속자)가  서버에 접속 요청 메시지(SYN)를 보낸다.

2. 서버는 접속 허가시 클라이언트에게 접속 요청 수락(SYN + ACK)을 보낸다.

 * Ack(Acknowledgement) : 긍정 응답

3. 클라이언트는 서버에 수락 확인(ACK)를 보내고 서버와 연결이 성립 ESTABLISHED된다.

슬라이딩 윈도우와 패킷 흐름 제어

- TCP 통신같이 연결 지향 프로토콜의 경우 패킷이 하나 하나 정상적으로 전달되었는지 확인(ACK)을 함.

- 패킷이 분실된 경우 재전송이 필요.

- 윈도우에 모든 패킷을 전송하고, 모든 패킷들이 전달이 확인 되면 윈도우를 옆으로 이동 시켜 다음 패킷을 전송시킴.

투포인터와 슬라이딩 윈도우

- 투포인터의 경우 정렬된 배열에서 두 포인터를 이용하여 알고리즘 문제를 풀이해감.

- 슬라이딩 윈도우는 정렬 여부에 상관 없이 일정 크기의 윈도우를 사용함.

슬라이딩 윈도우 예시

1. 물체 검출 Object Detection

- 고정 크기의 윈도우의 이미지를 합성곱 신경망에 입력으로 주어 물건을 검출

- 다양한 크기의 물체를 검출하기 위해 다양한 크기의 윈도우를 사용.

- 계산 비용이 너무 커져 잘 사용되지 않음.

2. 이동 평균 Moving Average

- 특정 지점의 값을 앞 뒤 일정 구간의 평균 값으로 지정

- 노이즈 제거(스무딩)에 주로 사용됨.

퀵 정렬 개요 quick sort 

- 영국의 컴퓨터 과학자 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘

 * 토니 호어는 프로그래밍 언어의 정의와 설계에 대한 공헌으로 튜링상 수상

- 피벗을 기준으로 작은 데이터는 앞으로, 큰 데이터는 뒤로 분리해나가며 정리하는 방법.

- n개의 데이터 정렬시. 최악의 경우 O($n^2$), 평균적으로 O(n log n)번의 복잡도를 가진다.

퀵 정렬 알고리즘 

1. 리스트에서 하나의 원소를 고르고, 이 원소를 피벗이라 부른다.

2. 피벗을 기준으로 작은 원소들은 피벗 앞으로, 큰 원소들은 피벗의 뒤로 리스트를 둘로 나눈다.

3. 분할된 두 리스트에 대해 재귀적으로 수행한다.

퀵 정렬 예제

(1)

5 - 3 - 7 - 6 - 2 - 1 - 4 - 8

                p

5 - 3 - 2 - 1 - 4 - 6 - 7 - 8

                          p

(2)

5 - 3 - 2 - 1 - 4     6    7 - 8

     p                                p

2 - 1 - 3 - 5 - 4     6 - 7 - 8

           p

(3)

2 - 1       3   5 - 4   6-7-8

p                  p 

1 - 2        3   4 - 5   6-7-8

(4) 

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8

퀵 정렬 예제 2

퀵 정렬의 시간 복잡도

- 길이가 n인 리스트, 매번 n번 비교

- 재귀 호출 횟수가 $log_{2} n$

- 평균 시간 복잡도 : n $log_{2} n$

 시간 복잡도 비교

지난번 그래프 정리 글에서 그래프에 관련한 기본적인 이론과 활용 예시 들을 간단하게 살펴보았고,

ref : throwexception.tistory.com/1185

이번에는 그래프의 역사적인 배경과 다양한 문제들, 그래프 탐색 등에 대해 알아보자.

1. 그래프 이론의 시작 : 쾨니흐스베르크의 다리

- 오일러가 1736년에 쓴 쾨니히스베르크의 다리 문제에 대한 논문에서부터 시작됨

- 질문 : 프로이센 쾨니히스베르크에는 다리가 7개가 있는데, 모든 다리를 한 번씩만 건너서 모두 지나갈수 있을까?

- 아래의 그림은 쾨니히스베르크의 지도

2. 오일러 경로 Eulerian Path

- 오일러는 강으로 나눠지는 육지들을 A ~ D라고 이름을 주고, 각 다리마다 a ~ g라는 이름으로 

- 여기서 A ~ D는 노드/정점이며, a ~ g 에지/간선이 된다.

- 아래의 그림은 오일러가 1736년 발표한 논문에서의 다리 스캐치

- 아래의 그림은 쾨니히스베르크의 다리를 그래프로 나타낸 결과물

- 오일러는 정점/노드가 짝수개의 차수를 갖는다면 모든 다리를 한번씩 건너는게 가능하다고 정리

 * 오일러 경로 : 유한 그래프 Finite Graph의 모든 에지/간선를 한번씩 통과하는 경로(한붓 그리기)

 => 쾨니히스베르크의 다리는 정점 갯수가 짝수 개의 차수가 아니므로 오일러 경로가 아니다/한붓 그리기가 안된다.

3. 해밀턴 경로 Hamilton path

3.1 해밀턴 경로 개요

- 그래프이론에서 오일러 경로와 비슷한 경로로 해밀턴 경로가 있다.

- 해밀턴 경로 : 모든 정점을 한번씩 방문하는 그래프 경로

  * 오일러 경로는 모든 에지를 한번씩 방문한다면, 해밀턴 경로는 모든 정점을 한번씩 방문해야함.

- 해밀턴 경로 찾기 -> 최적 알고리즘이 없는 NP-완전/NP-complete 문제

ref : ko.wikipedia.org/wiki/%ED%95%B4%EB%B0%80%ED%84%B4_%EA%B2%BD%EB%A1%9C

* 오일러경로와 해밀턴 경로의 비교

* 입체 도형의 해밀턴 경로들

3.2 해밀턴 순환

- 해밀턴 순환 출발점으로 돌아오는 해밀턴 경로

3.3 외판원 문제 Travelling Salesman Problem : TSP

- 각 도시를 방문하고 최단 경로를 찾는 문제

- NP-난해에 속하는 문제로, 계산 복잡도 이론에서 최적의 해를 구하기 힘든 문제의 대표적인 예시가 된다.

 * 다항식 시간 내 풀수 있는 알고리즘이 없으므로 모의 담금질이나 유전 알고리즘으로 근사해를 구한다!

ref : ko.wikipedia.org/wiki/%EC%99%B8%ED%8C%90%EC%9B%90_%EB%AC%B8%EC%A0%9C

- Question : 도시가 20개인 경우, 최적의 경로를 찾으러면 얼마나 많은 경로를 다녀야 할까?

  => Answer : 20! = 2,432,902,008,176,640,000  이 중에서 가장 짧은 경로를 찾기는 힘들다.

4. 복잡도와 문제들

4.1 NP 복잡도

- 비결정론적 튜링 기계 Non Deterministic Turing Machine : NTM으로 다항 시간안에 풀수 있는 판별 문제의 집합

- NP는 Non deterministic Polynomial time의 약어

- NP에 속하는 문제들은 결정론적 튜링 기계로 다항 시간에 검증이 가능하다.

ref : ko.wikipedia.org/wiki/NP_(%EB%B3%B5%EC%9E%A1%EB%8F%84)

4.2 계산 복잡도 이론 Computational Complexity theory

- 컴퓨터 과학의 계산 이론의 한 분야로 알고리즘을 복잡도에 따라 분류한 문제의 모임을 구성하는 방법을 다룸

- 알고리즘 수행을 (실제 컴퓨터로도 가능하나) 튜링 기계를 이용한 방법을 사용

- 복잡도의 기준 : 시간 복잡도(알고리즘 소요 시간)와 공간 복잡도(메모리 등 자원 사용량)

  => 복잡도에는 어떤게 있을까?

4.3 복잡도 종류

- 계산 복잡도에 따라 문제를 분류한 것

- 일반적인 정의 : 추상 기계 abstract machine이 O(f(n)) 만큼의 자원 R을 이용하여 풀수 있는 문제의 종류

- 복잡도 종류의 예시

   example 1) NP : 확률적 튜링기계가 다항 시간에 풀 수 있는 판정 문제의 집합

   example 2) PSPACE : 결정론적 튜링 기계가 다항 공간에서 풀 수 있는 판정 문제의 집합

  ref : ko.wikipedia.org/wiki/%EB%B3%B5%EC%9E%A1%EB%8F%84_%EC%A2%85%EB%A5%98

 => 추상 기계, 튜링 기계, 판정 문제, 다항 시간, 다항 공간란 무엇일까?

4.4 추상 기계 abstract machine

- 컴퓨터 하드웨어나 소프트웨어의 이상적인 모형, 추상컴퓨터라고도 부름

- 계산 이론에서 추상 기계를 사고 실험에서 사용해, 계산 가능성이나 알고리즘 복잡도 추정

- 추상 기계를 통해 실제 컴퓨터를 만들지 않더라도 실행 시간이나 메모리 등 자원이 얼마나 필요한지 예측 가능

* 사고실험 though experiment : 가상 시나리오가 어떻게 동작하는지 생각하는 방법. 경험적 방법(관찰, 실험)과 반대됨

ref : ko.wikipedia.org/wiki/%EC%B6%94%EC%83%81_%EA%B8%B0%EA%B3%84

- 아래는 사고 실험의 예시. 이발사는 누구를 면도해야 할까?

4.5 튜링 기계 Turing Machine

- 수학/이론 전산학에서의 튜링 머신 :계산을 할수 있는 기계를 대표하는 가상의 장치, 수학적 모형

- 1936년 튜링은 automatic의 a자를 따서 a-기계라는 이름을 붙였으나 창시자의 엘런 튜링의 이름을따 튜링 기계가 됨.

- 튜링 기계의 구성 : 무한한 길이의 테이프(저장공간)과 테이프에 정보를 쓰고 읽을 수 있는 기계, 그리고 어떻게 값을 줄지 기록하는 상태, 행동표로 구성

* 실제 컴퓨터는 CPU, GPU로 정보를 처리하고, 주/보조 기억장치로 정보를 저장

 => 튜링 머신은 실제 컴퓨터를 대신하여 사고 실험에 사용하기 위한 가상의 수학적 모형/장치

- 튜링이 말하는 튜링 머신의 정의

 "무한한 저장공간은 무한한 길이의 테이프로 나타나는데 이 테이프는 하나의 기호를 인쇄할 수 있는 크기의 정사각형들로 쪼개져있다. 언제든지 기계속에는 하나의 기호가 들어가있고 이를 "읽힌 기호"라고 한다. 이 기계는 "읽힌 기호"를 바꿀 수 있는데 그 기계의 행동은 오직 읽힌 기호만이 결정한다. 테이프는 앞뒤로 움직일 수 있어서 모든 기호들은 적어도 한번씩은 기계에게 읽힐 것이다"

ref : ko.wikipedia.org/wiki/%ED%8A%9C%EB%A7%81_%EA%B8%B0%EA%B3%84

- 아래는 세 정수를 다루는 어셈블리 코드

  1. EAX 레지스터(위치)에 10000h를 쓰기

  2. EAX 레지스터(위치)의 값과 40000h를 더하고 쓰기

  3. EAX 레지스터(위치)의 값과 20000h를 빼고 쓰기

  4. 모든 레지스터를 호출

4.6 결정 문제/판정 문제 Decision Problem

- 계산이론에서의 판정 문제 : 형식 체계에서 예-아니오로 답이 있는 질문

- example 1 : 두 수 x, y가 있을때 y는 x로 나누어 떨어지는가?

- 결정 문제와 알고리즘 : 판별 문제를 푸는데 사용되는 방법이 알고리즘.

- 결정 문제를 풀 수 있는 알고리즘이 존재한다. -> 결정 가능

- 결정 문제를 풀 수 있는 알고리즘이 존재하지 않는다. -> 결정 불가능

* 결정가능성 decidability : 해답을 내놓는 기계적인 절차/알고리즘이 존재하는 성질

ref : ko.wikipedia.org/wiki/%EA%B2%B0%EC%A0%95_%EB%AC%B8%EC%A0%9C

   ps. 판정 문제는 예 혹은 아니오라는 답이 존재하는 질문인데, 외판원 문제의 경우 경로같은 정답이 나온다. 복잡도 종류에서 말하는 판정 가능이란 예/아니오라는 범위를 넘어서 해답이 존재하는 문제를 말하는것 같다.

* 계산 이론에서 결정 Decision과 결정론적 deterministic이란 단어는 한글로 동일하게 결정이라 부르나 구분을 해야되는것으로 보인다.

4.7 결정론적 알고리즘 deterministic algorithm

- 예측한 그대로, 생각한 그대로 동작하는 알고리즘

- 대표적인 예시로 수학에서 사용하는 함수

- 한계 : 결정론적 알고리즘을 찾기 힘든 문제가 존재한다

   -> 예시 : NP-완전(실생활에 중요한 많은 문제들이 NP-완전. ex : TSP)

   => 비결정론적 알고리즘이 필요하다!

4.8 비결정론적 알고리즘 non deterministic algorithm 만들기

- 입력 이외의 외부 상태를 알고리즘에 적용

- 알고리즘이 시간에 민감하게 영향을 받도록 동작.

- 하드웨어의 오류를 반영하여 알고리즘 진행을 예상할 수 없게 한다. 

  => 예상한 대로 정확하게 동작하지 않는 알고리즘

- 비결정론적 알고리즘의 한계 : 비결정론적 튜링 기계를 이용하면 쉽게 풀수 있으나, 실제 구현하지 못함.

  => NP-완전 문제들의 근사해 approxminate solution이나 특이해를 구하는게 한계

ref : ko.wikipedia.org/wiki/%EA%B2%B0%EC%A0%95%EB%A1%A0%EC%A0%81_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

4,9 비결정론적 튜링 기계 Non deterministic Turing Machine(NTM)

- 튜링 머신에서 움직일수 있는 상태의 개수가 하나였던과 달리 움직일 수 있는 상태 갯수가 하나로 정히지지 않은 머신

- 이동 가능한 상태가 여러개 되거나 아예 없을 수 있음.

 => 기존의 컴퓨터는 쓰레드나 멀티프로세싱 등 병렬 처리 기법이 존재하지만, 모든 CPU의 연산들은 기계어까지 내려가서보면 병렬로 동작하는게 아니라 순차적으로 연산되니. 아예 병렬 연산이 가능한 기계를 말하는 것으로 보임.

ref : ko.wikipedia.org/wiki/%EB%B9%84%EA%B2%B0%EC%A0%95%EB%A1%A0%EC%A0%81_%ED%8A%9C%EB%A7%81_%EA%B8%B0%EA%B3%84

4.9 다항 시간 polynomial time과 복잡도 클래스

- 다항 시간 : T(n) = O(n^k)와 같이 다항 표현의 상한을 가지고 수행되는 알고리즘은 다항 시간을 가진다.

• P: 다항 시간동안 결정적 튜링 머신에서 해결할 수 있는 결정 문제의 복잡도 클래스
• NP: 다항 시간동안 비결정적 튜링 머신에서 해결할 수 있는 결정 문제의 복잡도 클래스
• ZPP: 다항 시간동안 확률적 튜링 머신에서 0의 에러확률로 해결할 수 있는 결정 문제의 복잡도 클래스
• RP: 다항 시간동안 확률적 튜링 머신에서 단방향 에러를 가지고 해결할 수 있는 결정 문제의 복잡도 클래스
• BPP: 다항 시간동안 확률적 튜링 머신에서 양방향 에러를 가지고 해결할 수 있는 결정 문제의 복잡도 클래스
• BQP: 다항 시간 동안 양자 튜링 머신에서 양방향 에러를 가지고 해결할 수 있는 결정 문제의 복잡도 클래스

ref :  ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84

=> P 문제 : 다항 시간동안 결정론적 튜링 머신으로 풀 수 있는 문제. (일반적인 알고리즘 테스트 문제들)

=> NP 문제 : 다항 시간동안 비결정론적 튜링 머신으로 푸는게 가능한 문제(P 문제를 포함함)

4.10 지금까지 본 내용들

- 계산복잡도 이론 : 알고리즘을 복잡도에 따라 어떻게 분류할지 연구하는 이론

- 판정 문제 decision problem : 실제로 해답을 찾을 수 있는 문제(해답이 존재하는 문제)

- 사고 실험 : 실제 하드웨어나 소프트웨어 없이 가상의 시나리오로 어떤 결과가 나오는지 다루는 실험.

- 튜링 머신 : 사고 실험에 사용하기 위한 가상의 장치. 실제 컴퓨터로 구현됨.

- 비결정론적 튜링 머신 NTM : 여러 상태를 동시에 처리 가능한 튜링 머신, 병렬 처리 가능한 가상 기계

- 결정론적 알고리즘 : 예측한 대로 동작하는 알고리즘. ex) 수학 함수

- 비결정론적 알고리즘 : 예측한대로 정확히 동작하지 않는 알고리즘. NTM으로 풀기가능 ex)NP-완전

- 다항 시간 알고리즘 : 시간 복잡도가 O(n^k)로 다항식 시간인 알고리즘.

=> 아래의 그림을 참고하여 대표적인 문제들을 살펴보자.

4.11 복잡도 정리

- EXPSPACE : 결정론적 튜링 기계가 O(2^{p(n)}) 공간으로 풀수 있는 판정 문제 집합. p(n)은 n에대한 다항함수

- EXPTIME : 결정론적 튜링 기계가 O(2^{p(n)}) 시간에 풀수 있는 모든 판정 문제 집합. p(n)엔 n에대한 다항함수

- PSPACE : 결정론/비결정론적 튜링기계가 시간에 상관없이, 다항 공간을 써서 풀수 있는 판정 문제 집합

- NP : 비결정론적 튜링기계 NTM으로 다항시간에 풀수 있는 판정 문제 집합.

- NP-HARD : 적어도 모든 NP 문제만큼 어려운 문제들의 집합

  * NP는 NTM으로 다항식 시간에 풀수 있는 문제 집합, NP-hard는 NP만큼이나 어려운 문제 집합점에서 다름

  * NP-Hard 중에서 NP에 속하지 않은 문제들이 존재.

- NP-Complete : NP-HARD이지만, NP로 바꿀수 있는 문제 집합

- P(PTIME) : 결정론적 튜링 기계로 다항 시간안에 풀수 있는 판정 문제 집합.

4.11. 해밀턴 경로와 외판원 문제를 계산 복집도 이론으로 보기

4.11.1 해밀턴 경로 문제와 외판원 문제의 관계

- 해밀턴 경로 : 한 번만 방문하는 경로

- 해밀턴 순환 : 한 번만 방문하여 출발지로 돌아오는 경로

- 외판원 문제 : 한 번만 방문하여 출발지로 돌아오는 경로 중가장 짧은 분류

=> 해밀턴 경로 > 해밀턴 순환 > 외판원 문제

4.11.2 문제 정의

 문제 1. 해밀턴 경로가 존재하는가?

 문제 2. 각 도시를 방문하고, 돌아오는 가장 짧은 경로 찾아라(최단거리 해밀턴 순환 찾기)

4.11.3 문제 1번 보기

 - 질문 : 해밀턴 경로가 존재하는가?

 - 예/아니오로 대답할 수 있는 결정 문제이며, 다항 시간에 검증이 가능한 NP 문제이며, NP-Hard -> NP-완전

4.11.4 문제 2번 보기

 - 질문 : 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾아라

 - 예/아니오로 대답할 수 있는 결정 문제가 아니므로, NP 문제가 아닐 수 있다. 

 - 증명된 NP-난해 문제이나 NP 문제가 아닐수 있어 NP-완전 문제가아니며, NP-난해

5. 그래프 순회 Graph Traversals, 그래프 탐색 Graph Search

5.1 그래프 탐색 개요

- 그래프 순회/탐색은 그래프가 가지고 있는 정점들을 방문하는 것을 말함.

- 대표적인 그래프 탐색 방법으로 깊이 우선 탐색 Depth First Search DFS와 너비 우선 탐색 Breadth First Search BFS

 * 위와 같은 기본적인 그래프 탐색 알고리즘에서 최적 탐색 방법과 경험적 탐색 방법을 활용하여 개선된 방법들이 존재

5.2 깊이 우선 탐색과 너비 우선 탐색

- DFS는 왼쪽 깊이 방향을 우선으로 탐색

- BFS는 너비 방향을 우선으로 탐색

5.3 백트래킹 BackTracking

- 탐색을 하다가 진행 할 수 없을때(후보 경로를 포기) 왔던 길을 되돌아서 탐색을 진행하는 것에서 유례

- DFS 같은 방식으로 탐색하는 모든 방법을 의미, 주로 재귀로 구현하며 기본적으로 DFS에 속함.

- 최적의 경우 적은 시행착오로 목표 도달하나 최악의 경우 모든 경우를 고려해야함

   * 브루트 포스와 다른 점은 가능성이 없는 경우 후보를 즉시 포기해서 되돌아간다는 점에서 개선됨.(가지치기)

ref : en.wikipedia.org/wiki/Backtracking

5.4 백트래킹과 제약충족 문제 Constraint Satisfaction Problems(CSP)

- 제약 충족 문제 : 제약 조건 Constraints를 충족하는 상태 States를 찾아내는 수학 문제.

- CSP의 예시 : 스도쿠, 십자말풀이, 퍼즐 문제, 문자열 파싱 등

- 제약 충족 문제를 푸는데 (가지치기로 최적화) 백트래킹이 필수적임.

ref : en.wikipedia.org/wiki/Constraint_satisfaction_problem

그래프에 대해서 정리를 하려고하는데

그래프 이론이 되는 위상 수학에 대해 잘 모르기도 하고

일단 생각 나는데로 정리하고자 한다.

1. 그래프 graph (자료 구조에서의 그래프)

- 노드 node(or 정점, 꼭지점 vertex)과 에지 edge로 구성된 자료 구조

- 노드 node / 정점 vertex :  하나의 지점

- 에지 edge / 간선 : 두 노드/정점 사이를 이어주는 경로

=> 그래프 G = (V, E)로 표기

2. 그래프 이론

* 그래프 이론에 대한 역사적인 배경은 이후에 설명하고 일단 그래프에 관한 전반적인 내용들을 설명한다.

2.1 Wikipedia에서 말하는 그래프 이론

- 정점(에지)과 간선(노드)로 이루어진 수학적 구조 그래프에 대한 연구 이론

- 그래프 관련 주요 용어 : 경로, 순환, 부분 그래프, 연결 그래프

- 그래프 종류 : 순환 그래프, 완전 그래프, 트리 등

- 그래프 이론의 연구 분야 : 대수적 그래프 이론, 위상 그래프 이론, 기하 그래프 이론, 확률 그래프 이론, 알고리즘 그래프 이론

 * 알고리즘 그래프 이론 : 그래프를 이용해 알고리즘 문제를 해결하고, 계산 복잡도를 다루는 분야

    알고리즘 그래프 이론 문제 예시 : 해밀턴 경로, 클릭, 그래프 색칠

2.2 AIStudy에서 설명하는 그래프의 예시

ref : www.aistudy.com/math/graph_johnsonbaugh.htm

- 아래의 그림은 와이오밍 주의 고속도로 시스템이며, 모든 도로를 가장 경제적으로 순찰하는 방법을 찾아야 한다. 하지만 순찰하는 방법에 대해서 생략하고, 우선 아래의 그림은 그래프로 표현, 모델링 할수 있는데 어떻게 나타내는지 한번 살펴보자 살펴보자.

- 위의 그림에서보면 각 도시들과 도시들을 이어주는 도로들을 볼 수 있다. 각각의 도시를 노드(정점)로 보고, 두 도시를 연결하는 도로를 에지(간선)이라고 하자. 그러면 위 그림의 그래프 G = (V, E)는 아래와 같이 그릴 수 있다. 각 노드의 이름은 이름의 앞 세글자로 하고, 에지들은 $e_{1}$, . . ., $e_{13}$과 같은 식으로 정리하였다.

- 아래의 그래프도 모양은 다르지만 위의 그래프와 동일한 그래프라고 볼 수 있다.

2.3 AIStudy에서 설명해주는 그래프 정리

- 우리는 그래프를 다음과 같이 표기한다. : G = (V, E)

- 하나의 간선 e는 간선 집합 E의 원소로 다음과 같이 표기한다 : e $\in$ E

- 하나의 간선 e는 두 노드 v, w를 연결하므로 e = (v, w) 혹은 e = (w, v)로 표기한다.

   * 무방향 그래프 undirected graph의 경우 노드의 순서가 상관없으나, 유방향 그래프의 경우 노드 순서를 지켜야한다.

   * 그래프 G가 유방향 그래프이고, e = (v, w) 라면, 노드 v에서 노드 w를 가리키는 간선이 된다.

2.4 와이오밍 주 고속도로의 간선과 정점 정리

- 아래의 와이오밍 주 고속도로 그래프 시스템은 무방향 그래프

- 노드에 대한 집합 V = {Gre, She, Wor, Buf, Gil, Sho, Cas, Dou, Lan, Mud}

- 에지에 대한 집합 E = {$e_{1}$, $e_{2}$, . . ., $e_{13}$}

- 간선 예시 1 :  간선 $e_{1}$ = (Gre, She) = (She, Gre)

- 간선 예시 2 : 간선 $e_{10}$ = (Cas, Dou) = (Dou, Cas)

2.5 방향 그래프와 무방향 그래프 비교

- 에지/간선이 화살표 직선인 경우 방향 그래프

- 에지/간선이 그냥 직선인 경우 무방향 그래프

2.6 그래프 이론에서의 경로 path와 사이클 cycle

- 경로 Path : 하나의 정점에서 다른 정점으로 가는 길.

  * example : 정점 A에서 정점 D로 가는 경로  A -> C -> D

- 사이클 Cyle : 한 정점에서 자기 자신으로 돌아갈 수 있는 경로. 사이클이 없는 경우 트리가 된다.

  * example : 정점 A의 사이클 : A -> C-> B -> A

2.7 그래프와 토폴로지 Topology

- 일반적인 토폴로지(위키백과) : 위상 수학을 가리킨다.

- 네트워크 토폴로지(위키백과) : 컴퓨터 네트워크 구성을 말한다.

- 그래프에서의 토폴로지(고어쿤님의 블로그) : 그래프가 이루는 전체적인 모양

 ref : blog.gorekun.com/?p=1518

* 토폴로지의 예시

- 위 토폴로지들은 모두 기본적으로 네트워크 구조로 사용 되고 있다.

- 성형 토폴로지 star topology : 중앙 허브가 모든 장치와 연결하는 대표적인 네트워크 연결 형태

 ref : topologynetwork.com/what-is-star-topology-definition-examples-advantages-disadvantages/

- Bus topology : 네트워크 이외에도 CPU와 메모리, 그외 입출력 장치 데이터, 명령 전송에 사용된다.

- tree topology : 컴퓨터 과학에서 탐색, 정렬 문제 등에 많이 사용하는 자료 구조

위상 수학에 대한 참고 영상

3.그래프의 예시

3.1. 네트워크 토폴로지

3.2. 트리 구조

- 사이클이 존재하지않는 그래프를 트리라고 부른다.

3.3. 신경망 neural network

- 계산 그래프로 만들어진 인공 신경망도 그래프

Quiz. 컴퓨터 과학에서 다루는 트리가 아니라 (조금 더 큰범위의)그래프 이론의 트리는 방향 그래프인가? 무방향 그래프일까?

-----------------------정답선 -------------------------------------

ref : en.wikipedia.org/wiki/Tree_%28graph_theory%29

정답 : 그래프 이론에서 말하는 일반적인 트리는 무방향/무향 그래프이다.

컴퓨터 과학에서 다루는 트리는 루트가 있는 루트 트리 rooted tree

4. 그래프를 어떻게 저장하는가?

- 아래의 그림은 방향 그래프 directed graph의 노드와 에지를 저장하는 방법을 보여주고 있다.

- 인접 리스트 adjacency list와 adjacency maxtrix를 이용하는 방법이 존재.

5. 그래프를 가지고 뭘 할수있는고?

- 그래프를 이용하여 다양한 경로 탐색 문제들을 풀수 있다

 -> 경로 탐색 방법으로 퍼즐을 풀거나 목적지까지 가장 빠른 경로를 찾을 수 있다.

5.1 8 퍼즐 문제

- 아래와 같이 초기 상태와 목표 상태가 주어질때, 

 * 아래의 목표 상태는 잘못 그려짐. 1, 2, 3, 4, 5, 6, 7, 8 순서대로 퍼즐이 맞춰지는게 목표.

- 다양한 탐색 방법으로 (트리이기도 하지만) 비용을 비교해서 원하는 노드를 찾아나갈 수 있다.

 * 아래의 그림은 astar 알고리즘으로 목표 상태까지 최단 경로를 찾은 결과.

- 다른 링크에서 구한거지만 위 방법으로 퍼즐을 찾은 결과

5.2 최단 경로를 찾아보자

5.2.1 다양한 그래프 탐색방법들

- 맹목적 탐색 : 목표 노드와 상관없이 무작위로 탐색해나가는 방법으로 계산비용이 크며 소모적임.

- 경험적 탐색 : 목표 노드와 관한 정보, 경험적 정보를 활용한 탐색

- 아래의 그림은 다익스트라 알고리즘으로 한 그래프의 노드 a에서 노드 b까지 최단 경로를 찾는 과정

5.2 휴리스틱 탐색 방법을 이용한 경로 계획

- 이러한 경로 탐색, 계획 방법들을 이용해서 로봇을 스스로 이동시키는데 사용된다.

ref : github.com/AtsushiSakai/PythonRobotics

- 아래는 다익스트라 알고리즘을 이용한 경로 계획 예시

- 아래는 Astar 알고리즘을 이용한 경로 계획 예시

- 아래는 로봇 시뮬레이션 환경에서 경로 탐색 알고리즘을 통한 자율 주행 예시 

- 그 외에도 그래프 최적화가 자율 주행, SLAM 연구에서 필요한 2/3차원 점구름 지도를 작성하는데 사용되기도 한다. (KITTI dataset ORB SLAM 적용 영상)

ref : www.youtube.com/watch?v=sLjsnQrmtVM

2. 두 수의 합

21. 두 연렬 리스트를 병합 후 정렬하기

24. 쌍으로 바꾸기

92. 역 연결리스트2

206 : 역 연결리스트

234 : 팰린드롬 연결리스트

328 홀수, 짝수 연결리스트

• 1번 두 수의 합
• 561번 배열 파티션
• 15번 세 수의 합
• 1672번 가장 부유한 고객 찾기
• 42번 빗물 트래핑
• 238번 자신을 제외한 배열의 곱

판별 분석 discriminant analysis

- 측정 변수들로 각 행, 개체들이 어느 그룹에 속하는지 판별하는 방법

- 주어진 데이터로 가장 잘 판별할수 있는 판별식을 만들어, 새로운 데이터를 분류함

판별 분석의 예시

- 은행이 기업에 대출 시, 대출 전 기업의 도산 가능 여부를 판별하는 경우

- 과거 도산 기업과 도산하지 않은 기업에 대한 데이터(자산, 부채, 이익 등)을 관측

- 도산 여부 판별할수 있는 판별식, 판별함수를 만들어 대출 받으려는 기업의 도산 가능 여부를 판별

선형 판별 함수 Linear Discriminant Function

- 판별 오류가 최소가 되는 선형 함수

- 람다 = 그룹 간 분산/그룹 내 분산, 람다가 최대가 되는 계수벡터 b를 구해야 함

 => 그룹 내부는 잘 뭉치고, 그룹 간에는 잘 떨어지는 판별식 계수를 구하라는 말.

- 선형 판별함수 식 Y = b' X

정준판별분석 canonial discriminant analysis

- 여러개 집단으로 분류하는 경우 판별분석.

 -> 분류하고자 하는 집단이 3개 이상인 경우도 판별 분석이 가능하며, 판별식이 여러개가 됨.

- 정준 판별 함수는 정준 상관 분석으로 구할 수 있다.

참고 : 정준 상관분석 수행 과정

 - X의 선형 결합 변수 W와 Y의 선형결합 변수 V 준비 -> Corr(W,V)

 - Corr(W, V)가 최대로 하는 계수 벡터 b를 추정

정준 상관 분석의 판별 분석

- X의 선형 결합 변수 W와 라벨 Y에 대한 정준 상관분석 수행

 -> 제1 정준 변수 = b1은 Y를 가장 잘 이진분류하는 판별함수의 계수벡터가 됨.

- 모든 그룹으로 나눌수 있도록 여러개의 정준 변수들은 생성

상관계수 Correlation

- 두 변수 간의 선형적 상관 관계를 나타내는 통계량

- 피어슨의 상관계수 = Corr(x,y) = Cov(x, y)/(std(x)*std(y))

- -1 ~ 1사이 값을 가짐

- |corr(x,y)|가 1에 가까울수록 선형적 관계를 가짐

정준상관분석Canonical Correlation Analysis

- 상관 계수가 두 변수의 관계를 다루었다면

- 정준상관분석은 독립 변수들과 한개 이상의 종속변수의 연관성을 다루는 분석

 => 상관분석과 회귀분석의 결합

- 독립변수들과 종속변수들의 상관계수가 최대가 되는 선형 결합을 유도하여 분석하는 방법

정준상관분석의 예시

- 독립 변수 : 신체조건에 대한 변수 -> x1 : 키, x2, : 앉은키, x3: 가슴 둘레

- 종속 변수 : 운동능력에 대한 변수 -> y1 : 50m 달리기, y2 : 공던지기 

 => 신체조건과 운동 능력 간의 연관성을 구해보자

- 방법 1. 각 독립변수와 종속변수의 상관계수 구하기 -> 종합적인 독립변수와 종속변수간 연관성을 구하기 힘듬

- 방법 2. 독립 변수의 선형 결합으로 변수 W 만들고 Y 변수의 선형결합으로 변수 V 만들어, 두 변수간 상관계수로 파악

 => 정준 상관 분석

정준상관분석 정리

- 독립 변수들과 종속 변수들간 상관관계를 분석

- 독립변수들의 선형 결합 변수 W = a1x1 + ... + bpxp

- 종속 변수들의 선형 결합 변수 V = b1y1 + ... + bqyq

- 정준상관분석 -> Corr(W, V)

다차원 척도법

- 개채들의 특징, 변수들을 측정 후, 개채들 간의 거리(유사성), 비유사성을 측정하여 다차원 공간에서 점으로 표현.

- 일반적으로 2/3차원 공간상의 점으로 표현하여 개체들간 관계표현.

- 클러스터링에 많이 사용.

다차원 척도법의 예시

- 국내 도시들의 인구수, 면적, 학교 수 등 통계들을 조사 후 다차원 척도법을 사용하는 경우

 -> 도시들간 유사한 정도, 가까운 정도를 2차원 공간 상에서 표현할수 있음.

 -> 위 통계로 어느 도시와 어느 도시가 가까운지 알수 있다.

MDS 분석 과정

1. 변수 측정

2. 거리, 비유사성 측정

3. 2/3차원 공간상에서 시각화

4. 최적 표현 결정 : 개체들 간 거리를 가장 잘 나타내는 위치 구함. 스트레스를 이용.

 * 스트레스 : 개체 간 비유사성이 얼마나 부적합한가 측정 척도

거리 측정 방법

- 비유사성, 유사성은 거리를 이용하여 판단

- 유클리디안 거리, 채비셰프거리, 맨해튼거리 등이 있음.

- 측정 단위의 영향을 제거하기위해 변수들을 표준화한 뒤 거리측정

인자 factor : 숨어있는 요인 

주성분 분석과 인자분석의 차이

- 주성분 분석 : 서로 관련있는 변수간의 선형결합으로 새로운 변수, 주성분을 만들어 분석

- 인자 분석 : 서로 관련있는 변수들을 설명할수있는 새로운 공통 변수를 파악하는 방법

인자분석의 예시

- 고등학교 학생 대상으로 국어, 영어, 수학, 사회, 지리, 역사 등 10개 과목 시험 실시

=> 과목들을 공통적으로 설명할수 있는 공통 인자들을 유도하여 분석

=> 공통인자 : 추상적 개념, 이해력, 분석력 등을 나타내는 변수로 각 과목은 인자들의 선형결합으로 표현

=> 인자분석에선 인자들을 생성하는데 해석은 주관적으로 자료에 적절하도록 해석해야함

주성분 분석과 인자분석

- 관측된 변수들로 소수의 새로운 변수들을 생성하는 통계적 방법

- 분석 과정이 유사하지만 접근 방법은 다름.

- 주성분 분석 : 변이(분산)에 구조적 해석이 힘드나 상관관계가있는 변수들을 적절히 선형변환시킴

- 인자 분석 목적 : 직접적으로 해석 힘든 변수간 구조적 관계와 개념적 의미를 부여할수 있는 적은 수의 공통인자 유도

 => 개념적 의미를 부여하는 변수 생성

공통 인자

- 변수들이 구조적 측면서 공유하는 확률적 인자.

- 변수간 상관관계를 생성시키는 가설, 이론, 관찰불가한 변수를 말함.

주성분 분석과 인자 분석의 차이점

- 주성분 분석 : 변수들의 선형 결합. 인자 분석 : 가공의 인자를 만든 후, 가공 인자들의 선형 결합식

- 주성분 분석 : 주성분들이 갖는 크기에 따라 순서 있음. 인자 분석 : 인자들엔 순서 없음

- 주성분 분석 : 관측 변수들의 선형 결합. 오차항이 없다.

    인자분석 : 인자들이 선형식으로 설명. 설명불가한 부분을 오차항/특수인자가 있음.

인자분석 모형

- 인자 분석에서 p개의 변수 X = (X1, X2, .., Xp)가 있을때, X의 공분산 행렬과 기대값은 아래와 같음

- 인자 모형 : 각 변수 X에서 평균 mu을 뺀 값이 q개의 가공 인자들의 선형 결합 lf과 오차항 e으로 표현되는모형

- 관심 가져야하는 부분 : 계수 l_ij의 추정과 각 변수와 인자들의 선형 결합으로 설명되는 수준

인자분석 기본 가정

- 변수벡터 X는 다변량 정규분포 따름

- 인자 f와 오차항 e 평균은 모두 0, 인자들의 분산은 1

- 인자 쌍의 공분산은 0, 인자 f와 특수인자 e는 서로 독립

- 오차항은 각각의 분산을 가지나, 오차항 쌍의 공분산은 0

공통성 communality

- 수식

- Sigma의 분산 = L L'의 대각 원소들의 합과 오차항 분산의 합

- 공통성의 의미 : q개의 인자에 의해 설명할수 있는 정도. -> q개 인자로 획득가능한 정보의 비율을 측정하는 척도

- 공통성 h_i^2는 [0, 1]사이 값으로 1에 가까울 수록 변수 Xi가 가지고 잇는 정보 중에서 인자가 확보하는 비율이 큼

인자 분석 초점

- 인자 부하값(l11, ..., l1q)을 추정하여 변수 Xi와 q개의 인자사이 관계 추정

- 공통성 hi2를 구하여 변수 xi 정보를 어느정도 확보되는가 추정

=> 가능한 적은 q개의 인자들로 최대한 정보를 확보해야함.

인자 모형 추정 방법

1. 주성분 분석 방법 principal compoent method

- 주성분 분석을 통해 인자를 구한느 방법.

- 상관계수행렬 R의 대각 요소에 1대신 공통성 추정치를 대치하여 사용. 많이사용

2. 최우추정법(최대가능성방법)

- 가능성 함수를 구하고, 가능성을 최대화 하는 인자부하 (l11, ... l1q)과 오차항 e를 구하는 방법

인자의 수와 인자부하값의 유의성

- 인자 수 최대는 변수의 개수. 하지만 최소의 인자를 구하고자하니 보통 3~4개 선택

- 인자의 수는 상관계수행렬 R의 고유값이 1보다 큰 경우만 사용.

- 인자 부하의 유의성 : n>50인 경우, 0.3인 경우 유의함, 0.4는 더 유의함. 0.5는 아주 유의함. 

인자 회전 factor rotation

- 인자 부하값들의 크기에 따라 변수들을 유사한 것끼리 묶거나 공통 요인 찾음.

   -> 해석을 용이 하기 위해 인자 회전 실시

인자 회전 예시 1

- 고등학생 100명 대상, 국/영/수/물리/사회 시험 후 인자분석실시, 아래의 2개 유이한 인자에 대해 인자 부하행렬

- 인자 F1은 수학, 물리에 큰 가중치 가지며, F2는 국영사에 큰 가중치 가짐

=> 인자 F1는 분석력, F2는 이해력이라 정의할 수 있음.

인자 회전 예시 2

- 인자 부하가 다음과 같은 경우, 모든 과목들이 F1에 대해서 높은 부하를 F1, F2 특성 구분이 쉽지 않음

- 인자축 F1, F2를 F1*, F2*로 회전하는것이 용이

- 인자 회전 방법 : 직교 회전, 사각 회전(각 변수의 인자 가중치가 한 인자에만 크도록 축을 회전)

인자 분석 예시

- 검진 프로그램 유횽성 모니터링 자료. 11개의 검진 항목, 128개의 자료

- psych 패키지의 principal()함수로 주성분 인자법으로 인자 모형 추정

1. 자료 가져오기, 통계량 요약

2. 초기 인자분석 실시

- principla() 함수로 주성분 인자법으로 인자분석 실시

- values는 고유값. 고유값을 보면 세번재 인자까지 1이상임을 알 수 있음.

3. 인자분석 결과 : 인자회전varimax이용

- h2 : 각 변수 공통성, 각 변수의 공통성은 아래와 같이 구함

- U2 : 고유분산(u2 = 1- h2)

- 공통성은 많은 변수 주에서 서로 연관 갖는 일부 변수를 구하기 위해 인자분석시 변수 선택기준으로 사용

 ex. 변수 100개로 인자분석 결과 공통성이 0.3이하인 것이 40개라면, 해당 변수들은 다른 분항과 공통성이 적음

- ss lodings : 인자 가중치들 제곱의 합으로 구함.

- proportion var : 인자가 설명하는 총 분산 비율.

 => RC1 : 22%, RC2 : 19%, RC3 : 14%로 세 인자로 설명 가능한 변동은 총 변동의 56%

- 인자 모형 식

- 첫번째 인자 RC1은 lung, liver, kidney, heart가 가장 높은 값을 가짐. => 생물 의학

- 두번째 인자 RC2는 stamina, Strech, blow, urine의 값이 높음 => 인체 기능

- 세번째 인자 RC3는 muscle과 skeleton이 높은 값 => 근육골

4. 인자 점수

5. 행렬도