백준 [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..
백준 [9663] N-Queen
백트래킹을 이용한 문제. 생각한 방법은 3가지였다. 3번째 방법이 내가 적용한 풀이다. 1. 2차원 배열을 선언해, 퀸이 배치 될 때, 퀸의 경로에 1을 더해서, 다음 퀸이 이 자리에 오지 못하게 한다. 만약, 다른 퀸의 경로하고 겹치는 경우 1을 또 더해준다. 아래 그림이 예시다. 하지만, 이렇게 되면, 퀸 배치를 옮길 때, 복구 작업도 해줘야 하기 때문에, 시간이 오래걸리고, 코드도 깔끔하게 나오진 않았다. 2. 매 탐색마다, N 크기를 1씩 줄이기 어떤 자리에 퀸이 들어왔단 것은 해당 행과 열엔 퀸이 들어오지 못하니, 다음 재귀함수에선 (N-1 * N-1)만큼의 크기를 검사하는 방식 여기서 문제는 위의 그림에서 보듯이, 2번째 퀸이 3번째 열에 배치되면, 2번째 열에 퀸을 배치할 수 있음에도 불구하..
