Word Search 문제의 시간 복잡도 분석

[obzva]

Word Search을 DFS 방식을 이용하여 풀 경우의 시간 복잡도에 대해서 이야기 합니다.

4주차 모임에서 Word Search 문제 발표자셨던 @TonyKim9401 님의 python코드입니다.

class Solution(object):
   def exist(self, board, word):
       rows, cols = len(board), len(board[0])
       visit = [[False] * cols for _ in range(rows)]

       def word_search(i, j, idx):
           if idx == len(word):
               return True
           if i < 0 or i >= rows or j < 0 or j >= cols:
               return False
           if board[i][j] != word[idx]:
               return False
           if visit[i][j]:
               return False
           visit[i][j] = True
           next_idx = idx + 1
           if (word_search(i + 1, j, next_idx) or
               word_search(i - 1, j, next_idx) or
               word_search(i, j + 1, next_idx) or
               word_search(i, j - 1, next_idx)
           ):
               return True

           visit[i][j] = False
           return False

       for i in range(rows):
           for j in range(cols):
               if word_search(i, j, 0):
                   return True
       return False

[obzva]

제가 저번주에 했던 이야기의 요지는 아래와 같고, 제가 이해하고 있는 시간복잡도의 개념은 이 글에 설명하였습니다 :D

class Solution(object):
   def exist(self, board, word):
       rows, cols = len(board), len(board[0])
       visit = [[False] * cols for _ in range(rows)]

       def word_search(i, j, idx):
           # word를 찾은 경우 True 반환하며 탈출
           if idx == len(word):
               return True

           # 현재 탐색하려는 좌표에서 False를 반환하는 경우
           # 유의미한 연산을 진행하지 않으므로 시간 복잡도 계산에서 제외되어도 무방하다고 생각함
           if i < 0 or i >= rows or j < 0 or j >= cols:
               return False
           if board[i][j] != word[idx]:
               return False
           if visit[i][j]:
               return False

           # 그 외의 경우엔 word_search 함수를 현재 좌표로부터 3방향으로 재귀 호출
           # 코드 상으로는 4방향으로 호출하는 것처럼 보이지만
           # word_search 첫번째 호출을 제외하면 3방향으로만 재귀 호출한다고 봐야 한다고 생각함
           # 왜냐하면 그 전에 방문했던 좌표는 방문해도 바로 False를 반환하기 때문
           # 따라서 word의 길이 k가 증가함에 따라 재귀 호출의 수는 3^k 꼴로 증가할 것임
           visit[i][j] = True
           next_idx = idx + 1
           if (word_search(i + 1, j, next_idx) or
               word_search(i - 1, j, next_idx) or
               word_search(i, j + 1, next_idx) or
               word_search(i, j - 1, next_idx)
           ):
               return True

           visit[i][j] = False
           return False

       for i in range(rows):
           for j in range(cols):
               if word_search(i, j, 0):
                   return True
       return False

따라서 해당 코드의 실행시간 f(m, n, k)은 다음과 같으며

f(m, n, k) = m * n * 4 * (3^k)

m * n: board의 크기
k: word의 길이

시간 복잡도는 O(m * n * (3^k))라고 생각합니다.

[DaleSeo]

@obzva 님, 우선 복잡도 개념과 Big O 표기법 대해서 따로 정리 해주신 글에 대해서는 이견이 없고요.

       # 그 외의 경우엔 word_search 함수를 현재 좌표로부터 3방향으로 재귀 호출
       # 코드 상으로는 4방향으로 호출하는 것처럼 보이지만
       # word_search 첫번째 호출을 제외하면 3방향으로만 재귀 호출한다고 봐야 한다고 생각함
       # 왜냐하면 그 전에 방문했던 좌표는 방문해도 바로 False를 반환하기 때문
       # 따라서 word의 길이 k가 증가함에 따라 재귀 호출의 수는 3^k 꼴로 증가할 것임

위 설명은 모임 때 해주신 설명과 크게 다르지 않은 느낌인데요?
저는 시각 자료나 수학적인 증명과 같은 좀 더 구체적인 분석을 기대했었습니다! ㅎㅎ

지금 이 설명으로는 명쾌하게 이해가 된다고 보다는 흠... 말 되네? 그렇게 볼 수도 있겠네? 이 수준으로 저는 이해가 됩니다 ㅠㅠ
수학적인 사고가 좀 부족한 멍청한 면접관을 만났다고 생각해보시면 좋을 것 같습니다 :)

P.S. 제가 너무 까다롭게 구는 것 같다면 죄송합니다. @obzva 님도 이런 챌린지를 좋아하시는 것 같아서 ㅋㅋㅋ

[obzva]

ㅎㅎㅎㅎ 저는 이런 이야기 너무 좋습니다
제 기억 상으로 그 때 달레님과 몇몇 분께서 "처음엔 4방향으로 탐색을 시작하지 않느냐"라는 이야기를 하셨던게 생각나서 이 부분에 대해서만 설득하면 된다고 생각했습니다 ㅠㅠ

그래서 처음엔 4방향으로 탐색하지만, 증가율 관점에서는 3의 지수함수 형태로 증가한다는 내용을 전달드리고 싶었어요

[obzva]

구체적인 분석은 좀 더 머리를 굴려보겠습니다 :)

[HC-kang]

이 문제도 면접관과 긴밀한 협의가 필요할 것 같습니다
저도 처음에는 O(m * n * (4^k))로 표기하는것이 맞지 않을까 생각했는데, 좀 더 생각해보고나서는 @obzva 님 말씀대로 O(m * n * (3^k))쪽으로 기울었습니다.. ㅎㅎ

// 0, 1로 이루어진 매우 큰 배열로 가정
const arr = [0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0... ];

function someAlgorithm(arr: number[]): number {
  let result = 0;

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === 1) {
      for (let j = 0; j < arr.length; j++) {
        result += arr[j];
      }
    }
  }
  return result;
}

위 함수는 명확히 O(n^2)의 시간 복잡도를 가지는데요,
만약 arr 내에 1이 하나만 존재하는 희소행렬 형태라면 실제 동작은 O(n)라고 말할 수 있습니다.

이 코드의 경우:

알고리즘 자체는 O(n^2)이지만, 특정 조건을 갖춘 입력에 대해서는 O(n)으로 동작할 수 있습니다.

라는 느낌인 반면, Word Search 문제에서는

알고리즘 코드 내부에 '같은 글자 셀은 한 번만 사용할 수 있다(직전의 셀로 돌아갈 수 없다)'라는 조건이 명확히 구현되어있고, 입력과 무관하게 그렇게 동작합니다.

따라서 입력과 상관없이 탐색의 복잡도는 O(3^k)로 제한됩니다.

이 점에서 보면, O(m * n * (3^k))가 조금 더 정확한 표현이라고 생각합니다.

[obzva]

따라서 입력과 상관없이 탐색의 복잡도는 O(3^k)로 제한됩니다.

제 생각도 동일합니다. 입력값 K가 증가함에 따른 DFS의 시간 복잡도는 O(3^K)가 upper bound라고 생각해요.