[파이썬 기초] 알고리즘의 개념 / 코딩 연습 - 예제 1(팔린드롬)

#1. 알고리즘 : 어떤 문제를 해결하기 위한 자세한 방법

컴퓨터 알고리즘 : 컴퓨터가 어떤 문제를 해결하기 위해 컴퓨터가 이해할 수 있는 방식으로 정리되어 있는 해결 방법

길찾기 서비스, 영화 추천서비스 등은 모두 알고리즘에 기반함

 

코드잇 예제풀이(팔린드롬 문제) : 문자열 word가 팔린드롬인지 확인하는 함수 is_palindrome을 정의하여 True / False를 리턴

 

Hint 1 : 문자열의 첫 번째 원소와 마지막 원소, 두번째 원소와 뒤에서 두번째 원소~의 쌍을 만들어, 이 쌍들이 서로 일치하는지 확인하도록 만든다. → 한 쌍이라도 불일치하면 False, 모두 일치하면 True가 되도록 하면 됨

문자열 word의 첫 번째 원소 = "word"[0] = "w"

문자열 word의 마지막 번째 원소(뒤에서 첫 번째 원소) = "word"[len("word")-1] = "word"[3] = "d"가 된다. (len("word") = 4 이므로)

→ 문자열 word의 i번째 원소 = "word"[i-1]

    문자열 word의 뒤에서 i번째 원소 = "word"[len("word")-i]

 

Hint 2 : 문자열의 i번째 원소와 뒤에서 i번째 원소의 쌍이 일치하는지 확인하려면..? 둘의 합을 기준으로 수식을 만들어 확인할 수 있다. 

→ 문자열이 "abcdefg"라면, "abcdefg"[0] = a, "abcdefg"[6] = "abcdefg"[len("abcdefg")-1]=g 이다.

문자열 word의 i번째 원소와 뒤에서 i번째 원소의 쌍이 일치한다면,

"word"[i-1] = "word"[len("word")-i] 이고, i자리에 i+1이 들어가면 "word"[i] = "word"[len("word")-i-1] 이 된다.

쌍이 되는 문자의 인덱스를 더하면 len("word")-1이 된다.

 

Hint 3 : For 반복문을 사용하는데, 어디까지 반복할까를 생각해보고 반복문 설정한다. : 한쪽(왼쪽,시작점)이 2로 나눈 몫되는 범위까지 반복(문자열 개수가 홀수라면 가운데 문자에 대해서는 반복할 필요 없으므로)

 

==========================================================================

 

def is_palindrome(word) :

     for left in range(len(word) // 2) :                                                    ------------ Hint 3

          # 한 쌍이라도 일치하지 않으면 바로 False를 리턴하고 함수를 끝냄

     right = len(word) - left - 1                                                           ------------ Hint 1,2

     if word[left] != word[right]:

        return False

 

    # for문에서 나왔다면 모든 쌍이 일치

    return True

 

print(is_palindrome("racecar"))
print(is_palindrome("stars"))
print(is_palindrome("토마토"))
print(is_palindrome("kayak"))
print(is_palindrome("hello"))

결과 :

 

True

False

True

True

False

 

==========================================================================

 

궁금증 : 왜 수식에서는 palindrome("word")나 len("word")가 아닌 palindrome(word)와 len(word)를 쓸까..?