728x90

슬라이딩 윈도우란?

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

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

 

 

 

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

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

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

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

 * Ack(Acknowledgement) : 긍정 응답

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

https://sjlim5092.tistory.com/35

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

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

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

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

 

 

 

 

 

 

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

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

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

 

이름 정렬 여부 윈도우 사이즈 이동
투 포인터 대부분 정렬됨 가변 좌우 포인터 양뱡향
슬라이딩 윈도우 X 고정 좌 혹은 우 단방향

https://9327144.tistory.com/entry/%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0-%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0-%EA%B8%B0%EB%B2%95?category=945533

 

 

 

 

 

 

슬라이딩 윈도우 예시

1. 물체 검출 Object Detection

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

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

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

https://www.researchgate.net/figure/Object-detection-by-sliding-window-approach_fig1_266215670

 

2. 이동 평균 Moving Average

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

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

 

300x250

'수학 > 알고리즘' 카테고리의 다른 글

퀵 정렬 quick sort  (0) 2021.04.07
그래프 정리 2  (0) 2021.02.24
그래프 정리 1  (0) 2021.02.23
[리트코드 문제 풀기] 연결 리스트  (0) 2021.01.27
[리트코드 문제 풀기] 배열  (0) 2021.01.20
728x90

 

퀵 정렬 개요 quick sort 

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

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

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

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

            찰스 앤터니 리처드 호어(토니 호어).             출생일 :  1934년 1월 11일 현(87세)

 

 

퀵 정렬 알고리즘 

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

https://blog.naver.com/sehoon95/80212692808?viewType=pc

 

 

퀵 정렬의 시간 복잡도

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

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

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

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

 

 

 

 시간 복잡도 비교

 

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

 

 

 

 

300x250

'수학 > 알고리즘' 카테고리의 다른 글

슬라이딩 윈도우  (0) 2021.04.28
그래프 정리 2  (0) 2021.02.24
그래프 정리 1  (0) 2021.02.23
[리트코드 문제 풀기] 연결 리스트  (0) 2021.01.27
[리트코드 문제 풀기] 배열  (0) 2021.01.20
728x90

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

ref : throwexception.tistory.com/1185

 

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

 

 

 

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

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

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

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

https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_%EC%9D%B4%EB%A1%A0

 

2. 오일러 경로 Eulerian Path

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

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

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

https://suhak.tistory.com/54

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

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

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

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

https://steemit.com/kr-science/@rubymaker/tb24i-rubymaker

 

 

 

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

 

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

http://nogwon.blogspot.com/2013/12/blog-post_7760.html

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

https://blog.daum.net/sshyorim/900498

 

 

 

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

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

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

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

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

https://brilliant.org/wiki/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

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

https://fs.blog/2017/06/thought-experiment/

 

 

4.5 튜링 기계 Turing Machine

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

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

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

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

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

 

https://www.futurelearn.com/info/courses/how-computers-work/0/steps/49259

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

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

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) : 결정론적 튜링 기계로 다항 시간안에 풀수 있는 판정 문제 집합.

P 문제와 NP완전은 NP 문제들의 부분집합
NP 문제와 NP완전의 관계

 

 

 

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

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

  임의 경로 탐색 최적 경로 탐색
맹목적 탐색 blind search 깊이 우선 탐색 Depth First Search
너비 우선 탐색 Breadth First Search
균일 비용 탐색 Uniform Cost Search
경험적 탐색 heuristic search 언덕 오르기 탐색 hill Climbing Search
최적 우선 탐색
다익스트라 알고리즘 Dijkstra algorithm
A* 알고리즘 Astar Algorithm

 

 

 

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

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

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

 

https://medium.com/@kenny.hom27/breadth-first-vs-depth-first-tree-traversal-in-javascript-48df2ebfc6d1

 

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

백트래킹으로 스도쿠 풀기

 

300x250

'수학 > 알고리즘' 카테고리의 다른 글

