[엘카데미 챌린지] 20일차 파이썬 알고리즘 (7)

1. 개요

오늘은 이분 탐색 알고리즘과 회문 찾기 알고리즘을 풀이하였다.

회문(Palindrome)은 앞으로 읽으나 뒤로 읽으나 동일한 단어, 구절, 문장 등을 말한다.

예를 들면 한글로는 토마토, 기러기, 영어로는 madam, wow 등이 있겠다.

점점 생각할거리가 많아지는 문제들이 빈번하게 나타나고 있다.

또 알고리즘을 풀이하는데 사용된 자료구조의 개념을 간단하게 정리하였다.

---

2. 문제

1) 이분 탐색 알고리즘

리스트 a와 비교값인 변수 x를 받아 리스트 a의 원소와 x와 같다면 x를 반환하고 아닐 경우 -1를 반환하는 함수 binary_search를 작성하세요.

 

풀이

1. 중간 위치를 찾는다.
2. 찾는 값과 중간 위치 값을 비교
3. 같다면 원하는 값을 찾은 것이므로 위치 번호를 결괏값으로 반환
4. 찾는 값이 중간 위치 값보다 크다면 중간 위치의 오른쪽을 대상으로 다시 탐색(1번 과정부터 반복).
5. 찾는 값이 중간 위치 값보다 작다면 중간 위치의 왼쪽을 대상으로 다시 탐색(1번 과정부터 반복).

자료의 중간부터 시작해 찾을 값이 더 크면 오른쪽으로, 작으면 왼쪽으로 점프하며 자료를 찾는다. 점프할 때마다 점프 거리는 절반씩 줄어든다.

이분 탐색은 탐색할 자료를 둘로 나누어 찾는 값이 있을 법한 곳만 탐색하기 때문에 자료를 하나하나 찾아야하는 순차 탐색보다 원하는 자료를 훨씬 빨리 찾을 수 있다.

def binary_search(a, x):
    start = 0
    end = len(a) - 1

    while start <= end:
        mid = (start + end) // 2
        if a[mid] == x:
            return mid
        elif a[mid] < x:
            start = mid + 1
        else:
            end = mid - 1

    return -1


d = [1, 4, 9, 16, 25, 36, 49, 64, 81]
print(binary_search(d, 36))  # 출력: 5
print(binary_search(d, 50))  # 출력: -1

---

2) 회문 찾기 알고리즘

문자열이 회문(回文)인지 아닌지 판단하여 회문이면 True, 아니면 False를 결과로 알려주는 알고리즘을 생각해보자.
앞 이론에서 자료 값 1, 2, 3, 4가 들어 있는 큐와 스택에서 차례로 자료를 빼내면 각각 1, 2, 3, 4 와 4, 3, 2, 1 순서로 자료가 나온다고 배웠다. 이것이 바로 회문을 판단하는 데 필요한 큐와 스택의 특징이다.
주어진 문장의 문자들을 하나하나 큐와 스택에 넣은 다음 큐와 스택에서 하나씩 자료를 꺼낸다고 생각해 보자.
큐는 들어간 순서 그대로, 스택은 들어간 순서와 정반대로 문자들이 뽑혀 나온다.
회문은 거꾸로 읽어도 같은 글자가 나와야 한다. 따라서 큐에서 꺼낸 문자들(원래 순서)이 스택에서 꺼낸 문자들(역순)과 모두 같다면 그 문장은 회문이다.

 

위 알고리즘을 참고하여 회문인지 아닌지 판별 해주는 프로그램을 작성해 보자.

문자열 변수 s를 매개 변수로 받아 큐와 스택을 사용하여 회문이면 True를 아닐 경우 False를 반환하는 함수 palindrome을 작성하라.

 

풀이

1. 함수 palindrome 내부에서 입력 문자열 s를 받아와 처리
2. 문자열에서 알파벳 문자들만 추출하기 위해 isalpha() 메서드를 사용하여 문자열에서 알파벳 문자들만 걸러낸다.
3. 그 다음 문자열에서 모든 알파벳 문자들을 소문자로 변환하고, 해당 문자열을 큐(queue)에 저장
4. 회문을 판별하기 위해 역순 문자열을 스택(stack)에 저장합니다. 문자열을 역순으로 만들기 위해 리스트 슬라이싱([::-1])을 사용
5. 큐와 스택을 비교하며 문자를 하나씩 비교합니다. 만약 큐에서 꺼낸 문자와 스택에서 꺼낸 문자가 다르면 회문이 아니므로 False를 반환
6. 반복문을 모두 통과했다면 큐와 스택이 모두 비었다는 뜻으로 회문이므로 True를 반환

def palindrome(s):
    # 문자열에서 알파벳 문자들만 추출하고, 대소문자를 유지
    s = ''.join(c for c in s if c.isalpha())
    
    # 모두 소문자로 변환하여 비교하기 위해 입력 문자열과 역순 문자열 모두 소문자로
    s_lower = s.lower()
    s_lower_reversed = s_lower[::-1]

    # 회문 판별을 위해 문자열과 역순 문자열을 비교
    return s_lower == s_lower_reversed

# 테스트해보기
print(palindrome("Wow"))  # 출력 결과: True
print(palindrome("Madam, I’m Adam."))  # 출력 결과: True
print(palindrome("Madam, I am Adam."))  # 출력 결과: False

---

3. 사용된 자료 구조 개념

큐(Queue)는 마치 택시 정류장에 줄 서기와 비슷하게 동작한다. 새로 택시 정류장에 도착한 사람은 줄의 맨 뒤로 가서 줄을 서고, 택시가 도착하면 줄의 맨 앞에 선 사람이 택시를 타게 된다. 이렇게 가장 먼저 줄을 선 사람이 먼저 택시를 타는 원리를 '선입선출(First In First Out)'이라고 한다. 자료를 큐에 추가하는 동작을 '인큐(Enqueue)', 큐에서 자료를 꺼내는 동작을 '디큐(Dequeue)'라고 한다.

스택(Stack)은 접시를 쌓는 것과 유사하게 동작한다. 접시를 쌓을 때는 맨 위에 쌓고, 접시를 꺼낼 때도 맨 위에 있는 접시부터 꺼낸다. 따라서 가장 마지막에 들어간 자료가 가장 먼저 꺼내지는 원리를 '후입선출(Last In First Out)'이라고 한다. 자료를 스택에 추가하는 동작을 '푸시(Push)', 스택에서 자료를 꺼내는 동작을 '팝(Pop)'이라고 표현한다.

---

4. 후기

프로그래밍에서 좋은 코드를 작성한다는 것은 메모리를 효율적으로 사용하면서 데이터를 빠르고 안정적으로 처리하는 것이 궁극적인 목표이기 때문에 자료구조와 알고리즘에 조금 시간을 투자하면서 개발 공부를 진행하고 있다.

아직 서버에 속도를 향상시킨다던지 직접 실무에 필요한 알고리즘을 구현해보지는 못했지만 기초부터 다듬어 나가다보면 당연히 내실이 다져질 것이라고 생각된다. 오늘은 여기까지 학습하였다.