Python algorithm 개념 및 실습 - 큐와 스택(회문찾기)

알고리즘이란 ?

• 어떤 일을 하기 위한 명령의 집합
• 문제 해결 방법을 추상화하여 각 절차를 논리적으로 기술해 놓은 것
• 어떤 문제를 해결하기 위한 절차나 방법

 

알고리즘 복잡도

• Complexity
  • 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한가?
• 알고리즘의 성능을 객관적으로 평가하는 기준
  • 시간복잡도(time complexity) : 실행 횟수로 판단
  • 공간복잡도(space complexity) : 기억공간과 파일 공간의 사용량
• 빅오 표기법 ( Big O Notation)
  • 알고리즘이 얼마나 빠른지 표시하는 방법
  • 입력 데이터 크기 증가할 때 알고리즘 연산 시간(횟수)의 증가 방식
  • 연산의 횟수를 비교함
  • O(n) : 계산 복잡도 
    • O : 빅 O
    • n : 연산 횟수
    • O(1) : 입력 크기 n과 계산 복잡도가 무관 할때 ex) n(n+1)/2
    • O(logn) : 입력 크기 n의 로그 값에 비례하여 증가 ex) 이분탐색
    • O(n) : 입력 크기 n에 비례하여 복잡도 증가 ex) 최댓값, 순차탐색
    • O(nlogn) : 입력 크기 n과 로그 n 값의 곱에 비례하여 복잡도 증가 ex) 병합정렬, 퀵정렬
    • O(n²) : 입력 크기 n의 제곱에 비례하여 복잡도 증가 ex) 선택정렬, 삽입정렬
    • O(n₂) : 입력 크기가 n 일 때, 2의 n 제곱 값에 비례하여 복잡도 증가 ex)하노이의 탑

 

 

스택(후입선출구조 : LIFO, Last In First Out)

• 접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조
• 스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능
• 마지막에 삽입한 원소가 맨 위에 쌓여 있다가 가장 먼저 삭제
• 삽입 1 2 3 4 반출 4 3 2 1

 

큐 (선입선출구조 : FIFO, First In First Out)

• 삽입과 삭제의 위치가 제한된 유한 순서 리스트
• 뒤에서 삽입만 하고, 앞에서 삭제만 가능
• 삽입한 순서대로 나열되어 가장 먼저 삽입한 원소가 가장먼저 삭제
• 삽입 1 2 3 4 반출 1 2 3 4

 

회문찾기

회문 : 순서대로 읽어도, 거꾸로 읽어도 내용이 같은 낱말이나 문장

• ex :  역삼역, 기러기, 일요일, 사진사, 복불복
• ex : mom, wow, level, radar

# 주어진 문장이 회문인지 아닌지 찾기

# 회문이면 True, 아니면 False

def palindrome(s):

    qu = []  # queue

    st = []  # stack

    # 받은 문자를 큐와 스택에 담기(알파벳인 경우만 소문자로 변경)

    for x in s:

        # 알아서 알파벳을 담아줌

        if x.isalpha():

            qu.append(x.lower())

            st.append(x.lower())

    # 큐와 스택에 들어있는 문자를 꺼내면서 비교

    # 큐에 문자가 남아 있는 동안 반복

    while qu:

        # 큐와 스택에서 꺼낸 문자가 다르면 return false

        # pop() : 뒤에서부터 인출

        # pop(번호) : 해당번호 인출

        if qu.pop(0) != st.pop():

            return False

    # 루프 종료 후 true 리턴

    return True

# 큐와 스택 쓰지 않고 반복문 문장의 앞뒤를 차례로 비교

def palindrome2(s):

    # 시작 위치 지정

    start = 0

    # 끝 위치 지정

    end = len(s) - 1

    while start < end:

        # start 위치에 있는 문자가 알파벳 문자가 아니면 start + 1

        # ! == not

        if not s[start].isalpha():

            start += 1

        # end 위치에 있는 문자가 알파벳 문자가 아니라면 end -1

        elif not s[end].isalpha():

            end -= 1

        # start와 end 위치에 있는 문자를 소문자로 변경한 후 비교

        # 같지 않으면 False 리턴

        elif s[start].lower() != s[end].lower():

            return False

        # 위 세가지 경우가 아니라면 start +1, end -1

        else:

            start += 1

            end -= 1

    # 반복문 종료 후 True 리턴

    return True

if __name__ == "__main__":

    print(palindrome("Wow"))

    print(palindrome("Madam, I'm Adam."))

    print(palindrome("Madam, I am Adam."))

   

    print(palindrome2("Wow"))

    print(palindrome2("Madam, I'm Adam."))

    print(palindrome2("Madam, I am Adam."))