이분 매칭 질문점.. - PS 마이너 갤러리

알고리즘 문제를 해결하는 Problem Solving을 다루는 갤러리입니다.

매니저

캐티(tae826)

부매니저

하루룽(ailedear) Gravekper(gravekpe…) 옥토끼(moonrabb…) 나는최고(mebest)

개설일

2018-05-28

[일반] 이분 매칭 질문점..모바일에서 작성

ㅇㅇ(117.111) 2024.04.25 14:14:34

조회 129 추천 0 댓글 1

블로그 설명 쭉 보는데

a와 매칭하려는 정점 b가 매칭된 상태면

정점 b와 매칭된 정점 a'를
다른 정점과 매칭할 수 있는 지 반복 체크하는 것

이렇게 하면 왜 최대 매칭 수가 되는 지 이해가 잘 안감.
시간복잡도도 잘 이해못하겠고...

저 방법이 왜 최대 매칭 수가 되는지 증명에 대한 글 링크라두..

고정닉 0

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	말머리	제목	글쓴이	작성일	조회	추천
2856	설문	주위 눈치 안 보고(어쩌면 눈치 없이) MZ식 '직설 화법' 날릴 것 같은 스타는?	운영자	24/04/29	-	-
44058	공지	알고리즘 대회 공부 과정 [21]	*나는최고*	24.04.20	1586	31
19170	공지	규칙 v2022.02.16 [8]	*0xrgb*	22.02.06	6360	36
1	공지	와 PS! [24]	*0xrgb*	18.05.28	21562	30
44399	일반	소마 2차 1솔컷이라고? [3]	ㅇㅇ(106.101)	05.04	89	0
44398	일반	F 어케 품 [7]	ㅇㅇ(1.210)	05.04	123	0
44397	일반	씹덕 조합론 fft << 이 개 씨발 새끼좀 치워 븅신아 [1]	ㅌ(58.29)	05.04	162	3
44396	일반	오늘 abc 4솔함 [1]	ㅇㅇ(106.101)	05.04	83	1
44395	풀이	이분탐색 응용 튜토리얼 (연습문제 있음) [1]	biximo	05.04	80	1
44394	일반	G 에디토리얼에 NTT 들어가있네 [2]	ㅇㅇ(125.129)	05.04	103	0
44391	일반	다이아 한번만 풀어보고 싶다 [2]	ㅇㅇ(219.241)	05.04	122	0
44390	일반	3일간 휴일인데 전부 ps만해야겠다 [3]	ㅇㅇ(118.235)	05.04	164	2
44389	일반	백준 티어랑 코포 비례 안하는듯 [14]	ㅇㅇ(211.234)	05.04	314	1
44388	일기	왜 오늘 오픈콘은 두시간 반인거야 [3]	ㅇㅇ(125.129)	05.04	203	0
44387	일반	오 이틀동안 미친 듯이 풀었더니 프로그래머스 레벨 4도 다 풀었어요	행복을쫓아	05.04	153	3
44386	일기	소마코테 얘기하니까 생각났는데요 [7]	EN_SA	05.04	203	0
44385	일기	. [10]	EN_SA	05.04	363	11
44384	일반	소마 준비는 다들 어떻게 함? [20]	ㅇㅇ(118.235)	05.04	240	0
44383	일반	dp 왜케 어렵냐 -;- [5]	ㅇㅇ(116.39)	05.04	129	0
44382	질문	뉴비 질문 [4]	ㅇㅇ	05.04	56	0
44381	질문	코포 블루가 앳코더 민트라는데 이거 맞음..? [3]	ㅇㅇ(106.101)	05.04	155	0
44380	일반	코테 준비겸 실 1~3랜디하는데 이것도 빡세네 [1]	ㅇㅇ(39.114)	05.04	85	1
44378	질문	물플레 뜻이 뭐임? [12]	ㅇㅇ(219.241)	05.04	297	0
44377	일기	골드찍었다 [2]	ㅇㅇ(183.104)	05.04	209	9
44376	일반	초등부 플레 문제는	ㅇㅇ(211.234)	05.04	174	0
44374	일반	드디어 나도 코드포스 스타트	코더(59.16)	05.04	118	3
44373	질문	파이썬은 import 하는 거 별루 업나요?? [6]	ㅇㅇ(39.127)	05.04	168	0
44372	일반	답볼때마다 존나 초라해지네 [1]	ㅇㅇ(118.235)	05.04	177	0
44371	일반	치터의 기준이뭐임? [3]	ㅇㅇ(118.235)	05.04	251	1
44370	일반	백준 본격 시작 2일차,, 어느정도 감이오네 [9]	ㅇㅇ(118.235)	05.04	218	1
44369	일반	금호공대 학교 이름 진짜 웃기네 ㅋㅋ [3]	ㅇㅇ(106.101)	05.04	293	0
44367	일반	이분 매칭 자주쓰이냐..? [4]	ㅇㅇ(115.22)	05.04	210	0
44366	일반	중기 저새끼 꽤 전에 ps갤에서 본거같은데 [5]	ㅇㅇ(59.6)	05.04	353	0
44365	일반	중기야 제발	ㅇㅇ(223.39)	05.04	216	0
44364	일반	PS가 게임보다 재밌음 [2]	ㅇㅇ(221.151)	05.03	273	5
44362	일반	'초등부' [8]	멍청봇	05.03	385	8
44360	일반	밑에 ps는 수능수학 어쩌고 쓴 글쓴이인데 공부법 이게맞음? [4]	ㅇㅇ(118.235)	05.03	213	0
44359	일반	노베->플레 얼마나걸림? [6]	ㅇㅇ(118.235)	05.03	215	0
44356	일반	졸업프로젝트만 끝나면 업솔빙해야지.. [1]	ㅇㅇ(211.217)	05.03	148	1
44355	질문	이거 제가 왜틀렸을까요 형님들.. [14]	ㅇㅇ(118.235)	05.03	266	0
44354	일반	ps공부할때마다 느끼는건데 수능수학30번문제 풀때랑 똑같은거같음 [8]	ㅇㅇ(118.235)	05.03	312	0
44353	일반	열심히해서 언잰가는 선형대수학문제풀어줄수있는 알고리즘도 풀고싶어요@! [2]	ㅇㅇ(118.235)	05.03	187	3
44352	일반	플상위 이상 문제들 업솔빙할때 질문 [1]	ㅇㅇ	05.03	147	0
44351	일반	안녕하세요 공부법 질문합니다 [12]	ㅇㅇ(118.235)	05.03	244	0
44350	일반	키보드 타이핑 어떤 식으로 하는게 좋을까 [4]	ㅇㅇ(115.92)	05.03	165	0
44349	질문	귀류법 같은 증명방법 공부하기 좋은 자료 있나요? [3]	ㅇㅇ(222.112)	05.03	198	0
44348	일반	이런 거 물어봐도 되는지 모르겠는데 [12]	ㅇㅇ(223.39)	05.03	336	0
44347	일반	G1 핵이 수백개인데 아직까지 내 거 안 털린 거면 [3]	ㅇㅇ(211.234)	05.03	229	0
44346	일반	G2도 반례 해킹이 있네 [3]	ㅇㅇ(106.102)	05.03	181	0
44345	일반	dp늅) 이렇게는 왜 안댐?? [4]	ㅇㅇ(39.7)	05.03	242	0
44344	일기	G1 hack있나본데 [6]	EN_SA	05.03	281	0
44343	일반	G2풀이 [2]	ㅇㅇ(211.57)	05.03	181	0
44342	일반	한주제 깊게 파는게 도움 많이되는듯	ㅇㅇ(49.174)	05.03	174	0
44341	일반	CP 진짜 잘하고싶다 [5]	ㅇㅇ(220.79)	05.03	251	0