[내일배움캠프 18일차] 알고리즘&자료구조 시작

점근 표기법

• 빅오(Big-O)표기법
  최악의 성능이 나오는 경우 어느 정도의 연산량인지
  
  
• 빅 오메가(Big-Ω) 표기법
  최선의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지
  사실 이 표기법은 거의 안씀

---

알파벳 찾기

• 복잡도 O(n^2) 식

def get_idx_naive(word):
    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 and char == lo:
                result[j] = i
    print(' '.join([str(num) for num in result]))

우선 result에 알파벳 개수만큼 -1을 채움.

입력받은 매개변수(여기서는 baekjoon이라고 가정)의 길이만큼 반복하여 char 변수에 baekjoon을 차례로 하나씩 넣음.

즉 i 에는 0부터 7까지 들어가고, char에는 b부터 n까지 들어가는 것.

다음 알파벳의 개수만큼 반복하여 lo 변수에 알파벳을 하나씩 넣음 -> lo에는 a부터 z까지 들어가는 것

result 리스트의 j번째 인덱스의 값이 -1이고, baekjoon을 도는 char == 알파벳을 도는 lo 라면 result의 j인덱스를 i로 바꿈.

 

• 복잡도 O(n)식

def get_idx(word):
    # point 1. ord
    # point 2. O(n^2) -> O(n)
    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]))

baekjoon을 하나씩 돌면서 그 문자를 숫자의 형태로 바꾸고 - 97을 해줌. 그 값을 idx 변수에 할당.

예를 들면 word[0]은 b이고 ord(word[0])은 98이므로 idx에는 1이라는 값이 들어가는 것.

쉽게 말해 매개변수인 baekjoon의 알파벳 하나하나를 알파벳 순서로 따졌을 때 몇번째 숫자인지로 바꾼 것

이렇게 되면 바로 result 리스트에서 idx를 활용하여 바로 i를 할당할 수 있다.

두 개의 변수(char과 lo)를 모두 돌며 서로 비교하는 N*N 형태의 계산이 없어지게 되는 것.

---

stack

# 스택 문제(유용한 괄호)
def is_valid_parenthesis(s):
    pair = {
        '}': '{',
        ')': '(',
        ']': '[',
    }
    opener = "({["
    stack = []

    for char in s:
        if char in opener:
            stack.append(char)
        # opener가 아니라는 것은 닫는 괄호의 등장
        else:
            # 닫는 괄호가 등장했는데 stack이 비어있다면 이건 짝이 안맞음 -> False
            if not stack:
                return False
            # 닫는 괄호가 등장하면 stack을 pop해서 비교
            top = stack.pop()
            if pair[char] != top:
                return False
    # for문이 False를 반환하지 않고 끝까지 종료가 되었다면, stack이 비어있는지만 체크
    return not stack

---

queue

# 큐 문제(카드 한 장 남기기)
from collections import deque

def test_problem_queue(num):
    # deq라는 리스트에 deque형태로 1부터 num까지 입력 -> deque([1, 2, 3, ... N])
    deq = deque([i for i in range(1, num+1)])
    # deq 리스트 안에 한 개 남을 때까지 반복
    while len(deq) > 1:
        # 하나 빼고
        deq.popleft()
        # 하나 마지막 인덱스로 옮기고
        deq.append(deq.popleft())
    # 한 개 남았을 때 반환
    return deq.popleft()

---

오늘의 회고

팀이 새로 정해졌다. 새로 자료구조 & 알고리즘 세션도 시작됐다.

열심히 해보자.

 

내일 목표는 알고리즘 코드카타 해보기 + 새로운 강의 적어도 1주차까지는 마무리