밤이 블로그

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#1339 단어 수학 * 문제https://www.acmicpc.net/problem/1339 * 풀이 이 문제는 두가지 풀이법으로 풀어보겠습니다. 예)MCR ACDEB 1) 수학으로 풀기 위의 두 숫자를 풀어보면MCR = M * 100 + C * 10 + R * 1ACDEB = A * 10000 + C * 1000 + D * 100 + E * 10 + B * 1 두 숫자를 더해보면MCR + ACDEB = 10000A + 1001C + 100M + 100D + 10E + R + B 가 됩니다. 하나의 문자는 하나의 숫자(0~9)로 대응되고합의 최대값을 구하고 싶으므로 즉, 10000A + 1001C + 100M + 100D + 10E + R + B의 최대값을 구하면 되는 것입니다. A -> C ->..

BOJ#3109 빵집 (PLINOVOD) * 문제https://www.acmicpc.net/problem/3109 * 풀이 1) 가스관과 빵집을 연결하는 가스 파이프 라인은 첫번째 열에서 시작하고, 마지막 열에서 끝나게 됩니다. 2) 첫번째 열과 마지막 열은 항상 비어있습니다.3) 각 칸은 3가지 방향으로 (↗️, ➡️, ↘️) 연결할 수 있습니다.4) 건물이 있을 경우 파이프를 설치할 수 없고, 파이프끼리 겹칠 수도 없습니다. 1번 조건 : 첫번째 열에서 시작하여 마지막 열까지 진행 후 return 되는 Backtracking 함수 구현 : 마지막 열 도달 시 1을 return하여 파이프라인 개수를 증가시킨다. 2번, 3번 조건 : 첫번째 열은 모든 행을 검사해야 하고, 그 다음부터는 최대 3개의 행만..

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..