Punch!

5월 14일에 마곡 LG사이언스파크에서 진행한 LG Aimers 4기 Mentoring Day에 참석했다.

LG Aimers 4기 활동 참여자 중에서 이메일 폼 작성 선착순으로 참석할 수 있었는데, 운이 좋게도 메일을 일찍 봐서 선착순 안에 들 수 있었다.

집이랑 마곡이 20분 거리라서 종종 마곡에 놀러갔다가 LG 건물을 보곤 했는데, 직접 들어가보니 생각보다 더 삐까뻔쩍했다..ㅎㅎ 지어진지 오래되지 않아서 그런지 빌딩이 매우 깨끗했다. 1층 로비에서는 LG Twins의 우승을 기원하는 행사를 하고 계셨다ㅋㅋㅋ

멘토링 데이의 순서는 다음과 같다.

총 세 분의 LG AI 연구원 분들이 발표를 해주셨다.

각각 Material Intelligence Lab, Multimodal Lab, Data Intelligence Lab에 계신 분들이었다.

세미나 내용이 매우 흥미로웠고, 국내 대기업이 어떻게 인공지능을 연구하고 자사에 활용하는지 알 수 있었던 시간이었다.

발표해주신 내용을 문제가 되지 않는 선에서 정리해보려고 한다.

(혹시 문제가 있거나.. 틀린 내용이 있다면 댓글 부탁드립니다!)

1. Material Intelligence Lab

연구원 분께서는 생물학 전공을 하셨고, LG에서는 융복합 연구를 진행하고 계셨다.

그 중에서도 '신약 생성 모델'과 '개인화 암 백신 개발'에 대한 내용을 말씀해주셨다.

(1) 신약 생성 모델 (Drug Generative Model)

새로운 약을 개발할 때 시간이 매우 많이 소요된다. 평균 15년을 잡고 개발비도 굉장히 많이 들어간다고 한다.

신약 하나를 개발하는 데 약 10,000번의 실험이 필요하다고 하는데..

그럼에도 계속해서 신약 개발을 시도하는 이유는 성공 시에 계속 매출을 발생하기 때문이다.

신약 생성 과정은

- Target 발굴 ⭢ Hit 발굴 ⭢ Lead 발굴 및 최적화 ⭢ 임상 과정

이렇게 이루어진다.

'Target'은 질병의 원인으로 주로 단백질이다.

'Hit'는 단백질 결합 분자이며,

'Lead 발굴 및 최적화' 과정에서는 질병의 원인 단백질과 잘 결합하며 독성이 없고, 안전하고 안정성 있는 Lead를 발견한다.

이 중에서 'Lead 발굴 및 최적화'에서 사람이 직접 하나하나 실험하는 것을 줄이기 위해 인공지능을 도입한다.

사용 모델까지도 상세하게 설명해주셨는데, 그 부분까지는 언급하면 안 될 것 같아서 최대한 러프하게 정리해보겠다.

신약 '생성' 모델이기 때문에 특정 약물 타겟과 결합할 수 있으며 안정성, 안전성이 양호한 약물을 생성하는 과정을 모델링하였다.

이 과정에서의 어려운 점은 특정 약물 타겟과의 결합 안정성이 있는지 없는지에 관한 데이터가 부족하다는 것이었다.

이를 타개하기 위해!

(1) 기존에 알려진 약물과의 유사성과 (2) 예측 효능을 바탕으로 리워드를 제공하고 최적화하였다.

이후에는 Domain 연구원 분들이 특정 기준에 따라서 모델링 결과를 필터링 후 직접 실험을 통해 실제로 유효한 약물 후보를 도출한다고 한다.

결과적으로 Lead 물질 개발 시간을 약 8년에서 3.5년으로 대폭 줄였다는 의의가 있다.

또한, 해당 연구의 시사점으로

(1) 공개된 기술과 현업에서의 간극 (대표적으로는 데이터의 현황이 있다.)과 (2) 도메인 전문가와의 계속 협업이 필요하다는 점이 있다.

(2) 개인화 암 백신 개발 (Personalized Cancer Vaccine)

암은 몸에 있던 유전자에 변이가 생기고 비정상적인 세포가 생기며, 그러한 세포들이 증식하면서 발병한다.

기존의 항암제는

- 1세대 : 암세포 말고도 다른 정상 세포 공격 ⭢ 부작용이 매우 큰 방식

- 2세대 : 독성 물질을 암세포에만 targeting ⭢ 부작용이 0%라고 말할 수는 없으며 재발 가능성 있음