슬라이딩 윈도우  (0) 2021.04.28
퀵 정렬 quick sort  (0) 2021.04.07
그래프 정리 1  (0) 2021.02.23
[리트코드 문제 풀기] 연결 리스트  (0) 2021.01.27
[리트코드 문제 풀기] 배열  (0) 2021.01.20
728x90

 

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

 

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

 

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

 

 

 

 

 

 

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

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

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

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

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

https://mathworld.wolfram.com/GraphEdge.html

 

 

 

 

2. 그래프 이론

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

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

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

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

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

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

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

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

 

 

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

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

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

 

와이오밍 주 고속도로 시스템. AiStudy

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

와이오밍 주 고속도로 시스템의 그래프화. AIStudy

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

와이오밍 주 고속도로 시스템의 대안 그래프. AIStudy

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)

 

와이오밍 주 고속도로 시스템의 그래프화. AIStudy

 

 

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와 메모리, 그외 입출력 장치 데이터, 명령 전송에 사용된다.

http://fourier.eng.hmc.edu/e85_old/lectures/peripheral/node1.html

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

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

 

 

 

 

위상 수학에 대한 참고 영상

 

 

 

 

 

 

 

3.그래프의 예시

3.1. 네트워크 토폴로지

https://www.router-switch.com/faq/what-is-lan-concept-features-topology-setting.html

 

http://dudleysenanayakacc.blogspot.com/p/network-topology.html

 

3.2. 트리 구조

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

http://suyeongpark.me/archives/1928
https://techdifferences.com/difference-between-tree-and-graph.html

3.3. 신경망 neural network

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

Justin Joneshon, Michigan Online, Deep Learning for Computer Vision, Lecture 6 Back Propagation
,http://cs-people.bu.edu/lsz/ml_3/pset3.html

 

 

 

 

 

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

 

https://en.wikipedia.org/wiki/Tree_(graph_theory)

 

 

 

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

 

 

 

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

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

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

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

 

 

 

 

 

 

 

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

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

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

https://jackpot53.tistory.com/m/79?category=715451

 

 

 

 

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

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

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

 

5.1 8 퍼즐 문제

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

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

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

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

https://blog.goodaudience.com/solving-8-puzzle-using-a-algorithm-7b509c331288

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

https://dev.to/kaxi1993/solving-8-puzzle-problem-using-a-algorithm-1683

 

 

 

5.2 최단 경로를 찾아보자

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

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

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

  임의 경로 탐색 최적 경로 탐색
맹목적 탐색 blind search 깊이 우선 탐색 Depth First Search
너비 우선 탐색 Breadth First Search
균일 비용 탐색 Uniform Cost Search
경험적 탐색 heuristic search 언덕 오르기 탐색 hill Climbing Search
최적 우선 탐색
다익스트라 알고리즘 Dijkstra algorithm
A* 알고리즘 Astar Algorithm

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

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

 

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

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

ref : github.com/AtsushiSakai/PythonRobotics

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

 

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

https://github.com/AtsushiSakai/PythonRobotics#dijkstra-algorithm

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

https://github.com/vsouda/Robot-Motion-Planning-in-ROS-Kinetic

 

 

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

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

 

 

 

 

 

 

300x250

'수학 > 알고리즘' 카테고리의 다른 글

퀵 정렬 quick sort  (0) 2021.04.07
그래프 정리 2  (0) 2021.02.24
[리트코드 문제 풀기] 연결 리스트  (0) 2021.01.27
[리트코드 문제 풀기] 배열  (0) 2021.01.20
알고리즘설계기법 - 7. 근사해법  (0) 2020.08.09
728x90

 

2. 두 수의 합

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

24. 쌍으로 바꾸기

92. 역 연결리스트2

206 : 역 연결리스트

234 : 팰린드롬 연결리스트

328 홀수, 짝수 연결리스트

 

 

 

300x250

'수학 > 알고리즘' 카테고리의 다른 글

