[알고리즘 기초] 스택(Stack), 큐(Queue), deque, 점근 표기법, 시간복잡도, 공간복잡도, 최빈값 찾기

---

최빈값 찾기

Q. 다음과 같은 문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환하시오

"hello my name is sparta"

 

두 개의 다른 방법으로 풀이.

import string
from pprint import pprint

text = 'hello, this is sparta'

counter = {}
# 21 번 연산
for char in text:
    # .isalpha() 알파벳인지 체크
    if not char.isalpha():
        continue # 알파벳이 아니라면 넘어감
    if char in counter:
        counter[char] += 1
    else:
        counter[char] = 1
        
#pretty print 내장함수. 예쁘게 출력해줌
pprint(counter)

counter2 = {}

# 26 * 21 번 연산

# string.ascii_lowercase: a-z 소문자가 쭉 나열이됨. (lo라는 이름을 붙여서 나열됨)
for lo in string.ascii_lowercase:
    for char in text:
    
        # 내가 보고있는 알파벳과 같다면
        if lo == char:
            if lo in counter2:
                # 있으면 횟수 더해줌
                counter2[lo] += 1
            else:
                # 없으면 1로 설정해줌
                counter2[lo] = 1
pprint(counter2)

 

두 함수의 연산이 일어나는 횟수

 

방법1. 텍스트의 길이 만큼 연산

 

방법2. 텍스트길이 * 26(a-z소문자 알파벳의 수)만큼 연산

 

➡️ 문장 길이가 1억이라면, 방법1은 1억번, 방법2는 26억번 ➡️ 차이 큼!

➡️ 방법 1이 더 효율적인 방법

 

방법 1. for문 1개 사용

방법 2. for문 2개 (for문 안에 for문 중첩) 사용

🚨 for문 중첩을 썼을 경우 내 로직 꼭 확인해볼 것.
사용해야 하는 경우도 아주 드물게 존재하지만, 대부분 다른 방법이 있는데 내 로직이 잘못된 것이다.
for문 중첩 사용하면 시간 복잡도가 폭발적으로 증가함..

 

 

점근 표기법

• 알고리즘의 성능을 수학적으로 표기하는 방법
• 알고리즘의 “효율성”을 평가하는 방법

점근 표기법의 종류

빅오(Big-O)표기법 : 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기
빅 오메가(Big-Ω) 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기

예를 들어 빅오 표기법으로 표시하면O(N), 빅 오메가 표기법으로 표시하면 Ω(1)
의 시간복잡도를 가진 알고리즘이다! 라고 표현할 수 있습니다. 

알고리즘에서는 사실상 거의  모든 알고리즘을 빅오 표기법으로 분석합니다.
대부분의 입력값이 최선의 경우일 가능성은 굉장히 적을 뿐더러, 우리는 최악의 경우를 대비해야 하기 때문입니다.

 

💡 거의 한번의 for문은 그냥 O(N)의 시간복잡도를 가진다고 보면 된다.

 

방법 1. O(N) 의 시간복잡도를 가진다.

방법 2. O(N^2) 의 시간복잡도를 가진다. (N제곱)

 

 

---

 

배열에서 특정 요소 찾기

 

Q. 다음과 같은 숫자로 이루어진 배열이 있을 때, 이 배열 내에 특정 숫자가 존재한다면 True, 존재하지 않다면 False 를 반환하시오.

[3, 5, 6, 1, 2, 4]

 

숫자를 찾았다면 끝까지 더 볼 필요 없이 나가면 된다.(return True로 끝냄.) 끝까지 없다면 False 를 반환한다.

def is_number_exist(num, arr):
    for el in arr:
        if num == el:
            return True
    return False

 

위에서 연산된 것들을 더해보면, 이렇게 빅오메가 총 N * 1의 시간 복잡도를 가진다는 걸 볼 수 있습니다. O(N)

그런데 여기서, 모든 경우에 N 만큼의 시간이 걸릴까요?

 

input = [3, 5, 6, 1, 2, 4] 이라는 입력값에 대해서 3을 찾으면, 첫 번째 원소를 비교하는 순간!! 바로 결괏값을 반환하게 됩니다.

즉, 운이 좋으면 1번의 연산 이후에 답을 찾을 수 있다는 의미입니다. 최선의 경우 O(1)

 

