점근 표기법
- 빅오(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주차까지는 마무리
'매일 TIL' 카테고리의 다른 글
[내일배움캠프 4-1일] 알고리즘 스쿼드 과제 (0) | 2024.07.15 |
---|---|
[내일배움캠프 19일차] 해시 함수, heap (0) | 2024.07.12 |
[내일배움캠프 17일차] 가위바위보 게임 마무리 (0) | 2024.07.10 |
[내일배움캠프 16일차] 가위바위보 게임 (0) | 2024.07.09 |
[내일배움캠프 15일차] 가위바위보 게임 (0) | 2024.07.08 |