꾸준히 하기/알고리즘 12

✍ 이분 그래프 (Bipartite Graph) 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 즉, 꼭짓점들의 집합 V와 변들의 집합 E로 이루어진 그래프 G = (V, E)가 이분 그래프라면, 꼭짓점들의 집합 V가 두 집합 A, B로 나눠져 E에 속한 모든 변들이 A와 B사이에만 존재할 수 있다는 것이다. 이분 그래프의 주요 특징 이분 그래프의 활용 1. 그래프 내의 정점들을 두 그룹으로 나눌 수 있다. 2. 같은 그룹 내에 정점들 간에는 간선이 없다. 3. 서로 다른 그룹에 속한 정점들 사이에만 간선이 존재한다. 혼합 결혼 문제 작업 할당 문제 네트워크 흐름 ..

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 예제 입력 예제 출력 3 1 3 2 4 3 5 2 문제 바로가기 문제 풀이 앞구르기 뒷구르기를 하면서 봐도 우선순위 큐를 사용해야 하는 문제다. 문제를 읽으면서 자연스럽게 정렬 사용 여부, 정렬 사용 기준, 스택 사용 여부, 우선순위 큐 사용 여부 등을 생각하게 된다. 다양한 문제들을 풀어서 경험치를 쌓다보면 해당 문제에 맞는 적..

1차원 좌표계 위에 선분 N개가 있다. 선분이 최대로 겹쳐있는 부분의 겹친 선분의 개수를 구해보자. 선분의 끝 점에서 겹치는 것은 겹치는 것으로 세지 않는다. 예제 입력 예제 출력 11 1 2 3 6 7 8 10 11 13 16 0 5 5 6 2 5 6 10 9 14 12 15 3 문제 바로가기 백준의 철로 문제와 비슷한 유형이라고 생각됩니다. 골드 2의 문제이니 먼저 풀고 오시는 것을 추천합니다. 문제 해석 서로 겹치는 선분의 최대 개수가 아니라, 겹쳐 있는 부분의 최대 개수를 구하는 문제였습니다. 처음에 문제를 읽고 전자로 오해해서 시간이 좀 걸렸지만 문제를 다시 읽어본 후 후자라는 것을 알아차렸습니다. 처음 문제를 읽을 때 꼼꼼히 잘 읽어봐야겠습니다. 라인 스와핑 철로 문제를 풀어봤기 때문에 푸는 ..

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 예제 입력 예제 출력 7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0 8 4000 문제 바로가기 문제 풀이 가장 큰 직사각형을 구해야 함으로, 지금의 길이가 이전 길이보다 길다면 스택에 넣는 방식으로 구현했다. 그렇게 하나씩 넣다가 이전보다 짧은 길이가 나타나면 현재까지 스택에 들어있는 값들을 가지고 만들 수 있는 가장 큰 넓이를 구한다. 풀이 과정 전..

x축 위에 원이 N개 있다. 원은 서로 교차하지 않는다. 하지만, 접할 수는 있다. 원으로 만들어지는 영역이 몇 개인지 구하는 프로그램을 작성하시오. 영역은 점의 집합으로 모든 두 점은 원을 교차하지 않는 연속되는 곡선으로 연결될 수 있어야 한다. 예제 입력 예제 출력 2 1 3 5 1 3 3 2 2 1 1 3 1 5 4 7 5 -9 11 11 9 0 20 6 문제 바로가기 문제 해석 문제를 보면, 원은 서로 교차하진 않지만 접할 수 있다고 했다. 우리는 원으로 만들어지는 영역의 개수를 구하면 되는 것이기 때문에 원이 완성됐을 때 개수가 하나 추가되는지, 두개 추가되는지를 판단하면 된다. 접하는 두원의 지름 합이 바깥원의 지름과 같으면 영역이 두군데가 생기기 때문이다. 즉, 원들의 지름값도 계산을 해야 ..