문제본문 스도쿠 규칙 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 백트래킹이란 가능하지 않는 집합을 배제하는 완전 탐색(브루트포스)을 의미합니다. 모든 경우의 수를 구하지만 정답이 아닐 확률이 높다면 시도하지 않는 것이죠. 때문에 완전탐색보다 빠른 시간안에 정답을 구현할 수 있습니다. 관련 알고리즘의 흐름과 설명은 참고 링크에 더 자세히 나와 있습니다. 스도쿠 입력 9 x 9 스도쿠판에 0 ~ 9 숫자 값이 들어 있습니다. 빈칸은 여러개 존재할 수 있으며 빈칸은 0으로 표시합니다. 0 3 5 4 6 9 2 7 8 7 8 2 1 0 5 6 0 9 0 6 0 2 7 8 1 3 ..
문제 본문 하노이 탑의 규칙 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 하노이 탑은 재귀 함수로 구현하는 대표적인 문제입니다. 재귀 함수란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법입니다.풀고자 하는 문제가 동일한 성격의 작은 문제들로 구성되어 있을 때 사용하면 좋습니다. 하노이 탑의 규칙으로 함수의 성격을 분석해보자 문제: N개의 원판을 1번째에서 3번째로 옮긴다. (1): N - 1개의 원판을 1번째에서 2번째로 옮긴다. (2): N번째 원판을 1번째에서 3번째로 옮긴다. (3): N - 1개의 원판을 2번째에서 3번째로 옮긴다. (1)과 (3) 을 보면 N의 크기만 다를 뿐 성격을..
문제 본문 소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수입니다. 대표적으로 2, 3, 5, 7.. 등등이 있습니다. 단순 소수 찾기 - O(n^2) public static boolean isPrime(int num) { if (num == 1) return false; for (int n = 2; n < num; n++) { if (num % n == 0 ) { return false; } } return true; } 가장 간단하게 소수를 구하는 방법은 1을 제외하고 자신보다 작은 자연수로 나누어 나머지가 0이 나오는 지 확인하는 것입니다. 하지만 위 방법은 O(n^2)의 시간 복잡도를 가져서 num의 값이 크다면 시간초과를 발생합니다. 제곱근을 활용하여 소수 찾기 -..
