Algorithm 공부 #26 - 이분 매칭 ✏️이분 매칭이란? 이분 그래프에서 주로 사용하는 알고리즘 이분 그래프는 두 개의 정점 그룹이 존재할 때 모든 간선의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프 이러한 이분 그래프에서 예를 들어, 한 그룹은 X그룹, 다른 한 그룹은 Y그룹이고 간선의 방향은 X->Y라고 할 때 모든 경로의 방향은 X->Y인 그래프의 최대 유량을 구하는 것 ✏️예시 먼저 알파벳 그룹과 숫자 그룹이 있다고 가정을 하면 A에서 갈 수 있는 숫자는 1과 3 B에서 갈 수 있는 숫자는 1과 2 C에서 갈 수 있는 숫자는 5 D에서 갈 수 잇는 숫자는 3 E에서 갈 수 있는 숫자는 2 A부터 매칭을 시작하면 각 점에서는 한 개의 숫자만 갈 수 있으므로 A는 1과 연결(총..
✏️ 문제 링크 https://www.acmicpc.net/problem/14245 14245번: XOR 첫 번째 줄에 수열의 크기 n (0 < n ≤ 500,000)이 주어진다. 두 번째 줄에 수열의 원소가 0번부터 n - 1번까지 차례대로 주어진다. 수열의 원소는 100,000보다 크지 않은 음이 아닌 정수이다. 세 번째 줄 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 느리게 갱신되는 세그먼트 트리를 이용하는 문제입니다. 백준 19975번 문제에서 XOR연산이 추가되었습니다. 느리게 갱신되는 세그먼트 트리를 구현하면서 XOR연산을 넣어주시면 됩니다. XOR기호는 ^이고, 단 갱신할려는 구간의 길이가 짝수이면 XOR연산을 해도 0이므로 구간의 길이가 홀수일 때만 XOR연산을 해주도록 설..
✏️ 문제 링크 https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 이 문제 역시 느리게 갱신되는 세그먼트 트리로 구현하는 문제입니다. 여기서 조금 더 생각해 봐야 할 것은 x번째 원소를 출력하는 건데, x번째 인덱스를 구하는 과정은 이분 탐색 과정을 통해서 값을 찾아낼 수 있습니다. 아래 문제는 느리게 갱신되는 세그먼트 트리의 기본 틀을 구현한 문제입니다. https://pooreumjung.t..
✏️ 문제 링크 https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 세그먼트 트리의 한 종류인 느리게 갱신되는 세그먼트 트리를 구현하는 문제입니다. 구간에다가 특정 값을 더하게 되는 연산을 하게되면 일반적인 세그먼트 트리로 구현하게 되면 시간초과가 발생하게 됩니다. 이를 해결하기 위해 만들어진게 느리게 갱신되는 세그먼트 트리입니다. 특정 구간에 값을 ..
- Total
- Today
- Yesterday
- 에라토스테네스의 체
- 스택
- 유클리드 호제법
- c++ string
- 투 포인터
- 이분 매칭
- 백준
- DP
- 우선순위 큐
- 알고리즘
- 스프링 부트 crud 게시판 구현
- BFS
- java
- Do it!
- 카운팅 정렬
- 자료구조
- C++
- 백준 풀이
- js
- html
- DFS
- 유니온 파인드
- 알고리즘 공부
- HTML5
- C++ Stack
- 세그먼트 트리
- 반복문
- 자바스크립트
- CSS
- 자바
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |