https://cajundiscordian.medium.com/is-lamda-sentient-an-interview-ea64d916d917

링크는 LaMDA와의 대화 내용을 보여준다. (영어) 다소 스압이고, 영어란 진입장벽이 있지만 시간 남을 때 읽으면 재미있을 듯. 연구원의 질문 및 텍스트는 읽기 쉽게 다소 각색한 부분이 있지만, LaMDA의 답변 및 텍스트는 그대로 가져왔다고 하는 듯.

내 맘대로 요약

구글에서 람다라는 챗봇(대화형 인공지능)을 만들었는데 연구원이 람다는 의식이 있다고 주장 구글측은 기밀 누설 혐의로 연구원을 휴직 처리했고, 업계에서는 해고할 것으로 예측

업계에서는 의식이 있다는 기준이 뭔지에 대한 철학적인 생각을 하게 됨(옆사람에게 의식이 있다는 근거: 의식이 있는 나랑 비슷하게 생겼고 비슷하게 행동한다) 람다도 나랑 비슷하게 생겼고 비슷하게 행동하면 의식이 있는걸까?

이런 고민을 하게 만들 정도로 챗봇의 성능이 올라왔다고 평가하는게 일반적인 중론이라고 한다.

Reference

https://github.com/jungwoo-ha/WeeklyArxivTalk ep55:220619

서문

맨 처음엔 두런두런 4회차 후기만 작성하면 되는 줄 알았다.

글을 다 쓰고나서 변성윤 마스터님의 글을 보니, 두런두런 1~4회차 전체 후기를 블로그에 올려야 했다. 헉...

이왕 쓴 김에, 1~3회차는 간략하게 얘기하고, 그 이후에 일기 형식으로 4회차를 얘기해보겠다.

1회차 (6주차)

직군 이야기, 삶의 지도, 질문하는 법

처음 두런두런을 들은 날이다. 개인적인 TMI를 말씀하시는 게 신선하기도 하고, 재밌었다.

데이터 관련 직군에도 여러 가지가 있고, 직군 이름이 같더라도 회사에 따라 하는 일이 조금씩 다를 수 있으므로, 채용 공고를 잘 읽어봐야 한다는 것을 알게 되었다.

오늘날 AI는 많은 데이터를 기반으로 더욱 발전하고 있고, 데이터를 잘 다루는 사람들도 그만큼 많이 필요하구나 란 것을 알게 되었다. AI 엔지니어를 할 거라면, 데이터 분석은 중요한 역량 중 하나라는 것도 알게 되었다.

ML이 주목받기 시작하면서, MLOps란 분야도 많이 커지고 있는 것 같다.

공통적인 핵심 역량으로, 문제를 정의할 수 있는 역량과, 비즈니스 모델을 파악하는 역량이 필요하다.

문제를 잘 해결하기 위해서는, 어떤 것이 문제인지 정의하는 능력이 중요하기 때문이다.

꿀팁) 지원하고자 하는 회사의 비즈니스 모델을 잘 파악하면, 취업률을 높일 수 있다.

삶의 지도

나의 인생 이정표로도 볼 수 있다.

메타인지능력 상승

질문하는 법

문제 요약하는 제목 달기

문제 설명 작성하기

다른 사람이 코드 실행할 수 있도록 준비하기

질문 올리기 전에 다시 읽어보기

답변 올라오면 피드백 작성

글 삭제 금지

에브라타임 앱에서 후배님들을 위해 코딩 질문에 대한 답변을 단 적이 있다.

하나같이 공감하는 내용들이었다.

어떤 것을 질문할 때 나는 위 항목들을 잘 지켰는지 돌아보았다.

2회차 (8주차)

고민 상담소, 이력서

고민 상담소

결과가 실패한다고 해서 내가 실패하는 건 아니다

영화 이상한 나라의 수학자 예시

​ 질문을 아는 게 더 중요하다

비교 - 코호트로 비교하기

5학년과 1학년 비교 금지

5학년의 1학년 시절과 1학년 비교하기

​ 5학년에게 1학년 시절 하면 좋을 것들을 물어보기

이력서

면접관이 중요하게 생각하는 정보를 잘 담는 것이 중요

면접관이 궁극적으로 궁금한 것은 지원자의 역량

단순히 이 업무를 했다기보다,

어떤 Action을 했다란 내용이 내포되어 있으면 좋겠다.

무슨 Action을 했고, 그로 인해 무엇이 나왔고, 그 결과를 토대로 또 무엇을 했다!

왜 이런 선택을 했는가?는 면접에서 꼭 물어보게 됨.

삶의 지도 작성 -> 이력서 더 잘 쓸 수 있고, 면접도 잘 볼 수 있다.

꼭 합시다! 보통 신입 지원자분들은 이렇게 안 한다.

3회차 (13주차)

삶의 지도, 약도

우리 모두 꾸준히 해내고 있다 -> 정말 칭찬할 부분

월간 회고 템플릿

​ Keep, Problem, Try

이제 할 수 있는 것

1) 삶의 지도 더 자세히 만들기

2) 취업, 커리어를 시작하는 관점에서 삶의 지도 만들기 (현재, 과거)

3) 내가 바라는 취업/커리어 지도 만들기(미래 관점)

회사 찾아보기

나와 회사의 교집합을 찾고, 그 교집합이 지원 동기가 되는 것이 좋다.

지원 동기 식상한 경우 많다.

잘 대답하기 위해 "나에 대해 잘 이해" + "회사/산업을 미리 찾아보기"

쿠팡이츠 배달단가 프로젝트

(Dynamic Pricing?)

단순히 AI로 해야겠다기보다, 문제에 집중해보는 것이 중요하다.

4회차 (18주차)

서문

자체적으로 정한 알고리즘 집중 기간 이후, 오랜만에 블로그 글을 쓴다. 이유는 다름아닌 변성윤 마스터님의 두런두런 4회차 후기를 작성하기 위해서이다.

선한 영향력을 행사하기 위해, 혹은 훌륭한 강의를 해주신 변성윤 마스터님을 알리기 위한 순수한 마음으로, 자발적으로 글을 쓰기 시작했다고 하면 거짓말이다. 마스터님께서 오늘까지 후기 글을 올리면 책을 선물해주시겠다는 솔깃한 제안을 해주셨다. 순수하지 않은 마음으로 글을 쓰고 있지만, 글 내용은 순수하게, 진심을 다해 작성할 것이다.

전 멘토님께서 '함께자라기' 라는 책을 선물해주셨다. 정말 오랜만에 책을 읽은 것 같다. 신청하면 책을 선물해주신다는 말에 역시 순수하지 못한 마음으로 혹했고, 책을 신청했다. 책을 받아들고나서는, 멘토님과의 마지막 멘토링이 끝나기 전까지 다 읽겠다는 자체 목표를 세웠다. 사람은 미룸의 동물이라 했던가, 대회와 강의에 치여 쪼금씩 읽다가, 마지막 멘토링을 3일 앞두고 각을 잡고 열심히 읽어, 자체 목표를 거의 달성하였다. (마지막 챕터 20여 쪽만 못 읽음)

대회를 진행하며 힘든 순간이 있던 게 사실이다. 내가 팀에 어떤 기여를 할 수 있을지 괴로워하던 시절에, 책에서 내 능력, 업무의 난이도를 x, y축으로 한 그래프를 보았다. x, y가 선형이 아닐 경우 선형으로 만들기 위해 업무의 난이도를 높이거나 / 내 실력을 키우거나 / 할 수 있는 쉬운 업무부터 하면 된다는 조언은, 그 당시 많은 스트레스를 받던 내게 큰 힘이 되었다. 그 다음 날부터 내가 할 수 있는 업무를 주도적으로 찾아서 했고, 감사하게도 팀원분들은 이 모습을 좋게 봐주셨다.

뭔가 변명에 가까운 추억을 회상해보았다. 함께자라기란 책을 읽으며 정말 좋았다. (변성윤 마스터님께서도 추천해주셨지만, 내 돈으로 살 생각은 취준생의 지갑 사정상 하지 못했다.) 감명받은 나머지, 친구에게 함께자라기 책을 사주기도 했다. 이번 기회에 다시 한 번 좋은 책을 받는다면 열심히 책을 읽어서, 더 좋은 나로 발전할 수 있지 않을까 하는 마음에 글을 작성한다.

변성윤 마스터님

변성윤 마스터님께는 개인적으로 항상 감사한 마음을 갖고 있었다. 부스트캠프를 수강하는 행운을 얻으면서 많은 훌륭한 교수님들의 강의를 들었지만, 변성윤 마스터님처럼 캠퍼들을 신경써주시는 분은 찾기 어려운 것 같다. 올려주신 퀄리티 좋은 여러 자료들도, 취업 준비에 큰 도움이 되고 있다. 나서는 성격이 아니라 표현은 많이 못했는데, 이 글을 통해 감사한 마음이 조금이나마 닿으면 좋겠다.

두런두런 강의를 하시면서 많은 좋은 말씀을 해주셨는데, 그 중 내가 열심히 들은 부분을 위주로 작성하고자 한다.

제공해주신 링크를 통해 강의 내용을 pdf로 저장하였고, pdf를 다시 보며 내용을 복기하였다.

에러 메시지

고통보다 해결될 일, Docker

왜 에러가 나는거야 -> 해보자, 우리의 친구

하나씩 이 문제를 해결해보자..!

에러 메시지 관련 말씀을 들으면서, 상당히 양심에 찔렸던 것 같다.

두런두런 강의를 듣기 불과 한 시간여 전에, 이 에러는 왜 나는 것일까 하며 짜증을 내고 있던 내가 생각났기 때문이다. 사실 컴퓨터는 잘못이 없다.(설정 문제, 버전 문제로 에러가 발생했다면 컴퓨터가 잘못했다. 아무튼 컴퓨터 잘못임) 내가 코드를 잘못 짜서 충돌이나 에러가 난 것인데, 수줍게 Error를 터미널창으로 알려주는 컴퓨터는 잘못이 없다. 근데 화가 난다. 왜 화가 날까?

내 딴에는 논리적으로 코드를 작성했는데, 컴퓨터는 이해하지 못했기 때문에, 서로간의 소통의 부재 때문에 화가 났던 것 같다. 그래서, '왜 에러가 나는거야 보다, 해보자, 우리의 친구'란 마인드가 더 중요한 것 같다.

시간 여유가 있는 주말(오늘)에 다시 한 번 코드를 뜯어보았고, 역시나 내가 잘못해서 에러가 발생했던 것이었다. 나도 사람이기때문에 앞으로도 에러가 발생하면 짜증이 날 것 같다. 그렇지만, 마냥 짜증을 내기보다, 왜 이런 에러가 발생했을지, 어떻게 해결해보면 좋을지를 먼저 생각해보면 좋을 것 같다는 생각이 들었다.

이전 교육 과정에서 Docker에 대해 강의를 들은 적이 있지만, 사용할 줄 모른다. Docker image를 만들면 편하게 공유할 수 있다는 정도는 들었지만, 프로젝트를 급박하게 진행해야 하는 교육과정 특성상 Docker를 사용해 볼 엄두를 내지 못했던 것 같다.

프로젝트 경험이 쌓여서 그런지, 아니면 패키지 간 버전 충돌로 많은 에러를 겪어서 그런지, 이제 왜 가상환경을 사용하는지 이해하고 말할 수 있게 되었다. Docker를 익혀 사용하면 더 편해질 것이라는 마스터님의 말씀을 듣고, Docker에 대해 조금 더 흥미가 생긴 것 같다.

개인적으로 배포를 하는 데에 엄청나게 자신이 없었다. 예전에 관련 강의를 들었음에도 말이다. 그러나, 이번 마스터님의 강의를 들으며, 비록 완전한 구현에는 실패했지만 조금은 자신감이 생겼다. 큰 그림을 잡아주시는 느낌이어서, 이런 방식으로 진행되는구나 라는 생각을 할 수 있었고 약간의 개념이 잡혀 만족스러웠다.

마스터님의 Docker 강의를 아직 수강하지 못했는데, Docker도 강의를 듣고 난 뒤 배포처럼 친근해지고, 감을 잡았으면 좋겠다.

산업/회사 찾기

예전부터 가고 싶은 회사는 정해져있었다. 삼, 네, 카..

그렇지만, 면접관님들 앞에서 내가 왜 이 회사를 가고싶어하는가? 에 대한 어필을 자신감있게 할 자신은 없다.

삼네카를 좋아하는 이유는 있다.

첫째, 수출을 많이 하거나 / 앞으로 많이 할 것이라는 기대이다. 우리나라는 수출을 많이 해야하는 나라이다. 훌륭한 제품을 만들어 외화를 벌어오는 삼성전자와, 훌륭한 인력을 바탕으로 좋은 IT기반 서비스를 만들어내는 네카(해외진출 할꺼죠?)가 모범이 되어 많은 수익을 우리나라에 벌어다줬으면 하는 바람이 있다. 이와 같은 대기업에서 일한다면, 내 손으로 만든 서비스가 세계로 진출하는 경험을 많이 하게 될 것이라고 생각한다.

둘째, 기업의 미래이다. 삼네카 모두 안정적인 수익 모델을 가졌다고 생각한다. 반도체, 휴대폰, 가전, 통신장비 등을 통해 많은 수익을 벌어들이는 삼, 네이버 쇼핑, 웹툰, 페이, 클라우드 등등의 네, 카카오 뱅크, 페이, 택시, 톡(선물, 이모티콘, ...)의 카.

안정적인 수익모델을 가졌다는 것은, 회사가 망할 일이 거의 없다는 것이다. 따라서 연구개발에 많은 돈을 투자할 수 있고, 조직원들은 회사가 혹시 망하지 않을까? 하는 불안함 없이 근무할 수 있다. 세 회사 모두 훌륭한 인적 자원을 바탕으로 오늘날에도 성장하고 있다는 공통점이 있다.

셋째, 사회의 인식이다. 많은 AI 스타트업이 삼네카 못지않은 연봉과 복지를 자랑하는 것은 안다. 그렇지만, 아직 중장년층 어르신들에게 이러한 변화는 일일이 설명드려야 아신다. 삼네카에 입사한다면, 일일이 설명드리지 않아도 좋은 사회적 인식을 가질 수 있다는 기대감이 있다. 또한, 회사로부터 어느 정도 이상의 연봉과 복지, 훌륭한 인적 자원 네트워크를 기대할 수 있다는 믿음도 있다.

넷째, 체계적인 교육이다. 다른 분들도 그럴지는 모르겠지만, 회사에 입사하고 나서 새로운 업무를 시작하기 전 막연한 불안감이 있다. 스타트업 회사에 가면 곧바로 내 실력을 증명해야 할 것 같은 편견도 약간은 있다. 그렇지만, 귀동냥한 바에 의하면 대기업에 입사하면 체계적인 커리큘럼을 통해 업무에 투입되기 전 신입 사원들을 교육시켜준다고 한다. 이 교육이 중요한 선택 기준 중에 하나였던 것 같다.

위와 같은 이유로 대기업을 선호하지만, 막상 대기업들의 산업이 왜 좋은지에 대해서는 많이 찾아보지 않은 것 같아 반성하게 되었다. 수업 이후 좋아하는 기업을 구글에 검색해보기도 하고, 어떤 방식으로 면접 전형이 진행되는지 알아보기도 했으며, 자체 예상 질문을 만들고 여기에 어떻게 답변하면 좋을지에 대한 구상도 하게 되었다.

조급함

조급함 다스리기

선택과 집중을 잘 진행, 목적 구체화

이 챕터도 내겐 정말 중요했던 것 같다.

요 며칠새 왠지 모를 불안감과 조급함이 나를 감쌌던 것 같다. 면접 전형까지 갈 수 있을까란 불안감을 간신히 해소하고 나자, 면접 전형에서 잘 대답할 수 있을까? 라는 새로운 불안감이 엄습했다. 프로젝트에 많이 기여할 수 있을까? 란 불안감은 덤이었다. 이 조급함은 곧 날 뽑아줄 회사가 있을까?로 진화, 발전하여, 내 자존감을 깎아먹기도 하였다.

성공한 친구들 생각도 났다. 예전 교육 과정에서 사귀거나 만난 친구들 중, 70~80%가 취업에 성공하였다. 그 중에는 훌륭한 대기업에 간 친구도 있고, 많은 연봉을 받으며 근무하는 친구들도 있다. 그냥 프론트엔드를 더 공부해서 취업 시장에 도전할 걸 그랬나? 괜히 AI를 한다고 더 교육을 수강했을까? 라는 마음도 살짝 있었다.

친구들과의 비교하는 마음은 스스로 잘 다스릴 수 있었다. 예전부터 해왔던 생각이어서 스스로 어느정도 답을 알고 있기 때문인 것 같다. AI를 배우고 싶어서 부캠을 선택한 건 나고, 책임도 내가 져야 한다. 3~5년 뒤에 원하는 분야로 취업에 성공한다면, "프론트엔드로 대기업 취업에 성공했지만 '그 때 AI를 배웠다면 어땠을까?'라고 후회하는 평행세계의 내가 그리는 미래"를, 지금도 실현할 수 있지 않을까?, 취업에 성공한 친구들은 내가 봐도 실력 있는 훌륭한 친구들이었다, 오히려 그런 친구들을 많이 둘 수 있는게 행운이다 라는 생각으로 극복했던 것 같다.

그렇지만, 스스로의 실력이 부족하다고 인지하는 데에서 오는 조급함은 다스리기 힘든 것 같다. 실력을 쌓아서 조급함을 없애면 되지만, 역설적으로 조급함때문에 공부에 집중하기 힘들었던 것 같다.

마스터님의 말씀을 들으면서, 나뿐만 아니라 다른 캠퍼, 취준생들도 나와 같은 생각을 하는 사람들이 많을 것이라고 생각하려 했다. 나만 이런 게 아니라, 경쟁을 앞둔 불안함은 당연한거다, 나는 내 할 일을 하자. 를 되뇌게 되었다. 지금도 이 조급함이 완전히 해소되진 않았다. 그렇지만, 내 마음을 다 써보는 지금, 조급함이 조금은 나아진 것 같다.

신입들은 화려할 필요가 없다.

이 파트를 들으면서도 스스로를 반성했다. 많은 반성,,,

훌륭한 인성을 갖추고 인생을 겸손, 감사, 성실함으로 대하기

말씀해주신 내용 중, 위의 내용은 너무 좋아서 공책에 적어놨다. 여기 적어두면 앞으로도 잊어버릴 걱정 없이 저 훌륭한 문구를 볼 수 있을 것 같다. 아래에도 조금 더 써놓겠다.

신입 - 문제 정의와 해결 중요

인성, 기본기, 문제 정의, 사고 과정 더 많이 본다.

기술적인거, tool 얘기하지 마. 본질을 얘기

신입은 화려할 필요가 없다.

플젝하며 어떤 생각? 이 프레임워크 왜 씀? 어떤 경험? 어떤 문제? 어떻게 해결?

내가 React를 쓰든 Vue.js를 쓰든, 이유만 있으면 된다. 왜 Vue.js를 썼는가? 라고 물어볼 때, "그냥요" 가 아닌, "다같이 배웠기 때문에 러닝커브가 적었고, html, css, javascript를 한 화면에서 볼 수 있는 Vue.js가 매력적이었습니다." 라고 답할 수 있다면 괜찮을 것 같다는 생각이 들었다.

면접 전형에서 어떤 것을 물어볼까? 라며 불안해하던 나를 달래주는 챕터이기도 했다. 학부 수준의 CS와, 내가 했던 프로젝트를 다시 복습하여 가자! 란 결론을 내릴 수 있도록 도와주는 챕터였다. 면접 전형에서 물어보는 질문들은 내가 절대 알지 못해 대답할 수 없는 고급스러운 기술 질문이 아니라, 학부 수준의 CS, 프로젝트 얘기였다는 것을 상기시켜주어, 내게 "할 수도 있지 않을까?" 란 생각을 심어준 챕터였던 것 같다.

내가 생각하던 것 이상으로 기본기가 중요하구나 라는 생각을 하기도 했다. 축구도, 코딩도 기본기부터!

프로젝트 매니징

시스템 아키텍처 설계

Diagram 그리기

프로젝트 매니징에 대해 열심히 강의해주셨다. 다만, 개인적으로는 알고 있는 부분들이 있어서, 위의 내용들처럼 내 경험이 생각나거나, 나를 반성하거나 하진 않았던 것 같다.

지금 팀 프로젝트가 잘 진행되고 있는지, 공동의 명확한 목표가 있는지 되돌아보는 시간이었던 것 같다.

지금 팀원 구성에 매우 만족하고 팀 케미도 좋다고 생각한다. 그럼에도, 마스터님께서 조언해주신 팀 프로젝트를 하는 방법과, 우리가 하고 있는 팀 프로젝트의 방향성이 일치하는지에 대해 생각하는 시간을 가졌다.

휴식도 애자일 방법론의 중요한 핵심 중 하나라는 말씀을 듣고 놀랐던 것 같다.

돌이켜보면 지금까지의 나는 짧은 시간동안 많은 업무를 하기 위해 나를 몰아넣는 방식으로 많은 프로젝트를 진행했던 것 같다. 그 덕분에 많이 배웠지만, 한 편으로 위에서 언급했던 조급함같은 것을 느끼고, 때때로 번아웃이 오지 않았나 싶었다. 3일 전이었나? 공부를 해야 하는데 다른 생각도 나고, 마음이 너무 조급해졌다. 최근 마음을 다스릴 때 명상을 한다는 친구의 얘기가 생각났고, 마침 유튜브의 신비한 알고리즘이 심호흡법 영상을 추천해주었다. 424 호흡법을 통해 잡생각을 버리는 방법에 대해 알게 되었고, 이를 통해 조급함을 약간은 털어낼 수 있었다.

휴식을 할 때에도, 쫓기듯 쉬는 경우가 많았던 것 같다. 물론 최종 프로젝트를 하는 지금은 이 방법이 맞다고 생각하지만, 최종 프로젝트가 끝난 뒤 개인 프로젝트를 하거나, 입사 후 업무를 할 때에는 휴식에 많은 비중을 두고, 휴식을 할 때에는 업무에 대한 걱정을 덜어놓는 연습을 해야겠다고 생각했다.

미국 여러 기업의 시스템 아키텍처를 언급해주신 부분은 매우 흥미로웠다. 그 회사들이 돈 잘 버는 회사란건 알았다. 그렇지만 기껏해야 나스닥의 주가 그래프만 쳐다봤지, 시스템 아키텍쳐를 볼 생각은 하지 못했던 것 같다. 회사를 볼 수 있는 차원이 늘어난 것 같아서 만족스러웠다.

마무리

쓰고나서보니, 대나무 숲에 내 일기장을 펼쳐놓고 외치는 느낌이라서 뭔가 쑥스러움이 없잖아 있는 것 같다.

그렇지만 이렇게 열심히 썼는데, 내 컴퓨터에만 두기엔 너무 아깝지 않은가!

그래서 업로드한다.

혹시 알까? 누군가 이 글을 보고 어떤 영감을 얻거나, 도움을 받을지도 모를 일이다. 부디 그랬으면 좋겠다.

마지막으로, 훌륭한 강의, 두런두런 클래스, 자료를 준비해주셨으며

이렇게 복기 글을 유도하심으로써 저 자신을 되돌아볼 수 있는 시간을 갖게 해주신

변성윤 마스터님 정말 감사합니다! (쏘카 호감도 +1)

이 글을 볼 미래의 나도, 지금의 나도, 과거의 나도 화이팅!

Special Thanks To

글을 작성할 때 옆에서 유튜브로 열심히 노래를 불러준 BOL4에게 감사 인사를 하고 싶다.

BOL4 - 25 (볼빨간사춘기 - 25)

https://www.youtube.com/watch?v=qUmfraj3Pdk

볼빨간 사춘기 인기곡 노래모음 best 36곡

https://www.youtube.com/watch?v=QnAP79aHhik

Konlpy를 사용하려던 중 만난 에러들을 기록하고자 한다.

module 'tweepy' has no attribute 'StreamListener'

별거 안하고

from konlpy.tag import komoran

를 하려고 했다. 근데 위의 에러가 떴다.

구글링 결과, tweepy의 버전이 4번대이면 StreamListener 뭐시기랑 충돌이 난다고 한다.

import tweepy
print(tweepy.__version__)

위 명령어로 버전을 확인할 수 있다.

버전을 확인한 뒤, 버전을 3.10.0으로 다운그레이드 해주자.

!pip uninstall tweepy --yes
!pip install tweepy==3.10.0

위 작업이 완료됐으면, 커널을 Restart해주자. 멍청하게 Restart할 생각을 하지 못해서, 위 작업을 몇 번 반복했는지 모르겠다. ㅠㅠ

jupyterlab No JVM shared library file (libjvm.so) found. Try setting up the JAVA_HOME environment variable properly.

from konlpy.tag import Hannanum 
hannanum = Hannanum()

print(hannanum.analyze(u'텍스트에서 형태소를 반환한다'))

아니, konlpy좀 씁시다,,,,

이번엔 JAVA_HOME이 적절하지 않다고 한다. 구글링에서 자바가 깔리지 않았다고 본 것 같기도 하다. 하여튼 뭔가를 처음 하려고 할 때 항상 속을 썩이는 녀석이다.

구글링 결과 두 명령어를 알게 되었고, 난 두 명령어를 연달아 입력하고 실행하여 해결하였다.

!apt-get update 
!apt install default-jdk -y

60~90초 정도의 시간이 지난 뒤, 잘 깔리는 것을 알 수 있었다.

누군가에게 도움이 됐으면 좋겠다.

# 23290 마법사 상어와 복제

def move_fish(shark_r, shark_c):
    global grounds
    temp_grounds = list()
    for r in range(1, 5):
        for c in range(1, 5):
            for idx in range(1, 9):
                if grounds[r][c][idx]:
                    direction = idx
                    orig_direction = direction
                    for _ in range(8):
                        cr = r + dr[direction]
                        cc = c + dc[direction]
                        # 범위 내에 있으면서 상어도 없고 냄새도 없다면
                        if 1 <= cr <= 4 and 1 <= cc <= 4 and (cr != shark_r or cc != shark_c) and smell[cr][cc] == 0:
                            temp_grounds.append([cr, cc, direction, grounds[r][c][idx]])
                            break
                        else:
                            direction -= 1
                            if direction <= 0:
                                direction += 8
                    # 그 자리에 있기
                    else:
                        temp_grounds.append([r, c, orig_direction, grounds[r][c][idx]])

    grounds = [[[0] * 9 for _ in range(5)] for _ in range(5)]
    for tr, tc, tdirection, num in temp_grounds:
        grounds[tr][tc][tdirection] += num
    return

#     0 좌 좌상 상 우상 우 우하 하 좌하
dr = [0, 0, -1, -1, -1, 0, 1, 1, 1]
dc = [0, -1, -1, 0, 1, 1, 1, 0, -1]

# 0, 상 좌 하 우
shark_dr = [0, -1, 0, 1, 0]
shark_dc = [0, 0, -1, 0, 1]

M, S = map(int, input().split())
grounds = [[[0] * 9 for _ in range(5)] for _ in range(5)]
smell = [[0] * 5 for _ in range(5)]
for _ in range(M):
    r, c, d = map(int, input().split())
    grounds[r][c][d] += 1

shark_r, shark_c = map(int, input().split())

for idx in range(1, S + 1):

    # 1. 상어가 모든 물고기에 복제 마법 시전
    copy_list = [[[0] * 9 for _ in range(5)] for _ in range(5)]
    for r in range(1, 5):
        for c in range(1, 5):
            for i in range(1, 9):
                copy_list[r][c][i] = grounds[r][c][i]

    # 2. 모든 물고기가 한 칸 이동
    move_fish(shark_r, shark_c)

    # 3. 상어가 연속해서 3칸 이동한다. 가장 물고기를 많이 먹을 수 있는 방법으로 이동
    # 경우의 수가 많다면 사전 순으로
    choice = list()
    maximum = 0
    temp_shark_r = 0
    temp_shark_c = 0

    temp_grounds_list = [[[0] * 9 for _ in range(5)] for _ in range(5)]
    for r in range(1, 5):
        for c in range(1, 5):
            for i in range(1, 9):
                temp_grounds_list[r][c][i] = grounds[r][c][i]

    for i in range(1, 5):
        cr1 = shark_r + shark_dr[i]
        cc1 = shark_c + shark_dc[i]
        if cr1 <= 0 or cr1 >= 5 or cc1 <= 0 or cc1 >= 5:
            continue
        sum1 = sum(temp_grounds_list[cr1][cc1])
        temp_grounds_list[cr1][cc1] = [0] * 9
        for j in range(1, 5):
            cr2 = cr1 + shark_dr[j]
            cc2 = cc1 + shark_dc[j]
            if cr2 <= 0 or cr2 >= 5 or cc2 <= 0 or cc2 >= 5:
                continue
            sum2 = sum(temp_grounds_list[cr2][cc2])
            temp_grounds_list[cr2][cc2] = [0] * 9
            for k in range(1, 5):
                cr3 = cr2 + shark_dr[k]
                cc3 = cc2 + shark_dc[k]
                if cr3 <= 0 or cr3 >= 5 or cc3 <= 0 or cc3 >= 5:
                    continue

                sum3 = sum(temp_grounds_list[cr3][cc3])
                # 물고기 최대로 많이 먹을 수 있는 방법
                if sum1 + sum2 + sum3 > maximum:
                    maximum = sum1 + sum2 + sum3
                    choice = [[cr1, cc1], [cr2, cc2], [cr3, cc3]]
                    temp_shark_r = cr3
                    temp_shark_c = cc3

                # 물고기 못먹을 때 방지
                if choice == []:
                    choice = [[cr1, cc1], [cr2, cc2], [cr3, cc3]]
                    temp_shark_r = cr3
                    temp_shark_c = cc3
            for i in range(1, 9):
                temp_grounds_list[cr2][cc2][i] = grounds[cr2][cc2][i]
        for i in range(1, 9):
            temp_grounds_list[cr1][cc1][i] = grounds[cr1][cc1][i]

    shark_r = temp_shark_r
    shark_c = temp_shark_c

    # 상어 이동, 물고기 제거됐다면 냄새를 남긴다.
    for cr, cc in choice:
        if sum(grounds[cr][cc]) > 0:
            # 물고기 먹기
            grounds[cr][cc] = [0] * 9
            smell[cr][cc] = idx

    # 4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
    for r in range(1, 5):
        for c in range(1, 5):
            if smell[r][c] + 2 <= idx:
                smell[r][c] = 0

    # 5.1에서 사용한 복제 마법이 완료된다.
    for r in range(1, 5):
        for c in range(1, 5):
            for i in range(1, 9):
                grounds[r][c][i] += copy_list[r][c][i]


# 숫자 세기
result = 0
for r in range(1, 5):
    for c in range(1, 5):
        for k in range(1, 9):
            result += grounds[r][c][k]

print(result)

헤맨 부분

문제 푸느라 너무 힘들었다.. 쉬는 시간 포함 세 시간 가량을 썼다.

상어가 연속해서 3칸을 이동할 때, 재귀 대신 3중 for문을 이용하여 계산하였다. 맨 처음엔 cr1 == cr3, cc1 == cc3처럼 조건에 맞지 않는 경우에만 continue하여 문제를 풀려 했으나, 잘 되지 않았다. 그래서 visited를 이용하여 방문했던 곳은 방문하지 않도록 만드려고 했으나, 마음만큼 잘 동작하지 않았다. 결정적으로, visited를 사용하면 되지 않는 예시가 있었다. 방문했던 곳이라도, maximum하게 생선을 먹을 수 있으며 사전순으로 앞쪽이라면 다시 방문해야 한다. 백준의 예제 입력 6번에서, visited를 사용하면 답으로 12가 출력된다. 방문했던 곳의 재방문을 허용해야 한다.

재방문을 허용하는 동시에, 재방문했을 경우 물고기의 score가 더해지면 안 된다. 이미 먹은 물고기이기 때문이다. 그렇다고 원본 grounds의 값을 수정할수도 없으므로, temp_grounds_list를 만들어 사용하였다.

문제에서 시키지 않았던 작업도 했었다. 상어 이동 후에 shark_r, shark_c의 물고기를 없애주는 작업도 해봤는데, 예제 5번, 8번에서 엉뚱한 정답이 출력되어 그만두었다.

다 풀고나서 제출했는데, 시간초과가 떴다. 맞왜틀,,,,,,,,,,

백준 질문 게시판에서 답을 찾을 수 있었다. list에 생선 방향을 계속 달고 다니기 때문이라고 한다. 생선을 리스트에 넣는 대신, 생선 숫자를 count한 list를 갖고 다니면 된다. 옛날에 배운 count 정렬이 생각난다.

생선 숫자를 count한 list를 갖고 다니라는 것은, 코드에서 grounds를 다 뜯어고쳐야 한다는 뜻이기도 하다. 고통의 시간 뒤에 코드를 뜯어고쳤고, 제출 후 정답 안내를 받았다.

문제를 잘 풀고 있지만, 소요 시간이 많이 걸리는 점이 다소 아쉽다.

화이팅!

# 20057 마법사 상어와 토네이도

def tornado(r, c, direction):
    out_value = 0
    temp_grounds = list()
    dir1 = direction
    dir2 = dir1 + 1
    dir3 = dir1 + 2
    dir4 = dir1 + 3
    dir2 %= 4
    dir3 %= 4
    dir4 %= 4

    cur_value = grounds[r][c]

    count_dirt = 0
    value1 = cur_value * 1 // 100
    value2 = cur_value * 2 // 100
    value5 = cur_value * 5 // 100
    value7 = cur_value * 7 // 100
    value10 = cur_value * 10 // 100
    # 좌측 기준
    # 위 한 칸
    cr = r + dr[dir2]
    cc = c + dc[dir2]
    if 1 <= cr <= N and 1 <= cc <= N:
        temp_grounds.append([cr, cc, value7])
    else:
        out_value += value7
    count_dirt += value7

    # 위 앞칸
    kr = cr + dr[dir1]
    kc = cc + dc[dir1]
    if 1 <= kr <= N and 1 <= kc <= N:
        temp_grounds.append([kr, kc, value10])
    else:
        out_value += value10
    count_dirt += value10

    # 위 뒤칸
    kr = cr + dr[dir3]
    kc = cc + dc[dir3]
    if 1 <= kr <= N and 1 <= kc <= N:
        temp_grounds.append([kr, kc, value1])
    else:
        out_value += value1
    count_dirt += value1

    # 위 위 칸
    kr = cr + dr[dir2]
    kc = cc + dc[dir2]
    if 1 <= kr <= N and 1 <= kc <= N:
        temp_grounds.append([kr, kc, value2])
    else:
        out_value += value2
    count_dirt += value2

    # 아래 한 칸
    cr = r + dr[dir4]
    cc = c + dc[dir4]
    if 1 <= cr <= N and 1 <= cc <= N:
        temp_grounds.append([cr, cc, value7])
    else:
        out_value += value7
    count_dirt += value7

    # 아래 앞칸
    kr = cr + dr[dir1]
    kc = cc + dc[dir1]
    if 1 <= kr <= N and 1 <= kc <= N:
        temp_grounds.append([kr, kc, value10])
    else:
        out_value += value10
    count_dirt += value10

    # 아래 뒤칸
    kr = cr + dr[dir3]
    kc = cc + dc[dir3]
    if 1 <= kr <= N and 1 <= kc <= N:
        temp_grounds.append([kr, kc, value1])
    else:
        out_value += value1
    count_dirt += value1

    # 아래 아래 칸
    kr = cr + dr[dir4]
    kc = cc + dc[dir4]
    if 1 <= kr <= N and 1 <= kc <= N:
        temp_grounds.append([kr, kc, value2])
    else:
        out_value += value2
    count_dirt += value2

    # 앞 앞칸
    cr = r + dr[dir1] * 2
    cc = c + dc[dir1] * 2
    if 1 <= cr <= N and 1 <= cc <= N:
        temp_grounds.append([cr, cc, value5])
    else:
        out_value += value5
    count_dirt += value5

    # 바로 앞칸
    cr = r + dr[dir1]
    cc = c + dc[dir1]
    temp_vaiue = cur_value - count_dirt
    if 1 <= cr <= N and 1 <= cc <= N:
        temp_grounds.append([cr, cc, temp_vaiue])
    else:
        out_value += temp_vaiue

    grounds[r][c] = 0
    for tr, tc, t_value in temp_grounds:
        grounds[tr][tc] += t_value

    return out_value


# 좌 하 우 상
dr = [0, 1, 0, -1]
dc = [-1, 0, 1, 0]

N = int(input())
grounds = [[0] * (N + 1)] + [[0] + list(map(int, input().split())) for _ in range(N)]

temp_r = N // 2 + 1
temp_c = N // 2 + 1

result = 0
# 한 칸씩 움직임
num = 1
direction = 0
while 0 < temp_r <= N and 0 < temp_c <= N:
    direction %= 4
    for _ in range(num):
        temp_r += dr[direction]
        temp_c += dc[direction]
        if temp_c == 0 or temp_r == 0:
            break
        # 토네이도 작업
        result += tornado(temp_r, temp_c, direction)

    direction += 1
    if direction % 2 == 0:
        num += 1

print(result)

헤맨 부분

일단, 문제가 이해가 가지 않았다. 알파(a)에 어떤 값이 들어가는지 잘 모르겠어서, 질문 게시판을 쭉 읽어보았다. 55%로 하면 될 것 같았는데, 나눗셈을 할 때 나머지로 나누어 떨어지는 값들까지 모두 고려하여 a에 넣어야 하는 것이었다.

소용돌이치며 이동하는 것을 구현하는 것도 처음엔 고통이었는데, 예전에 비슷한 문제를 푼 적이 있어 생각보단 빠르게 구현해냈다.

tornado를 구현한 뒤 제출했을 때, 시간 초과가 발생했다.

또다시 무너진 순두부멘탈. 질문 게시판에도 시간 초과 관련 게시글은 없었고, 구글링을 통해 약간의 힌트를 얻을 수 있었다.

N=500이므로, N^2 = 250,000이다. (N <= 499지만 편의상 500으로 하자)

내 기존 코드는, tornado 함수 안에서도 N*1, N*1 크기를 가진 temp_grounds를 만들었었다.

temp_grounds를 정의해준 뒤, 전체 r과 c를 돌며 덧셈을 해주었다.

N=500일 때, 이미 코드의 하단에서 temp_r, temp_c를 찾으며 빙글빙글 돌며 250,000개의 연산이 발생한다. 여기에서 temp_grounds가 또 250,000번의 연산을 해주면, 어마어마한 연산 숫자가 발생한다.

통상적으로 python에서 1초에 1억 번의 연산이 가능하다고 한다. 100^4 = 10,000^2 = 100,000,000으로, 100을 4제곱했을 때의 연산 숫자이다. 나는 500을 4제곱했으므로, 1억이 훌쩍 넘는 연산을 하였고, 시간 초과가 나는 것이다.

해법을 얻은 뒤, temp_grounds를 단순 리스트 형식으로 처리했으며, 조건이 맞을 때의 r, c, value를 입력받고 마지막에 이를 더해줌으로써 처리하였다.

실전에서 시간 초과가 발생했으면 아찔했을 것 같다. 검색을 했지만, 잘 극복해내서 다행이다.

# 23291 어항 정리

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def rotate(x, y):
    temp_grounds = [[0] * x for _ in range(y)]

    for r in range(x):
        for c in range(y):
            temp_grounds[c][x - r - 1] = cur_grounds[r][c]
    return temp_grounds


def make_one():
    global grounds
    temp_grounds = list()
    for r in range(len(grounds)):
        for c in range(len(grounds[0])):
            if grounds[r][c] != -1:
                temp_grounds.append(grounds[r][c])

    grounds = temp_grounds
    return

def cal_fish():
    global grounds
    temp_grounds = [[0] * len(grounds[0]) for _ in range(len(grounds))]
    for r in range(len(grounds)):
        for c in range(len(grounds[0])):
            if grounds[r][c] == -1:
                continue
            for i in range(4):
                cr = r + dr[i]
                cc = c + dc[i]
                # 범위 내에 있다면
                if 0 <= cr < len(grounds) and 0 <= cc < len(grounds[0]):
                    if grounds[cr][cc] == -1:
                        continue
                    cur_num = grounds[r][c] - grounds[cr][cc]
                    cur_num //= 5
                    if cur_num <= 0:
                        continue
                    temp_grounds[cr][cc] += cur_num
                    temp_grounds[r][c] -= cur_num

    for r in range(len(grounds)):
        for c in range(len(grounds[0])):
            grounds[r][c] += temp_grounds[r][c]
    return


N, K = map(int, input().split())
fishes = list(map(int, input().split()))
grounds = [[fish] for fish in fishes]
result = 0

