https://www.acmicpc.net/problem/2580 문제조건스도쿠판을 채우자각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.접근방법 문제를 보자마자 떠오른 생각은 N-Queen 문제와 상당히 유사한 문제라는 생각 이었다. 물론 Brute Force로 모든 경우의 수를 탐색해서 구할 수도 있겠지만, O(2^n) 이상의 시간소요로 시간초과가 날 것이 분명했고, N-Queen문제와 같이 백트래킹으로 접근했다.유망한지 판단하고, 유망하다면 DFS를 진행하는 백트래킹 방식에서 시간단축이 됨을 인지하고, 가로, 세로, 3x3 크기의 칸에서 같은 숫자가 하나도 없는지 체크하고 그..

https://www.acmicpc.net/problem/17136 문제조건  1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류의 색종이가 있다.각 종류마다 5개씩 가지고 있다. 10×10인 종이에 색종이를 붙인다. 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다., 0이 적힌 칸에는 색종이가 있으면 안 된다. 필요한 색종이의 최소의 개수?모두 덮는것이 불가능한 경우 -1을 출력 접근방법 하나씩 범위를 넓혀주는 BFS 방법을 써야하나,,? 라는 생각이 들었지만 정형화 시킬 방법이 떠오르지 않았다. 따라서 DFS측면으로 접근했는데, 한변의 길이가 1일때부터 5일때 까지 하나씩 판단해야하고, 그럴려면 중복을 방지 하기위해 visited 배열을 활용해야한다. 이 ..

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명의 사람을 각각 n/2 명씩 두팀으로 나눈다. 한 팀의 능력치는 (i, j) 가 같은 팀이라면 map[i][j] + map[j][i]로 나타내고, 같은 팀의 사람들의 능력치를 모두더한다. 두 팀의 능력치 차이의 최솟값은? 접근방법 보자마자 입력값도 작고, 최솟값을 구하기 위해 모든 경우의 수를 Brute Force로 탐색하면 되는 거 아닌가? 생각이 들었고, DFS로 모든 경우의 수에 대해서 탐색했다. 너..