2.4. An Anagram Detaction Example

이 문서는 영문으로된 내용을 구글 번역기를 활용하여 번역한 내용입니다. 
개인적인 공부 및 추후 다시 볼 수 있도록 하기 위해 개인 블로그에 번역 내용을 옮겨 놓았습니다.
원문과 내용이 다를시 책임지지 않으며, 저작권 문제가 발생시 언제든 삭제 될 수 있습니다. 

Problem Solving with Algorithms and Data Structures using Python by Bradley N. Miller, David L. Ranum is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. 

서로 다른 차수의 알고리즘 표시에 대한 좋은 예는 문자열에 대한 고전적인 아나그램(anagram) 검색 문제입니다. 하나의 문자열은 두 번째 문자열이 단순히 첫 번째 문자열의 재배치일 경우 다른 문자열의 아나그램입니다. 예를 들어, 'heart'과 'earth'는 아나그램입니다. 문자열 'python'과 'typhon'도 아나그램입니다. 단순화를 위해, 문제의 두 문자열이 동일한 길이이고 26 개의 소문자 알파벳 문자 세트로 된 기호로 구성된다고 가정합니다. 우리의 목표는 두 개의 문자열을 받아서 아나그램인지를 반환하는 부울 함수를 작성하는 것입니다.

2.4.1. Solution 1: Checking Off

아나그램 문제에 대한 우리의 첫 번째 해결책은 첫 번째 문자열의 각 문자가 실제로 두 번째 문자열에서 발생하는지 확인합니다. 각 문자를 “확인(checkoff)"할 수 있다면 두 문자열은 아나그램이어야합니다. 문자를 확인하는 것은 특수 파이썬 값 None으로 대체하여 수행됩니다. 그러나 파이썬의 문자열은 불변이므로 이 과정의 첫 번째 단계는 두 번째 문자열을 목록으로 변환하는 것입니다. 첫 번째 문자열의 각 문자는 목록의 문자와 비교하여 확인할 수 있으며, 발견되면 교체로 선택합니다. ActiveCode 1은 이 기능을 보여줍니다.

RunLoad HistoryShow CodeLens

1

def anagramSolution1(s1,s2):

2

    alist = list(s2)

3

4

    pos1 = 0

5

    stillOK = True

6

7

    while pos1 < len(s1) and stillOK:

8

        pos2 = 0

9

        found = False

10

        while pos2 < len(alist) and not found:

11

            if s1[pos1] == alist[pos2]:

12

                found = True

13

            else:

14

                pos2 = pos2 + 1

15

16

        if found:

17

            alist[pos2] = None

18

        else:

19

            stillOK = False

20

21

        pos1 = pos1 + 1

22

23

    return stillOK

24

25

print(anagramSolution1('abcd','dcba'))

26

Checking Off (active5)

이 알고리즘을 분석하기 위해, s1의 n 문자 각각은 s2의 목록에서 최대 n 문자를 반복 할 수 있습니다. 목록의 n 위치는 각각 s1의 문자와 일치하도록 한 번 방문됩니다. 방문수는 1에서 n까지의 정수의 합이됩니다. 앞서 우리는 이것을 다음과 같이 쓸 수 있다고 말했습니다.

n이 커지면 n2 항이 n 항을 지배하게되고 1/2은 무시 될 수 있습니다. 따라서,이 해는 O(n2)입니다.

2.4.2. Solution 2: Sort and Compare

아나그램 문제에 대한 또 다른 해법은 비록 s1과 s2가 다르더라도 똑같은 문자로만 구성된 경우에만 아나그램이라는 사실을 이용합니다. 따라서 각 문자열을 알파벳순으로, a에서 z로 정렬하면 원래 두 문자열이 아나그램 인 경우 동일한 문자열로 끝납니다. ActiveCode 2는 이 솔루션을 보여줍니다. 다시 말하지만, 파이썬에서는 처음에 각 문자열을 목록으로 변환하여 목록에 내장 된 정렬(sort) 방법을 사용할 수 있습니다.

RunLoad HistoryShow CodeLens

1

def anagramSolution2(s1,s2):

2

    alist1 = list(s1)

3

    alist2 = list(s2)

4

5

    alist1.sort()

6

    alist2.sort()

7

8

    pos = 0

9

    matches = True

10

11

    while pos < len(s1) and matches:

12

        if alist1[pos]==alist2[pos]:

13

            pos = pos + 1

14

        else:

15

            matches = False

16

17

    return matches

18

19

print(anagramSolution2('abcde','edcba'))

20

Sort and Compare (active6)

At first glance you may be tempted to think that this algorithm is O(n), since there is one simple iteration to compare the n characters after the sorting process. However, the two calls to the Python sort method are not without their own cost. As we will see in a later chapter, sorting is typically either O(n2) or O(nlogn), so the sorting operations dominate the iteration. In the end, this algorithm will have the same order of magnitude as that of the sorting process.

얼핏보기에 이 알고리즘이 O(n)라고 생각하고 싶을지도 모릅니다. 왜냐하면 정렬 과정 후에 n 개의 문자를 비교하는 간단한 반복이 있기 때문입니다. 그러나 파이썬 정렬 메소드에 대한 두 번의 호출은 비용이 들지 않습니다. 이후 장에서 보겠지만, 정렬은 대개 O(n2) 또는 O(nlogn)이므로 정렬 작업이 반복을 지배합니다. 결국이 알고리즘은 정렬 프로세스와 동일한 크기의 순서를 갖게됩니다.