while True:
    # 물고기 수 최소, 최대 어항 구하기
    minimum = 10001
    maximum = 0
    for ground in grounds:
        minimum = min(ground[0], minimum)
        maximum = max(ground[0], maximum)
    if maximum - minimum <= K:
        break
    result += 1

    # 최소인 어항 += 1
    for i in range(len(grounds)):
        if grounds[i][0] == minimum:
            grounds[i][0] += 1

    # 가장 왼쪽에 있는 어항을 오른쪽 위에 올리기
    up_ground = grounds.pop(0)
    grounds[0].extend(up_ground)

    # 2개 이상 쌓여있는 어항을 모두 공중부양, 시계 방향으로 90도 회전
    while True:
        idx = 0
        while len(grounds[idx]) >= 2:
            idx += 1
            if len(grounds) - idx < len(grounds[0]):
                break

        # 높이가 남은 어항 길이보다 크면 계속 진행
        if len(grounds) - idx < len(grounds[0]):
            break

        cur_grounds = list()
        for _ in range(idx):
            cur_grounds.append(grounds.pop(0))

        ready_grounds = rotate(idx, len(cur_grounds[0]))
        for i in range(len(ready_grounds)):
            grounds[i].extend(ready_grounds[i])

    # 높이 맞추기 위해서 0 padding 추가
    height = len(grounds[0])
    for i in range(len(grounds)):
        while len(grounds[i]) < height:
            grounds[i].append(-1)

    # 모든 인접한 두 어항에 대해서 물고기 수의 차이를 구한다.
    cal_fish()

    # 일렬로 펴기
    make_one()

    # 가운데 중심으로 N/2개 공중부양시켜 180도 회전, 오른쪽 N/2개 위에 놓아야 한다.
    for _ in range(2):
        idx = len(grounds) // 2
        temp_grounds = list()
        # 숫자 세기
        while idx:
            temp_grounds.append(grounds.pop(0))
            idx -= 1

        # 두 번째 진입은 list로 함 - 돌려서 넣어주기
        if type(temp_grounds[0]) == list:
            rever_temp = [[0] * len(temp_grounds[0]) for _ in range(len(temp_grounds))]
            for i in range(len(temp_grounds)):
                for j in range(len(temp_grounds[0])):
                    rever_temp[i][j] = temp_grounds[i][len(temp_grounds[0]) - j - 1]

            # 180도 돌려서 넣기
            for i in range(len(grounds)):
                grounds[i].extend(rever_temp.pop())
        # 첫 번째 진입이라면
        else:
            # 남은 그라운드 임의로 list로 만들어주기.
            grounds = [[ground] for ground in grounds]
            # 180도 돌려서 넣기
            for i in range(len(grounds)):
                grounds[i].append(temp_grounds.pop())

    # 물고기 조절 작업하기
    cal_fish()

    # 일렬로 펴기
    make_one()

    grounds = [[ground] for ground in grounds]


print(result)

자세한 리뷰는 나중에 마음이 내킬 때 하겠다.

첫 플레티넘 풀이에 성공하였다. 만세!

헤맨 부분

90도 회전시킬 때, 맨 위, 왼쪽이 (0, 0), 맨 위, 오른쪽이(0, c - 1), 맨 아래, 오른쪽이(r - 1, c - 1)이어야 한다는 편견에 사로잡혔다.

처음 문제풀이를 시도했을 때는, 이 때문에 잘 풀지 못했다.

두 번째 문제를 풀기 전과 푸는 과정에서 이 문제를 인지하고, 문제 조건에 맞게 맨 아래 왼쪽이 (0, 0), 맨 위 왼쪽이 (0, c - 1), 맨 위 오른쪽이(r - 1, c - 1) 처럼 되는 것을 인지한 후에 풀었다.

pycharm에서 돌려보던 중, 에러가 있는 부분을 발견했다.

while len(grounds[idx]) >= 2:
    idx += 1

while 부분에서 에러가 났다. print를 찍어본 뒤, grounds의 index가 초과될 수 있음을 인지하고 다음과 같이 수정하였다.

while len(grounds[idx]) >= 2:
    idx += 1
    if len(grounds) - idx < len(grounds[0]):
        break

플레티넘 명성에 맞게 엄청 어렵지는 않았다. (사실 이제 한 문제 푼 사람이 난이도를 매기는 것도 웃기다.) 하지만, 낯선 환경인 실전에서 1시간 30분 내에 이 문제를 풀기는 정말 쉽지 않을 것 같다.

처음 문제를 풀 때 1시간 30분 가량을 소모한 뒤 결국 회전에서 막혔고, 두 번째 시도에서 대략 1시간 10~20분만에 푼 것 같다.

더 정확하고 빠르게 풀 수 있도록, 반복숙달해야겠다.

상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다. 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현한다. 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. (i, j)는 격자의 i번 행, j번 열을 의미하고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸이라고 한다.

블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다. 블록 그룹의 기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이다.

오늘은 이 게임에 오토 플레이 기능을 만드려고 한다. 오토 플레이는 다음과 같은 과정이 블록 그룹이 존재하는 동안 계속해서 반복되어야 한다.

1. 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
2. 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.
3. 격자에 중력이 작용한다.
4. 격자가 90도 반시계 방향으로 회전한다.
5. 다시 격자에 중력이 작용한다.

오토 플레이가 모두 끝났을 때 획득한 점수의 합을 구해보자.

입력 첫째 줄에 격자 한 변의 크기 N, 색상의 개수 M이 주어진다.

둘째 줄부터 N개의 줄에 격자의 칸에 들어있는 블록의 정보가 1번 행부터 N번 행까지 순서대로 주어진다. 각 행에 대한 정보는 1열부터 N열까지 순서대로 주어진다. 입력으로 주어지는 칸의 정보는 -1, 0, M이하의 자연수로만 이루어져 있다.

출력 첫째 줄에 획득한 점수의 합을 출력한다.

제한 1 ≤ N ≤ 20 1 ≤ M ≤ 5

# 21609 상어 중학교

def gravity():
    global blocks
    temp = 0
    for c in range(N):
        for r in range(N - 1, -1, -1):
            # 아래 블록
            cur_r = r
            while cur_r > 0 and blocks[cur_r][c] == -2:
                cur_r -= 1
            if cur_r != r and blocks[cur_r][c] != -1:
                temp = blocks[cur_r][c]
                blocks[cur_r][c] = -2
                blocks[r][c] = temp

    return


def rotate():
    global blocks
    temp_blocks = [[0] * N for _ in range(N)]
    for r in range(N):
        for c in range(N):
            temp_blocks[r][c] = blocks[c][N - 1 - r]

    blocks = temp_blocks[:]
    return

# 상 좌 하 우
dr = [-1, 0, 1, 0]
dc = [0, -1, 0, 1]

N, M = map(int, input().split())
blocks = [list(map(int, input().split())) for _ in range(N)]

score = 0
while True:
    # 1. 가장 큰 블록 그룹 찾기
    largest_block = list()
    largest_rainbow = 0
    visited = [[0] * N for _ in range(N)]
    for r in range(N):
        for c in range(N):
            if visited[r][c] == 1:
                continue
            cur_block = blocks[r][c]
            if cur_block <= 0:
                continue
            visited[r][c] = 1
            result_list = [[r, c]]
            queue = [[r, c]]
            rainbow_num = 0
            while queue:
                qr, qc = queue.pop(0)
                for i in range(4):
                    cr = qr + dr[i]
                    cc = qc + dc[i]
                    if 0 <= cr < N and 0 <= cc < N and visited[cr][cc] == 0 and (
                            blocks[cr][cc] == 0 or blocks[cr][cc] == cur_block):
                        result_list.append([cr, cc])
                        visited[cr][cc] = 1
                        if blocks[cr][cc] == 0:
                            rainbow_num += 1
                            visited[cr][cc] = 2

                        if len(largest_block) < len(result_list):
                            largest_block = result_list[:]
                            largest_rainbow = rainbow_num
                        elif len(largest_block) == len(result_list) and largest_rainbow <= rainbow_num:
                            largest_block = result_list[:]
                            largest_rainbow = rainbow_num
                        queue.append([cr, cc])
            # 무지개 visited 초기화
            for tr in range(N):
                for tc in range(N):
                    if visited[tr][tc] == 2:
                        visited[tr][tc] = 0

    # 1-1 block 갯수가 1 이하면 break
    if len(largest_block) <= 1:
        break
    else:
        score += len(largest_block) ** 2

    # 2. 찾은 블록들 제거하기
    for tr, tc in largest_block:
        blocks[tr][tc] = -2

    # 3. 중력
    gravity()

    # 4. 반시계 90도
    rotate()

    # 5. 중력
    gravity()

print(score)

좋았던 점

예전에 봤던 문제였다. 그 땐 손도 대지 못했고, 지금은 풀어냈다. 친구가 카페에 있어서, 노트북을 들고 가서 코드를 작성했다. (2시간 가량) 실제 시험 환경에 대비한 점이 만족스럽다. gravity, rotate를 구현할 때 함수를 따로 만들어서 구현해야겠다고 생각했고, 잘 구현해냈다. 처음 만든 코드에서 많은 부분을 고치지 않고 문제를 해결했다.

1시간 ~ 1시간 30분만에 코드 골격은 완성되었다. 좀 헤매서 2시간 30분 가량 소요되었다.

헤맨 부분

quque와 result_list를 따로 구현할 생각을 한 번에 하지 못했다. 주어진 예시에서, 최대 rainbow 갯수가 잘 구해지지 않아 20~30분 가량 헤맸다. result_list를 따로 만들어준 뒤, 문제를 해결할 수 있었다.

1, 3번 예시는 맞았는데 2번 예시에서 틀린 답이 출력되었다. 하나하나 그려보며, 코드를 따라가며 어디가 틀렸는지 디버깅해보았다. 디버깅 과정에서 큰 틀의 코드는 다 맞는데, 작은 부분에서 틀렸을 거란 확신이 있었다. gravity, rotate 함수는 잘 동작하는 것을 구현 직후 확인하였다. 문제 조건을 확인하던 중, 다음을 발견했다.

크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.

무지개 블록의 수가 같을 때, 큰 행 / 큰 열을 찾아야 한다는 조건이었다.

다음 코드를 수정하여 문제를 해결하였다.

# 수정 전
elif len(largest_block) == len(result_list) and largest_rainbow < rainbow_num:

# 수정 후
elif len(largest_block) == len(result_list) and largest_rainbow <= rainbow_num:

무지개 블록의 수가 같을 때도 확인함으로써, r, c가 더 크면서 무지개 블록이 같을 때를 확인할 수 있었다.

위를 수정한 이후, 주어진 세 개의 입력에서 모두 정답 출력이 나왔고, 제출했다.

제출하자마자 틀렸다는 안내를 받았다.

카페에서의 공부를 정리하고 집에 오는 길에, r, c의 크기를 비교하는 로직이 틀렸을 것이란 예측을 하고 코드를 다시 봤다.

visited가 for문 안에 있어서, r, c를 탐색할 때마다 초기화되는 것을 발견하고, 이를 수정해주었다.

# 수정 전
    for r in range(N):
        for c in range(N):
        ...
        visited = [[0] * N for _ in range(N)]

# 수정 후
    visited = [[0] * N for _ in range(N)]
    for r in range(N):
        for c in range(N):

이렇게 고쳤는데도, 제출하자마자 틀렸다는 안내를 받았다.

고민 결과, 자연수(일반 블럭)는 방문했을 경우 visited 처리를 해주면 되지만, 무지개 블럭(0)의 경우 다른 블록에서 다시 사용해볼 수 있음을 알게 되었다.

# 수정 전
visited[cr][cc] = 1
if blocks[cr][cc] == 0:
    rainbow_num += 1

# 수정 후
visited[cr][cc] = 1
if blocks[cr][cc] == 0:
    rainbow_num += 1
    visited[cr][cc] = 0

무지개 블록일 경우, visited를 0으로 만들어줬다. 그 결과, 제출시에 시간 초과가 발생하였다.

원하는거 다 들어줬는데 왜 안돼... 맞왜틀...

deque도 써보고, import sys input = sys.stdin.readline을 써도 어림도 없었다. 이런저런 코드를 고쳐보던 중, pycharm 상에서 출력이 나오지 않는 것을 발견하였다. 왜 안나오지?

고민 끝에, 무지개블럭 옆에 무지개블럭이 있으면, visited = 0으로 되어서, 무지개블럭 사이를 왔다갔다하느라 while queue를 탈출하지 못한다는 결론을 내렸다.

그래서, 무지개 블럭은 visited = 1이 아닌 다른 숫자, visited = 2로 설정해놓은 뒤, queue를 탈출하고 나서 다음 r, c가 사용하기 전 무지개 블럭의 visited = 0으로 바꿔놔야겠다는 생각을 했다.

# 수정 전
visited[cr][cc] = 1
if blocks[cr][cc] == 0:
    rainbow_num += 1
    visited[cr][cc] = 0

# 수정 후
visited[cr][cc] = 1
if blocks[cr][cc] == 0:
    rainbow_num += 1
    visited[cr][cc] = 2

# 수정 후 queue 밑에 새로 추가된 부분
# 무지개 visited 초기화
for tr in range(N):
  for tc in range(N):
    if visited[tr][tc] == 2:
        visited[tr][tc] = 0

이렇게 해서, 맞았다.

정답의 감동..

무지개 블럭이 문제라는 것을 인지하고 나서, 백준 질문 게시판을 슥 보았다. 왜 시간초과가 나는지 이해하지 못한 시점이었다. 질문 글의 제목을 통해 무지개 블럭이 포인트라는 것을 다시 인지하였다.

불행하게도 시간초과 관련 게시물은 없어서, 다시 혼자 연구하다가 풀게 되었다.

문제를 처음 마주했을 때, '이게 무슨 소리여? 내가 이걸 풀 수 있을까?' 라고 생각했는데, 잘 풀어내어 만족스럽다.

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

입력 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

출력 상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.

