본문 바로가기 메뉴 바로가기

Hani_Levenshtein

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

Hani_Levenshtein

검색하기 폼
  • 분류 전체보기 (343)
    • Test (1)
    • Xcode (0)
    • 컴파일러 (0)
    • iOS (0)
    • Apple (0)
    • Swift (0)
    • RxSwift (0)
    • HIG (0)
    • WWDC (0)
    • 컴퓨터구조 (0)
    • 운영체제 (0)
    • 백준 (320)
    • 소식 (0)
    • 알고리즘 (8)
    • 사물인터넷 (0)
    • 프로그래머스 (14)
    • Metal (0)
    • 컴퓨터 그래픽스 (0)
    • OS - OSTEP (0)
    • 시스템 디자인 (0)
    • 짬통 (0)
  • 방명록

네트워크 플로우 (2)
이분 매칭

이번 포스팅의 주제인 이분 매칭 문제는 네트워크 플로우 연장선에 있는 문제입니다. 2020/09/09 - [알고리즘] - 포드 풀커슨 알고리즘 우선, 이분 매칭을 공부하기 위해선 이분 그래프라는 것을 알 필요가 있습니다. 이분 그래프란 두 집합으로 나뉜 그래프의 정점들의 간선이 상대 집합에 속한 정점으로 연결된 그래프입니다. 성별이나, 주종관계, 사람과 작업 등의 관계가 주어진다면 이를 이분 그래프로 표현할 수 있습니다. 여기서 이분 그래프의 각 요소들을 문제의 조건에 맞춰 대응시키는 것이 이분 매칭 문제입니다. 이런 이분 매칭 문제는 앞서 소개한 네트워크 플로우를 이용하면 쉽게 풀 수 있습니다. 이분 그래프의 각 간선을, 연결되지 않은 것(0) 과 연결된 것(1) 인 용량이 1인 간선으로 고려할 수 있..

알고리즘 2020. 9. 12. 04:04
포드 풀커슨 알고리즘

최단 경로 문제에서는 정점 간 간선의 가중치의 합이 최소가 되는 경로의 길이를 찾으려 했습니다. 네트워크 플로우는 시작점에서 도착점까지 유량을 최대로 흘려보내는 것이 목적입니다. 어떻게 보면 가중치의 합을 최대로 만드는 것인데 여기서 용량이라는 개념이 추가됩니다. 네트워크 유량은 항상 3가지 규칙을 만족해야 합니다. 1. 용량 제한 속성 flow(u,v)

알고리즘 2020. 9. 9. 20:33
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
  • Levenshtein Git
TAG
  • State Restoration
  • 최대 매칭
  • 최단경로문제
  • 강한 순환 참조
  • 에드몬드 카프 알고리즘
  • 포드 풀커슨 알고리즘
  • IOS
  • 벨만포드 알고리즘
  • 벨만포드 시간복잡도
  • 최단경로 알고리즘
  • 부스트캠프 6기
  • rxswift
  • HIG
  • 네트워크 유량
  • 최단경로 문제
  • 다익스트라 시간복잡도
  • CompositionalLayout
  • CPU와 Memory
  • MeTal
  • 네트워크 플로우
  • 코딩대회
  • mach-o
  • observeOn
  • WWDC17
  • WWDC21
  • 컴퓨터 추상화
  • Testable
  • test coverage
  • WWDC16
  • WWDC19
more
«   2025/07   »
일 월 화 수 목 금 토
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
글 보관함

Blog is powered by Tistory / Designed by Tistory

티스토리툴바