그러나, input = [4, 5, 6, 1, 2, 3] 이라는 입력값에 대해서 3을 찾으면 어떻게 될까요?

마지막 원소 끝까지 찾다가 겨우 마지막에 3을 찾아 결괏값을 반환하게 됩니다. 즉, 운이 좋지 않으면 input의 길이(N) 만큼 연산 이후에 답을 찾을 수 있습니다.  O(N)

 

 

이처럼, 알고리즘의 성능은 항상 동일한 게 아니라 입력값에 따라서 달라질 수 있습니다.

어떤 값을 가지고 있는지, 어떤 패턴을 이루는 데이터인지에 따라서 뭐가 좋은 알고리즘인지 달라질 수 있다는 의미입니다.

 

 

시간 복잡도

입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계

 

상수 시간 복잡도 O(1) < 로그 시간 복잡도 O(logN) < 선형시간 복잡도 O(N)

로그(logN)은 N 값이 매우 커져도 크게 영향을 받지 않는다.

N^2  <  2^n

N = 10일때 10^2=100  , 2^10 = 1024

 

공간 복잡도

입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말합니다 (메모리를 얼마나 쓰느냐)

 

변수를 저장하면 비용이 든다.

비용 ⬆️ 시스템 성능 저하 ⬆️

함수화된 코드는 굳이 변수에 담지 않더라도, return 값으로 주면

차후에 x = 함수() 이 가능하므로

재사용이 없는 함수 내 지역변수는 굳이 변수에 담지 않는 것을 추천한다.

 

 

➡️ 시간 복잡도와 공간복잡도가 낮은 방법을 찾는게 바로 알고리즘

코딩테스트에서 보통 c로 코딩하는 일(ex. 임베디드 시스템 개발 등)이 아닌이상
공간복잡도를 따지는 경우까지는 안나옴.
시간복잡도만 신경쓰면 된다.

 

 

📌 알고리즘 연습 사이트 

백준
leetcode
프로그래머스

백준이 시간복잡도가 타이트한 편인데, python3 대신 pypy로 선택하여 제출하면 시간복잡도 통과할 수 있다.

 

 

---

 

알파벳 찾기

 

아스키(ASCII) 코드

ex. a는 97로 하자는 약속.

 

 

Q. 알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오.

(https://www.acmicpc.net/problem/10809)

import string


# 방법 1. 나이브한 방법
def get_idx_naive(word):
        
    # string.ascii_lowercase = abcdefghijklmnopqrstuvwxyz
    result = [-1]*len(string.ascii_lowercase)
    
    for i in range(len(word)):
        char = word[i]
        
        for j in range(len(string.ascii_lowercase)):
            lo = string.ascii_lowercase[j]
            
            # 이미 적혀있다면 그냥 넘어가야하므로 if result[j]==-1
            if result[j] == -1 and char == lo:
                result[j] = i
                
    print(' '.join([str(num) for num in result]))

# ==> 시간복잡도 O(N^2)


# 방법 2. 
def get_idx(word):
   
    result = [-1]*len(string.ascii_lowercase)
    
    for i in range(len(word)):
        # 내가 보고있는 알파벳의 위치
        idx = ord(word[i]) - 97
        
        # 이 알파벳이 등장한적이 없으면
        if result[idx] == -1:
            # 위치 기록
            result[idx] = i
            
    print(' '.join([str(num) for num in result]))
    
# ==> 시간복잡도 O(N)


get_idx_naive('baekjoon')
get_idx('baekjoon')

 

ord() 함수 : 문자(알파벳 대소문자) -> 숫자(아스키 코드)로 바꿔줌 (a -> 97, b-> 98, ....) 
ord('z') - ord('z')  = 25
ord('b') - ord('a')  =  1

idx = ord(word[i]) - ord('a')  ➡️  a=0, b=1, c=2, ... 가 나올 것!
➡️ 내가 보고있는 알파벳의 위치!!

💡 결과 리스트 깔끔하게 프린트 하는법

print(' '.join(
      [str(num) for num in result]
))​

실무에서도 매우 자주 사용하는 패턴!

리스트로 출력해도 되지만 , 요소들을 문자열로 바꾸고 공백으로 구분해주는 코드이다.

ex)
[0, -1, -1, ...]