2.4.3. Solution 3: Brute Force

문제를 해결하기위한 무차별 대입(brute force) 기법은 일반적으로 모든 가능성을 고갈하려고 시도합니다. 아나그램 검출 문제의 경우, s1의 문자를 사용하여 가능한 모든 문자열의 목록을 생성한 다음 s2가 발생하는지 확인할 수 있습니다. 그러나 이 방법에는 어려움이 있습니다. s1에서 가능한 모든 문자열을 생성 할 때 가능한 첫 번째 문자, 두 번째 위치에 대해 n−1 가능한 문자, 세 번째 위치에 대해 n−2 등이 있습니다. 후보 문자열의 총 수는 n∗(n−1)∗(n−2)∗...∗3∗2∗1 입니다. 문자열 중 일부가 중복 될 수 있지만 프로그램이 이를 미리 알 수 없으므로 여전히 n!의 다른 문자열을 생성합니다!.

n!은 n이 커질수록 2n보다 빠르게 성장합니다. 사실, s1이 20 자 길이라면, 20!=2,432,902,008,176,640,000 개의 가능한 후보 문자열이 있습니다. 매초마다 한 가지씩 가능성을 처리한다면 전체 목록을 살펴볼 때 77,146,816,596 년이 걸릴 것입니다. 이것은 아마도 좋은 해결책이 될 수 없습니다.

2.4.4. Solution 4: Count and Compare

아나그램 문제에 대한 우리의 최종 솔루션은 두 개의 아나그램이 같은 수의 a, 같은 수의 b, 같은 수의 c 등을 갖게된다는 사실을 이용합니다. 두 문자열이 아나그램인지 여부를 결정하기 위해 먼저 각 문자가 발생하는 횟수를 계산합니다. 26 개의 가능한 문자가 있으므로 가능한 문자마다 하나씩 26 개의 카운터 목록을 사용할 수 있습니다. 특정 캐릭터를 볼 때마다 그 위치에서 카운터를 증가시킵니다. 결국 카운터의 두 목록이 동일하면 문자열이 아나그램이어야합니다. ActiveCode 3은 이 솔루션을 보여줍니다.

RunLoad HistoryShow CodeLens

1

def anagramSolution4(s1,s2):

2

    c1 = [0]*26

3

    c2 = [0]*26

4

5

    for i in range(len(s1)):

6

        pos = ord(s1[i])-ord('a')

7

        c1[pos] = c1[pos] + 1

8

9

    for i in range(len(s2)):

10

        pos = ord(s2[i])-ord('a')

11

        c2[pos] = c2[pos] + 1

12

13

    j = 0

14

    stillOK = True

15

    while j<26 and stillOK:

16

        if c1[j]==c2[j]:

17

            j = j + 1

18

        else:

19

            stillOK = False

20

21

    return stillOK

22

23

print(anagramSolution4('apple','pleap'))

24

Count and Compare (active7)

다시 말하면, 이 솔루션에는 여러 가지 반복이 있습니다. 그러나 첫 번째 솔루션과 달리 중첩 된 솔루션은 없습니다. 문자를 세는 데 사용되는 처음 두 반복은 모두 n을 기반으로 합니다. 두 번째 목록을 비교하는 세 번째 반복은 문자열에 26 개의 가능한 문자가 있기 때문에 항상 26 단계를 필요로합니다. 그것을 모두 더하면 T(n)=2n+26 단계가됩니다. 그것은 O(n)입니다. 우리는 이 문제를 해결하기 위해 선형 차수 알고리즘을 발견했습니다.

이 예제를 떠나기 전에, 우리는 공간 요구 사항에 대해 말할 필요가 있습니다. 마지막 솔루션은 선형 시간 내에 실행될 수 있었지만 추가 저장 장치를 사용하여 두 문자 수 목록을 유지해야 합니다. 즉,이 알고리즘은 시간을 확보하기 위해 공간을 희생했습니다.

이것은 일반적인 경우입니다. 많은 경우에 시간과 공간의 절충 사이에서 결정을 내려야합니다. 이 경우 추가 공간의 크기는 중요하지 않습니다. 그러나 기본 알파벳에 수백만 자의 문자가 포함되어 있다면 더 많은 우려가 있을 수 있습니다. 컴퓨터 과학자로서 알고리즘의 선택이 주어지면 특정 문제가 있는 컴퓨팅 리소스를 최대한 활용할 수 있는지를 결정해야합니다.

Self Check

Q-1: Given the following code fragment, what is its Big-O running time?

test = 0

for i in range(n):

   for j in range(n):

      test = test + i * j

(A) O(n)

(B) O(n^2)

(C) O(log n)

(D) O(n^3)

Check MeCompare me

Q-2: Given the following code fragment what is its Big-O running time?

test = 0

for i in range(n):

   test = test + 1

for j in range(n):

   test = test - 1

(A) O(n)

(B) O(n^2)

(C) O(log n)

(D) O(n^3)

Check MeCompare me

Q-3: Given the following code fragment what is its Big-O running time?

i = n

while i > 0:

   k = 2 + 2

   i = i // 2

(A) O(n)

(B) O(n^2)

(C) O(log n)

(D) O(n^3)

Check MeCompare me