- 3세대 : 인체의 면역 시스템을 활용 ⭢ 암세포가 만들어지기 전, 우리 몸에 있지 않은 단백질에 대해 포획하여 제거하기

3세대의 항암제를 개발하면 부작용과 재발 가능성을 줄일 수 있다.

하지만, 어려운 점은 암 환자마다 변이된 부분이 다르다는 것이다. 따라서, '개인화'가 필요하다.

우리 몸의 어떤 세포가 생산한 단백질이 조각나고, MHC (Major Histocompatibility Complex)라는 단백질에 의해서 세포 밖으로 나온다.

세포 밖으로 나온 단백질 조각을 T세포가 인식하고, 원래 있던 단백질이라면 지나치게, 그렇지 않다면 항원으로 인식해 세포를 공격한다.

여기에서 아이디어를 얻어, 신항원을 예측하여 인위적으로 넣어준다면 암에 대한 면역원성을 증가시킬 수 있다는 결론을 냈다. 암을 우리 몸의 내부적인 면역 세포로 치료 가능한 것이다.

하지만, 사람마다 DNA가 다르고 가지수가 매우 다양하기 때문에 어려운 점이 있다.

사람마다 MHC Binding 분포가 다르다는데, 이는

(1) MHC 분자와 단백질 펩타이드가 결합을 하는지, 하지 않는지에 대한 것과 (2) 이 결합된 것이 T세포 수용체와 결합을 하는지, 하지 않는지에 대한 문제이다.

LG AI 연구원에서는 환자에게서 암 조직과 정상 조직을 받아 DNA를 분석하고, 이 사람이 가진 MHC 타입을 알아내었다. 또한, 정상 조직과 그렇지 않은 조직의 비교를 통해 어떤 부분이 변이 되었는지를 판단하여 초기 후보로 두었다.

실제로 NeurlPS 2022에서 Attention 기반의 MHC Binding 특성 모델링으로 accept 되었다고 한다.

결과적으로 펩타이드의 위치 및 아미노산 종류별 Attention score를 확인 및 시각화할 수 있게 되었다.

사실 이런 바이오 쪽 도메인 지식이 없다보니.. 충분히 쉽게 설명해주셨음에도 이해되지 않는 부분이 많았다.

요약을 해보면 다음과 같다.

바이오 분야에서 인공지능 융합은 '데이터 분석'과 '큐레이션'이 중요하다고 하셨다.

학습에 사용되는 데이터는 굉장히 많고 다양한데, 각 논문마다 실험 목적과 방법이 다르기 때문에 데이터베이스 선별이 매우 중요하다고 한다.

직접 실험을 따라하면서 해당 논문의 실험 과정과 결과 도출을 완벽히 이해한 상태가 필요한 것이다!

이쪽 분야에서는 아직 벤치마크가 활발하게 정리된 상황이 아니라서 아직 발전 가능성이 무궁무진한 분야라고 한다. 실제로 많은 해외 제약회사에서는 이러한 방식으로 신약 개발과 의료 개발이 이뤄지고 있다고 한다.

인공지능 활용의 대표적인 모범 사례인 것 같다.

2. Multimodal Lab

이미지-텍스트의 멀티모달리티 연구의 주제로는 다양한데,

(1) Image Generation : 텍스트를 입력했을 때 이미지 생성 (예. Dalle-3, Stable diffusion-3)

(2) Image Understanding : 이미지를 넣었을 때 이미지를 해석. 사용자에게 정보 제공 (예. GPT-4, LLaVA)

산업 현장에서 현재의 생성형 인공지능을 사용할 수 있을까? 라고 한다면,

사실 산업 현장의 인공지능 수요는 매우 많지만 데이터가 부족하다는 벽이 있다.

1) 보안 이슈로 인해 공개를 하지 못하거나, 2) 업종 특성상 디지털 데이터가 축적되지 못한다거나, 3) 신뢰성과 저작권으로 인해 어떤 데이터를 사용해야 할 지가 문제인 경우가 많다,

LG의 비즈니스 모델은 'Advancing AI for a better life'이다.

실제 산업 현장에서 바로 사용할 수 있는 생성 모델을 만들어 제공하는 것이다.

명확한 비전을 수립하고 구성원들과 공유하여 실제 산업 현장에 적용 가능한 '전문가 AI'를 개발한다.

이때, 신뢰할 수 있는 고품질 데이터를 수집하여 멀티모달 이해 기술을 확보한다.