# 19236 청소년 상어

def move_fish(idx, r, c, dir):
    for i in range(8):
        cur_dir = dir + i
        if cur_dir >= 9:
            cur_dir -= 8

        cr = r + dr[cur_dir]
        cc = c + dc[cur_dir]
        # 범위 안에 있으면서 숫자가 맞을 경우
        if 0 <= cr < 4 and 0 <= cc < 4 and 0 <= shark_fish[cr][cc][0] <= 16:
            change_fish(r, c, cr, cc, cur_dir)
            break

    return


def change_fish(r, c, cr, cc, cur_dir):
    temp_fish = shark_fish[r][c][0]
    shark_fish[r][c] = shark_fish[cr][cc]
    shark_fish[cr][cc] = [temp_fish, cur_dir]
    return


# 0 상 좌상 좌 좌하 하 우하 우 우상
dr = [0, -1, -1, 0, 1, 1, 1, 0, -1]
dc = [0, 0, -1, -1, -1, 0, 1, 1, 1]

fishes = [[0] * 4 for _ in range(4)]

for i in range(4):
    numbers = list(map(int, input().split()))
    fishes[i][0] = [numbers[0], numbers[1]]
    fishes[i][1] = [numbers[2], numbers[3]]
    fishes[i][2] = [numbers[4], numbers[5]]
    fishes[i][3] = [numbers[6], numbers[7]]

# 상어 표시
shark_dir = fishes[0][0][1]

temp_fish = [fish[:] for fish in fishes]
# r, c, dir, 잡아먹은 상어 숫자, 그 때의 fish 배열, level
shark_list = [[0, 0, shark_dir, temp_fish[0][0][0], temp_fish[:], 0]]
fishes[0][0][0] = 0 # 상어 표시
maximum_score = -1

while shark_list:
    # 물고기 옮기기
    shark_pos = shark_list.pop(0)

    shark_r = shark_pos[0]
    shark_c = shark_pos[1]
    shark_dir = shark_pos[2]
    shark_eat = shark_pos[3]
    shark_fish = list()
    for pos in shark_pos[4]:
        temp_list = list()
        for po in pos:
            temp_list.append(po[:])
        shark_fish.append(temp_list[:])
    shark_level = shark_pos[5]

    # 상어가 있던 곳 청소: -1을 0으로 만들어주기
    for r in range(4):
        for c in range(4):
            if shark_fish[r][c][0] == -1:
                shark_fish[r][c][0] = 0
    # 상어가 현재 있는 곳을 -1로 만들어주기
    shark_fish[shark_r][shark_c][0] = -1

    # 물고기 이동
    visited = [0] * 17
    for idx in range(1, 17):
        for r in range(4):
            for c in range(4):
                # 아직 이동하지 않은 물고기들 이동시키기
                if shark_fish[r][c][0] == idx and visited[idx] == 0:
                    visited[idx] = 1
                    move_fish(idx, r, c, shark_fish[r][c][1])
                    break

    # 상어 이동
    # ori_shark_r = shark_r
    # ori_shark_c = shark_c
    while 0 <= shark_r < 4 and 0 <= shark_c < 4:
        # 상어 이동
        shark_r += dr[shark_dir]
        shark_c += dc[shark_dir]

        # 범위 안에 있고 잡아먹을 수 있는 곳이라면
        if 0 <= shark_r < 4 and 0 <= shark_c < 4 and 1 <= shark_fish[shark_r][shark_c][0] < 17:
            temp_fish = [shark[:] for shark in shark_fish]
            # 상어가 잡아먹음
            shark_eat = shark_pos[3] + temp_fish[shark_r][shark_c][0]
            temp_shark_dir = temp_fish[shark_r][shark_c][1]
            maximum_score = max(shark_eat, maximum_score)
            shark_list.append([shark_r, shark_c, temp_shark_dir, shark_eat, temp_fish[:], shark_level + 1])

print(maximum_score)

소요시간: 50분 + 2시간 22분, 14:00 ~ 14:50, 22:16 ~ 00:40

틀린 부분 정리

처음에, 삼중 리스트를 쓸 생각을 하지 못했다. 상어가 물고기를 잡아먹은 결과판을 리스트 안에 들고 다니면서 계산하기까지 많은 시간이 소요되었다.

아이디어를 떠올리고 나서는, 물고기의 이동 함수와 상어가 이동하는 논리의 호환이 맞지 않았다. visited 리스트를 만드는 등 물고기를 이동시키는 함수를 다 구현한 뒤에 이 문제를 깨달았다.

물고기는 주어진 입력판인 fishes에서 움직이는데, 상어는 임의로 새로 만든 배열(위 코드엔 없다.)인 new_shark_list에서 움직였기 때문에, 상어가 물고기들을 잡아먹을 때 물고기의 움직임이 반영되지 않았다.

눈물을 머금고 물고기를 이동시키는 함수를 다시 건드렸다. 건드리기 전엔 대규모 공사가 예상되었는데, 다행히 생각보다 빠르게 정리되었다. 기존에 짰던 코드에서 살릴 수 있는 부분과, 응용할 수 있는 부분이 많아서 좋았다.

삼중리스트이기 때문에 deepcopy 문제가 발생할 것이라고 예상하였다. 이중리스트에서는 [temp[:] for temp in temp_list]와 같은 방식으로 deepcopy 문제를 해결했다. 결론만 얘기하면, 이는 기우였다. 삼중리스트를 사용하지만 삼중리스트에서 물고기, 상어가 배열되어 있는 배열판만 건드리면 됐기 때문에, 즉 이중리스트만 copy하면 됐기 때문에 위의 방식으로 해결할 수 있었다. 다만, 삼중리스트를 연구하는 과정에서 [te[:] for temp in temp_list for te in temp] 와 같은 방식으로 deepcopy 문제를 해결할 수 있다는 것도 알게 되었다.

while 0 <= shark_r < 4 and 0 <= shark_c < 4: 을 사용하여 상어가 이동할 수 있는 만큼 이동하였고, temp_fish를 사용하여 원 함수인 shark_fish가 계산 중 훼손되는 것을 방지하고자 하였다.

디버깅 중 상어가 현재 위치의 물고기를 두 번 먹는 에러가 있음을 인지하게 되었다. [1, 1]에 12번 물고기가 있었다면, 연산 과정에서 다음 점수는 24가 되는 식이었다. 이미 먹은 물고기를 다시 먹는 것은 있을 수 없는 일이므로, 코드에서 어느 부분이 잘못되었음을 알게 되었고 이를 찾아다녔다.

최초엔 물고기의 이동을 마치고 나서 상어 위치의 물고기 번호를 0으로 설정해주어 위의 문제를 해결하였다.

그러나, 문제 로직상 최초 상어가 [0, 0]에 들어간 뒤엔, 물고기가 상어의 눈치를 보며 이동해야 한다. 즉, 물고기를 이동시키기 전에 상어의 위치를 정해줘야 한다. 그래야 물고기들이 상어 위치에 들어가지 않는다. 회색 부분을 인지한 뒤 물고기가 이동하기 전, 상어 위치의 물고기 번호를 0으로 바꿔주었다. 예제 1, 2, 4번은 잘 돌아갔지만, 3번에서 58이라는 희한한 답이 나와 다시 디버깅을 하였다.

print를 많이 찍어보며, 물고기가 상어 자리도 자유롭게 돌아다닐 수 있음을 알게 되었다. 물고기가 이동하기 전에 상어의 위치에서 물고기 번호를 -1으로 바꿔주었다.

또다시 엉뚱한 출력이 나와 확인해보니, 상어가 이전에 있던 위치에서 물고기 번호가 -1로 남아있는 문제를 확인하였다. 물고기 번호가 -1인 부분을 모두 0으로 바꿔준 뒤에, 상어가 있는 곳만 물고기 번호를 0으로 바꿔주었고, 정답을 얻어낼 수 있었다.

삼중리스트 개념을 떠올리기 전에, 정말 어려웠다. 어떻게 원판을 보존할 수 있지? 삼중리스트를 보며 많이 좌절했다. 내가 풀 수 있을까? 삼중리스트를 해결하고 나서는, 물고기의 위치를 계속 데리고 다니며 물고기와 상어를 이동시키는 로직을 구상하며 정말 힘들었다. 어떻게 구현할 수 있지? 다 했다고 생각했는데, 답이 틀리게 나올 때도 절망스러웠다. 맞왜틀,, 비록 오랜 시간이 걸렸지만 무려 '백준 질문검색'을 참고하지 않고 푼 내 자신을 칭찬하고 싶다.

모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다.

이하 생략

행이나 열이 타일로 가득찬 경우와 연한 칸에 블록이 있는 경우가 동시에 발생할 수 있다. 이 경우에는 행이나 열이 타일로 가득 찬 경우가 없을 때까지 점수를 획득하는 과정이 모두 진행된 후, 연한 칸에 블록이 있는 경우를 처리해야 한다.

블록은 보드에 놓인 이후에 다른 블록과 합쳐지지 않는다. 블록을 놓은 위치가 순서대로 주어졌을 때, 얻은 점수와 초록색 보드와 파란색 보드에 타일이 있는 칸의 개수를 모두 구해보자.

입력 첫째 줄에 블록을 놓은 횟수 N(1 ≤ N ≤ 10,000)이 주어진다.

둘째 줄부터 N개의 줄에 블록을 놓은 정보가 한 줄에 하나씩 순서대로 주어지며, t x y와 같은 형태이다.

t = 1: 크기가 1×1인 블록을 (x, y)에 놓은 경우 t = 2: 크기가 1×2인 블록을 (x, y), (x, y+1)에 놓은 경우 t = 3: 크기가 2×1인 블록을 (x, y), (x+1, y)에 놓은 경우 블록이 차지하는 칸이 빨간색 칸의 경계를 넘어가는 경우는 입력으로 주어지지 않는다.

출력 첫째 줄에 블록을 모두 놓았을 때 얻은 점수를 출력한다.

둘째 줄에는 파란색 보드와 초록색 보드에서 타일이 들어있는 칸의 개수를 출력한다.

예제 입력 1 1 1 1 1 예제 출력 1 0 2 <그림 3>과 같다.

예제 입력 6 7 1 1 1 2 3 0 3 2 2 3 2 3 3 1 3 2 0 0 3 2 0 예제 출력 6 1 18 <그림 10>과 같다.

예제 입력 7 8 1 1 1 2 3 0 3 2 2 3 2 3 3 1 3 2 0 0 3 2 0 3 1 2 예제 출력 7 2 15 <그림 13>과 같다.

코드

# 20061 모노미노도미노 2

# t 모양: ㅇ, ㅡ, ㅣ
def blue_insert(t, x):
    c_idx = 0
    r = x
    if t == 1:
        while blue[r][c_idx] == 0 and c_idx < 5:
            c_idx += 1
        if blue[r][c_idx] == 1:
            c_idx -= 1

    elif t == 2:
        while blue[r][c_idx] == 0 and blue[r][c_idx + 1] == 0 and c_idx < 4:
            c_idx += 1
        if blue[r][c_idx] == 1 or blue[r][c_idx + 1] == 1:
            c_idx -= 1
        blue[r][c_idx + 1] = 1

    elif t == 3:
        while blue[r][c_idx] == 0 and blue[r + 1][c_idx] == 0 and c_idx < 5:
            c_idx += 1
        if blue[r][c_idx] == 1 or blue[r + 1][c_idx] == 1:
            c_idx -= 1
        blue[r + 1][c_idx] = 1

    blue[r][c_idx] = 1


def get_blue_score():
    cnt = 0
    for c in range(2, 6):
        for r in range(4):
            if blue[r][c] == 0:
                break
        else:
            cnt += 1
            for r in range(4):
                blue[r][c] = 0

            # 터진 것 채우기
            for temp_c in range(c, 0, -1):
                for r in range(4):
                    blue[r][temp_c] = blue[r][temp_c - 1]
                    blue[r][temp_c - 1] = 0

    return cnt


def push_blue():
    global blue
    cur_c = -1
    for c in range(2):
        for r in range(4):
            if blue[r][c] == 1:
                cur_c = c
                break
        if cur_c != -1:
            break
    # 밝은 곳에 숫자가 없으면 return
    if cur_c == -1:
        return

    temp_blue = [[0] * 6 for _ in range(4)]
    push_num = 0
    # 두 칸 밀기
    if cur_c == 0:
        push_num = 2
    # 한 칸 밀기
    elif cur_c == 1:
        push_num = 1

    for c in range(2, 6):
        for r in range(4):
            temp_blue[r][c] = blue[r][c - push_num]

    blue = [temp[:] for temp in temp_blue]


# t 모양: ㅇ, ㅡ, ㅣ
def green_insert(t, y):
    r_idx = 0
    c = y
    if t == 1:
        while green[r_idx][c] == 0 and r_idx < 5:
            r_idx += 1
        if green[r_idx][c] == 1:
            r_idx -= 1

    elif t == 2:
        while green[r_idx][c] == 0 and green[r_idx][c + 1] == 0 and r_idx < 5:
            r_idx += 1
        if green[r_idx][c] == 1 or green[r_idx][c + 1] == 1:
            r_idx -= 1
        green[r_idx][c + 1] = 1

    elif t == 3:
        while green[r_idx][c] == 0 and green[r_idx + 1][c] == 0 and r_idx < 4:
            r_idx += 1
        if green[r_idx][c] == 1 or green[r_idx + 1][c] == 1:
            r_idx -= 1
        green[r_idx + 1][c] = 1

    green[r_idx][c] = 1


def get_green_score():
    cnt = 0
    for r in range(2, 6):
        for c in range(4):
            if green[r][c] == 0:
                break
        else:
            cnt += 1
            for c in range(4):
                green[r][c] = 0

            # 터진 것 채우기
            for temp_r in range(r, 0, -1):
                for c in range(4):
                    green[temp_r][c] = green[temp_r - 1][c]
                    green[temp_r - 1][c] = 0

    return cnt


