★Word Search★
★ 나중에 다시 풀어봐야 할 문제 ★
접근 방법 [필수 작성]
제약 조건 확인
- 최대 6x6 matrix → 전체 36개 원소 & tree depth 최대 15
- 시간복잡도 어떻게 계산? → 그냥 경험적으로 제약조건 숫자가 작으니 완전탐색으로 풀 수 있을것이다 라고 예상하는 것인가? → Q1
강의에서 나온 기본 재귀 구조를 활용
def backtrack():
a.append()
backtrack()
a.pop()Grid Search 에 필요한 자료구조 활용
dx = [1,0,-1,0]
dy = [0,1,0,-1]
visited = [[False for _ in range(len(board[0]))] for _ in range(len(board))]코드 구현 [필수 작성]
# 6시55분 시작 -> 8시 끝
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m,n = len(board[0]),len(board)
visited = [[False for _ in range(m)] for _ in range(n)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
#curr = ''
flag = False
def in_range(ny,nx):
if 0 <= ny < n and 0 <= nx < m:
return True
else:
return False
def backtrack(y,x,pointer,visited):
#nonlocal curr
nonlocal flag
if not visited[y][x] and board[y][x] == word[pointer]: #basecase
if pointer == len(word)-1:
flag = True
return
visited[y][x] = True
#curr += board[y][x]
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if in_range(ny,nx):
backtrack(ny,nx,pointer+1,visited)
visited[y][x] = False
#curr = curr[:-1]
for y in range(n):
for x in range(m):
backtrack(y,x,0,visited)
return flag
배우게 된 점 [ 필수 X ]
맨 처음에는 flag 가 왜 필요한 지에 대해서 직관적으로 이해가 가지 않았다. 그러나 문제를 풀면서 재귀함수 특성상 재귀를 돌다 보면 조건을 만족했을 때 특정 시점의 정보를 저장하기 까다롭다는 점을 알았다. 그래서 nonlocal 변수로 flag 를 빼주는 선택을 하였다. 또한, DFS 랑 다를게 없는 재귀함수를 활용한 Grid Search 문제이지만, 재귀+Grid 문제를 오랜만에 풀다보니 해설코드를 많이 참고하였다. 반복학습 및 체화를 통해 해설코드 없이 혼자서 풀 수 있는 힘을 길러야한다.
질문 [ 필수 X ]
Q1
시간복잡도 어떻게 계산? → 그냥 경험적으로 제약조건 숫자가 작으니 완전탐색으로 풀 수 있을것이다 라고 예상하는 것인가?
Q2
문제를 풀기 전, 해설코드의 flag 의 필요성에 대해서 의구심을 가졌었습니다. 문제를 풀면서 flag 의 필요성에 대해서 알게되었고, 해설코드에서 활용한 함수의 결과값으로 flag를 받지 않고 nonlocal 변수로 flag 를 저장하였습니다. 가독성 관점에서 제 코드가 더 괜찮을 건 같은데, nonlocal 변수로 flag 를 받는데 혹시 모를 위험성이 있을지, 해설코드와 다르게 nonlocal 로 빼준 아이디어에 대해서 어떻게 생각하는지 여쭙고 싶습니다.
피드백 [ 코치 작성 ]
재귀 함수의 시간 복잡도는 언제나 계산하기 어렵습니다. 하지만 big-O 표기법의 정의를 통해 실제 실행시간과의 편차가 크더라도 실행시간 보다 더 큰 수식이라면 big-O표기법을 사용할 수 있습니다.(f(n) = n^2일 때 f(n) = O(n^2)이지만 O(n^3) 또한 성립합니다.) 그렇기에 실제 실행에서 최악을 가정하고 계산을 하는 과정을 통해 시간 복잡도를 계산할 수 있습니다.
해당 문제의 최악의 조건은 6*6 이차원 리스트에서 모든 칸을 백트래킹 했을때 마지막에 결과가 나오는 경우 입니다. 즉 36개의 칸에서 백트래킹을 모두 수행하는 것입니다. 또한 재귀 함수가 실행될 때 한개의 칸에서 나아갈 수 있는 경우의 수는 3개입니다.(처음에 중앙에서 시작하는 경우 4개의 경우의 수가 존재하지만 이는 제외하겠습니다. 엄밀하게 계산하고 싶다면 첫 시작의 경우는 따로 *4로 배제한 후 계산하면 됩니다.) 문자열의 최대 길이는 15이며 이를 전부 고려하면 36 * 3^14로 10^8 범위와 유사하게 나타납니다. 그렇기에 시간 복잡도는 O(m*n*3^s)로 표현할 수 있습니다. -> 재귀함수 시간복잡도 계산하는 직관적인 방법 예시flag는 말씀해 주신 대로 필수적인 코드가 아닙니다. flag를 사용하지 않고 조건이 확인되는 즉시 return True를 함을 통해 해결할 수도 있고 동연님의 의견과 같이 nonlocal 변수로 저장할 수도 있습니다. 이는 코드 구현상의 개개인의 사고 방식 및 습관에 따라 달라질 수 있는 구현의 영역이며 해설 코드는 수강생 분들의 이해를 돕기 위해 최적화된 코드가 아닐지라도 보다 이해를 쉽게 하실 수 있도록 고려하여 작성되었습니다.(이 word search 문제 또한 약간의 전처리 작업을 거치면 실행 시간을 크게 줄일 수 있습니다.)
한가지 이야기드리고 싶은 내용은 nonlocal 변수에 대한 내용입니다. nonlocal은 선언 시 파이썬 영역에서 block scope를 생성하게 되며 이는 다른 작업들 보다 소요가 큰 작업입니다. 또한 예상치 못한 결과를 초래할 수 있는 문법이기에 선호되는 문법은 아닙니다. 하지만 이와 같은 설명은 일반적으로 프로젝트에 대한 내용이며 코딩 테스트에 큰 영향은 미치지 않기에 주의해서 사용하시면 될 것 같습니다.
