더보기https://velog.io/@ashooozzz/Python-%EC%9D%B4%EB%B6%84-%EB%A7%A4%EC%B9%ADfeat.-DFS [Python] 이분 매칭(feat. DFS)오랜만에 적어보는 벨로그..오늘은 이분 매칭에 대해서 적어보고자 한다.이분 매칭은 A, B로 나뉜 이분 그래프에서 A에서 B로 이동하는 최대 유량... 어쩌구... 는 모르겠고, 그래프에서 정점들의velog.io 이분 그래프로 나뉜 두 정점의 집합에서 각 그룹간의 최대 매칭수를 구하는 알고리즘각 정점은 다른 집합에 정확히 1개 또는 0개의 간선으로 연결이 되며, 이때 간선의 수가 최대가 되는 경우를 구하는 것.2개이상의 간선으로 연결이 되는 경우는(1개의 정점이 다른 그룹의 2개이상 정점을 점유가능 한 경우) ..

세그먼트 트리란?이름의 유래와 원리이름이 곧 핵심 원리를 담고 있다.즉, '구간' 을 뜻하는 Segment와 Tree 자료구조로, 전체 데이터의 특정 구간에 대한 정보를 트리 구조에 저장해 효율적으로 관리하는 자료구조 이다.O(log n)의 시간복잡도를 가진다.어디에 사용되는가?쿼리문제(구간합, 구간 최대/최소값, 구간곱, 구간 최대공약수/최소공배수)특정 조건을 만족하는 원소쿼리(구간내 K보다 작거나 큰 원소갯수, 구간내 짝수,홀수, K번째로 작거나 큰수 등등)구간 업데이트 문제(Lazy Propagation을 통해 시간복잡도를 최소한으로 줄일 수 있다)기하 및 스위핑(Sweeping) 알고리즘(2차원 평면 문제를 1차원으로 바꿔 해결할 때 사용)기타등등..방법세그먼트 트리는 주로 3개의 함수로 구성된다..

오일러 경로 테크닉이란?오일러 경로 테크닉(오일러 투어 테크닉, Euler Tour Technique, ETT)은 간단하게 설명하면 복잡한 트리 구조를 단순한 1차원 배열 구조로 변환해 문제를 해결하는 방법이다. 예를 들어, 특정 팀원이 있을 때, 해당 팀원과 모든 직속 부하들에게 영향을 주는 작업을 처리하거나(ex, 백준 14268), 특정 팀의 능력치 총합을 구하는 등 서브트리(Subtree)에 대한 쿼리를 효율적으로 처리하기 위해 사용한다.이름의 유래와 원리이름은 그래프 이론의 아버지, 레온하르트 오일러의 '오일러 경로'에서 유래했다. 오일러 경로는 그래프의 '모든 간선'을 한 번씩만 지나는 경로를 의미하는데, 트리에서의 오일러 투어는 이 개념을 차용해 DFS(깊이 우선 탐색)로 트리의 모든 노드를..