LG의 LMM (Large Multi-modal Model)은 Image-to-Text Generation에서의 Image Captioning (이미지에 대한 설명 출력)에서 더 나아가 고객의 더 많은 니즈에 맞춘 기술을 개발한다고 한다.

예컨데, '이미지 설명 및 요약', '홍보 문구 생성', '시나리오 생성', '구성 요소 추천 (음악, 화풍)', '차트 & 문서 분석' 등이 있다.

또한, 텍스트를 입력으로 넣었을 때 이미지에 대한 처리를 하는 Text-to-Image Generation에서는 색상 변화, 배경 융화 등의 작업이 이뤄진다.

타사 모델과의 차별점으로는 'Single Model'로 지원하여 고객이 어떤 모델을 써야하는지 고민하는 시간을 줄여준다는 점이다.

현재 이미지 생성 모델로 생성한 이미지를 다른 계열사와 외부 사업에서 활용 중에 있다고 한다.

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 연구원 분들께 다시 한번 감사의 말씀 드리고 싶습니다!

1. 문제 설명

유사한 기사를 묶는 기준으로 "자카드 유사도"라는 방법을 채택했다.

자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있는데, 두 집합 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개 가지게 된다.

- 예2)

다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합은 {1, 2, 2}, 합집합은 {1, 1, 2, 2, 3, 4, 5}이므로 자카드 유사도는 3/7이다.

이를 문자열을 두 글자씩 끊어서 다중집합으로 만든 것에 응용하고자 한다.

- 예)

문자열 "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

def solution(str1, str2):
	# 문자열 소문자로 변경
    str1 = str1.lower()
    str2 = str2.lower()
    
    arr1 = []
    arr2 = []
    
    # 특수문자 들어가지 않은 문자열만 취급하기
    for i in range(len(str1)-1):
        if str1[i:i+2].isalpha():
            arr1.append(str1[i:i+2])
    for i in range(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) = 1
    if len(union) == 0 and len(inter) == 0:
        return 65536
    else:
        return int(len(inter) / len(union) * 65536)

(2) 다중 집합 사용하기

def solution(str1, str2):
	# 문자열 소문자로 변경
    str1 = str1.lower()
    str2 = str2.lower()
    
    arr1 = []
    arr2 = []
    
    # 특수문자 들어가지 않은 문자열만 취급하기
    for i in range(len(str1)-1):
        if str1[i:i+2].isalpha():
            arr1.append(str1[i:i+2])
    for i in range(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)
    
    if len(arr1_result) == 0 and len(intersection) == 0:
    	return 65536
    else:
    	return int(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 not in 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)

reference : https://velog.io/@munang/%EA%B0%9C%EB%85%90%EC%A0%95%EB%A6%AC-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%8B%A4%EC%A4%91-%EC%A7%91%ED%95%A9

1. 문제 설명

어떤 게임은 일정 피로도를 사용하여 던전을 탐험할 수 있다.

이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있다.

- 최소 필요 피로도 : 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도

- 소모 피로도 : 던전을 탐험한 후 소모되는 피로도

예를 들어 '최소 필요 피로도'가 80, '소모 피로도'가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모된다.

하루에 한 번씩 탐험할 수 있는 던전이 있을 때, 한 유저가 오늘 최대한 많이 탐험하려고 할 때, 유저가 탐험할 수 있는 최대 던전 수를 반환하라.

2. 제한 사항

- k는 1 이상 5,000 이하인 자연수

- dungeons의 각 행은 각 던전의 ['최소 필요 피로도', '소모 피로도'] 이다.

3. 코드

(1) 완전 탐색 - DFS

answer = 0

def explore(power, cnt, is_visited, dungeons):
	global answer
	if cnt > answer:
    	answer = cnt
        
        for i in range(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] = False

def solution(k, dungeons):
	global answer
        is_visited = [ False for _ in range(len(dungeons)) ]

        explore(k, 0, is_visited, dungeons)

        return answer

(2) 순열

from itertools import permutations

def solution(k, dungeons):
	answer = 0
    
        for pemutation in permutations(dungeons, len(dungeons)):
            power = k
            cnt = 0

            for need, spend in permutation:
                if power >= need:
                    power -= spend
                    cnt += 1
                else:
                    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))

예시 :

([80, 20], [50, 40], [30, 10])
([80, 20], [30, 10], [50, 40])
([50, 40], [80, 20], [30, 10])
([50, 40], [30, 10], [80, 20])
([30, 10], [80, 20], [50, 40])
([30, 10], [50, 40], [80, 20]))