문제 링크 https://www.acmicpc.net/problem/10597 풀이- 백트래킹 사용- 정답은 구했으나 boolean[] visited 배열을 사용하는 것과 최대 수가 50인걸 파악하지 못한 풀이로 시간 초과 발생- 잘못 풀이한 부분에 대한 이력 남김 문제 설명과 같이 1 ~ N까지의 숫자로 이루어진 순열을 구해야한다- N = 10인 경우 1 부터 10 까지의 수가 중복 없이 모두 포함되어 있어야 한다는 의미- "kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다."에서 (러프하게)최대 수가 50까지 라는 것을 파악할 수 있다- 연산을 편하게 하기 위해서 int[] nums 배열을 선언 후 숫자 초기화를 수행하였다 백트래킹 수행할 함수를 아래와 같이 선언하였다(idx >= 배열..

문제 링크https://www.acmicpc.net/problem/2661  풀이- 백트래킹 사용- 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다- 인접한 두 개의 부분 수열이 서로 다르면서 좋은 수열 중 가장 작은 값을 찾는다 ①재귀를 호출할 때 항상 1 ~ 3을 순차적으로 순회하기 때문에 처음 종료 조건(길이가 N인)에 부합하는 값이 최소값임이 보장된다for(int i = 1; i   *좋은 수열이기 위한 유효성 검사 관련하여 ② 이전 값(prev)를 재귀 호출시 파라미터로 전달하고 for문에서 다음으로 연결할 값과 같은 경우(prev == i) continue③ 이전 값(prev)과 다른 경우 해당 숫자를 문자열..

문제 링크 https://www.acmicpc.net/problem/2580  풀이- 백트래킹, 비트 마스킹으로 문제 해결 문제를 한번만 읽고 풀다가 유효성 검사에서 3 * 3 그리드를 누락하여 "틀렸습니다"를 맛 보았다..🥹스도쿠의 필드가 0인 영역을 채울 때 유효성 검사를 총 3가지를 수행해야 했다 ① 행② 열③ 3 * 3 그리드 영역 rows, cols, boxes 각 배열을 사용하여 비트 마스킹을 표현하고, 유효성 검사를 하도록 하였다private static long[] rows;private static long[] cols;private static long[] boxes; 입력 데이터 초기화시  값이 0인 경우 리스트에 좌표 정보를 담고, 나머지의 경우 비트 마스킹 표기를 할 수 있도록 ..

문제 링크 https://www.acmicpc.net/problem/19236 풀이백트래킹이 약한 나에게 있어 정말 실수 연발했던 문제였다 (그래도 백트래킹 재미있다) ① 입력 데이터 초기화 후 상어가 `(0, 0)` 에 물고기를 먹고 그 방향을 가진다 ② 모든 물고기들이 이사를 시작한다- 작은 번호부터 순차적으로 이사- 이동 가능한 위치를 찾을 때 까지 반 시계 방향으로 제자리 회전하면서 빈칸 또는 물고기를 찾아 위치를 교환한다- 상어가 있거나, 맵의 경계를 벗어난 경우 다음 위치로 회전- 만약 이사 가능한 위치가 없다면 제자리를 유지한다③ 상어가 먹이를 탐색한다- 상어는 빈칸으로 이동 불가하고 이동하는 도중에 있는 물고기는 먹지 않는다- 이때, 큰 물고기를 먹는다고 항상 최적의 해를 보장하지 않는다 ..

문제 링크 https://www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net 문제 풀이 중복 방문을 허용하고, 상하좌우 대각선(8개 방향) 방향으로 이동하여 문자열을 만듦 참고. 시간 복잡도 행 * 열 * (8방향으로 이동^최대 단어 길이 5) = 100 * (8^5) = 3,276,800 (1초안에 수행 가능) 참고. 방향 이동 관련하여 ( 3 x 3 ) (0, 0) 좌표에서 아래 대각선 방향으로 이동할 경우 맵의 범위를 벗나게 될 것이다 (-1, -1) (-1, 0) (-1, 1) (0, -1) 시작 (0, 1) (1, -1) (1, 0) (..

문제 링크 https://www.acmicpc.net/problem/20164 20164번: 홀수 홀릭 호석 호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 www.acmicpc.net 문제 풀이 하나의 수가 주어졌을 때 호석이는 한 번의 연산에서 다음과 같은 순서를 거친다. 1. 수의 각 자리 숫자 중에서 홀수의 개수를 종이에 적는다. 2. 수가 한 자리이면 더 이상 아무것도 하지 못하고 종료한다. 3. 수가 두 자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각한다. 4. 수가 세 자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새로..

문제 링크 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 풀이 - DFS로 연산자에 대한 순열(Permutation)을 구한 후 연산 결과값 구함 - N(2 ≤ N ≤ 11) 이므로 최대 연산자 개수는 10개, 순열 10! = 3,628,800 - 시간복잡도 O(N! * N ) = O(10! * 11) = 약 3,600만번 이므로 풀이가능 제출 코드 풀이1. 연산자 순열을 구한 후 연..