이분 매칭 알고리즘은 유량 그래프의 특수한 형태이다. 유량 그래프는 다음 포스팅에서 다루기로 하고... 이분 매칭 알고리즘에 대해 알아보자. 이분 매칭 알고리즘을 알아보기 전에, 이분 그래프에 대해 먼저 알고 넘어가야 한다. 이분 그래프란 정점을 두 개의 그룹으로 나누었을 때, 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 말한다. 위의 그림에서 보면 파란색 노드의 집합을 X, 빨간색 노드의 집합을 Y로 표현할 수 있고, 따라서 위의 그래프는 이분 그래프이다. 이분 매칭 알고리즘은 위와 같은 이분 그래프에서 최대 매칭의 개수를 찾는 것과 같다. 매칭이란 간선 하나를 선택하는 것을 말하는데, 예를 들어 그림에서 A와 a를 연결하는 간선을 선택하면 (A, a)라는 매칭이 생기는 것이다..
https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 작년 하반기 카카오 공채 문제로 나왔던 표 병합 문제이다! union-find 문제인데 당시에 문제를 풀 때는 거의 마지막쯤에나 깨달아서 결국 효율성 점수를 받지 못했었다... union-find 알고리즘 자체가 어려운 편은 아니라 구현만 꼼꼼하게 한다면 충분히 풀 수 있는 문제다. 구현 문제인 만큼 문제를 꼼꼼히 읽고 시작하자! 마치 엑셀을 연상시키는 것 같은 문제였는데, 엑셀과는..
Queue 오늘은 큐에 대해 공부했다. 큐의 구현 방식에는 Linear Queue, Circular Queue, Double Ended Queue 등 다양한 방식이 있는데, 오늘은 Circular Queue의 구현을 집중적으로 다뤄볼 예정이다. 큐는 후입선출 구조인 스택과는 다르게, 선입선출 구조를 가진 자료구조이다. 선입선출 구조란? 영어로는 First In First Out, 줄여서 FIFO라고 부르기도 하며, 자료구조에 먼저 삽입된 데이터가 먼저 빠져나온다는 의미이다. 우리가 맛집 웨이팅을 할 때 대기줄이 먼저 온 사람부터 들어가는 구조와 같다! 가장 기본적인 큐 자료구조는 리스트를 활용하여 구현한다. 리스트의 맨 앞부터 원소를 하나하나 쌓아나가고, 큐에서 원소를 삭제하면 가장 앞에 있는 원소부터 ..
