Backtracking 썸네일형 리스트형 [백준 9663] N-Queen (Java) https://www.acmicpc.net/problem/9663 접근 방법 1차원 배열을 만들어 행은 인덱스에 열은 해당 행의 번째에 배열의 값으로 들어가게 하였다. (예를 들어, 1행 3열이면 positoins[1] = 3) 백트래킹 알고리즘을 통해 1 -> N행으로 depth를 넘어가면서 조건을 통과하는 경우 다음 깊이로 재귀하도록 구현했다. 다음 깊이로 재귀하는 조건과 구현 방법은 다음과 같다 1. 이미 같은 열에 퀸이 놓여있지 않은 경우 -> 열을 나타내는 것은 1차 배열의 값이다. 따라서 이전까지의 배열 인덱스를 탐색하면서 값이 존재하지 않으면 조건에 부합하다. 즉, position[i] != number 2. 이미 놓여있는 퀸이 대각선에 있지 않은 경우 -> 대각선에 놓여있는 경우의 기울기는.. [백준 1182] 부분수열의 합 (Java) https://www.acmicpc.net/problem/1182 접근 방법 백트래킹 방법을 이용했다. dfs와 유사하게 깊이 우선으로 탐색을 하되, 조건에 충족하지 않으면 이전 깊이로 돌아가 이어서 진행하는 방식으로 구현하였다. 입력값으로 받은 수열을 배열로 만들고 순차적으로 탐색을 하는데 깊이 들어갈 때 마다 해당 깊이의 값을 포함하고 다음 깊이로 재귀 해당 깊이의 값을 포함하지 않고 다음 깊이로 재귀 를 나누어 탐색하였다. 이 문제에서 조건은 total == S 구현 시 주의해야 할 점은 다음과 같았다. 원소가 하나인 경우도 경우의 수++ (ex. S = 0인 경우, {0}도 해당됨) 마지막 depth까지 가지 않았는데 total == S가 되더라도 경우의 수++하고, 마지막까지 가봐야 함 (또 다.. 이전 1 다음
