알고리즘/백트래킹
-
[백준 1799] - [백트래킹] - 비숍 (JAVA)알고리즘/백트래킹 2018. 12. 26. 17:13
문제 링크 : https://www.acmicpc.net/problem/1799이 문제는 이전에 풀었던 N-Queen 문제의 확장판 문제이다. 2018/11/21 - [알고리즘/백트래킹] - [백준-9663]-[백트래킹] - N-Queen 그리고 백트래킹 문제의 최고존엄 문제 급이지 않을까 생각한다. 이 문제를 잘못 접근하게 되면 문제는 풀겠지만 시간 초과에 걸리게 된다. 잘못접근하는 대부분의 이슈는 하나의 체스판을 전체 탐색을 할경우 생기게 된다. 비숍은 대각선으로 움직인다. 그렇다면 대각선에는 비숍이 위치할 수 없다. 아래처럼 2,2 에 비숍이 위치할 경우 대각선에 위치한 모든 좌표에는 비숍을 놓을 수 없다. B 또 여기서 하나 중요하게 고려해야할게 있는데 2, 2에 비숍을 놓았을경우 비숍의 좌표 기..
-
[백준 2661] - [백트래킹] - 좋은 수열 (JAVA)알고리즘/백트래킹 2018. 12. 26. 16:13
문제링크 : https://www.acmicpc.net/problem/2661 이 문제는 아주 쉽게 백트래킹으로 접근 할 수 있다. 모든 경우의 수를 탐색하면서 조건에 성립되면 결과를 출력하면 된다. 이 문제에서 제시하는 조건은 다음과 같다.임의의 길이의 인접한 두 개의 부분 수열이 동일하지 않아야 한다. (나쁜 수열이면 안된다.)나올 수 있는 좋은 수열 중에서 가장 작은 수를 출력해야 한다. 첫번째 조건을 확인하는 함수 하나를 만들고 두번째 조건은 첫번째로 좋은 수열이 나온 좋은 수열이 제일 작은 수열이기 때문에 좋은 수열이 나오면 모든 탐색을 종료 시키면 되기 때문에 따로 조건을 확인하는 함수를 만들 필요는 없다. 좋은 수열인지 확인하는 함수는 아래와 같이 만들었다. public static bool..
-
[백준 1759] - [백트래킹] - 암호 만들기 (JAVA)알고리즘/백트래킹 2018. 12. 26. 15:19
문제 링크 : https://www.acmicpc.net/problem/1759 이 문제는 백트래킹으로 쉽게 접근 할 수 있다. 이전에 풀었던 백트래킹 문제들을 하나씩 풀어본다면 아주 쉽게 코드를 작성 할 수 있다. 모든 경우에 수를 전부 탐색하면서 문제에서 제시한 3가지 조건을 만족 시키는 경우 생성된 암호를 출력 해주고 다시 다른 경우의 수를 탐색하면 된다. 이전에 풀었던 백트래킹 문제를 기억해가면서 풀어보니 정말 쉽게 문제를 풀 수 있었다. 만약 기억이 안난다면 다른 백트래킹 문제를 풀어보면서 접근해보면 좋을듯 하다. 백트래킹 관련 글 2018/11/21 - [알고리즘/백트래킹] - [백준-9663]-[백트래킹] - N-Queen2018/11/23 - [알고리즘/백트래킹] - [백준-1987]-[D..
-
[백준 6603] - [백트래킹] - 로또 (JAVA)알고리즘/백트래킹 2018. 12. 26. 14:08
문제 링크 : https://www.acmicpc.net/problem/6603 이 문제는 백트래킹으로 접근 하면 되는 문제다. 백트래킹은 모든 경우의 수를 탐색을 진행 할때 탐색을 한 후에 다시 값을 탐색하기 이전으로 되돌리는 형태의 알고리즘 이다. 이 문제는 그럼 어떻게 접근을 해야 할까? 주어진 k 개의 원소 중에서 하나씩 뽑아서 로또 번호를 생성하면 된다. 한번 로또 번호에 사용된 원소는 다시 사용 될 수 없기 때문에 i 번째 원소가 로또 번호로 생성 됐다면 그 다음 로또번호는 i+1 부터 k-1 번 째 원소가 될 수 있다. 예를 들어 k 는 7 이고 원소들의 집합으로 {1, 2, 3, 4, 5, 6, 7} 을 입력 받은 상태에서 { 1, 2, 3} 까지 로또 번호를 생성 했다면 그 다음 로또 번..
-
[백준 2580] - [백트래킹] - 스도쿠알고리즘/백트래킹 2018. 12. 21. 17:58
문제링크 : https://www.acmicpc.net/problem/2580 이문제는 백트래킹으로 접근 할 수 있는 문제이다. 예전에 풀었던 N-Queen 문제도 백트래킹이었는데 간단하게 설명하자면 현재 인덱스에 값을 넣어보고 다음 탐색을 돌린다. 다시 현재 인덱스에는 값을 초기화 시킨다. arr[y][x] = i; backtracking(idx+1, cnt+1); arr[y][x] = 0; 위에 소스처럼 백트래킹을 진행하는데 이렇게 하면 결국엔 다 초기화 되는거 아냐?? 하겠지만 잘 생각해보면 그렇지 않다. 최종 arr의 값은 당연히 초기 탐색할때의 값이 되겠지만 탐색을 하는 도중에 맞는 결과가 나왔을거고 맞는 결과가 나왔을때 배열을 바로 출력을 했다. 이해가 안된다면 백트래킹에 대한 설명 N-Que..
-
[백준-1987]-[DFS-백트래킹]-알파벳알고리즘/백트래킹 2018. 11. 23. 02:38
문제링크 : https://www.acmicpc.net/problem/1987 이문제를 어떻게 접근할까 하다가 간단하겠지 하고 BFS로 풀었는데 절대 BFS풀면 안된다더라..그 이유는 동시에 같은 레벨의 다른 접점을 접근하기 때문에 만약 2레벨의 같은 알파벳이 있으면 방문 여부를 파악하기가 힘들다. 백트래킹으로 가능한 모든 방향을 접근하고 지나간 최대 칸수를 출력해주면 된다. 말이 쉽지 참 힘들었다. 예제는 항상 답이 나오는데 제출을 하면 항상 문제였다. 내가 푼 문제에 반례가 어떤게 있을까 하다가 스스로 예제를 만들어 보았다. 이것만 통과하면 제출해도 정답이 나올거 같다.. 내가 생각해낸 예제는 아래 표다. A B B C EC E D FG D H 만약 단순한 DFS만으로 결과를 도출해낸다면 최대 길이는..
-
[백준-9663]-[백트래킹] - N-Queen알고리즘/백트래킹 2018. 11. 21. 18:00
문제 링크 : https://www.acmicpc.net/problem/9663 이 문제는 백트래킹 알고리즘의 기본적인 예제라고 한다. 백트래킹 알고리즘은 그리디 알고리즘과 모든 가능성을 조회하고 조회 한 값으로 결과를 구한다는 비슷한 성질을 가진다. 차이점은 그리디 알고리즘은 정말 모든 가능성을 조회하지만 백 트래킹의 경우는 다음경우가 유효한 경우가 아니면 진행하지 않는다. 그런 개념을 이해할 수 있는 문제가 N-Queen 문제인거 같다. 이 문제는 퀸을 N x N 체스 판에 N 개만큼 위치 시킬 수 있는 경우의 수가 얼마만큼 있는지 구하는 문제이다. 예로 4 x 4 체스판에 (1, 2) 위치에 퀸이 놓여져 있다고 가정하면 (1번 인덱스가 제일 앞 인덱스라 할 때) Q 위의 빨간색인 부분에는 퀸을 놓을..