22.02.21

1. 해시테이블

해시테이블은 문자열의 key를 기준으로 읽고 쓸 수 있기 때문에 상수시간이 걸린다.

1-1. 해시테이블 만들기 & 원소에 접근하기

dict = {"aa": 24, "bb": 20, "cc": 30}

cc = dict["cc"]
dict["dd"] = 22 

사전의 원소들을 해시를 이용해 O(1)시간에 접근이 가능하다.
(값을 수정할 때도 O(1) 시간)

1-2. get method

dict = {}

for x in dict:
	dict[x] = dict.get(x, 0)  # x인 키가 존재하면 그 value를, 없으면 0을 return

dict.get(key): key에 해당하는 value를 return
dict.get(key, otherValue): key가 dict에 존재하지 않으면 otherValue를 return

1-3. dict.items()

dict = {"aa": 24, "bb": 20, "cc": 30}

for key, value in dict.items():
	print(key, value)

2. sort()의 시간복잡도 = O(NlogN)

하지만 프로그래머스나 다른 플랫폼에서는 O(N)과 O(NlogN)의 차이를 잘 잡지 못한다고 한다.

3. 탐욕법 (Greedy Algorithm)

• 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택
• 탐욕법을 사용할 수 있는 문제는?
  ➡️ 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때

4. 길이가 n인 리스트 만들기

n = 4
newList = [1] * n	# [1,1,1,1]