백준 [1707] 이분 그래프 (bfs)
같은 레벨의 정점끼린 같은 색, 인접 노드 끼리는 다른 색을 칠한다. 만약, 인접 노드가 자신과 같은 색이라면 이분 그래프가 아니다. 예를 들면, 정점이 4개인 임의의 그래프가 있다면, 칠하는 방식은 다음과 같다. (하얀색, 검은색) 하지만, 자신과 인접한 노드가 자기와 같은 색이 된다면 이분 그래프라 할 수 없다. 아래 그래프에서 3과 4가 연결 됐을 때, 3을 탐색 할 때, 인접 노드인 4를 검은색으로 칠해야 하는데, 4는 인접 노드인 3과 같은 하얀색이기 때문에, 이분 그래프라 할 수 없다. 반대로, 4부터 탐색한다 해도, 같은 문제가 발생한다. 여기서 주의할 점은, 주어진 입력이 비연결 그래프일 수 있기 때문에, V범위 전부를 탐색해야 한다. 따라서 시간 복잡도는 O(V + E)가 나온다. bfs..
백준 [11054] 가장 긴 바이토닉 부분 수열
이 두 문제를 풀었다면 쉽게 풀 수 있다. www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A..
