이분 매칭 알고리즘은 유량 그래프의 특수한 형태이다. 유량 그래프는 다음 포스팅에서 다루기로 하고... 이분 매칭 알고리즘에 대해 알아보자. 이분 매칭 알고리즘을 알아보기 전에, 이분 그래프에 대해 먼저 알고 넘어가야 한다. 이분 그래프란 정점을 두 개의 그룹으로 나누었을 때, 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 말한다. 위의 그림에서 보면 파란색 노드의 집합을 X, 빨간색 노드의 집합을 Y로 표현할 수 있고, 따라서 위의 그래프는 이분 그래프이다. 이분 매칭 알고리즘은 위와 같은 이분 그래프에서 최대 매칭의 개수를 찾는 것과 같다. 매칭이란 간선 하나를 선택하는 것을 말하는데, 예를 들어 그림에서 A와 a를 연결하는 간선을 선택하면 (A, a)라는 매칭이 생기는 것이다..
https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 2020 카카오 공채 1차 코딩테스트 7번 문제로 출제된 블록 이동하기 문제이다. 이렇게 맵을 탐색하는 문제는 굉장히 흔한데, 그런 문제들과 이 문제의 가장 큰 차이점은 바로 로봇이 한 칸이 아닌 두 칸을 차지한다는 점이다. 또한 로봇이 이동할 때에도 두 칸이 모두 이동할 수 있어야 한다는 제약이 걸려있다. 또 이러한 점을 고려하여 로봇이 회전까지 할 수 있다... 위의 조건들을 고려..
https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 작년 하반기 카카오 공채 문제로 나왔던 표 병합 문제이다! union-find 문제인데 당시에 문제를 풀 때는 거의 마지막쯤에나 깨달아서 결국 효율성 점수를 받지 못했었다... union-find 알고리즘 자체가 어려운 편은 아니라 구현만 꼼꼼하게 한다면 충분히 풀 수 있는 문제다. 구현 문제인 만큼 문제를 꼼꼼히 읽고 시작하자! 마치 엑셀을 연상시키는 것 같은 문제였는데, 엑셀과는..
