💪 Today I Learned

• 알고리즘 3, 4주차 강의 수강

Algorithm

집합 자료형

• 존재하는지 아닌지 여부를 판단하기 위한 방법 -> 집합 자료형 사용
• 중복을 허용하지 않음

  a = set([1, 2, 3, 4, 1, 2, 3])
  {1, 2, 3, 4}

이분 탐색 알고리즘이 모든 경우에 효율적인 것은 아니다. 어떤 경우에는 집합 자료형, 어떤 경우에는 이분 탐색을 사용하는게 효율적이다.

해쉬

• 해쉬 테이블을 구현할 때 해쉬 값 혹은 인덱스가 중복되어 충돌이 일어나는 경우 체이닝과 개방 주소법으로 해결할 수 있음

그래프

그래프를 표현하는 방법

1) 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현
- 즉각적으로 0과 1이 연결되었는지 여부를 바로 알 수 있음
- 모든 조합의 연결 여부를 저장해야 하므로 O(노드^2) 만큼의 공간을 사용
2) 인접 리스트: 링크드 리스트로 그래프의 연결 관계를 표현
- 즉각적으로 연결되었는지 알 수 없고, 각 리스트를 돌아봐야 함
- 연결되었는지 여부를 알기 위해서 최대 O(간선) 만큼의 시간을 사용
- 모든 조합의 연결 여부를 저장할 필요가 없으므로 O(노드 + 간선) 만큼의 공간을 사용

Dynamic Programming(동적 계획법)

• 겹치는 부분 문제일 경우 동적 계획법을 사용하면 됨
• 이 때 사용하는 방법이 메모이제이션

Python

Call by Object Reference

• 함수에서 파라미터로 배열을 넘기면 그 내부에서 원소를 추가하거나 할 수 있는데 파라미터로 int, str 타입의 변수를 넘기면 그 값이 복제되어 새로운 값을 형성함
• 함수에서 외부의 변수를 사용하기 위해 global이라는 키워드를 사용해야 함

	global result_count

딕셔너리 정렬

• items 함수는 Key와 Value의 쌍을 튜플로 묶은 값을 dict_items 객체로 돌려줌
• dict_items 객체는 리스트를 사용하는 것과 동일하게 사용할 수 있음

	dict_items([('classic', 1450), ('pop', 3100)])

• sorted 함수, lambda 사용

sorted(genre_total_play_dict.items(), key=lambda item: item[1], reverse=True)

📢 한마디

너무 많은 알고리즘 개념을 한 번에 머릿속에 넣으려니까 힘들다. 지금은 어렵게 느껴지더라도 계속 하다 보면 늘겠지..?