밤이 블로그

BOJ#2580 스도쿠 * 문제https://www.acmicpc.net/problem/2580 * 풀이스도쿠는 어떻게 푸는 것일까요?사람이 스도쿠를 푸는 과정을 생각해보면 아래와 같습니다.(Backtracking) 숫자를 하나 검증해서 넣어보고 -> 다른 칸으로 진행 -> 실패하면 되돌아와서 다른 숫자를 넣어보고 -> 반복.. 계산량을 줄이기 위해 최초 map 정보를 입력 받을 때 필요한 정보들을 미리 저장해두면 됩니다.1. 빈칸의 정보를 저장한다.2. 각 행의 정보를 저장한다.3. 각 열의 정보를 저장한다.4. 각 사각형의 정보를 저장한다. 자료구조는 boolean 배열로 해도 되고, bit mask를 이용해도 됩니다. * 나의 코드 https://github.com/stack07142/BOJ/blo..

BOJ#1405 미친 로봇 * 문제https://www.acmicpc.net/problem/1405 * 풀이 - N의 범위가 작으므로 visited 배열을 이용하여 간단하게 단순 경로인지 아닌지 체크해줍니다.- 각 방향으로 움직일 확률을 입력 받을 때, double 타입의 확률로 바꿔서 입력받아줍니다.- 1번 이동해서 단순경로가 된다면 확률은 1.0, 그렇지 않으면 0.0 입니다.- 4방향으로 움직일 수 있으므로4방향 Sum(각 방향으로 움직일 확률 * 현재 위치에서 N-1번 움직일 때 단순경로가 될 확률) * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%231405_CrazyRobot/src import java.io.BufferedReader; i..

BOJ#2661 좋은수열 * 문제https://www.acmicpc.net/problem/2661 * 풀이 - 수열의 시작은 무조건 1이다. - 나쁜 수열인지 체크하는 알고리즘 세우기- Backtracking 구성 1) 나쁜 수열 체크2-1) 나쁜 수열인 경우 돌아가기2-2) 좋은 수열인 경우3-1) 길이를 다 채운 경우 -> 답을 return하고 모든 재귀함수를 종료한다.3-2) 길이를 다 못채운 경우4) 숫자 추가 (1~3 순서대로, 가장 작은 수를 만들어야 하기 때문에) * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%232661_GoodSequence/src import java.io.BufferedReader; import java.io.IO..

BOJ#9663 N-Queen * 문제https://www.acmicpc.net/problem/9663 * 풀이 유명하면서도 어려운 문제입니다. Queen을 1개~N개까지 배치하면서, 잘못 배치한 경우 되돌아가서 다른 시도를 해봐야 합니다. 따라서 backTracking을 이용합니다. 주의할 점 0. QueenQueen은 상하좌우, 대각선 모두 이동할 수 있습니다. 1. 꼭 행렬로 map을 만들 필요가 없습니다.보통 map 행렬을 만든 후 -1, 0, 1등의 숫자를 이용해배치할 수 있는 곳과 아닌 곳을 표시하고, 이 정보를 기반으로 다음 행동을 결정하는데 이 경우 불필요한 리소스와 시간이 소요됩니다. 2. Queen은 N개 이므로 행(row) 1개당 Queen 1개가 배치됩니다. = 각 행마다 Queen..