backtracking5 [백준] 9663번 N-Queen JAVA (자바) 풀이 문제 9663번 (백트래킹) : N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제 N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램 [입력] : 첫째 줄에 N이 주어진다. (1 ≤ N [출력] : 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력 [과정] 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 pos메서드를 통해 참이 아니라면 다시 바꿔서 탐색한다 참이면 더 깊이 들어간다 종료 조건) depth==N 모두 종료되는 것이 아니라 N의 퀸을 세웠으면 경우의 수 1개를 카운트한다 1. 퀸의 공격 방향은 대각선, 세로, 가로같은 행, 같은 열, 같은 대각선은 피해야한다하나의 행씩.. 2024. 8. 6. [백준] 1987번 알파벳 JAVA (자바) 풀이 문제 1967번 (백트래킹) : 세로 R칸, 가로 C칸으로 된 표 모양의 보드 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다 말은 상하좌우로 이동 가능 새로 이동한 칸의 알파벳 ≠ 지금까지 지나온 모든 칸에 적혀 있는 알파벳 (즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다) 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구해라 (좌측 상단의 칸 포함) [입력] : 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다 (1 ≤ R,C ≤ 20) : 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳 [출력] : 첫째 줄에 트리의 지름을 출력 [과정] 탐색하자 → 브루트.. 2024. 8. 6. [백준] 15686번 치킨 배달 JAVA (자바) 풀이 문제 15686번 (백트래킹, 브루트포스) : 크기가 N×N인 도시 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나 : 사람들은 "치킨 거리"라는 말을 주로 사용 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리 각각의 집은 치킨 거리를 가지고 있고 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 거리는 |r1-r2| + |c1-c2|로 구한다 : 0은 빈 칸, 1은 집, 2는 치킨집 이 도시에 있는 치킨집은 모두 같은 프랜차이즈이며 일부 치킨집을 폐업시키려고 한다 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개 나머지 치킨집은 모두 폐업시켜야 한다 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성 .. 2024. 8. 3. [백준] 2529번 부등호 JAVA (자바) 풀이 문제 2529번 (백트래킹) : 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다 부등호 기호 앞 뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다 : 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있다 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다 [입력] : 첫 줄에 부등호 문자의 개수 정수 k : 그 다음 줄에는 k개의 부등호 기호 (k의 범위는 2 ≤ k ≤ 9) [출력] : k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력 (첫 자리가 0인 경우도 정수에 포함) [과정] 탐색하자 → 브루트.. 2024. 6. 25. 탐색 알고리즘 (브루트포스, DFS, BFS, 백트래킹) 탐색데이터 구조 내에서 가능한 경우의 수를 탐색해 최적의 결과를 찾는 방법선형 탐색 알고리즘 순차적 탐색이진 탐색비선형 탐색 알고리즘트리나 그래프 같이 복잡한 형태에 사용dfs / bfs 1. 브루트 포스완전 탐색모든 경우의 수 탐색단순하지만 경우의 수가 많아서 비효율적일 수 있다 2. DFS 깊이 우선 탐색그래프 또는 트리에서 모든 경로 탐색한 방향으로 깊숙이 노드 탐색 후 더이상 갈 곳이 없으면 다른 방향 탐색스택 / 재귀 함수 사용 3. 백트래킹DFS의 확장 개념해결 가능성 없는 경로일 경우 탐색 중지하고 되돌아가 다른 경로 탐색 4. BFS 너비 우선 탐색시작 노드에서 가까운 노드부터 탐색같은 깊이 층의 노드들 모두 탐색 후 층 내려가면서 탐색큐 함수 사용최단 경로 문제 알고리즘 선택 가이드 ▣.. 2024. 4. 30. 이전 1 다음