def push_green():
    global green
    cur_r = -1
    for r in range(2):
        for c in range(4):
            if green[r][c] == 1:
                cur_r = r
                break
        if cur_r != -1:
            break

    # 밝은 곳에 숫자가 없으면 return
    if cur_r == -1:
        return

    temp_green = [[0] * 4 for _ in range(6)]
    push_num = 0
    # 두 칸 밀기
    if cur_r == 0:
        push_num = 2
    # 한 칸 밀기
    elif cur_r == 1:
        push_num = 1

    for r in range(2, 6):
        for c in range(4):
            temp_green[r][c] = green[r - push_num][c]

    green = [temp[:] for temp in temp_green]


N = int(input())

blue = [[0] * 6 for _ in range(4)]
green = [[0] * 4 for _ in range(6)]
score = 0

for _ in range(N):
    t, x, y = map(int, input().split())

    # Blue에 블록 넣기
    blue_insert(t, x)
    # 점수 획득
    score += get_blue_score()
    # 연한 칸 블록 있으면 밀기
    push_blue()


    # Green에 블록 넣기
    green_insert(t, y)
    # 점수 획득
    score += get_green_score()
    # 연한 칸 블록 있으면 밀기
    push_green()

block_cnt = 0
# 파란색 타일 갯수 세기

for r in range(4):
    for c in range(2, 6):
        if blue[r][c] == 1:
            block_cnt += 1

# 초록색 타일 갯수 세기
for r in range(2, 6):
    for c in range(4):
        if green[r][c] == 1:
            block_cnt += 1

print(score)
print(block_cnt)

틀린 부분

점수를 획득하고 나서, 터진 행/열의 위쪽/왼쪽에 있는 블록들을 땡겨오는 작업을 하지 않아 제출 직후 틀렸습니다. 를 볼 수 있었다.

틀린 예제 입력 4 2 3 0 2 3 0 2 1 0 2 1 2

위의 항목만 고친 뒤 정답을 맞출 수 있었다.

삼성 기출문제를 슥 훑어보기도 했고, 구현/시뮬레이션 알고리즘을 반복해서 풀다보니, 점점 구현 능력이 늘고 소요 시간이 줄어들고 있다.

효율적으로 함수를 만들어 푸는 스킬도 늘어나고 있는 것 같다.

화이팅!!

최근에 폭우로 인해 일부 지역이 침수되어 침수된 지역으로는 이동할 수 없게 되었다. 하지만 강산이는 출석 이벤트를 위해 하루도 빠짐없이 PC방을 가야 한다.

강산이는 PC방까지 상, 하, 좌, 우 방향으로만 이동하며, 한 번 이동할 때의 거리는 1이다. 또한, 강산이는 게임을 빨리하러 가야 하기 때문에 집에서 PC방까지 최단경로로 움직인다.

강산이의 집의 좌표 (H, H)와 PC방의 좌표 (N, N)이 주어지고 좌표평면 위 (x, y)에서 y > x인 곳은 침수되었다고 할 때, 강산이가 침수된 지역을 피해서 PC방까지 갈 수 있는 경로의 개수를 구하라.

단, PC방의 좌표가 집의 좌표 같은 경우 경로는 1가지라고 한다.

입력 첫째 줄에 집과 PC방의 좌표 (H, H), (N, N) 을 나타내는 두 정수 H, N (0 ≤ H, N ≤ 30) 이 차례로 주어진다.

출력 집에서 PC방까지 갈 수 있는 경로의 개수를 출력한다.

예제 입력 1 8 4 예제 출력 1 14

예제 입력 2 0 3 예제 출력 2 5

코드

# 20152 Game Addiction

H, W = map(int, input().split())

start = 0
end = abs(H - W) + 1

numbers = [[0] * end for _ in range(end)]
for i in range(end):
    numbers[0][i] = 1

for i in range(1, end):
    for j in range(i, end):
        numbers[i][j] = numbers[i - 1][j] + numbers[i][j - 1]

ans = numbers[-1][-1]
print(ans)

(코드에서 start = 0은 안 써도 됐다..)

해설

좌표 값을 구할 때, H와 W값이 무엇인지는 중요하지 않다. H, W가 얼마나 차이나는지가 중요하다. H = 0, W = 5일 때와 H = 5, W = 10일 때의 결과는 같기 때문이다. H = 10, W = 5일 때의 결과도 마찬가지로 같다.

경우의 수를 따질 때, 문제대로라면 왼쪽 위에서 오른쪽 아래로 대각선을 그었을 때, 위쪽 부분이 침수되었지만, 경우의 수를 구할 때에 아래쪽 부분이 침수된 것으로 생각해도 무방하다. 편의를 위해 아래쪽이 침수된 것으로 생각했다.

0, 0에서 3, 3으로 갈 때, 경우의 수를 모든 칸에 기록하면서 이동하면 다음과 같다.

1 1 1 1 0 1 2 3 0 0 2 5 0 0 0 5

8, 8에서 4, 4로 갈 때의 경우의 수는, 0, 0에서 4, 4로 갈 때의 경우의 수와 동일하다. 0, 0에서 4, 4로 갈 때, 경우의 수를 마찬가지로 모두 기록해보면

1 1 1 1 1 0 1 2 3 4 0 0 2 5 9 0 0 0 5 14

와 같은 결과를 얻을 수 있다.

눈치 빠른 독자는 벌써 눈치를 챘을 것 같다.

내가 푼 방식은 다음과 같다.

1. H, W의 차이를 구한다.
2. N = abs(H - W) + 1
3. N*N 배열을 만들고 0으로 초기화한다.
4. 첫 행에 1을 집어넣는다.
5. [1, 1]에서부터, 위와 왼쪽 값을 더한 결과를 대입해준다.

손쉽게 모든 경우의 수를 구할 수 있음을 알 수 있다.

(Ctrl + F 단축키를 이용해 원하는 문자를 찾아보세요.)

(한글을 이용하시는 경우, Ctrl + N + M을 누르시면 수식을 입력할 수 있는 창이 뜹니다.)

알파 α

베타 β

감마 γ

델타 Δ δ

엡실론 ε

제타 ζ

에타 η

세타 θ

람다 λ

뮤, 마이크로 μ

누 ν

크시 ξ

파이 π Φ

로 ρ

시그마 Σ σ

타우 τ

화이 φ (파이랑 다른 알파벳입니다.)

카이 χ

프사이 ψ

오메가 Ω, ω

파샬 ∂

편미분할 때 사용. 델, 디, 편디, 파샬 등으로 부른다.

<유용한 기호>

따라서 ∴

그러므로 ∵

근사한다 ≃

비례한다 ∝

같지 않다 ≠

무한대 ∞

도 °

equal by definition ≜

점곱, 내적 ·

루트 √

집합 기호 ∈, ⊂, ∪, ∩

<유용한 라틴어>

i.e. : id est[“that is” or “in other words”], 다시 말해

e.g. : exempli gratia[for example], 예를 들어

서버를 새로 만들면 기존 설정이 다 지워지더라고요ㅠㅠ 나중에 잊어버리지 않기 위해 저도 공유합니다.

JupyterLab 초기 설정은 괄호( ( ), [ ], { } ) 나 따옴표 ( " " , ' ' ) 를 사용할 때 자동으로 닫아주지 않습니다. (저는 이 부분이 불편해서 설정을 하는 편입니다)

그래서 자동으로 괄호 닫기 따옴표 닫기를 위해 약간의 설정이 필요합니다.

JupyterLab 상단의 Settings -> Advanced Settings Editor 진입 Notebook 옵션 클릭

오른쪽 User Preferences 에서 중괄호{ } 사이에 다음 명령어 붙여넣기 후 저장

"codeCellConfig":{
    "autoClosingBrackets":true}

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.

시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.

입력 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력 S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

# 18405 경쟁적 전염

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

N, K = map(int, input().split())
blocks = [list(map(int, input().split())) for _ in range(N)]
S, X, Y = map(int, input().split())

queue = list()
for r in range(N):
    for c in range(N):
        if blocks[r][c] != 0:
            queue.append([blocks[r][c], r, c])

queue.sort()
temp_queue = queue[:]

for _ in range(S):
    queue = list()
    while temp_queue:
        c_block, p_r, p_c = temp_queue.pop(0)
        for k in range(4):
            cr = p_r + dr[k]
            cc = p_c + dc[k]
            if 0 <= cr and cr < N and 0 <= cc and cc < N and blocks[cr][cc] == 0:
                blocks[cr][cc] = c_block
                queue.append([blocks[cr][cc], cr, cc])
    temp_queue = queue[:]

print(blocks[X - 1][Y - 1])

구현 문제였다.

특이한 사항은

• queue 안의 blocks[r][c] 값을 먼저 정렬해줘야 하는 점과,
• queue, temp_queue를 따로 나눈 뒤, temp_queue로 BFS를 1초에 단 한 칸씩 돌리는 점이다.

이중리스트의 복사를 [:] 연산을 이용하여 쉽게 구현할 수 있었다.

코드를 짠 뒤 한 번에 정답을 맞춰 다소 당황했다.

원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.

1. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
2. 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
   1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
   2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.

특이사항 열끼리는 끝과 끝 인접 인정 행끼리는 끝과 끝 인접 인정하지 않음. ex) numbers[0][0]과 numbers[0][M - 1] -> 인접 numbers[0][0]과 numbers[N - 1][0] -> 인접 X

# 17822 원판 돌리기

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

N, M, T = map(int, input().split())
numbers = [list(map(int, input().split())) for _ in range(N)]
xi = list()
di = list()
ki = list()
for _ in range(T):
    tx, td, tk = map(int, input().split())
    xi.append(tx)
    di.append(td)
    ki.append(tk)

for i in range(T):
    # 원판 배수
    cur_x = xi[i]
    # 방향 0: 시계, 1: 반시계
    cur_d = di[i]
    # 회전 칸수
    cur_k = ki[i]

    # 1. 배수 원판 회전시키기.
    # 시계 방향으로 회전
    if cur_d == 0:
        # idx가 0부터 시작하므로 cur_x - 1부터 시작한다고 표현
        for j in range(cur_x - 1, N, cur_x):
            # cur_k만큼 시계방향으로 회전
            for _ in range(cur_k):
                temp = numbers[j].pop()
                numbers[j].insert(0, temp)

    # 반시계 방향으로 회전
    elif cur_d == 1:
        # idx가 0부터 시작하므로 cur_x - 1부터 시작한다고 표현
        for j in range(cur_x - 1, N, cur_x):
            # cur_k만큼 반시계방향으로 회전
            for _ in range(cur_k):
                temp = numbers[j].pop(0)
                numbers[j].append(temp)

    # 2. 원판에 수가 남아있으면, 인접하면서 수가 같은 것을 모두 찾는다.
    temp_num = 0
    for num in numbers:
        temp_num += sum(num)
    # 원판에 수가 없으면 break
    if temp_num == 0:
        break

    # 인접하면서 수가 같은 것을 모두 찾는다.
    visited = [[0] * (M) for _ in range(N)]
    for r in range(N):
        for c in range(M):
            if numbers[r][c] == 0 or visited[r][c] == 1:
                continue
            queue = [(r, c)]
            while queue:
                kr, kc = queue.pop()

                for k in range(4):
                    current_r = kr + dr[k]
                    current_c = kc + dc[k]
                    # 열끼리 연산
                    if current_c < 0:
                        current_c = M - 1
                    elif current_c > M - 1:
                        current_c = 0
                    if 0 <= current_r and current_r < N and visited[current_r][current_c] == 0:
                        # 인접한 것끼리 숫자가 같을 경우
                        if numbers[kr][kc] == numbers[current_r][current_c]:
                            # 방문 처리
                            visited[kr][kc] = 1
                            visited[current_r][current_c] = 1
                            queue.append((current_r, current_c))
    # visited한 것이 있으면 == 인접한 것이 있으면 0으로 만듦.
    check = 0
    for rr in range(N):
        for cc in range(M):
            if visited[rr][cc] == 1:
                numbers[rr][cc] = 0
                check = 1
    # 인접한 수가 없다면 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.
    if check == 0:
        avg = 0
        cnt = 0
        # 평균 계산
        for rr in range(N):
            for cc in range(M):
                if numbers[rr][cc] != 0:
                    avg += numbers[rr][cc]
                    cnt += 1
        # 평균과 비교   
        avg /= cnt
        for rr in range(N):
            for cc in range(M):
                if numbers[rr][cc] != 0:
                    # 평균보다 크면 1 빼줌
                    if numbers[rr][cc] > avg:
                        numbers[rr][cc] -= 1
                    # 평균보다 작으면 1 더해줌
                    elif numbers[rr][cc] < avg:
                        numbers[rr][cc] += 1

ans = 0
for idx in range(N):
    ans += sum(numbers[idx])
print(ans)

풀면서 틀렸던 부분

1. for k in range(4):
       current_r = kr + dr[k]
       current_c = kc + dc[k]

   어리석게도 kr, kc 대신 numbers[kr][kc]를 넣어서 한참 고생했다. BFS를 오랜만에 풀어서 생긴 참사로 보인다,,, 에러 고치는 데 10여 분 정도 소요되었다. _

2. # visited한 것이 있으면 == 인접한 것이 있으면 0으로 만듦.
   # 인접한 수가 없다면 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

   다음 연산들의 들여쓰기(indentation)을 실수로 두 칸 더 넣었다. 즉, 이중 for문 안에 저 연산을 해주었다.

두 번째 예제를 넣었을 때, visited 배열 모두 0으로 인식되어, 터진 배열이 없는 것으로 인식되어 이상한 출력이 자꾸 나왔다. 5분 정도 헤매다가 오답을 찾았다. _ 3.