0 -1 -1 ...

 

 

💡 Pycharm의 좋은 기능 Debug 
라인 넘버를 클릭하면 그 지점에서 브레이크를 걸 수 있다.
파일에서 우클릭  ->  디버그 클릭
실행버튼 누르며 다음 줄로 넘어가며 체크 가능

 

 

 

---

 

스택(Stack)

스택이란 자료 구조는 "빨래통"을 떠올리시면 됩니다. 데이터를 한 곳에서만 넣었다 뺄 수 있습니다.

가장 밑에 있는 빨래를 뺄 수 있나요? 아뇨! 가장 위에서만 빨래를 빼거나 넣을 수 있습니다!

그러면 가장 처음에 넣은 빨래는? 가장 늦게 나오겠죠! 가장 마지막에 넣은 빨래는? 가장 빨리 나옵니다!

이런 자료 구조를 Last In First Out 이라고 해서 LIFO 라고 부릅니다.

 

이런 자료구조가 왜 필요할까요?

바로, 넣은 순서를 쌓아두고 있기 때문입니다. 그 순서가 필요한 경우가 있습니다.

예를 들어 컴퓨터의 되돌리기(Ctrl + Z) 기능을 아시나요?

직전에 했던 행동을 되돌리고 싶을 때 사용하는 기능인데, 이를 위해서는 내가 했던 행동들을 순서대로 기억해야 하므로 스택을 사용합니다. 

 

 

스택 구현

면접에서도 굉장히 많이 나옴❗️

def test_node():
    assert Node(1, None).item == 1


def test_stack():
    stack = Stack()

    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)

    assert stack.pop() == 5
    assert stack.pop() == 4
    assert stack.pop() == 3
    assert stack.pop() == 2
    assert stack.pop() == 1
    assert stack.pop() is None
    assert stack.is_empty()

 

test.py

# 노드 먼저 생성
class Node:
    def __init__(self, item, next):
        # 노드는 내 값(item)과, 내가 가리키는 녀석(next) 두 가지로 구성된다.
        self.item = item
        self.next = next


class Stack:
    def __init__(self):
        # 처음 생성 했을 때는 당연히 탑은 비어있을 것
        self.top = None

    def push(self, value):
        self.top = Node(value, self.top)

    def pop(self):
        # 아직 넣은 게 없을 경우
        if self.top is None:
            return None
            
        # 탑을 새로 지정
        node = self.top
        self.top = self.top.next

        return node.item

    def is_empty(self):
        # 비어있는지 확인 ==> 탑이 비어있으면 비어있는 것!
        return self.top is None

 

---

유효한 괄호

Q. Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

https://leetcode.com/problems/valid-parentheses/description/

 

전형적으로 스택으로 풀기 좋은 문제이다.

# assert는 뒤의 조건이 True가 아니면 AssertError를 발생한다.
assert test_problem_stack("()")
assert test_problem_stack("()[]{}")
assert not test_problem_stack("(]")

 

def is_valid_parenthesis(s):
   # 딕셔너리로 짝을 지정해준다.
    pair = {
        '}': '{',
        ')': '(',
        ']': '[',
    }
    # 여는 녀석들(오프너)은 스택에 넣는다.
    opener = "({["
    stack = []

    for char in s:
        if char in opener:
            stack.append(char)
        else:
            # 스택이 비어있다면 무조건 볼것도없이 끝내버림.
            if not stack:
                return False
            top = stack.pop()
            if pair[char] != top:
                # 짝이 안맞는게 있다면 더 볼것도 없이 바로 나오면 됨
                return False

    # 이 중 해당이 없는데, 다 끝났다면 짝이 맞는 것!
   
    # 스택이 비어있는 지 확인해야함 
    # (ex. '[[{{}}' , '{{}}]]') 이런경우라면 for문은 잘 끝나겠지만 정답은 아니므로.
    return not stack

 

 

이 문제에서는 스택을 리스트로 사용하고 있다.

파이썬에서 스택은 보통 그냥 리스트 사용하면 됨.

(append있으면 뒤로 들어가고 pop도 있으므로)

 

---

 

큐(Queue)

한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조.

 

큐란 자료 구조는 "놀이기구"를 떠올리시면 됩니다.

