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라고 생각해요.

[DaleSeo]

스터디 4기 이번 주에 Word Search 문제가 있어서 답안 코드를 리뷰하다가 갑자기 이 논의가 생각이 났어요. 스터디 3기 때와 비슷하게 역시 대부분의 참여자 분들께서 O(m * n * 4^w)로 시간 복잡도 분석을 해주셨더라고요. 그래서 제가 천천히 다시 이 문제의 시간 복잡도 분석을 해봤는데, 그 결과를 공유드리고 의견을 듣고 싶습니다.

우선 @obzva 님께서 위에 올려주신 답안 코드의 재귀 함수 내에 로깅을 추가했어요.

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

        def word_search(i, j, idx):
            print("  " * idx + f"{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

그 다음에 좀 극단적인 예로, 모두 "A"로 채워져 있는 보드와 역시 "A"로만 채워져 있는 단어를 인자로 함수를 호출해보았습니다.

Solution().exist(
    [
        ["A", "A", "A", "A"], 
        ["A", "A", "A", "A"], 
        ["A", "A", "A", "A"]
    ], 
    "AAAAAAAAAAAA"
)

그러면 다음과 같이 로그가 찍히는데요. 호출 스택을 관찰해보시면 최대 4번의 재귀 호출이 일어난다는 것을 알 수 있어요. 이러한 경향은 입력 크기를 늘려보면 더 뚜렷히 나타나더라고요.

i=0, j=0, idx=0
  i=-1, j=0, idx=1
  i=1, j=0, idx=1
    i=0, j=0, idx=2
    i=2, j=0, idx=2
      i=1, j=0, idx=3
      i=3, j=0, idx=3
      i=2, j=-1, idx=3
      i=2, j=1, idx=3
        i=1, j=1, idx=4
          i=0, j=1, idx=5
            i=-1, j=1, idx=6
            i=1, j=1, idx=6
            i=0, j=0, idx=6
            i=0, j=2, idx=6
              i=-1, j=2, idx=7
              i=1, j=2, idx=7
                i=0, j=2, idx=8
                i=2, j=2, idx=8
                  i=1, j=2, idx=9
                  i=3, j=2, idx=9
                  i=2, j=1, idx=9
                  i=2, j=3, idx=9
                    i=1, j=3, idx=10
                      i=0, j=3, idx=11
                        i=-1, j=3, idx=12

그래서 많은 분들이 생각하시는 것처럼 이 답안의 시간 복잡도가 O(m * n * 4^w)이 맞지 않나라는 의심이 들었어요. @obzva 님과 @HC-kang 님 말씀처럼 3방향으로만 탐색을 하는 것은 맞지만, 어떤 좌표를 방문했는지 여부가 공짜로 알아내지는 게 아니잖아요? 이 작업 역시 함수 호출이라는 비용을 발생시키기 때문에 그냥 무시할 수 있는 게 아니라는 생각이 들었습니다. 일반적으로 재귀 알고리즘의 시간 복잡도는 호출 스택의 깊이와 그 단계에서 재귀 함수가 몇 번 호출되느냐에 달려있으니까요.

[HC-kang]

오랜만에 예전 논의를 다시 보니 반갑네요!
우선 이 글을 쓰는 시점에서는 이미 캐나다도 1월 1일이 되었겠네요 ㅋㅋ 한해 고생하셨고, 새해 복 많이 받으세요~

아무래도 함수 호출의 비용 지출을 어떻게 생각하느냐에 따른 관점 차이로 정리할수 있을 것 같아요.

1) 호출 자체가 비용이므로 4방향 - O(m * n * 4^w)

• 직전의 위치로 되돌아가는 경우도 함수의 호출 → 스택 프레임 생성 → 검사 → 반환 자체도 이미 비용의 지출임.

2) 의미 있는 경로는 어차피 3방향뿐이므로 3방향 - O(m * n * 3^w)

• 직전의 위치로 되돌아가는 경우에는 early return되므로, 우리가 작성한 코드 실행을 위한 비용(그리고 뒤에 이어지는 후속 탐색 비용)은 지출하지 않음.

지금의 논점과 정확하게 연관된 내용은 아니지만, 관련 자료를 찾아보다가 실효 분기율(Effective Branching Factor)의 개념도 접하게 되었는데요,
실제로는 경로가 대부분 pruning 되기 때문에 훨씬 빠른 성능을 보인다고 하네요.

결론

• 엄격한 의미론적 Upper bound: O(m * n * 4^w)
• 문제에 명시된 제약조건에서 추론할 수 있는 Upper bound: O(m * n * 3^w)
• 실제 체감되는(실효 분기에 따른) 알고리즘 성능의 Upper bound: O(m * n * (1~2)^w)

오늘도 달레님 덕분에 다시 한 번 깊이있는 내용까지 고민해보게 됐네요. 감사합니다!

[DaleSeo]

@HC-kang 와, 실효 분기율은 또 뭔가요? 이 쪽도 파다보면 끝이 없군요! 😳

수학적으로 더 깊이 들어가기 전에 한 가지 생각해볼 부분은 현실적으로 코딩 테스트의 관점에서 어느 수준의 복잡도 분석을 기대하느냐인데요. 저는 실제 코딩 테스트에서 이 정도까지 엄밀하고 섬세한 복잡도 분석을 요하지는 않는다고 봐요. 설사 지원자가 이 수준의 복잡도 분석을 제공했을 때 면접관이 제대로 이해하지 못하여 전혀 어필이 안 될 수도 있고 오히려 면접관과 불필요한 논쟁의 여지를 남길 수 있다고 생각합니다.

그래서 저는 이 풀이의 경우 O(m * n * 4^w)로 답변하는 게 적어도 제일 무난하고 현실적이며 안전한 복잡도 분석이 아닌가 하는 생각이 듭니다.

[obzva]

@HC-kang @DaleSeo 좋은 분석 해주셔서 감사합니다
우선 달레님 의견에도 동의합니다 :)

1. 의미 없는 돌다리더라도 두드려보는 비용을 포함시켜야 된다 <- 맞습니다, 비용이 적더라도 들어간 비용은 비용이니까요
2. 코딩 테스트의 관점에서 O(m * n * 4^w)이 현실적인 답변이다 <- 불필요한 논쟁의 여지를 남길 수도 있다는 부분에 동의합니다
   그럼에도 불구하고 여전히 마음에 걸리는 점은, '유의미한 경로에 대한 후속 연산과 의미 없는 경로에 대한 호출이 둘을 동일한 연산으로 보는 것이 합당한가' 입니다
   저는 이 부분에 있어서 희찬님이 분석해주신 1, 2안 둘 다 make sense하는 의견같아요

[obzva]

한 편으로 드는 생각은, 달레님께서는 Worst Case에 대한 관점을 설명하고 계시고 저는 Average(or Effective) Case에 대한 설명을 하려다 보니 의견이 좀 안 맞는 부분이 있는 것 같다는 것입니다

Big O notation이 Upper Bound를 설명하는 개념이긴 하지만, 우리는 Worst Case와 Average Case의 차이가 유의미하다고 판단될 경우 그 둘을 분리해서 설명하잖아요?

그런데 차이가 유의미하다 <- 이 부분을 판단하는게 좀 주관적이라 저는 분리해서 봐야한다고 생각하는 것 같고, 달레님은 그게 아니신 것 같다고 생각하시는 것 같아요