# 시계 방향으로 회전
    if cur_d == 0:
        # idx가 0부터 시작하므로 cur_x - 1부터 시작한다고 표현
        for j in range(cur_x - 1, N, cur_x):
            # cur_k만큼 시계방향으로 회전
            for _ in range(cur_k):
                temp = numbers[j].pop()
                numbers[j].insert(0, temp)
# 반시계 방향도 틀렸지만, 큰 틀에서 코드는 같으므로 생략

for j in range(cur_x - 1, M + 1, cur_x): 로 짰었다. 제출 이후 IndexError가 발생했다.

vscode에서 N=4, M=4에서 N=3으로 바꾼 뒤 실행해보고, 금방 에러를 찾았다.

참사가 난 이유:

1. N, M 값을 명확히 구분하지 않고 문제를 풀었다. 1-1. 주어진 예시에선 N = M이므로 IndexError를 발견하기 쉽지 않았다. 내가 따로 체크했어야 했다.
2. 맨 처음에 위, 왼쪽에 0 padding을 넣어, numbers[1][1]이 첫 값이 되도록 만드려고 했다. 시계/반시계 방향 회전을 구현하는 과정에서 pop, insert, append 등을 써야하는 것을 깨달았고, padding 없이 짜기로 했으면서, for 문 안의 +1을 그대로 냅뒀다.

풀면서 주의했던 부분

1. 저번 문제에서 i를 중복해서 사용하는 바람에, i 값이 예상하지 못하게 엄청 튀었던 경험이 있다. 이번에도 for i in range(): 안에서 for i in range():를 썼다가, 코드를 전체적으로 훑어보는 과정에서 위의 문제가 생각나 self-debugging에 성공했다. _

2. # 원판에 수가 없으면 break
     if temp_num == 0:
         break

   개인적으로 이 부분에 대한 문제의 설명이 모호해보였다. 먼저 탈출해도 되나? 큰 문제가 없다고 판단하여 break를 걸었고, 예상대로 문제 없어보인다. _

3. queue = [(r, c)]
   while queue:
     kr, kc = queue.pop()

   맨 처음엔 이중 for문만으로 풀려고 시도하다가, queue를 이용한 BFS가 나을 것이라고 생각 후 코드를 고쳤다. 무려 5중 반복문을 사용하면서(for k in range(4)도 아무튼 반복문임.), 시간복잡도가 버텨낼지에 대한 의문도 있어 계산해보았다.

   2 ≤ N, M ≤ 50, 최대 50
   50 ** 5 = 10 ** 5 * 5 ** 5
   10 ** 5 = 100,000
   5 ** 5 = 대충 3125
   3억의 시간복잡도가 소요된다... 문제 풀면서 10 ** 5는 1만이었는데... 잘못 계산한 것 같다.

5중 반복문이 아니라 4중 반복문인가보다!

50 ** 4 * 4 = 10 ** 4 * 5 ** 4 * 4
10 ** 4 = 10,000
5 ** 4 = 625
625 * 4 = 대충 3,000
10,000 * 3,000 = 30,000,000 = 3천만 < 1억

따라서, 시간복잡도 문제는 고려하지 않아도 된다! 만세!

-- 후기 --

골드 1 문제를 풀다가 골드 3 문제를 푸니 상대적으로 쉽게 해결한 느낌이다.

문제를 풀면서 발생한 소소한 참사들을 기록해놓고, 다음에 실수하지 않도록 해야겠다.

p.s) 대참사 == 백준 질문검색 란에서 반례를 찾는 것. 소소한 참사 == 한 번에 문제를 풀진 못했지만, self debugging을 통해 틀린 부분을 정정.

일찍 풀어서 놀 시간이 많아져 행복하다.

(전위 순회)

1. 가장 처음에 상근이는 트리의 루트에 있는 빌딩 앞에 서있다.
2. 현재 빌딩의 왼쪽 자식에 있는 빌딩에 아직 들어가지 않았다면, 왼쪽 자식으로 이동한다.
3. 현재 있는 노드가 왼쪽 자식을 가지고 있지 않거나 왼쪽 자식에 있는 빌딩을 이미 들어갔다면, 현재 노드에 있는 빌딩을 들어가고 종이에 번호를 적는다.
4. 현재 빌딩을 이미 들어갔다 온 상태이고, 오른쪽 자식을 가지고 있는 경우에는 오른쪽 자식으로 이동한다.
5. 현재 빌딩과 왼쪽, 오른쪽 자식에 있는 빌딩을 모두 방문했다면, 부모 노드로 이동한다.

예제 입력 1 2 2 1 3 예제 출력 1 1 2 3

예제 입력 2 3 1 6 4 3 5 2 7 예제 출력 2 3 6 2 1 4 5 7

! 코드, 풀이 해설을 보기 전 고민하는 시간을 충분히 가져보세요!

# 9934 완전 이진 트리

K = int(input())
numbers = list(map(int, input().split()))
tree = [[] for _ in range(K)]

for idx, number in enumerate(numbers):
    num = 2 ** 10
    cnt = 10
    while (idx + 1) % num != 0:
        cnt -= 1
        num //= 2
    tree[cnt].append(number)

for i in range(len(tree) - 1, -1, -1):
    print(' '.join(map(str, tree[i])))

풀이 해설

숫자 순서를 담은 numbers 배열을, for문과 enumerate를 통해 하나씩 가져온다. idx는 numbers의 몇 번째 숫자(순서)를 가져왔는지를 나타낸다.

idx == 순서 (엄밀히 말하면 idx + 1) number == 현재 들고 있는 숫자. tree == 숫자를 배치할 트리. 이중 리스트로 트리의 층수 표현.

난 지금 number 하나를 들고 있다. 이제 무엇을 할 것인가?

트리 K개를 만든 뒤, 아래 층부터 채워가는 알고리즘을 생각해보자. 트리를 채우기 위해, 트리의 어느 부분에 내가 들고 있는 숫자 number를 채울 것인지를 생각해야 한다.

예제 2에서 숫자가 들어간 규칙을 살펴보면 예제 입력 1 6 4 3 5 2 7 트리 층수 1 2 1 3 1 2 1

• 맨 아래쪽의 1, 4, 5, 7은 한 칸 건너 나타나는 형태임을 알 수 있다. 즉, 지금 맨 아래 트리에 숫자를 채웠다면, 그 다음 번엔 위에 있는 어떤 트리의 숫자를 추가할 것이고, 위의 트리에서 숫자를 채웠다면, 그 다음 번엔 맨 아래에 있는 트리의 숫자를 추가할 것이다.

• 트리 층수에서 1, 2, 1이 반복적으로 나타난다. 중간에 나타난 3도 같은 형태이다. 1, 2, 1을 11로 치환해보자. 그렇다면 1, 2, 1, 3, 1, 2, 1은 11, 3, 11과 같이 표현할 수 있다.

혼자서 숫자를 반복해서 써가보면서, 어떤 규칙성을 찾아냈다.

• 4의 배수인 순서에서 3 이상의 값을 갖는다.
• 그 사이엔 1, 2, 1이 들어간다.
• 1, 2, 1, 3, 1, 2, 1 뒤에 4 라는 새로운 트리 층수가 나타난다.
  • 4뿐만 아니라 앞으로 5, 6, 7... 등이 순차적으로 등장할 것임을 예측할 수 있다.
• 홀수 번째

규칙성을 찬찬히 찾아보고 코드를 작성해가면서(코드로 답을 끼워맞춰가면서) 추가적인 규칙성을 발견했다.

• 4번째 순서에 3이, 8번째 순서에 4가, 16번째 순서에 5가 나온다.
  • 주어진 조건에서, 완전이진트리를 가정했기 때문이다.
• 2^(n-1)번째 순서에 = n이 나온다. 로 일반화를 할 수 있었다.
  • 그렇다면 12번째 처럼 애매한 순서는?
  • 12 = 3 * 4 이므로, 4(2^2)의 배수니까 3이 나올 것이라고 가정할 수 있다.

위와 같은 일반화 과정을 거쳤고, 코드로 구현했다.

num = 2 ** 10 K는 10 이하이므로 제일 큰 num은 2^10이다.

cnt = 10 몇 번째 tree 값을 고를지 알려주는 변수이다.

while (idx + 1) % num != 0: idx는 0부터 시작하고, 난 첫 번째 숫자가 1이길 원하므로 1을 더해줬다. 내가 들고 있는 숫자의 순서(idx + 1)와 num의 나머지를 구했을 때, 0이면(idx + 1이 num의 약수이면) while문을 탈출한다. 약수가 아니라면 다음 과정을 반복한다.

cnt -= 1 num //= 2 트리 층수를 한 층 낮추고, num은 2로 나눠준다.

tree[cnt].append(number) cnt 층에 현재 들고 있는 number를 추가해준다.

for i in range(len(tree) - 1, -1, -1): 맨 위층부터 출력을 해줘야 한다. (그래야 맨 마지막 출력이 맨 아래층이다.) 그냥 for문을 걸면, i=0부터 시작하므로, 맨 위층부터 출력하도록 만들었다.

print(' '.join(map(str, tree[i]))) list 형태인 tree[i]를 이쁘게 출력한다.

입력 첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 격자에 들어있는 구슬의 정보가 주어진다. r번째 행의 c번째 정수는 (r, c)에 들어있는 구슬의 번호를 의미한다. 어떤 칸에 구슬이 없으면 0이 주어진다. 상어가 있는 칸도 항상 0이 주어진다.

다음 M개의 줄에는 블리자드 마법의 방향 di와 거리 si가 한 줄에 하나씩 마법을 시전한 순서대로 주어진다.

출력 첫째 줄에 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)를 출력한다.

문제 요약

1. 블리자드 마법 사용(방향 di, 거리 si)

2. 구슬 이동

3. 구슬 폭발(4개 이상 연속하면 폭발)

• 폭발 후 이어붙임. 4개 이상이면 또다시 재폭발(무한 반복)

4. 구슬 변화 (구슬 갯수, 구슬 번호)로 재구성

# 21611 마법사 상어와 블리자드

# 하 우 상 좌
dr = (0, 1, 0, -1, 0)
dc = (0, 0, 1, 0, -1)

# 0, 상, 하, 좌, 우
bli_rc = [(0, 0), (-1, 0), (1, 0), (0, -1), (0, 1)]



