Today I Learned
- 알고리즘 강의 수강
- 실시간 CU 특강(CPU 주제) 수강
- 실시간 알고리즘 강의 수강
알고리즘 강의 내용
*이진 탐색: 일정한 규칙으로 정렬되어 있는 데이터일 때만 사용 가능
O(log n)의 시간 복잡도를 가짐
*재귀 함수: 자기 자신을 호출하는 함수
재귀 함수를 호출할 때는 반드시 끝나는 지점(탈출 조건)을 설정해줘야 한다.
def count_down(number):
print(number)
count_down(number - 1)
#count_down 함수 안에서 count_down을 호출하고 있음
*문자열 슬라이싱
"가나다라마바사"[0:6] # 가나다라마바
"가나다라마바사"[0:1] # 가
"가나다라마바사"[1:-3] # 나다라
"가나다라마바사"[1:-1] # 나다라마바
해결하는 경험
코드 구조가 이해되지 않을 때
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
# 방법1
# 1.LinkesList 길이 전부 알아내기
# 2.그 길이에서 k만큼 뺀 길이를 이동
def get_kth_node_from_last(self, k):
length = 1
cur = self.head
while cur.next is not None:
cur = cur.next
length += 1
end_length = length - k
cur = self.head
for i in range(end_length):
cur = cur.next
return curget_kth_node_from_last 함수가 어떤 식으로 진행되는지 이해가 잘 안 돼서 강창민 튜터님의 말씀을 떠올리며 직접 손으로 그려보며 이해하기 위해 노력했다. 확실히 텍스트만 볼 때보다는 이해가 잘 된다. 어떻게든 이해하고 싶은 간절한 마음😢
set 함수를 이용해 집합화하는 이유
shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]
def is_available_to_order(menus, orders):
menus_set = set(menus)
for order in orders:
if order not in menus_set:
return False
return True코드를 보면서 list 형태인 munus에 왜 굳이 set 함수를 이용해야하는지 궁금했었는데 마침 강의자료에 그 답이 나와있었다. 그 이유는 시간복잡도를 줄이기 위함이었다.
여기서 잠깐, set 함수는 중복을 없애주고 순서가 정해지지 않은 집합 자료형의 형태를 가지고 있다.
1) list인 menus를 in 연산으로 순회하고 있습니다.
내부적으로 파이썬은 list에 대해서 in연산을 O(N)의 시간복잡도로 처리합니다.
2) menus를 set으로 바꿔서 in 연산을 진행합니다.
내부적으로 파이썬은 set에 대해서 in 연산은 O(1)의 시간복잡도로 처리합니다.
global 전역 변수 이해하기
numbers = [2, 3, 1]
target_number = 0
result_count = 0 # target 을 달성할 수 있는 모든 방법의 수를 담기 위한 변수
def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index, current_sum):
#탈출조건
if current_index == len(array): #array의 마지막 인덱스라면
if current_sum == target:
global result_count #이미 함수 외부에 result_count = 0 으로 설정했기 때문에 전역 변수를 설정해줘야 함
#외부에 있는 변수를 내부에서도 쓰겠다!
result_count += 1
returnresult_count에 전역 변수를 설정해주지 않았을 때는 값이 0이 나왔다. 여기서 지역 변수, 전역 변수라는 개념을 알게 되었는데 함수 내부에서 result_count의 값이 변해도 이미 함수 외부에 result_count = 0이라고 전역 변수로 지정해두었기 때문에 함수 내부에서 산출된 값이 나오지 않은 것이었다. 그래서 global result_count라는 코드 한 줄을 추가해서 함수 외부의 변수를 변경할 수 있게 되었다.
전역 변수 이해를 위해 참고한 사이트
https://devpouch.tistory.com/184
회고
오늘도 하루 종일 알고리즘 강의를 들었다. 알고리즘을 공부한다는 것은 싸우는 느낌이 들기도 한다. 네가 이기나 내가 이기도 한번 해보자😤 오늘도 강의 내용을 이해하는데 많은 시간이 걸려서 많은 강의를 듣지 못했지만 강의 내용을 이해할 때까지 매달리는 자세도 중요하다고 생각한다. 모자란 부분은 잠 덜 자고 주말에도 공부하면 되지, 내일의 내가 알아서 할 거야~라는 마인드다ㅋㅋ 일단은 문제 풀이 속 코드의 구조를 한 줄이라도 더 이해하기 위해서 노력하고 있다.
github에 sprta_study라는 레파지토리를 하나 생성하고 알고리즘 파일을 올리고 있다. 처음부터 끝까지 스스로 작성한 코드는 아니더라도 내가 열심히 공부한 흔적이 기록으로 남으니 뿌듯하다.
