java

문제9x9 스도쿠 판이 입력으로 주어지면 이 이 스도쿠 판을 다음의 규칙에 따라 완성해서 출력하는 문제이다. *(반드시 완성이 가능한 스도쿠만 입력으로 주어진다.)(1) 각각의 가로줄과 세로줄에 1부터 9까지의 숫자가 한번씩 나타나야한다.(2) 3x3 정사각형 안에도 1부터 9까지의 숫자가 한번씩 나타나야한다.접근이렇게 풀면 되지 않을까?(1) 판을 순회하면서 1 ~ 9 까지의 숫자가 해당 판에 가로조건, 세로조건, 3x3 조건을 충족하면 놓는다.(2) 그 다음으로 이동한다.(3) 만약 모든 숫자에 대해서 가로조건, 세로조건, 3x3 조건을 충족하지 못한다면 가능한 최소한의 경우의 수로 롤백한다. 그리고 이러한 문제 풀이는 백트래킹의 일종인 깊이우선 탐색을 통해 풀 수 있다. 풀이import java.i..

아무래도 백트래킹 문제가 약한거 같아서 GTP 에게 문제를 좀 내달라고 했다.  쉬운 문제 2개는 부분 수열의합 문제와 모든 순열 출력하기를 내줬고, 이는 백준에서 풀었던 문제와 비슷해서 복습하는 개념으로 풀었다. 그리고 중간 나이도 문제로 N Queen 문제를 내줬다. 문제  해결하기 재귀 호출 설계재귀를 잘못 설계하면 Stackoverflow 에 빠질 수 있다. NQueen 경우의 수를 구하는 문제일 때 재귀 횟수를 줄이려면 다음과 같이 해야한다. (1) 하나의 기준을 정하고 순회한다.'각 퀸이 서로 공격할 수 없다.' 라는 조건에 따라 Row, Col 을 기준으로 하나의 queen 을 넣을 수 있나? 만 고려하면 되고 그렇게 되면 순회 횟수가 N*N 에서 N 으로 줄어든다. (2) 기준 에 따라 놓..