알고리즘
-
[Algorithm] 델타 탐색 - PythonAlgorithm 2023. 11. 7. 17:17
2차원 배열의 한 좌표에서 4방향(또는 8방향 등 원하는 방향)의 인접 배열 요소를 탐색하는 방법 arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # 상하좌우 방향 제시 delta_row = [-1, 1, 0, 0] delta_col = [0, 0, -1, 1] #[0][0]=위 [1][1]=아래 [2][2]=오른쪽 [3][3]=왼쪽 # 상하좌우 한번에 할당 delta_row_col = [[-1, 0], [1, 0], [0, -1], [0, 1]] # 2(0, 1)의 위치를 기준 r = 0 c = 1 for i in range(4): next_row = r + delta_row[i] #위치 인덱스 찾기 next_col = c + delta_col[i] N = len(arr) #..
-
[Algorithm] 백트래킹(backtracking)Algorithm 2023. 11. 7. 17:15
백트래킹(backtracking)이란? 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다. 어떤 문제를 푸는데 있어 모든 경우의 수를 시도하여 문제의 정답을 찾아나간다. 하지만 백트래킹에서는 한정조건에서의 모든 경우의 수를 시도하는 것이기 때문에 실제로 상당한 경우의 수들이 배제되기 때문에 단순 다중 for문 보다는 빠르게 해결되는 경우가 많다. 즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다. 주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이..