BackTracking14 [Leetcode] 51. N-Queens 문제 : https://leetcode.com/problems/n-queens/ 두 개의 퀸이 서로 공격하지 않도록 n x n 체스판에 n개의 퀸을 배치하라. 가능한 모든 경우의 체스판 형태를 반환하라. (Q : 퀸, . : 빈칸) (참고로 퀸은 한 번 움직일 때 앞, 뒤, 옆, 대각선 어떤 방향이든 원하는 만큼 이동 가능) 백트래킹으로 풀었다. 퀸은 앞, 뒤, 옆, 대각선 방향을 원하는 만큼 이동 가능하기 때문에 row, col, 대각선에 놓을 수 있는지 여부를 저장해야 한다. 백트래킹 구현 시 하나의 행에 퀸을 두는 경우의 수를 판단한다고 하면 하나의 행에는 하나의 퀸만 놓게 구현하면 row 에 퀸을 놓을 수 있는지 여부는 저장을 하지 않아도 된다. 열의 퀸 저장가능 여부는 n 크기의 boolean .. 2022. 6. 4. [leetcode] 131. Palindrome Partitioning 문제 : https://leetcode.com/problems/palindrome-partitioning/ 문자열 s가 입력으로 주어지면 파티션의 모든 하위 문자열이 palidrome 이 되도록 하는 모든 경우를 구하라. 문자열을 앞뒤로 읽었을 때 같은 문자열인 경우 palidrome이라 한다. DP + backtracking 팰린드롬인지 구하는 함수. DP // dp[s][e] = str[s ~ e]가 palidrome인지 fun isPalidrome(str, s, e) { if(dp[s][e]가 없으면) dp[s][e] = str[s]와 str[e]가 같은 문자이며 isPalidrome(str, s+1, s-1) 인 경우 return dp[s][e]; } 팰린드롬 하위 문자열들을 만들어서 partit.. 2022. 1. 6. [Leetcode] 77. Combinations 문제 : https://leetcode.com/problems/combinations/ 백트래킹 문제. for(i = 현재 탐색중인 인덱스 ~ n){ arr 배열 뒤에 i 추가 재귀함수(i+1, arr); // 인덱스를 i+1부터 다시 탐색 arr 배열 뒤에 i 제거 } 위와 같은 재귀함수를 만들어서 arr 배열 크기가 k라면 정답 배열에 arr을 추가한다. 시간복잡도는 K크기의 배열을 만들므로 대충 O(N! / (N-K)!) 이 정도 나올듯. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/77.%20Combinations.cpp 2021. 11. 10. [Leetcode] 980. Unique Paths III 문제 : https://leetcode.com/problems/unique-paths-iii/ m x n 정수형 배열 grid가 주어진다. 1 : 시작 지점. (1개 존재) 2 : 종료 지점. (1개 존재) 0 : 걸을 수 있는 곳 -1 : 장애물 상하좌우 4방향으로 이동가능할 때, 시작지점에서 종료지점으로 갈 수 있는 방법의 수를 구하라. 백트래킹. 시작지점부터 장애물이 아닌 곳으로 이동하면서 이동횟수를 저장하면서 상하좌우 방향으로 탐색한다. 탐색하면서 지나간 자리는 다시 못 지나가게 별도의 플래그 배열에 탐색한 위치는 표시를 해둔다. 종료지점에 도달했을 때, 걸음의 수가 grid 배열의 0, 2 cell의 수와 같다면 정답이 가능하므로 정답 방법의 수에 1을 더한다. 시간복잡도는..? 소스코드 : h.. 2021. 11. 2. [Leetcode] 437. Path Sum III 문제 : https://leetcode.com/problems/path-sum-iii/ 이진 트리와 targetSum이 주어지면 경로의 노드들 값의 합이 targetSum과 같은 경로들의 수를 구하라. 백트래킹. 트리를 탐색하면서 탐색한 노드들의 val의 합의 개수를 map에 저장한다. 탐색하면서 이때까지의 합(sum)에서 targetSum을 뺀 값의 개수들의 합이 정답이 된다. [그림 1]에서는 테이블들의 빨간색 셸들이 이에 해당하여 정답은 3이 된다. 시간복잡도는 O(N). N = 노드 수 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/437.%20Path%20Sum%20III.cpp 2021. 10. 18. [leetcode] 113. Path Sum II 문제 : https://leetcode.com/problems/path-sum-ii/ 정수로 이루어진 이진트리와 targetSum이 주어질때, 루트에서 리프노드까지 경로의 노드들의 합이 targetSum과 같은 경로들을 구하여라. 백트래킹으로 경로들을 저장하면서 루트에서 리프노드에 도달할 때까지의 경로들의 합을 구한다. 리프노드에 도달했을때 합이 targetSum인 경우 정답 배열에 저장한다. 시간복잡도는 O(N). N = 트리의 노드 개수 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/113.%20Path%20Sum%20II.cpp 2021. 8. 4. 이전 1 2 3 다음
