[문제]https://www.acmicpc.net/problem/2239주어진 스도쿠 보드를 기준으로 완성시키는 문제입니다. 간단하게 생각하면 주어진 행, 열과 3x3 공간을 전부 탐색 후, 가능한 숫자를 끼워 넣고 퍼즐을 완성하면 됩니다. 이를 구현하기 위해 DFS 방식을 사용합니다. 깊이를 늘려가며 퍼즐을 만들어 가다가 유효하지 않은 퍼즐이 생성되면, 이전 단계로 이동해 유효하지 않은 숫자를 버리고 유효한 숫자를 집어넣어 재탐색을 진행합니다. 해당 문제는 까다로운 부분이 존재하는데, 답이 여러 개 생성될 수 있다는 것이고 이를 제한하지 않으면 "출력초과"가 발생하게 됩니다.또한 기본적인 백트래킹을 사용하면 시간 초과가 발생하기 때문에 최적화를 염두하여 문제를 풀어내야 합니다.[초기화] def _..
백준
[문제]https://www.acmicpc.net/problem/2143 누적합과 가능한 경우의 수를 모두 계산하고 해시를 통해 값을 관리하는 문제입니다. 누적합이란 배열의 각 값을 합산하여 특정 구간의 합을 빠르게 구할 수 있도록 만들어 낸 자료구조입니다.예시는 다음과 같습니다.A = [1, 2, 3, 4, 5]S = [0, 0, 0, 0, 0] -> 누적합 배열1. S[0] = A[0] = 12. S[1] = A[0] + A[1] = 1 + 2 = 33. S[2] = A[0] + A[1] + A[2] = 1 + 2 + 3 = 64. S[3] = A[0] + A[1] + A[2] + A[3] = 1 + 2 + 3 + 4 = 105. S[4] = A[0] + A[1] + A[2] + A[3] + A[4]..
[문제]https://www.acmicpc.net/problem/11559 BFS를 이용한 단순 구현문제였습니다. 아래 문제와 유사합니다.https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com[초기화] def __init__(self): self.stage = [list(input()) for _ in range(12)] self.directions = [[-1, 0], [1, 0], [0, -1], [0, 1]] # 상하좌..
[문제]https://www.acmicpc.net/problem/1525 인접한 네 개의 칸으로 이동할 수 있다는 점, 최소 이동 횟수를 구해야 한다는 점에서 BFS를 사용한 풀이를 유추할 수 있었습니다. 2차원 배열로 그대로 사용할 경우, 0의 위치를 탐색하거나 퍼즐의 이동을 구현하기 위해 임의의 배열을 만들고 카피하는 과정이 번거롭고 메모리에 제약이 걸리다는 점에서 1차원 배열과 문자열을 이용해 풀이하였습니다.[초기화] static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int[][] directions = {{-1, 0}, {1, ..
