1. 문제 1115번: 순열 (acmicpc.net) 1115번: 순열 0부터 N-1까지 모든 정수를 한 번씩 포함하고 있는 순열 A[0], A[1], ..., A[N-1]이 있다. 순열 A를 이용해서 A와 길이가 같은 자식 배열 B을 아래와 같은 방법으로 구할 수 있다. B[0] = 0 B[i] = A[B[i-1]] (1 ≤ www.acmicpc.net 완벽한 순열 == 순열이 해당 규칙에의해 모든 정점을 방문하는 순환형태 P와 Q의 차이 == P[i] 와 Q[i]의 값이 다른 i 의 개수 이 문제에서 주어진 규칙에 의해 주어진 순열은 한 정점당 한 엣지를 가지는 방향그래프로 생각할 수 있으며, 이는 곧 그래프 문제로 변형하여 문제를 해결 할 수 있음을 의미한다. 2. 차이가 가장 작은 완벽한 순열 찾..

1. 문제 n개의 노드가 있는 그래프 => 각 노드는 1부터 n까지 번호가 적혀있다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고한다. 가장 멀리 떨어진 노드란 최단 경로로 이동햇을 때 간선의 개수가 가장 많은 노드를 의미한다. 노드의 개수 n은 2 이상 20,000이하이다. 간선은 양방향이며 총 1개이상 50,000개 이하의 간선이 있다. vertex 배열 각 행 [a, b] 는 a번 노드와 b번 노드 사이에 간선이 있다는 의미이다. 2. 너비우선 탐색 그래프의 최단거리를 구하는 방법은 여러가지가 있다. 그 중 한점을 기준으로 하는 탐색방법은 bfs O(|V| + |E|)를 이용하는것과 bfs에 우선순위큐를 활용한 다익스트라 O(ElgV) , 간선을 기준으로 업데이트하여 구하는 벨만 포드 O..

1. 문제 반 학생들의 체육복이 도난당했다. 도난당한 학생의 번호와 여유분을 가진 학생의 번호가 주어진다. 여유분을 가진 학생이 도난당한 학생에게 체육복을 빌려줄때 체육복을 최대한 나눠주고, 체육수업을 들을 수 있는 최대 학생수를 구하여라 단, 체육복은 자신의 앞뒤 번호한테만 빌려줄 수 있다. 단, 여유분을 가지고 있던 학생이 도난당했을 수 있다. 그러면 빌려주지 않는다. 2. 자원분배 문제: 네트워크 플로 이 문제는 이분 그래프의 최대매칭 문제로 네트워크 플로로 풀 수 있다. 여유분 그룹에서 도난 그룹으로가는 그래프를 그린 후 네트워크 플로우 알고리즘을 사용하면 문제가 해결된다. 단, 여유분을 가지고 있던 학생이 도난당할경우 그래프를 그리지 않는다. 1 2 3 4 5 6 7 8 9 10 11 12 13..

1. 문제 타일이 주어지면 '.'에 함정을 설치한다고 한다. 이때 함정은 상하좌우 4칸에 다른 함정이 없어야된다. 이때 최대 함정을 설치할 수 있는 갯수와 함정의 위치를 포함한 타일을 출력해야한다. 2. 암시적 그래프 타일을 상하좌우를 간선으로 가지는 암시적인 그래프로 표현할 수 있다. 이를 이용해 이분 그래프의 매칭 문제의 dfs코드를 조금 변형하면 최대한 많은 타일에 함정을 매칭할 수 있다. 이분 그래프로 생각하면 다음과 같다. a그룹 = '#' 이 아닌 타일 전체 b그룹 = 상하좌우중간 으로 묶여진 타일들의 집합. 중간을 기준으로 구별할 수 있다. 3. 이분 그래프의 매칭 dfs 모든 타일을 조사하면서 '.' 인 타일에대해 dfs를 실행한다. (a그룹을 하나씩 조사) 주위에 함정이 없어 함정을 설치..

1. 문제 게임판과 장애물의 위치가 주어진다. 이 게임판 위에서 비숍을 서로 죽일수 없도록 최대한 몇개 배열할 수 있는지 계산하는 문제이다. 2. 이분 매칭 비숍은 대각선으로만 이동할 수 있다. 오른쪽으로 가는 대각선과 왼쪽으로 가는 대각선 두개로 비숍의 위치를 나타낼 수 있다. 그러므로 해당 대각선에 비숍이 두개 있을 경우 서로 죽일 수 있다. 이를 이용하여 오른쪽 대각선과 왼쪽대각선을 a그룹 b그룹으로 나누어 이분 할 수 있으며 최대한 많이 비숍을 배열해야하므로 이는 이분 최대 매칭 문제가 된다. 따라서 그래프만 적절히 표현하면 문제는 쉽게 해결된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ..

1. 매칭 문제 N명을 둘씩 짝으로 묶으려고한다. 단 사이가 좋은 사람끼리만 짝을 지어준다고 할때 모든 학생에게 짝을 지어 줄 수 있는지, 불가능하다면 최대 몇 쌍이나 만들 수 있는지 계산하는 문제가 매칭 문제의 예시이다. 이런 문제들은 그래프로 간단하게 표현할 수 있다. 각 사람을 표현하는 정점을 만든 뒤, 사이 좋은 학생들을 간선으로 연결한다. 이 때 서로 짝을 이룬 학생들을 연결하는 간선들을 모아 보면, 이들은 끝점을 공유하지 않는 간선의 집합이 된다. 이런 간선의 집합을 이 그래프의 매칭(matching)이라고 한다. 이때 가장 큰 매칭을 찾아내는 문제를 최대 매칭 문제(maximum matching), 매칭 문제라고 부른다. 매칭 문제는 직관적인 정의를 가진 중요한 문제이다. 하지만 모든 그래프..