[한기대] 순열 알고리즘 과제 => 알고리즘의 중요성 파악 가능!

한기대에 다니는 동생이 알고리즘 문제를 물어봐서 내 방식대로 푼 것과 동생이 교재를 보고 푼 것을 비교하면서 어떤 알고리즘이 더 좋은지 공부해 봤다.

문제

DFS(Depth First Search)에서 출발하는 Back­Track­ing 을 확인학습하기 위해,
주어진 문자열 내의 문자들을 재배열 할 수 있는 모든 경우의 수를 출력하는 알고리즘을 재귀함수로 작성해 보자.
다음과 같은 결과가 나오면 된다.

일단 동생이 짠 코드는 다음과 같다.

start = time.time()
def reArrange(text,prev_str):
    if len(text) == 0:
        print(prev_str)
    for i in text: 
        next_str = text
        next_str = next_str.replace(i,'')
        prev_str = prev_str+i
        reArrange(next_str, prev_str)        
        prev_str = prev_str.replace(i, '')
text = input("단어 입력>> ")
reArrange(text,"")
print(f"{time.time()-start:.4f} sec")

이 알고리즘을 그림으로 그리면 다음과 같다.

나는 이 문제를 처음 받았을 때 다음과 같이 풀었다.

start = time.time()
def reArrange(text,prev_str):
    if len(text) == 0:
        print(prev_str)
    for i in text: 
        next_str = text
        next_str = next_str.replace(i,'')
        prev_str = prev_str+i
        reArrange(next_str, prev_str)        
        prev_str = prev_str.replace(i, '')
text = input("단어 입력>> ")
reArrange(text,"")
print(f"{time.time()-start:.4f} sec")

코드를 보면 알 수 있듯이, 동생이 짠 코드가 훨씬 간결하다. 그리고 훨씬 더 빠르다.
나의 경우 이 모든 연산을 처리하는 속도가 21초 걸렸다.
반면에, 동생의 코드는 2초면 연산이 끝났다.
무려 10배나 빠른 속도의 동생이 짠 코드가 작동한 것이다!!!!
이럴 수가.…

이것을 보면 우리가 왜 알고리즘이라는 학문을 알아야 하고 익숙해져야 하는지 알 수 있다.
특히나 트리를 이용한 문제들은 어떤 상황에서 빠르게 연산을 할 수 있는지
정확하게 알고 있어야 한다.

만약 트리를 벗어나는 알고리즘은 그때 가서 공부해도 늦지 않았다.
이것으로 우리가 왜 알고리즘 학문을 소중히 해야 하는지 다시 한번 알게 되었다.