이산수학 5. 알고리즘 - swkim0128/PARA GitHub Wiki

type: 이산수학 archive: false

영상: https://www.youtube.com/playlist?list=PLD8rdlfZeJk6evHY9NsnBqXKrreNbTqFv

이산수학: 알고리즘(1)

알고리즘

문제를 해결하기 위한 절차를 기술한 것

순서대로 정의된 절차

  • 분명한 순서가 있어야 한다
  • 한 동작을 실행하면 다음 동작이 무엇인지 분명해야 한다

명확성

  • 모든 동작은 명확하게 정의되어야 한다
  • 모든 동작은 실행 가능해야 한다

반드시 원하는 결과가 나와야 한다

일정한 시간 안에 실행되어야 한다

알고리즘의 구조

  • 순차적 구조
  • 분기 구조
  • 반복 구조
  • 점프 구조

알고리즘 기술방법

  • 플로우차트
  • 프로그램 언어의 코드
  • 의사코드(pseudocode)

이산수학 그래프1: 오일러 순환과 해밀턴 순환

그래프

  • 그래프는 정점(Vertex)의 집합과 선(Edge)들의 집합으로 구성되며 G = {V, E}로 표시한다

  • 차수(degree)

    정점u에 접합된 연결선(Edge)의 수

    deg(u)와 같이 표기하기도 한다

    자기 자신을 연결하는 연결선(loop)의 경우 차수를 2로 본다

오일러 순환

  • 오일러 경로

    그래프 G의 모든 **연결선(Edge)**를 한번만 방문하는 경로

    2개 이상의 정점을 갖는 루프가 없는 연결 그래프에서 홀수 차수를 갖는 정점이 하나도 없거나 오직 2개(시작점, 끝점)만 존재해야 한다

  • 오일러 순환

    시작점과 끝점이 동일한 오일러 경로

    오일러 경로에서 모든 정점이 짝수 차수를 가지면 오일러 순환이 존재한다

  • 오일러 그래프

    오일러 순환이 존재하는 그래프

  • 각 정점의 차수를 이용해 오일러 순환을 구할경우 시간복잡도

    n 차수 ≤ n(n-1) ≤ n^2

    O(n^2) O(n*m) (m<n), (m은 평균차수)

해밀턴 순환

  • 해밀턴 경로

    그래프 G에서 모든 **정점(Vertex)**을 정확히 한번만 지나는 경로

  • 해밀턴 순환

    시작점과 끝점이 같은 해밀턴 경로

  • 해밀턴 순환을 찾는 알고리즘은 존재하지 않는다

    브루트포스 해야함

    O(x^n) (x는 간선의 갯수, n은 정점의 수)

    np Problem

  • TSP(traveling salesman problem, 방문 판매원 문제)

    연결선에는 비용이 주어진다

    일반적으로 완전 그래프

    이 그래프에서 비용이 최소가 되는 해밀톤 순환을 찾는문제

    n ≤ 11일경우: 브루트포스(O(n!))

    n ≤ 12일경우: 백트래킹

    n ≤ 16일경우: DP+BitMasking(2^n*n^2)

⚠️ **GitHub.com Fallback** ⚠️