백트래킹7

• 

  백준 - 죽음의 비 문제 설명 격자가 주어지고 출발지에서 도착지 까지는 체력이 소모된다. 출발지에서 도착지 까지 체력이 0이 되지 않으면서 가장 빠르게 이동하는 횟수를 구하는 문제이다. 출발지에서 도착지까지 해당 격자 공간안에 우산이 주어지면 우산의 내구성을 얻어 체력이 1씩 감소되는 경우를 우산으로 대체할 수 있다. 주의사항 일반 방문 T/F처리로는 목적지까지 온전히 갈수없다. 왜냐하면 빠르게 가는 것보다 체력이 도착지까지 0이 안되는 경우가 더 우선순위이기 때문이다. TRY DFS, 맨헤튼 거리를 통한 BFS 탐색 [FAIL] 방문 배열을 int로 선언한 현재 체력+우산의 내구도에 대한 흔적을 남기고 진행하기 이렇게 되면 가장 먼저 빠르게 목적지 인근에서 체력이0이 된 경우에도 뒤에 있는 노드들은 계속 진행할 수 있다... Algorithm/백준 2023. 4. 25.

• 

  백준 - 좋은 수열 문제 설명 숫자 1,2,3으로만 N길이의 좋은 수열을 만들 수 있는 수열중 가장 작은 수를 반환하는 문제이다. 여기에서의 좋은 수열은 인접한 두 개의 부분수열이 동일하지 않는 수열이다. 그리고 나쁜 수열은 인접한 두 개의 부분수열이 동일한 경우의 수열이다. ex) 33 32121323 123123213 주의사항 길이가 n자리를 만드는 것에 유념해아햔다. int 또는 long 형의 타입도 커버할 수 없다. 인접한 길이의 부분 수열 로직을 잘 작성해야한다. 앞자리에서 시작하는 부분 수열만을 체크하는 것이 아니라 중간 부분에서 시작한 부분수열에도 동일한 수열이 존재하면 그것은 나쁜 수열로 인식해야 한다. 풀이 static int n; static int arr[] = {1, 2, 3}; public stati.. Algorithm/백준 2023. 4. 25.

• 

  백준 - 스도쿠 문제 설명 가로, 세로 그리고 현재 위치한 작은 사각형 내부에 숫자를 1-9까지 고유하게 존재해야하는 스도쿠 판을 완성하는 문제이다. 고유한 숫자가 나오기 위해서 이처럼 검사를 진행해야한다. 1) 행, 열 유일성 검사 2) 작은 사각형 내부 안에서의 숫자의 유일성 검사 시작점을 찾는 규칙을 찾아야하며 해당 시작점부터 +3,까지 숫자의 유일성을 검사해야한다. 풀이 static final int N = 9; static int[][] grids; public static void main(String[] args) throws IOException { grids = new int[N][N]; BufferedReader reader = new BufferedReader(new InputStreamReader(.. Algorithm/백준 2023. 4. 22.

• 

  백준 - 무기공학 문제 설명 격자가 있는 칸에 부메랑(4가지 도형)을 형성하여 최댓값을 구하는 문제이다. 격자의 최대 칸이 5*5이므로 완탐해도 상관 없었다. 현재 위치하고 있는 칸을 부메랑의 중심부라 가정하고 부메랑을 형성하였다. 방문 여부를 판단하여 현재 위치에서 부메랑을 만들 수있는지 판별하였다. 풀이 static boolean v[][]; // 부매랑들의 강도 합의 최댓값을 출력하시오 public static int solution() { v = new boolean[n][m]; pick(0, 0); return answer; } public static void pick(int cnt, int sum) { if (n * m = n || nx >= m; } Algorithm/프로그래머스 2023. 4. 16.

• 

  백준 - 줄어드는 수 문제 설명 줄어드는 수 중 n번째인것을 출력하는 문제이다. 줄어드는 수를 321,950과 같은 숫자가 왼쪽에서 오른쪽으로 한자리씩 봤을 때, 작은 수여야 한다고 한다. 322와 859는 줄어드는 수가 아니라고 한다. 해당 문제는 아이디어를 잘 내야한다.. 주의사항 n의 입력을 명시적으로 주고 있지만 얼만큼의 줄어드는 수를 만들어야 할지 고민일 것이다. 위 문제를 보면 줄어드는 수 중 가장 큰수는 987654321이라는 것을 알 수 있다. TRY 선형적으로 1부터 987654321까지 String으로 변환하여 stack을 이용하여 줄어드는 수인지 판별 [시간초과] 백트래킹 9876543210을 배열에 위치시켜 하나씩 골라 수를 만든다. [성공] 수를 만들때 이전에 골랐던 범위는 절대 선택하지 않도록 해야한.. Algorithm/백준 2023. 4. 15.