- AI 예술 작품은 학습 데이터 기반이기 때문에 '창작성 (originality)'가 있는지 의문이 들기도 한다.
- 학습에 사용된 데이터를 제공한 사람에게도 혜택이 돌아가기가 어려운 것이 사실이다.
- 창작자인 AI는 법적 권리르 제공할 수 있는 법적 제도가 부재한 상황이며, 현존하는 예술가들의 스타일을 따라한 경우 상업적 피해를 발생시킨다.
- 또한, 창작된 작품이 인간의 윤리적 규범을 따르지 않을 수도 있다.
(3) 인공지능 법인
- 법인은 법적 권리와 의무에 대한 책임을 소지한다.
- 인공지능은 아직 법인에 속하지 않는다.
- '인공지능을 법인으로 인정할 것인가?'에 대한 의논이 벌어지기도 했다.
"장기적으로 로봇에 대한 구체적인 법적 지위를 창출하여, 적어도 가장 정교한 자율주행 로봇이 야기할 수 있는 손해를 충분히 배상할 책임이 있는 전자인의 지위를 갖게 하고, 로봇이 자율적인 의사결정을 하거나 그 밖에 독립적으로 제3자와 상호작용하는 경우에 전자인격을 적용할 가능성이 있는 경우"
- 법인격의 장점으로는 (1) 책임 문제가 쉽게 해결 (2) 혁신, 사회 발전 가능 (3) 법제도가 일관성 있게 유지 (4) 자연인이 아닌 것에 대한 법인이 이미 존재함
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려고 한다.
전화번호가 다음과 같은 경우, 구조대 전화번호는 영석이의 전화번호의 접두사이다.
- 구조대 :119
- 박준영 : 97674223
- 지영석 :1195524421
전화번호부에 적힌 전화번호를 담은 배열 phone_book이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 반환하라.
2. 코드
(1) 1차 코드 - 효율성 테스트 3, 4 실패 (시간 초과)
defsolution(phone_book):
phone_book = sorted(phone_book, key=len)
for phone in phone_book:
temp = phone_book.copy()
temp.remove(phone)
for t in temp:
n = len(phone)
if phone == t[:n]:
returnFalsereturnTrue
defsolution(phone_book):
phone_book = sorted(phone_book, key=len)
for i, phone inenumerate(phone_book):
for j, t inenumerate(phone_book):
n = len(phone)
if j != i:
if phone == t[:n]:
returnFalsereturnTrue
(2) zip, startswith 사용한 코드
defsolution(phone_book):
phone_book = sorted(phone_book)
for p1, p2 inzip(phone_book, phone_book[1:]):
if p2.startswith(p1):
returnFalsereturnTrue
(3) Hash Map 사용한 코드
defsolution(phone_book):
hash_map = {}
for phone_number in phone_book:
hash_map[phone_number] = 1for phone_number in phone_book:
temp = ""for number in phone_number:
temp += number
if temp in hash_map and temp != phone_number:
returnFalsereturnTrue
3. 설명
(1) 1차 코드
- 전화 번호 길이를 기준으로 배열을 sorting하고, phone_book에 있는 전화 번호 하나씩 검토하면서 t[:n]과 배열의 전화번호가 일치하는지 비교한다.
- 아무래도 sorting 후에 2중 for문을 해서 그런지, 시간 초과가 계속 떴다.
(2) zip, startswith 사용한 코드
- 숫자로 되어 있는 문자열을 sorting하면, 왼쪽에서부터 크기 순서대로 배열된다.
예를 들어, ['119', '9767423', '1195524421']은 ['119', '1195524421', '97674223'] 이렇게 정렬된다.
- 따라서,zip(phone_book, phone_book[1:])로 그 다음 원소와 비교하면서 다음 원소가 이전 원소로 시작되는지startswith()로 검토한다.
(3) Hash Map 사용한 코드
- 우선 Hash Map을 사용한 이유는, 리스트보다 원소의 존재를 파악하는데 더 낮은 복잡도를 가지고 있기 때문이다. (O(1))
- 전화번호를 hash_map에 key값으로 다 저장해둔다.
- 짧은 문자열 통째로 긴 문자열의 앞쪽과 비교하는 것이 아니라,긴 문자열의 앞쪽부터 하나씩 temp에 더해가며 짧은 문자열과 동일한 요소가 있는지 확인하는 방식이다.
(나는 문자열 통째로를 긴 문자열의 앞쪽과 비교할 생각만 했어서.. 관점의 변화를 확 느낄 수 있었던 코드였다.)
- 원소의 개수를 파악하기 위해서도 Hash map이 사용되지만, 특정 원소의 존재를 확인하는데 빠른 속도를 가지고 있다는 장점으로 다양한 문제에서도 활용 가능하다고 생각한다!
LG 생활건강의 'Portable 타투 프린터, 임프린투'는 타투 이미지가 생성형 모델을 기반으로 생성되어 고객이 원하는 디자인에 맞게 다양한 타투를 할 수 있도록 한다.
이 외에도 경기도 광주의 화담숲이 있는데, '화담채 아뜰리에 미디어 아트 전시'를 생성형 AI로 만들었다고 한다.
실사의 화담숲 사진을 입력으로 (계절별) → 사진에 대한 전체적인 가이드, 스토리라인, 화풍 생성 → 이미지-텍스트 모델 프롬프트로 입력 → 제안된 컨셉에 맞춘 이미지 생성 → 사람의 손을 거쳐서 미디어 아트화
LG는 사용자가 바로 사용할 수 있는 생성형 AI 보다는 End-user를 계열사, 외부 사업체로 두었다고 한다.
해당 전문가들이 아이디어를 얻고 작업을 효율적으로 할 수 있도록 돕는 방향으로 진행된다.
Q&A에서 유익한 질문들이 많이 나와서 정리해 보았다.
1) zero-shot 이미지 캡셔닝에서 CIDEr 메트릭으로 평가한 이유가 있나?
: 다양한 스코어들 중 하나일 뿐임. 랭킹을 매길 때 다양한 지표로 비교를 하는데 굳이 비교를 하자면 그나마 신뢰성이 있겠다고 생각하여 사용함. (정성적 평가) CIDEr가 더 우수해서 쓴다 이런건 아님.
2) 일반 대중보다는 계열사를 목표로 연구하고 계신건지 연구 방향이 궁금함
: 계열사들마다 일반적인 사용을 원하는 곳도 있고 특정화된 커스텀 모델을 원하는 곳도 있음. 일반화된 모델을 만들어 두고, 그때마다 커스터마이징하여 제공하는 것을 목표로 하고 있음
3) 모델의 개발 과정이 궁금. 문제가 없는 이미지 데이터란 무엇인지도 궁금함
: 요새 대부분의 AI 모델이 그렇듯 엄청나게 독창적이기보다는, shutterstock이랑 계약을 해서 직접 구매한 데이터로 scratch부터 학습했음
4) 다양한 계열사를 가진 만큼 hallucination도 있을텐데 자체적 rule base로 관리하고 있는 것인지, 아니면 할루시네이션을 분류할 수 있는 모델을 구축해서 사용하고 있는지가 궁금함
: 할루시네이션은 LLM 연구에서 진행 중이고, 엔드 유저가 바로 일반적인 대중이 아니라 단순 아이디어를 얻어서 디자인에 활용할 수 있도록 하는, 사람 손을 한번 거치는 식으로 하고 있음
5) GPT Evaluation도 어떻게 보면 정성적 평가에 유사한 정량적 평가인데, 모델의 최적 성능을 평가하는 입장으로서 어떤 부분을 더 고려하고 있는지 궁금함
: 그런 evaluation을 사용하는 것은 아무래도 사람이 평가해야 하는 공수를 덜기 위해서가 크다. 뭐가 정답이고 아니다 판단하기가 애매함. 일단 사람이 전체적인 평가를 하고, GPT Evaluation을 사용하여 경향성을 비교했을 때 차이는 있었지만 경향성이 비슷하기 때문에 어느정도 대체할 수 있겠다고 판단하여 사용하게 됨
6) 엔드 유저가 결국은 계열사 사람들인데 그럼에도 영어로 출력되는 모델을 만든 이유는?
: 데이터가 영어 쪽이 방대해서 그렇게 학습한 것이고, 실제로 한글에서도 잘 동작을 하고 있음. 현재 영어, 한국어 지원
3. Data Intelligence Lab
수요 예측 (Demand Forecasting)에 관한 발표였는데, 개인적으로 가장 인상 깊었던 세션이었다.
수요 예측을 한다는 것은, 단순하게 수요를 예측한다!는 관점보다는
1) 제조 → 리테일 → 컨슈머 이 과정에서 재고를 줄이고, 생산을 효율적으로 할 수 있도록 함
2) 여러 주체가 있는 만큼 문제 해결이 어려움
이 두 관점이 핵심이다.
그러면서 'The Bullwhip effect (채찍효과)'에 대해서 말씀해주셨는데,
- 공급사슬관리에서 반복적으로 발생하는 문제점 중 하나로, 이것은 제품에 대한 수요정보가 공급사슬상의 참여 주체를 하나씩 거쳐서 전달될 때마다 계속 왜곡됨을 의미한다. - 어떤 아이템에 대한 수요가 변동은 공급사슬상의 다른 구성원(유통업체, 제조업체, 공급업체, 2차공급업체, 3차공급업체) 각자의 입장에서 ‘만약에 대비하기에’ 충분할 정도의 재고를 축적하도록 만든다. - 이런 대응 추세는 주문계획에서 작은 변화가 증가되고, 재고, 생산, 창고, 운송과 관련된 과도한 비용이 발생되는 가운데, 공급사슬을 통해 확산되어 나간다.
(출처 : 위키백과)
여기에서 예측해야 할 것이 맨 끝에 있는 시계열이다 보니 어려움이 많은 것이다.
'Sales Demanding'은 pricing, promotions, shortage가 3개의 Key로 작동한다.
이때, Inventory (재고)가 Sales (판매)를 따라가지 못 할 때 '그냥 생산 많이 하면 되지!'가 아니다. 재고 비용을 생각해야 하기 때문이다!
관점에 따라서 다르기 때문에 학습과 평가가 모두 어렵다.
예측 오차를 평가 지표로 쓰는 것이 맞는 지도 고민해야 한다!
(1) LLM based Forecasting
LG AI 연구원에서는 'LLM based Forecasting'을 하였다.
LLM의 임베딩의 이점을 살려서 단순하게 사용하였고, 모델 구조상 어디에 위치하는지에 집중하여 agent화 하였다.
수요 예측에 LLM까지 도입을 해야 하는가에 대한 고민도 있었지만, 최대한 다양하고 많은 데이터를 활용하기 위해 도입했다고 하였다.
예측의 큰 틀이 'Distribution Shift'를 가정하기 때문에, 이전에 있었던 일을 미래에 그대로 예측하는, 그런 단순한 문제가 아니다.
시계열을 시계열 자체 데이터만 사용해서는 예측이 불가능하다는 의미이다.
최대한 필요한 데이터를 정보화 하여 다 쓰고자 LLM을 도입하였다.
(2) Causality (인과성)
현재 계속 연구 시도 중인 주제라고 한다. 많은 원인들 중에서 진짜 영향을 주는 것이 맞는지? 따져보는 것이다.
시계열을 그래프로 표현하고, 시간에 따른 변화를 그래프 수정을 통해 변화해나간다.
'인과성'은 정말 어려운 것이다.. 상관관계와는 다르다.
인과관계는 '반례'가 없다!
(3) Multi-modal Forecasting
모든 가지고 있는 데이터를 활용하기 위해서 Multi-modal 예측을 한다.
매대 사진 같은 것도 충분히 데이터가 될 수 있다. 시계열이라고 해서 시계열 데이터만 학습에 사용하는 것이 아니다.
(4) Probability of Forecasting
한편, 이미지와 텍스트는 사용자 측면에서 받아들이기가 쉽다. Output이 명확하기 때문이다.
하지만 예측은 사용자 입장에서 판단이 어렵다. 예측한 바를 믿고 그대로 따를 것인가에 대한 고민이 남게 되는 것이다.
따라서 '신뢰 구간'을 제공해야 한다. (DeepAR, Distribution Loss 참고하기)
연구원 분께서 마지막에 하신 말씀이 인상 깊었다.
"그래서, 예측을 잘 해야 할까요?"
예측 정확도가 1순위가 아닐 수도 있다는 말씀이셨다.
모델은 당연히 사람보다 예측 정확도가 높을 수밖에 없다. 모델은 모든 데이터를 반영할 수 있기 때문이다.
실제로 예측을 잘하는 분야가 늘어나고 있고, 예측 정확도가 100%라고 해서 무조건 따르는 것이 아니다.
비즈니스 임펙트가 있는지를 따져야 한다!
의사 결정에 영향을 주는 요소가 '예측 정확도'가 아닐 수 있다는 점이다. 즉, ROI 관점이 필요하고, 이는 LG 내부에서도 계속해서 고민하고 있는 과제라고 한다.
그래서 결론적으로는,
모든 형태의 데이터를 바탕으로 미리 알고 있는 정보에 대한 반영이 제대로 이뤄지면서, 변동의 속성을 파악하고 변동의 원인을 설명할 수 있는, 마지막으로 도메인 전문가와의 상호작용을 통해 더 개선되는 모델을 구축하는 것이 목표가 되겠다.
연구원 분들을 직접 뵙고 궁금한 내용을 여쭤볼 수 있는 기회를 주신 LG AI 연구원 분들께 다시 한번 감사의 말씀 드리고 싶습니다!
자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있는데, 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.
이러한 자카드 유사도를 원소의 중복을 허용하는 다중집합에 대해서 확장한다.
- 예1)
다중집합 A는 원소 1을 3개 가지고 있고 (A = {1, 1, 1}), 다중집합 B는 원소 1을 5개 가지고 있다 (B = {1, 1, 1, 1, 1}). 이 다중집합의 교집합은 원소 1을 min(3, 5)인 3개, 합집합은 원소 1을 max(3, 5)인 5개 가지게 된다.
문자열 "France"와 "French"가 주어졌을 때, 이를 두 글자씩 끊어서 다중 집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로 자카드유사도는 2/8이다.
2. 입력 형식
- 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.
- 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.
3. 코드
(1) Counter 사용하기
from collections import Counter
defsolution(str1, str2):# 문자열 소문자로 변경
str1 = str1.lower()
str2 = str2.lower()
arr1 = []
arr2 = []
# 특수문자 들어가지 않은 문자열만 취급하기for i inrange(len(str1)-1):
if str1[i:i+2].isalpha():
arr1.append(str1[i:i+2])
for i inrange(len(str2)-1):
if str2[i:i+2].isalpha():
arr2.append(str2[i:i+2])
# 중복 원소 고려를 위해 Counter 사용
arr1_counter = Counter(arr1)
arr2_counter = Counter(arr2)
# 합집합, 교집합 구하기
hab = list((Counter1 & Counter2).elements())
kyo = list((Counter1 | Counter2).elements())
# 집합 A, B가 모둔 공집합일 경우 J(A, B) = 1iflen(union) == 0andlen(inter) == 0:
return65536else:
returnint(len(inter) / len(union) * 65536)
(2) 다중 집합 사용하기
defsolution(str1, str2):# 문자열 소문자로 변경
str1 = str1.lower()
str2 = str2.lower()
arr1 = []
arr2 = []
# 특수문자 들어가지 않은 문자열만 취급하기for i inrange(len(str1)-1):
if str1[i:i+2].isalpha():
arr1.append(str1[i:i+2])
for i inrange(len(str2)-1):
if str2[i:i+2].isalpha():
arr2.append(str2[i:i+2])
# 다중 집합 구하기
arr1_result = arr1.copy() # 합집합
intersection = [] # 교집합for i in arr2:
if i in arr1:
arr1.remove(i)
intersection.append(i)
else:
arr1_result.append(i)
iflen(arr1_result) == 0andlen(intersection) == 0:
return65536else:
returnint(len(intersection) / len(arr1_result) * 65536)
4. 해설
(0) 공통
- 대문자와 소문자 구분이 없도록 string.lower() 함수로 문자열을 소문자로 변경해준다.
- 두 글자씩 끊어서 원소로 만들 때 영문자로 된 글자 쌍만 유효하도록 string.isalpha() 함수로 검토한다.
(1) Counter 사용하기
- 중복된 원소를 고려하기 위해서 원소의 개수를 Counter로 구한다.
- Counter는 '|', '&' 연산이 가능하다. 이때, 핵심은 Counter.elements()이다.
Counter.keys()를 하면 중복된 값이 존재해도 중복 없이 unique한 값이 반환된다. 따라서, elements()를 통해 중복된 개수만큼을 리스트로 저장한다.
(2) 다중 집합 사용하기
- 일반적인 Python의 집합은 중복 원소를 허용하지 않는다. 하지만, 다중 집합은 중복된 원소를 포함하기 때문에 실제로는 리스트에 저장하여 나타낸다.
- 마치 Sorting에서 stable sorting이 있고, unstable sorting이 있는 것처럼 생각하면 쉽다! 같은 '1'이지만 '1_a', '1_b'가 있는 것으로 생각하는 것이다.
- 다중집합에서 교집합과 합집합을 구하는 방법은 다음과 같다.
a = [1,2,2,3,4,5]
b = [1,1,2,3,4,6]
a_temp = a.copy()
a_result = a.copy()
for i in b:
if i notin a_temp:
a_result.append(i)
else:
a_temp.remove(i)
a_temp는 a - b (차집합)이 되고, a_result는 합집합이 된다.
교집합은 a_result에서 a_temp 원소를 뺀 원소들이 된다.
a_temp가 필요한 이유는, a에서 remove 해버리면 원본 데이터가 손실되기 때문이다.
이 문제에서는 이후에 arr1이 필요하지 않아서 바로 arr1에서 remove를 한 것이다.
arr1_result = arr1.copy() # 합집합
intersection = [] # 교집합for i in arr2:
if i in arr1:
arr1.remove(i)
intersection.append(i)
else:
arr1_result.append(i)
이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있다.
- 최소 필요 피로도 : 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도
- 소모 피로도 : 던전을 탐험한 후 소모되는 피로도
예를 들어 '최소 필요 피로도'가 80, '소모 피로도'가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모된다.
하루에 한 번씩 탐험할 수 있는 던전이 있을 때, 한 유저가 오늘 최대한 많이 탐험하려고 할 때, 유저가 탐험할 수 있는 최대 던전 수를 반환하라.
2. 제한 사항
- k는 1 이상 5,000 이하인 자연수
- dungeons의 각 행은 각 던전의 ['최소 필요 피로도', '소모 피로도'] 이다.
3. 코드
(1) 완전 탐색 - DFS
answer = 0defexplore(power, cnt, is_visited, dungeons):global answer
if cnt > answer:
answer = cnt
for i inrange(len(dungeons)):
if power >= dungeons[i][0] and is_visited[i] == False:
is_visited[i] = True
explore(power - dungeons[i][1], cnt + 1, is_visited, dungeons)
is_visited[i] = Falsedefsolution(k, dungeons):global answer
is_visited = [ Falsefor _ inrange(len(dungeons)) ]
explore(k, 0, is_visited, dungeons)
return answer
(2) 순열
from itertools import permutations
defsolution(k, dungeons):
answer = 0for pemutation in permutations(dungeons, len(dungeons)):
power = k
cnt = 0for need, spend in permutation:
if power >= need:
power -= spend
cnt += 1else:
break
answer = max(answer, cnt)
return answer
4. 해설
(1) 완전 탐색 - DFS
깊이 우선 탐색 방식으로 모든 경우를 따져준다.
전역 변수 answer를 선언하여, 던전의 최대 탐험 개수를 갱신했을 때 answer 값을 바꿔준다.
이미 지나온 던전인지를 저장하는 is_visited 배열을 만들어주고 DFS를 수행하는 함수인 explore를 호출한다.
explore 함수는
- 전역 변수 answer보다 탐험한 던전의 개수가 더 많을 경우 갱신을 해준다.
- 던전의 경우를 for문으로 모두 검토하면서 방문하지 않았는지, 방문할 수 있는지 (최소 필요 피로도를 만족하는지) 확인하여 재귀적 호출을 진행한다.
- 핵심은 호출 이후로 is_visited[i] = False로 만들어주어, 다음 경우에는 다시 방문할 수 있도록 하는 것이다.
(2) 순열
from itertools import permutations를 통해서 가능한 모든 경우의 수를 구한다.
- for permutation in permutations(dungeons, len(dungeons))
특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 반환하도록 하라.
2. 제한 사항
- s의 길이는 5 이상 1,000,000 이하이다.
- s는 숫자와 '{', '}', ','로만 이루어져 있다.
- 숫자가 0으로 시작하는 경우는 없다.
3. 코드
defsolution(s):
s1 = s.lstrip('}').rstrip('{').split('},{')
s2 = []
# 각 원소로 이루어진 배열을 삽입for i in s1:
if'{{'in i:
i = i.lstrip('{{')
if'}}'in i:
i = i.rstrip('}}')
s2.append(i.split(','))
# 원소의 길이를 기준으로 배열 정렬
s3 = []
fortupleinsorted(s2, key=len):
for t intuple:
# 배열에 존재하지 않는 경우 순서대로 추가if t notin s3:
s3.append(t)
returnlist(map(int, s3))
지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
이때, 데이터베이스에 캐시를 적용하여 성능 개선을 시도하고 있지만, 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.
DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하라.
2. 입력 형식
- 캐시 크기 (cacheSize)와 도시이름 배열 (cities)을 입력받는다.
- cacheSize는 수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
- 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다.
3. 출력 형식
- 입력된 도시 이름 배열을 순서대로 처리할 때, '총 실행시간'을 출력한다.
4. 조건
- 캐시 교체 알고리즘은 LRU (Least Recently Used)를 사용한다.
- Cache hit일 경우 실행시간은 1이다.
- Cache miss일 경우 실행시간은 5이다.
5. 코드
defsolution(cacheSize, cities):# 대소문자 구별하지 않도록 소문자로 만들어주기
cities = [c.lower() for c in cities]
# 캐시 사이즈가 0인 경우 전부 Cache miss로 간주if cacheSize == 0:
returnlen(cities) * 5# { 도시 이름 : 참조 시간 } 저장할 딕셔너리 선언
cache = dict()
total = 0for c in cities:
iflen(cache) < cacheSize:
if c notin cache.keys():
total += 5else:
total += 1else:
if c notin cache.keys():
total += 5# 가장 value가 큰 요소를 제거
max_time = -1
max_key = c
for city, time in cache.items():
if max_time < time:
max_key = city
max_time = time
del cache[max_key]
else:
total += 1# 공통적으로 c 아닌 도시들에 +1, c 도시에 0 부여
cache = { city : time+1for city, time in cache.items()}
cache[c] = 0return total
