처리중입니다. 잠시만 기다려주세요.
TTJ 코딩클래스
정규반 단과 자료실 테크 뉴스 코딩 퀴즈
더보기
인사이트 FAQ 유튜브 카페

로그인

| 비밀번호찾기

추가 정보 입력

서비스 이용을 위해 휴대전화 번호를 입력해주세요.

회원가입

무료 회원가입 가입비 없이 무료로 가입할 수 있습니다

이미 계정이 있으신가요?

비밀번호 찾기

퀴즈 / 알고리즘 / 문제

알고리즘에서 '호프크로프트-카프(Hopcroft-Karp)' 알고리즘의 용도는?

어려움 freeCodeCamp
보기 및 정답
A 이분 그래프에서 최대 매칭(Maximum Matching)을 효율적으로 구하는 알고리즘이다
B 가중치 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 구하는 탐색 알고리즘이다
C 문자열 데이터를 특정 규칙에 따라 인코딩하여 원본 대비 크기를 줄이는 압축 알고리즘이다
D 무방향 그래프에서 서로 연결된 정점들의 그룹인 연결 요소를 탐색하여 분리하는 알고리즘이다

해설

호프크로프트-카프 알고리즘은 이분 그래프에서 최대 매칭을 O(E√V) 시간에 구합니다. BFS로 증가 경로의 최단 길이를 구한 후 DFS로 해당 길이의 증가 경로를 모두 찾는 과정을 반복합니다. 직원-업무 배정, 학생-학교 매칭 등에 활용됩니다.

코딩, 제대로 배우고 싶다면?

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

정규반 살펴보기

관련 문제

알고리즘에서 '동적 프로그래밍(Dynamic Programming)'의 메모이제이션(Memoization)과 타뷸레이션(Tabulation)의 차이점으로 올바른 것은?
알고리즘
공간 복잡도(Space Complexity)란 무엇인가요?
알고리즘
선택 정렬(Selection Sort)의 동작 방식은?
알고리즘
A* 알고리즘의 핵심 특징으로 올바른 것은?
알고리즘
알고리즘에서 '크루스칼(Kruskal)' 알고리즘과 '프림(Prim)' 알고리즘의 공통점과 차이점은?
알고리즘