그래프 정리 2  (0) 2021.02.24
그래프 정리 1  (0) 2021.02.23
[리트코드 문제 풀기] 배열  (0) 2021.01.20
알고리즘설계기법 - 7. 근사해법  (0) 2020.08.09
알고리즘설계기법 - 6. 백트래킹  (0) 2020.08.09
728x90

 

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

 

 

300x250
728x90

알고리즘과 복잡도

- 복잡도가 O(n) 처럼 작은 경우가 있지만 복잡도가 매우 큰 알고리즘도 많음

 

NP 완비 문제

- 풀기 쉬운지 어려운지도 모르는 문제들

 

P 문제

- 결정론적 알고리즘 deterministic algorithm으로 다항식 시간에 해결할수 있는 문제

- 결정론적 알고리즘 : 명확하게 결정되어있어 데이터 입력시 어느 순서대로 동작하는지 알수있는 알고리즘

 

NP 문제

- 비결정론적 알고리즘 nondeterministic algorithm으로 다항식 시간에 해결할수 있는 문제

- 비결정성 알고리즘 : 결정 가능한 경우가 여러개로 나뉘어져 적당한 경로러 선택해 나가는 알고리즘

=> 가장 적절한 경로를 잘 선택한 경우 다항식 시간으로 해를 찾을수 있는 문제를 NP 문제라 부름

 

 

근사 알고리즘 approximation algorithm

- NP문제는 최악의 경우 복잡도가 지수적으로 됨.

 => 최적해는 아니더라도 최적해에 가깝기만 하면 됨.

- 최적해에 가까운 근사해를 구하는 (결정론적) 알고리즘

 

 

휴리스틱 알고리즘

- 해를 얻을때까지 경험해가는 알고리즘

- 최적해의 계산 비용이 크고, 근사해로도 충분한 경우 사용

 

 

https://optimization.mccormick.northwestern.edu/index.php/Heuristic_algorithms

 

 

 

 

300x250
728x90

백트래킹법

- 모든 가능성을 조사하지 않고도 최적해를 얻을수 있는 문제도 존재

- 하나의 시행을 통해 조사하다가 해를 구하지 못하면 이전으로 되돌아가 다른 경우를 조사

=> 해를 찾을떄까지 백트래킹 후 다른 경우를 조사하는 방법

 

 

 

백트래킹 방법의 예시

1. 수도크 플기

https://imgur.com/gallery/0sfWi

300x250
728x90

분할 통치법

- 잘 파악된 부분을 조금씩 넓혀가 결과를 찾음

- 해에 접근하는 방법에 따라 능률이 좋거나 나빠지기도 함.

 

 

탐욕법 greedy algorithm

- 현재 상태에서 볼때 가장 좋은 경우를 따라가는 방법

- 당장의 성능 개선이 보임

- 지역적 최선의 선택이 전역적으로 좋다고 보장할 수 없음

=> 당장의 최적의 방향으로만 쫓다간 지역해에 수렴함. 전역해에 도달못하는 경우 발생

 

https://commons.wikimedia.org/wiki/File:Greedy-search-path-example.gif

 

 

 

탐욕법의 예시

1. 다익스트라 알고리즘

 

 

 

2. 프림 알고리즘

https://en.wikipedia.org/wiki/Prim%27s_algorithm

 

 

 

 

300x250
728x90

재귀적인 recursive 방법의 한계

- 재귀적 방법은 문제를 간단한 부분 문제로 만듬

- 하지만 부분 문제의 크기 합을 작게 유지시켜야만 효과적임

- 부분 문제의 크기가 균형이 맞지 않을시 복잡도가 지수적으로 증가

 => 재귀적인 방법의 한계로 인해 동적 계획법 이용

 

 

 

동적 계획법 dynamic programming

- 부분 문제들의 답을 별도의 표에 기억

- 필요할때마다 표를 참조

   * 재귀적 방법의 문제 : 재귀적인 방법에선 그 표의 값을 매번 새로 계산했었음

=> 동적 계획법은 부분 문제의 답을 기억. 이후 다시 계산하지 않음

300x250

+ Recent posts