개발일지

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 그래프 이론중 이분 그래프에 대해 학습하기 좋은 문제를 찾아서 한번 이분 그래프에 대해 알아보고 해당 문제를 풀이해보겠다. 먼저 이분 그래프의 정의를 살펴보겠다. https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 이분 그래프 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 이분 그래프의 예..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 먼저 문제 해석을 하자면 n명의 사람을 두 팀으로 나눌 때 두팀의 능력치 차이가 제일 적은 경우에 대해 그 차를 출력하면 되는 문제이다. 각 인원은 서로 팀이 되는 경우마다 능력치가 바뀌기 때문에 각 인원에 대해 갖는 능력치를 행렬로 입력 받는다. 즉 i와 j가 팀인 경우 (i,j) + (j,i) 가 팀의 능력치로 계산된다. 모든 경우의 수를 구하고 각 경우의 수중에서 최소값을 찾는 문제이기 때문에 브루트포스로 접근하..

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 백트래킹 알고리즘을 공부하는 N과 M 시리즈의 문제중 하나이다. 오름차순으로 수열을 출력하는 점은 같지만 이문제의 특이한 점은 중복되는 수열을 출력하면 안된다는 점이다. 즉 수열이 중복되지 않게 백트래킹하는 과정에서 특수한 조건이 하나 필요하다. 이 문제를 풀기위한 아이디어는 우선 오름차순 정렬에 집중해보는것이다. 입력받는 숫자들을 오름차순으로 정렬한뒤 백트래킹을 시행한다. 이때 그전..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 연산할 숫자가 주어지고, 연산자 +,-,*,/에 대한 개수가 주어진뒤 해당 연산자와 숫자로 구할수 있는가장 큰수와 작은수를 구하는 문제이다. 이런 문제는 그냥 모든 경우의 수를 다 따져서 푸는 브루트포스 알고리즘을 사용하지만 중복되는 연산을 하지 않는 방법인 백트래킹 알고리즘을 사용해 간단히 풀수 있다. 즉 현재 연산자가 남은 개수에 따라..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net BFS 로 간단히 풀 수 있는 문제지만 탐색과정중 뱀이나 사다리를 만나면 아예 다른 칸을 점프를 해야하는 점이 특이해서 가져온 문제이다. 주사위를 구려 1~6까지 한번에 바로 진행이 가능하다 이때 진행한 칸이 뱀이나 사다리가 존재한다면 뱀이나 사다리를 통해 이동된 다른칸에서 탐색을 진행하면 된다. 우선 방문처리할 보드, 그리고 뱀,사다리에 대한 정보를..