놀이기구는 한 줄로 섰다가, 한 줄로 나옵니다!

데이터를 한쪽 끝으로 넣고, 반대쪽에서 빠져 나옵니다.

그러면 가장 처음에 줄 선 사람은? 가장 빨리 나오겠죠! 가장 마지막에 선 사람은? 가장 늦게 나옵니다!

이런 자료 구조를 First In First Out 이라고 해서 FIFO 라고 부릅니다.

 

이런 자료구조가 왜 필요할까요?

순서대로 처리되어야 하는 일에 필요하기 때문입니다!

주문이 들어왔을 때 먼저 들어온 순서대로 처리해야 할 때, 혹은 먼저 해야 하는 일들을 저장하고 싶을 때 큐를 사용합니다. 

 

 

큐 구현

def test_queue():
    queue = Queue()

    queue.push(1)
    queue.push(2)
    queue.push(3)
    queue.push(4)
    queue.push(5)

    assert queue.pop() == 1
    assert queue.pop() == 2
    assert queue.pop() == 3
    assert queue.pop() == 4
    assert queue.pop() == 5
    assert queue.pop() is None
    assert queue.is_empty()

 

test.py

class Queue:
    def __init__(self):
        self.front = None

    def push(self, value):
        #큐의 front가 없다면 바로 넣어주면됨
        if not self.front:
            self.front = Node(value, None)
            return
            
        # 비어있지 않다면, 일단 끝까지 가봐야함.
        node = self.front
        # 끝까지 가서 노드 추가
        while node.next:
            node = node.next
        node.next = Node(value, None)


    def pop(self):
        # 앞이 비어있다면 큐 자체가 비어있는것이므로 그냥 나가면됨(return none)
        if not self.front:
            return None
            
        # 비어있지 않다면
        node = self.front
        # 다음 노드를 첫번째로 지정함
        self.front = self.front.next
        return node.item

    def is_empty(self):
        return self.front is None

 

 

 

큐 응용  문제

Q. N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다.
우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자.
카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오. 

 

구현

assert test_problem_queue(6) == 4

 

def test_problem_queue(num):
    # 문제 https://www.acmicpc.net/problem/2164
    # 빠른이유 https://wiki.python.org/moin/TimeComplexity
    
    # 데크 생성 (1~num)
    deq = deque([i for i in range(1, num + 1)])
    
    # 하나가 남을 때 까지
    while len(deq) > 1:
        # 제일 앞에 있는 건 버리고
        deq.popleft()
        # 그다음으로 앞에 오는 것은 제일 뒤로 붙여준다.
        deq.append(deq.popleft())
    return deq.popleft()

 

파이썬에서 큐는 직접 구현하지 않고 내장 함수 deque()를 이용한다.

 

 

💡 deque는 앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형으로, 스택(stack)처럼 써도 되고 큐(queue)처럼 써도 된다. collections.deque 모듈은 deque 자료형을 생성하는 모듈이다. deque는 '데크'라 읽는다.

 

 

스택과 달리 큐를 list로 이용하지 않는 이유

스택에서 list.append와 list.pop()을 이용했던 것처럼 list.append와 list.pop(0)을 이용하면 리스트를 큐처럼 사용할 수 있다.

하지만 pop()의 time complexity는 O(1)인 반면 pop(0)의 time complexity는 O(N)이기 때문에 시간이 오래 걸린다.

따라서 시간 복잡도를 고려해 리스트는 큐로 사용하지 않는다.

참조: https://wiki.python.org/moin/TimeComplexity 

 

 

list 의 경우 append는 O(1)로 매우 저렴하지만

중간에서 빼오는게 O(n)으로 매우 비싸다.

(중간에 넣으면 중간 나머지 애들을 한칸씩 댕겨와야하므로)

반면 데크는 저렴함.

 

---

 

내배캠 서버 이슈로 저기까지 해싱을 듣다가 끊겼다..

그래서 분량 조절 실패로 해싱은 내일 정리하기로

 

그동안 소수정예로 3명이였던 조원들이랑 그새 정이 들었는데 헤어지게 되어서 아쉬웠다🥲

어색하지 않고 내적 친밀감이 많이 쌓였는데..

 

새로운 조원들과도 팀 프로젝트가 끝나면 같은 감정을 느끼겠지!?