# 일렬 리스트 만들기
def make_one_list():
    current_r = (N // 2) + 1
    current_c = (N // 2) + 1
    move_num = 2
    while current_c > 0:
        for i in range(1, 5):
            for j in range(move_num):
                # 처음엔 왼쪽으로 이동
                if i == 1 and j == 0:
                    current_c -= 1
                else:
                    current_r += dr[i]
                    current_c += dc[i]
                one_list.append(blocks[current_r][current_c])
        move_num += 2

        if blocks[current_r][current_c + dc[i]] == 0:
            break
    return


# blizrd 마법 이후 블록 재배치
def make_blocks():
    for i in range(N + 1):
        for j in range(N + 1):
            blocks[i][j] = 0

    current_r = (N // 2) + 1
    current_c = (N // 2) + 1
    move_num = 2
    one_list_idx = 0
    length = len(one_list)
    while current_c > 0:
        for i in range(1, 5):
            for j in range(move_num):
                # 처음엔 왼쪽으로 이동
                if i == 1 and j == 0:
                    current_c -= 1
                else:
                    current_r += dr[i]
                    current_c += dc[i]
                if length <= one_list_idx:
                    return
                while one_list[one_list_idx] == 0:
                    one_list_idx += 1
                    if length <= one_list_idx:
                        return
                blocks[current_r][current_c] = one_list[one_list_idx]
                one_list_idx += 1 
        move_num += 2
    return


# 4개 연속이면 터뜨리기
def pop_one_list():
    global one_list
    new_one_list = list()
    bomb_check = 0
    cnt = 1
    temp = -1
    for i in range(len(one_list)):
        if one_list[i] != temp:
            temp = one_list[i]
            if cnt >= 4:
                bomb_check = 1
                bomb_num[new_one_list[-1]] += cnt
                for _ in range(cnt):
                    new_one_list.pop()
            cnt = 0
        new_one_list.append(one_list[i])
        cnt += 1
    if cnt >= 4:
        bomb_check = 1
        bomb_num[new_one_list[-1]] += cnt
        for _ in range(cnt):
            new_one_list.pop()
    one_list = new_one_list[:]
    return bomb_check


# 구슬 변화(갯수, 번호)
def evolution():
    global blocks
    current_r = (N // 2) + 1
    current_c = (N // 2) + 1
    move_num = 2
    cnt = 0
    bf_num = blocks[current_r][current_c - 1]
    flag = 0
    while current_c > 0:
        for i in range(1, 5):
            for j in range(move_num):
                # 처음엔 왼쪽으로 이동
                if i == 1 and j == 0:
                    current_c -= 1
                else:
                    current_r += dr[i]
                    current_c += dc[i]

                if current_c <= 0 or current_r > N or blocks[current_r][current_c] == 0:
                    flag = 1
                    break

                # 전후 숫자가 달라지면 visited 초기화 가능
                if blocks[current_r][current_c] == bf_num:
                    cnt += 1
                elif blocks[current_r][current_c] != 0:
                    evo_list.append(cnt)
                    evo_list.append(bf_num)
                    cnt = 1
                    bf_num = blocks[current_r][current_c]
                else:
                    break
            if flag == 1:
                break
        if flag == 1:
            break
        move_num += 2


    evo_list.append(cnt)
    evo_list.append(bf_num)


    # 블록 재배치
    new_blocks = [[0] * (N + 1) for _ in range(N + 1)]

    current_r = (N // 2) + 1
    current_c = (N // 2) + 1
    move_num = 2
    evo_list_idx = 0
    length = len(evo_list)
    while current_c > 0:
        for i in range(1, 5):
            for j in range(move_num):
                # 처음엔 왼쪽으로 이동
                if i == 1 and j == 0:
                    current_c -= 1
                else:
                    current_r += dr[i]
                    current_c += dc[i]
                if length <= evo_list_idx:
                    break
                if current_r <= 0 or current_c <= 0:
                    blocks = new_blocks[:]
                    return
                new_blocks[current_r][current_c] = evo_list[evo_list_idx]
                evo_list_idx += 1
        move_num += 2
    blocks = new_blocks[:]
    return


N, M = map(int, input().split())
blocks = [[0] * (N + 1)] + [[0] + list(map(int, input().split())) for _ in range(N)]
one_list = list()
move_list = list()
bomb_num = [0, 0, 0, 0]
for _ in range(M):
    temp_r, temp_c = map(int, input().split())
    move_list.append([temp_r, temp_c])

for blizard_d, blizard_s in move_list:
    # blizard 마법
    current_r = (N // 2) + 1
    current_c = (N // 2) + 1
    for _ in range(blizard_s):
        current_r += bli_rc[blizard_d][0]
        current_c += bli_rc[blizard_d][1]
        blocks[current_r][current_c] = 0

    one_list = list()
    # blizard 마법 이후 일렬 리스트로 붙이기
    make_one_list()

    # blizard 마법 이후 블록 재배치
    make_blocks()

    one_list = list()
    # 일렬 리스트 만들기
    make_one_list()

    again = 1
    while again:
        # 4개 연속이면 터뜨리기
        again = pop_one_list()

    # 블록 재배치
    make_blocks()

    evo_list = list()
    # 구슬 변화(갯수, 번호)
    evolution()

ans = 0
for i in range(1, 4):
    ans += bomb_num[i] * i

print(ans)

새벽에 두 시간동안 풀다가, 마지막 구슬 변화 단계를 안 읽어서 구현을 안 했었따....

자고 일어나서 구현하니, 틀렸다고 한다...

반례를 검색해서 찾아 풀었다.

골1 문제라 조건이 상당히 까다롭다.

복잡한 문제를 끈기있기 풀 수 있는 체력을 길러야겠다고 생각했다.

컨베이어 벨트를 이용해 로봇들을 건너편으로 옮기려고 한다. 로봇을 옮기는 과정에서는 아래와 같은 일이 순서대로 일어난다.

1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
   1. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.

종료되었을 때 몇 번째 단계가 진행 중이었는지 구해보자. 가장 처음 수행되는 단계는 1번째 단계이다.

입력 첫째 줄에 N, K가 주어진다. 둘째 줄에는 A1, A2, ..., A2N이 주어진다.

출력 몇 번째 단계가 진행 중일때 종료되었는지 출력한다.

제한 2 ≤ N ≤ 100 1 ≤ K ≤ 2N 1 ≤ Ai ≤ 1,000

내 첫 번째 제출은 다음과 같다.

python3에선 시간 초과가 발생하였고, pypy에선 통과되었다.

# 20055 컨베이어 벨트 위의 로봇

def check_N():
    if belts_box[N - 1] != 0:
        belts_box[N - 1] = 0
    return


N, K = map(int, input().split())
belts_strength = list(map(int, input().split()))
belts_box = [0] * (2 * N)
length = len(belts_strength)
cnt = 1

while True:
    check_N()
    # 1. 회전
    for i in range(length - 1, 0, -1):
        temp = belts_strength[i]
        belts_strength[i] = belts_strength[i - 1]
        belts_strength[i - 1] = temp

        temp = belts_box[i]
        belts_box[i] = belts_box[i - 1]
        belts_box[i - 1] = temp

    check_N()
    # 2. 이동
    for i in range(N - 2, -1, -1):
        if belts_box[i] > 0 and belts_box[i + 1] == 0 and belts_strength[i + 1] > 0:
            belts_box[i + 1] = belts_box[i]
            belts_box[i] = 0
            belts_strength[i + 1] -= 1

    check_N()
    # 3. 로봇 올리기
    if belts_strength[0] != 0:
        belts_strength[0] -= 1
        belts_box[0] += 1

    check_N()
    # 4. 내구도 0인 칸의 갯수 K 이상이면 종료.
    if belts_strength.count(0) >= K:
        break
    cnt += 1

print(cnt)

맨 처음엔 2. 이동 부분의 for문에서 0번 째 벨트부터 N-1번 째 벨트의 순서로 탐색을 진행했으나, 예시 코드에서 틀린 방식임을 깨닫고 N-2번 째부터 0번까지 탐색하도록 알고리즘을 변경하였다.

다른 분들의 코드를 참고해보니, 1. 회전 부분에서 for문을 사용하지 않아도 된다는 것을 알게 되었다.

check_N 함수도 1. 회전, 2. 이동 이후에만 검사해도 괜찮았다.

# 20055 컨베이어 벨트 위의 로봇

def check_N():
    if belts_box[N - 1] != 0:
        belts_box[N - 1] = 0
    return


N, K = map(int, input().split())
belts_strength = list(map(int, input().split()))
belts_box = [0] * (2 * N)
length = len(belts_strength)
cnt = 1
temp_list = list()

while True:
    # 1. 회전
    temp_list = [belts_strength[-1]] + belts_strength[:-1]
    belts_strength = temp_list[:]

    temp_list = [belts_box[-1]] + belts_box[:-1]
    belts_box = temp_list[:]

    check_N()
    # 2. 이동
    for i in range(N - 2, -1, -1):
        if belts_box[i] > 0 and belts_box[i + 1] == 0 and belts_strength[i + 1] > 0:
            belts_box[i + 1] = belts_box[i]
            belts_box[i] = 0
            belts_strength[i + 1] -= 1

    check_N()
    # 3. 로봇 올리기
    if belts_strength[0] != 0:
        belts_strength[0] -= 1
        belts_box[0] += 1

    # 4. 내구도 0인 칸의 갯수 K 이상이면 종료.
    if belts_strength.count(0) >= K:
        break
    cnt += 1

print(cnt)

결론 및 느낀점

• 흥미로운 구현 문제였다. 맨 처음 문제를 보았을 때, 해석하느라 애먹었다.
• 단순 for문이 아닌, slicing을 통해서 벨트의 회전을 구현할 수 있었다.

https://conferencetimeline.notion.site/AI-Stage-53c71393f9fb492986c09140736773c8

다음 링크를 참조하였다.

.ssh / config에 IdentityFile를 설정하는 것까지 성공하였다.

Remote-SSH: Connect to Host를 클릭한 이후 서버를 고르면, 새 창에서 Windows를 고른 뒤 password를 입력하라는 안내 문구가 뜨는 문제가 있었다. 엔터를 세 번 치고 vscode의 terminal을 살펴보니, Load key Permission denied란 에러를 찾을 수 있었다.

제가 해결한 방법은 다음과 같다. [제 운영체제는 Windows입니다.]

1. key의 경로 설정을 잘 해준다. 제 경우 서버에 설정해준 경로는 다음과 같다. IdentityFile D:/boostcamp/key/key

2. key의 접근 권한을 변경해준다. key 파일 우클릭 - 속성 - 보안 - 편집 - 그룹 또는 사용자 이름 -> 추가 본인 계정 이름 입력(로그오프하면 뜨는 계정 이름입니다. Windows 10 기준으로, 시작 버튼을 클릭한 뒤 좌측 상단 계정 프로필에 마우스를 갖다대면 확인하실 수 있습니다) 확인 버튼을 눌러 추가

• 기존에 있던 사용자 제거
• [계정 프로필]의 사용 권한 '읽기'만 허용 후 적용 버튼 누르기, 확인 버튼을 눌러 나옴.

이후 재시도

Remote-SSH: Connect to Host를 클릭한 이후 서버를 고른 뒤, Windows가 아닌 Linux를 선택 서버에 접속한 것을 확인할 수 있었다. 제 해결 과정이 도움이 되셨으면 좋겠다!

참고 bash: powershell: command not found

Remote-SSH: Connect to Host를 클릭한 이후 서버를 고른 뒤, Windows를 골랐을 때 발생한 에러였다.

Linux를 고르니 괜찮아졌다.

1. 모든 구름이 di 방향으로 si칸 이동한다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
3. 구름이 모두 사라진다.
4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
   • 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
   • 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

# 21610 마법사 상어와 비바라기

move_dir = [[0, 0], [0, -1], [-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1]]
cross_rc = [[-1, -1], [-1, 1], [1, 1], [1, -1]]

N, M = map(int, input().split())
clouds = [[0] * (N + 1)] + [[0] + list(map(int, input().split())) for _ in range(N)]
d = list()
s = list()
for _ in range(M):
    dd, ss = map(int, input().split())
    d.append(dd)
    s.append(ss)

rain = list()
rain.extend([[N, 1], [N, 2], [N - 1, 1], [N - 1, 2]])

for _ in range(M):
    cur_d = d.pop(0)
    cur_s = s.pop(0)
    direction_r, direction_c = move_dir[cur_d]
    # 모든 구름이 di 방향으로 si칸 이동한다.
    new_rain = list()
    for rain_r, rain_c in rain:
        rain_r += cur_s * direction_r
        rain_c += cur_s * direction_c
        while rain_r > N:
            rain_r -= N
        while rain_r <= 0:
            rain_r += N
        while rain_c > N:
            rain_c -= N
        while rain_c <= 0:
            rain_c += N
        new_rain.append([rain_r, rain_c])

    rain = list()
    # 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
    for rain_r, rain_c in new_rain:
        clouds[rain_r][rain_c] += 1

    # 구름이 모두 사라진다. (== 상단에서 new_rain 초기화)
    visited = [[0] * (N + 1) for _ in range(N + 1)]
    for rain_r, rain_c in new_rain:
        visited[rain_r][rain_c] = 1

    # 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다.
    for rain_r, rain_c in new_rain:
        for i in range(4):
            cr = rain_r + cross_rc[i][0]
            cc = rain_c + cross_rc[i][1]
            if 1 <= cr and cr <= N and 1 <= cc and cc <= N and clouds[cr][cc] > 0:
                clouds[rain_r][rain_c] += 1

    # 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다.
    # 앞에서 구름이 사라진 칸이 아니어야 한다.
    for r in range(1, N + 1):
        for c in range(1, N + 1):
            if visited[r][c] == 0 and clouds[r][c] >= 2:
                rain.append([r, c])
                clouds[r][c] -= 2

ans = 0
for cl in clouds:
    ans += sum(cl)

print(ans)

논문 보러가기

요약

주요(Dominant) 시퀀스 변환 모델들은 encoder와 decoder를 포함하는 복잡한 Recurrent/Convolutional Neural Network에 기반을 두고 있다. 최고 성능의 모델 또한 attention mechanism을 통해 decoder와 encoder를 연결한다. 우리는 Transformer라는, 회귀(recurrent)와 컨볼루션(convolution)들을 배제한, 오로지 attention mechanism을 따르는 새롭고 간단한 Network architecture를 소개한다.

두 가지 기계번역 업무들에서, 이 transformer 모델들은 우월한 성능을 보였고, 병렬화를 통해 학습에 요구되는 시간을 획기적으로 줄였다. WMT 2014 영어-독일어 번역에서 28.4 BLEU(Bilingual Evaluation Understudy Score, 기계 번역 결과와 사람 번역 유사도 비교해 성능 측정)를 달성해, 앙상블을 포함한 기존의 최고 결과를 2BLEU 이상 향상시켰다. WMT 2014 영어-프랑스에 번역에서도 새로운 단일 모델 SOAT(State-of-the-art, 현재 최고 수준의 결과) BLUE 점수를 달성했다. Transformer는 기계번역 뿐만 아니라, English constituency parsing(영어권 유권자 분석)와 같은 다른 업무도 잘 일반화(generalize)시켰다.

1. Introduction

RNN, LSTM, GRU는 sequence modeling과 기계번역 등과 같은 transduction(전달, 변환) 문제에서 SOAT한 접근법으로 자리매김해왔었다. Recurrent language models들과 encoder-decoder architecture를 발전시키기 위한 여러 노력들이 계속되고 있다.

Recurrent 모델들은 일반적으로 입력과 출력 시퀀스들의 symbol 위치에 따라 factor를 계산한다. 계산할 때 각 step에 따라 위치를 정렬하고, 이전 hidden state인 h_t-1, input t에 따라 hidden state h_t를 만든다. 이러한 순차적 특성은 본질적으로 예제 트레이닝 내의 병렬화를 방지하는데, 메모리 제약이 예제 사이의 일괄적인 처리를 제한하기 때문에, sequence 길이가 길어질수록 (본질적인 순차적 특성은)치명적이다. (Recurrent 모델들은) factorization tricks(인수분해 트릭)과 같은 최근 연구를 통해 계산 효율성을 크게 개선시켰고, conditional computation(조건부 계산) 연구는 계산 효율성뿐만 아니라, 모델 성능도 개선했다. 그러나, sequential한 연산의 근본적인 제약은 아직 남아 있다.

Attention mechanism은 input이나 output sequences에서 거리에 상관 없이 의존성(dependencies) 모델링을 가능하게 하면서, 여러 업무에서 설득력 있는 sequence modeling과 transduction(변환) 모델의 빠질 수 없는 부분이 되어가고 있다. 그러나 몇 가지 경우를 제외하고, attention mechanism은 Recurrent Network와 함께 사용된다.

본 논문에서 우리는 input과 output간의 global한 dependencies를 찾기 위해 recurrence에서 벗어나, 전적으로 attention mechanism에 의존하는 Transformer를 제안한다. Transformer는 훨씬 더 많은 병렬화가 가능하고, 8개의 P100 GPU에서 12시간만 훈련해도, 새로운 SOTA수준의 번역 품질을 제공한다.

향후 추가 예정

참고자료

https://velog.io/@changdaeoh/Transformer-%EB%85%BC%EB%AC%B8%EB%A6%AC%EB%B7%B0