AWS CLI 환경 Set Up 하기 – AWS Configure

AWS CLI 환경 세팅하기 이전에 CLI 설치는 아래 AWS 문서를 참고해주시면 됩니다.

https://docs.aws.amazon.com/cli/latest/userguide/getting-started-install.html

aws configure 커맨드를 사용하면 아래와 같이 CLI 환경을 바로 세팅할 수 있습니다.

그러나 이번 포스트에서는 특정 유저 기준 Profile로 AWS CLI를 세팅하는 방법을 다루어보려고 합니다 🙂

aws configure --profile <YOUR PROFILE NAME>

여기서 기입할 Access Key ID와 Secret Access Key는 AWS IAM 콘솔 메뉴에서 Access management >> Users에서 생성된 유저 정보를 복사 붙여넣기하면 됩니다.

Default region name은 저는 us-east-1으로, Default output format은 json으로 해주었습니다.

User의 Permission은 Permission 옵션에서 원하는 방식으로 권한을 부여해주면 됩니다. 간단하게는 Attach policies directly 옵션으로 필요한 권한을 선택해서 부여할 수 있습니다.

특정 유저에 대해서 계정 세팅이 잘 되었는지 확인하기 위해서 간단하게 테스트해보려고 하는데요 프로필명을 매번 명령어에 붙여서 사용하기보다는 초반에 터미널에서

export AWS_PROFILE=<YOUR PROFILE NAME> 으로 세팅해줍니다.

그 후 aws configure list 를 실행하면 다음과 같이 설정된 프로필 정보가 보입니다.

또한 기본적으로 세팅되는 default VPC 가 아래 명령어로 조회되면 정상적으로 CLI가 세팅된 것입니다.

aws ec2 describe-vpcs

AWS의 다음 공식 문서도 참고해볼 수 있습니다.

https://aws.amazon.com/getting-started/guides/setup-environment/module-three/

나카가와 히데코 – 마음산책 강연에 다녀온 날

나카가와 히데코라는, 일본 분이신데 한국인 남편과 결혼해서 연희동에서 요리 교실을 운영하고 계시는 요리 연구가분의 이야기를 우연히 신문기사로 접하고 나서 관심이 생겨 인스타그램을 팔로우하고 있었다.

그러다가 마음산책이라는 출판사에서 오프라인 강연을 한다고 해서 강연을 신청해서 들으러갔다.

아래는 내가 본 인스타그램 강연 소개 글이다 🙂

강연을 들으러 가게된 계기는 나카가와 히데코 선생님의 이야기를 접하고 그 분께 요리와 인생을 배우고 싶다는 것도 있었고, 이런 니즈 자체가 내 내면에서 떠오르게 된 요즘의 나의 심리 상태를 적어보고 싶다.

올초 개인적으로 큰 일을 겪으면서 정신적으로는 계속 굴 안으로 안으로 들어가면서 일상을 회복하려고 노력했었다.

그러다가 또 한번의 개인적인 변화의 계기를 우연하게 겪으면서, 굴 안으로 들어가있던 내가 강제로 그 굴속에서 빠져나오게 되었다.

그러면서 오랜만에 사람들을 많이 만났고, 그러다가 갑자기 사람들을 여러 명 만나고 에너지를 써서인지, 아니면 변화에 대해서 나도 모르게 강박적였던 거에 대해 나도 모르던 내 몸이 저항을 하면서 아프게 되었다.

타고나기를 병원도 안 가고 감기도 잘 안 걸리는 건강한 상태였던 내가 몸이 아파서 병원에서 약을 처방받고 약을 먹으면서 정말 여러모로 인생을 정말 진지하게 점검하기 시작했다.

코시국은 많은 사람들에게 변화의 계기가 되었고, 나에게는 사실 모든 사회적 관계와 체험을 스탑하는 시간이었는데, 올 초에 일어났던 일 그리고 그 후 나에게 변화의 방아쇠를 당기게한 이벤트들, 최근에 사람들을 갑자기 만나면서 아프게 된 것까지 정말 모든 것이 나에게 근본적인 물음을 가져오게 했다.

원래 인생의 의미를 생각하고 왜 사는지를 고민하는 것을 좋아하지만, 직장인이 되고 나서는 비슷한 일상들을 유지해오던 내가, 매우 진지하고 근본적으로 나를 점검하고 변화하고 싶다는 강한 니즈를 느끼게 된 것이다.

이토록 정말 모든 면에서 의식적으로 강력한 변화를 꿈꾼 것은 처음인 것 같다. 아마 2022년에 일어난 일들이 내게 그런 것들을 가져온 것이겠지. 그리고 나의 나이가 20대 초반 중반 후반이 아니고 2022년에 30살이라는 것이 컸다. 그 전에는 모색하고 약간은 늘어져도 괜찮을 것 같다는 무의식이 있었던 거 같은데, 이제는 진지하게 변화를 만들어나가고 싶었던 것이다.

변화를 좋아하고 사람들이랑 이야기하는 것을 좋아하면서도 굉장한 집순이인 모순적인 나의 이 상태를 바꾸고, 사회와 소통하면서 변화를 만들어나가고 싶었다. 그리고 전혀 해보지 않았던 것들을 해보면서 새로운 나의 모습을 발굴해나가고 싶었다.

원래는 이러한 변화를 언제나 내가 하는 기술 업무나 새로운 공부 자격증에서 찾았다면, 이러한 변화를 모색하는 노력을 전혀 안 해보았던 분야에서 할 예정이다.

작게는 전혀 안 가봤던 동네 가보기, 한 번도 안 먹었던 메뉴 먹어보기, 새로운 강연 신청해서 들어보기, 전시회 다양하게 구경하기, 운전면허 따기 (부끄럽게도 아직도 없다), 나에게 두려움의 영역이었던 것을 도전해보기 등등등

운동의 경우 테니스, 스쿼시, 검도, 카포에라, 크로스핏, 클라이밍, 필라테스, PT, 서핑, 발레, 요가, 골프 등 다양하게 원데이 클래스라도 해보면서 운동 취향을 찾아보았었다. 그래서 운동을 새로 배워보는 게 나에게는 새로운 영역은 아니었다.

적다보니 내가 했던 새로운 모색의 시도들이 떠오르긴하는데, 그 시도들 말고 안 해보았던 것들을 해볼 예정이다.

이러한 심리 상태에 있었는데, 이 때 갔던 나카가와 히데코 선생님의 강연은 내게 매우 큰 위로와 에너지 충전이 되었다. 위치가 합정/상수 쪽이었는데 코시국 이후 거의 처음 방문한 것 같았다. 매우 오랜만에 가본 합정/상수였는데 예전에 방문했던 기억이 겹치면서 길거리를 걷는 것만으로도 새로운 생각들이 떠오르는 것 같았다.

그리고 강연 전 버섯크림소스 미트볼과 감자, 하몽같이 생긴 햄, 바게트가 담긴 도시락을 주셨는데 버섯 소스의 감칠맛이 정말 맛있었다. 강연 전에 든든하게 먹고 강연을 들었다.

정말 맛있게 든든하게 먹었던 도시락 🙂

실제로 만나 뵙게된 나카가와 히데코 선생님은 정말 맑고 호기심과 열정이 가득한 눈을 가지신 정말 귀여우시고 생생하고 에너지가 넘치시는 분이셨다.

히데코 선생님이 가지신 사진들을 보면서 선생님의 인생 이야기를 들었는데 독일, 스페인, 한국에 사셨던 분으로 일본에 산 시간들보다 해외에서 산 시간이 전체 인생에서 더 큰 부분을 차지한다고 하셨다.

언제나 변화하고 새로운 시도를 하면서 사람들과 맛있는 음식을 만들고 먹고 이야기하는 것을 좋아하신다는 말하시는 것을 보면서, 나도 올해 요리를 배워서 사랑하는 사람들에게 맛있는 요리를 해주고 같이 이야기를 나누는 그런 시간들을 가져보고 싶다는 생각이 들었다.

좋은 분위기에서, 정성스럽게 만든 음식을 제공해서 이야기를 나누는 취미를 가지고 싶다는 꿈이 생겼다.

배달음식을 시키고 밖에 나가서 먹고 그런 것이 아니라, 정성을 담아 만드는 한 끼.

기술 공부를 하면서 혼자서 공부하는 시간이 길었던 20대의 시간들을 돌이켜보면 내가 가진 조건들에 의해서 어쩔 수 없었다고 생각하면서도, 이제는 좀 더 사람냄새나는, 사람들 속에서 성장하고 배우고 나누는 사람이 되고 싶었다.

요리를 나누어먹는 시간들은 그런 커뮤니티를 풍성하게 해주는 좋은 순간들일 것 같다. 좋은 기회가 닿아 선생님의 연희동 쿠킹 클래스에 참여해서 같이 수업을 듣는 제자분들과도 교감하면서 레시피를 배우고, 소중한 사람들에게 나의 공간에서 요리를 해주고 같이 먹으면서 대화하는 교감의 시간을 가지고 싶다.

선생님의 첫 책이라고 하는 셰프의 딸이라는 에세이를 구매하여서 조금씩 읽고 있는데, 여기에 레시피도 수록되어있는 거 같아서 배워봐야겠다.

선생님 강연을 듣고 나서, 독일 교환학생 시절에 독일친구와 서로 요리를 가르쳐주는 즐거운 시간을 보냈던 기억이 문득 생각이 났다. 마지막에 한국으로 돌아오기 전 독일 친구가 독일 레시피북을 선물해주었었는데, 그 친구의 따뜻한 마음이 생생하게 기억이나서 너무 고마웠다.

히데코 선생님의 아버지께서 프랑스 요리 쉐프라고 하셨는데, 우리 아빠가 생각났다. 칠할머니는 요리를 매우 잘하셔서 동네 잔치가 있으면 늘 불려가셨다고 한다. 그래서인지 명절에 먹는 친가 요리는 늘 맛있었는데, 우리 아버지도 친할머니의 손맛을 물려받아서 족발, 오리 백숙, 떡국, 시래기 된장국 등등 정말 다양한 정성스런 한식을 집에서 자주 요리해주셨었다. 나는 나물 무치는 것을 좋아하고 직접 요리했을 때 맛있게 먹는데, 친할머니부터 이어져오는 그 손맛을 물려받은 것 같다는 은근한 기쁨(?)이 있다. 앞으로 다양한 요리를 배워서 사랑하는 사람들에게 즐거운 시간을 제공하고 싶다.

나카가와 히데코 선생님과 마음산책 출판사 분들께 좋은 강연 시간과 정성이 담긴 음식을 제공해주셔서 마음깊이 감사의 인사를 드립니다 🙂

Machine Learning Scholarship Program for Microsoft Azure 소개

Microsoft Scholarship Recipient

안녕하세요,

오늘은 Udacity의 Microsoft Azure Machine Learning 장학금 프로그램에 대한 이야기를 공유하고 싶습니다.

1단계 프로그램은 2020년 7월 8일부터 9월 30일까지 진행되었는데요, 전 세계 10,000명의 학생들이 Microsoft와 Udacity의 큰 지원을 받아 참여하는 프로그램입니다.

10,000명이 참여하는 프로그램이다보니 정말 엄청나게 열정적으로 다양한 아이디어가 공유되는 것을 체험할 수 있었습니다. 저는 마치 대학생 시절로 돌아간 느낌을 받았는데요, 그만큼 학생들과 같이 공부하면서 성장하는 “커뮤니티 리더십”이 모토인 프로그램이기 때문에 그동안의 온라인 코스들 중에서 가장 인상깊었던 프로그램이었습니다.

감사하게도 1단계와 2단계 장학금 프로그램을 모두 참여할 수 있게 되었는데요, 이 프로그램에 대한 간단한 소개 및 배웠던 점을 공유하고자 합니다. 이 글을 읽으시는 분들에게 조금이나마 도움이 되었으면 좋겠습니다 🙂

1. Microsoft Azure Machine Learning Scholarship 프로그램 1단계, 2단계 소개

이 장학금 프로그램에는 두 단계가 있습니다. 첫 번째 단계에서 지원자는 Data Science에 대한 사전 지식과, 이 프로그램에 참여해야하는 이유에 대해서 제출합니다. 첫번째 단계에서는 전세계에서 10,000명이 선발됩니다.

장학금 프로그램에 대한 자세한 정보는 아래 링크를 참조해주시면 됩니다.

1단계에서 학생들은 머신러닝 이론과 Azure 클라우드 플랫폼에 대해 배우고, Azure 환경 내에서 Hands-On을 진행합니다.

이 프로그램에서 Slack 메신저는 매우 중요한 커뮤니케이션 채널입니다. Slack을 통해서 다양한 이벤트에 대한 안내를 진행하는데요, 학생들이 자발적으로 만드는 이벤트도 같이 진행됩니다.

1단계를 마치면 300명의 학생들이 Microsoft Machine Learning Engineer Nanodegree 프로그램의 2단계 장학금을 받게 됩니다. 이 2번째 단계 프로그램은 10월 13일에 시작되었습니다.

마이크로소프트 Azure의 부사장 Julia White는 이 2번째 단계 프로그램에 대해서 다음과 같이 말했습니다.

” 이 새로운 Nanodegree 프로그램은 학생들에게 기계 학습 (ML)에서 심화된 기술 능력을 개발할 수있는 기회를 제공합니다. 학생들은 Azure Machine Learning을 사용하여 정교한 ML 모델을 구축하고 배포하여 기술을 강화합니다. ML 모델을 트레이닝하고, ML 파이프 라인을 관리하고, 하이퍼파라미터를 조정하여 모델 성능을 개선하는 방법을 배웁니다. 모델이 준비되면 학생들은 자동화, CI / CD 및 모니터링을 포함한 올바른 MLOps 사례를 사용하여 모델을 운영하는 방법을 배우게 됩니다. “

2. 1단계에서 배웠던 Lessons Learned

  • 전세계 다양한 나라에서 온 열정적인 학생들, 집단지성의 힘

이 프로그램을 진행하는 동안 저는 두 개의 스터디 그룹에 참여했었는데요, 그곳에서 정말 열정적인 다양한 배경을 지닌 분들을 만날 수 있었습니다. 한국, 미국, 모로코, 인도 등 다양한 나라에서 온 Data Science 컨설턴트, 로봇 공학 엔지니어, 헬스케어 Tech Lead, Tableau 전문가, 클라우드 솔루션 아키텍트 전문가 등 정말 다양한 배경의 분들을 만나면서 다양한 영감을 얻었습니다. 매주 일요일 오전 9시부터 오전 11시까지 온라인 스터디 그룹에서 머신 러닝 책 한 권과 Kaggle Competition Challenge를 공부했는데요, 혼자라면 하기 어려웠을 공부를 함께하면서 프로그램이 진행되는 동안 끝까지 같이 마무리할 수 있었습니다.

그 외에도 많은 슬랙 채널에서 활동하는 학생들의 메세지를 읽으면서 배울 수 있었는데요, Kaggle, 커리어, 머신러닝 등 여러 주제에 대해서 토론하는 많은 채널이 있었습니다. 이런 게 있었구나 싶을 정도로 다양하게 의견 교류를 하고 유용한 정보를 활발하게 공유하는 학생들을 보면서, 단기간 내에 이렇게 결속력이 강한 Learning Group에 속해있다는 게 너무 놀랍고 신기했던 순간이 많았습니다.

이 프로그램에서 진행하는 “Student Story Challenge” 이야기도 정말 좋았었는데요, 요즘 상황이 힘들지만 다양한 나라에서 온 많은 분들이 어려운 상황 속에서도 열심히 공부하는 이야기도 많았고, 이 프로그램이 전 세계 사람들을 하나의 커뮤니티로 만들었구나 하는 느낌을 프로그램을 진행하면서 많이 받았습니다.

  • 영감을 주는 다양한 이벤트와 적극적인 서포트

보통 온라인 코스를 수강 할 때는 자기 페이스대로 공부하고 학생들 간의 교류가 많지 않은데요,

특히 이 프로그램은 슬랙을 통해서 굉장히 많은 사람 간의 상호작용이 있습니다. Palak Sadani는 이 프로그램의 커뮤니티 매니저인데요, 1단계가 진행하는 동안 전 세계 만 명의 학생들과 정말 적극적으로 소통했습니다. 저도 이 프로그램 1단계가 진행되는 기간동안 그분으로부터 많은 영감을 주는 공지를 받았었는데 동기부여가 되었습니다.

위의 슬랙 메시지에서 볼 수 있듯이, 학생들을 위한 동기부여 이벤트나 챌린지가 많았기 때문에 꾸준히 학습을 지속하는 것에 도움을 받았습니다.

그리고 학생들은 필요한 경우 스스로 이벤트들을 만들어서 진행했기 때문에, 위에 메세지에 표시된 이벤트 외에도 다양한 이벤트들이 있었습니다.

  • 마이크로소프트 머신러닝 플랫폼 학습 기회

학생들은 클라우드 플랫폼에서 머신러닝 이론과 Microsoft Azure 솔루션을 배울 수 있습니다. 예를 들어, 머신러닝 분야에서 매우 핫한 분야 중에 하나인 Automated Machine Learning과 AI Explainability와 관련된 솔루션을 직접 Hands-On하면서 배울 수 있는 기회가 제공됩니다.

Image for post
Automated Machine Learning

그리고 Microsoft 전문가를 만날 수 있는 특별한 QnA 라이브 웨비나 시간도 있었습니다. 나중에 녹화본도 제공하지만, 라이브로 참여하고 싶어서 한국 시간으로 새벽 2시에 참여했던 기억이 생생합니다 🙂

3. 마무리하며

이 프로그램에 참여하면서 전세계의 많은 사람들이 배움을 통해 삶을 변화시켜나간다는 것을 느꼈습니다. 팬데믹으로 인해 전 세계적으로 매우 어려운 상황이지만 많은 분들이 Microsoft Udacity Machine Learning Scholarship과 같은 좋은 취지의 프로그램을 통해서 많은 영감을 받으실 수 있었으면 좋겠습니다.

끝으로 Microsoft 사장이신 Satya Nadella의 유명한 명언을 공유하고 싶습니다.

“Finally, I truly believe that each of us must find meaning in our work. The best work happens when you know that it’s not just work, but something that will improve other people’s lives.”

Introduction to Machine Learning Scholarship Program for Microsoft Azure

Microsoft Scholarship Recipient

I’d like to share stories for the Machine Learning Scholarship Program for Microsoft Azure in Udacity. The Phase 1 program ran from July 8th to September 30th in 2020.

It was one of the most motivational programs in Udacity since 10,000 students all around the world participated with great supports from Microsoft and Udacity. Because “Community Leadership” is the goal of this program, I was able to naturally learn the positive atmosphere that emphasized learning together energy.

Can you imagine how many ideas can be shared among enthusiastic 10,000 students? 🙂

I was very moved by sincere supports from Microsoft and Udacity. They made miracles for 10,000 students. Palak Sadani is the community leader of this program and she has done awesome works during this 3 months journey. The interactions between people were very special and great advantages here compared to any other learning programs. I felt like I was back in university since there were many special learning events with students.

Thanks to this program, I’ve learned very much by following the learning activities here and I could get the Phase 2 scholarship. I’d like to introduce this program and want to share my personal story during this journey. I hope this post can provide some helpful information to people who are interested in this program.

1. A Brief Introduction for Phase 1 & Phase 2

There are 2 phases for this special scholarship program. In the first phase, applicants will submit about their current knowledge in data science and why they need to particiate in this program. 10,000 students won the 1st phase scholarship.

You can find more information for this scholarship program by referring to the below link.

In the 1st phase, students will learn about machine learning concepts and Azure cloud platforms. Also students can do the hands-on within the Azure environments.

Here, slack is the very important communication channel so students can follow interesting events and learn together. There are great official events but also students voluntarily have created their own learning events.

After the completion of 1st phase, 300 students will win the 2nd phase scholarships for Microsoft Machine Learning Engineer Nanodegree program. This time the program began on October 13th.

“This new Nanodegree program offers students the opportunity to develop deeper technical skills in machine learning (ML). Students will strengthen their skills by building and deploying sophisticated ML models using Azure Machine Learning. They will learn how to train ML models, manage ML pipelines, and tune hyperparameters to improve model performance. Once the model is ready, students will learn how to operationalize the model with the right MLOps practices, including automation, CI/CD, and monitoring” according to the Julia White Corporate Vice President, Microsoft Azure.

2. Special Highlights in Phase 1

There were special highlights in Phase 1.

  • Enthusiastic Students with Diverse Backgrounds, the Community Power

I’ve joined in two study groups during this program and I could meet interesting people there. A Data Science Consultant, a Robotics Engineer, a Healthcare Tech-Lead, a Tableau Expert, a Cloud Solution Architect Expert …etc from the US, Morocco, India, Korea …etc. Every Sunday from 9 am to 11 am, I studied one machine learning book and one Kaggle competition challenge in the study group. We’ve learn many things by studying together, which would be difficult to do if I were alone.

There were many many active students in many slack channels. For several topics such as kaggle, career, learning subjects, technical issues … there were many slack channels to support all the brilliant ideas. Various youtube links, technical posts … are shared for many times.

There is such a saying in the proverb, “Two heads are better than one”. How about 10,000 students ideas? Creativity exploded 🙂

Also I really loved the stories from “Student Story Challenge” of this program. There are many great people even though situations are hard these days but keep studying hard. I felt that this program made people all over the world into one community.

  • Motivational Events & Supports

Usually when students take online courses, they study by themselves. There are not many human interactions.

But here, there are many many many human interactions on slack. Palak, who is the community manager of this program, has actively communicated with students all around the world. I’ve often gotten many motivational announcements from her during this program.

As you can see the above slack message, there were many motivational events or challenges for students so it’s easier to keep the learning progress steadily.

Also students can create more official / unofficial events if needed, so actually there were more events.

  • Microsoft Azure Machine Learning Opportunity

Students can learn machine learning theories and also Microsoft Azure solutions on their cloud platform. Since Microsoft is one of the leading IT companies in the world, the concepts are really interesting and trendy. For example, Automated Machine Learning and AI Explainability are really important topics in Machine Learning. Students can take relevant courses and can do hands-on to practice those important solutions on Azure.

Image for post
Automated Machine Learning

Also there was a special QnA live webinar to meet Microsoft experts.

3. Conclusion

As I participated in this program, I felt that many people are changing their lives through learning. It is a very difficult situation around the world because of the pandemic, but I hope that many people could find good inspiration and empowerment to create new opportunities from this motivational scholarship program which strongly emphasizes the community during the learning journey.

I would like to conclude this post with one famous quote from Microsoft President Satya Nadella,

“Finally, I truly believe that each of us must find meaning in our work. The best work happens when you know that it’s not just work, but something that will improve other people’s lives.”

Mac에서 어플리케이션 Screen Recording 옵션 활성화하기

Mac에서 어플리케이션 Screen Recording 옵션을 활성화하는 방법에 대해 알아보도록 하겠습니다.

간혹 미팅 앱을 사용할 때, 화면 공유 옵션을 누르면 자동으로 설정의 Security & Privacy 메뉴에서 Screen Recording을 허락할 것인지 친절하게 물어는데요,

여기서 Screen Recording을 허용하려는 어플리케이션이 아예 안 뜨는 경우가 있습니다. 그러면 옵션을 활성화해야하는데, 그 어플리케이션 자체가 안 보이다보니 허락을 못해서 화면 공유를 못하게 됩니다. 저의 경우 zoom 앱을 새로 다운로드 받았을 때 화면 공유를 하려고 하니까 시스템 설정에서 Screen Sharing을 허락하라고 하는데, 아래처럼 옵션에서 zoom 앱이 보여야하는데, 아예 없어서 허락을 못하는 상황이었습니다.

아마도 맨 처음에 설치할 때 실수로 Screen Sharing을 하겠냐는 질문창을 스킵해서 다시는 그 질문창이 안 뜨면서 허용 앱 리스트에서 안 보이는 것일 수 있습니다.

어플리케이션을 다시 지웠다가 새로 깔면 다시 물어보기 때문에 된다고 하지만 이것보다는 terminal에서 간단하게 컨트롤하는 방법을 소개해드리려고 합니다.

  1. app id 찾기

먼저 스크린 공유를 하고 싶은 앱의 id를 찾습니다. terminal을 실행한 후 아래 명령어를 타이핑하시면 app id가 출력됩니다. mdls -name kMDItemCFBundleIdentifier -r <YOUR APP NAME & EXTENSION> 이라는 명령어이고 zoom 앱의 경우 이름과 확장자명이 zoom.us.app 이었습니다. (Name & Extension 란에서 확인하실 수 있습니다.)

그래서 다음과 같이 타이핑하면,

mdls -name kMDItemCFBundleIdentifier -r zoom.us.app

터미널 결과로 us.zoom.xos% 가 출력되는데요, 이를 통해서 zoom 앱의 아이디는 us.zoom.xos 인 것을 알 수 있습니다.

2. Screen Recording 상태 리셋하기

Screen Recording 상태를 리셋하는 이유는, 리셋을 통해서 컴퓨터에서 직접 Screen Recording 하겠냐고 다시 물어보도록 하기 위해서입니다. 명령어는 tccutil reset ScreenCapture <YOUR APP ID> 입니다.

tccutil reset ScreenCapture us.zoom.xos

위와 같이 터미널에서 커맨드를 실행하면, zoom앱에서 Screen Recording 허락을 하겠냐는 질문을 맥북에서 다시 합니다. 그 때 시스템 설정에서 허용해주시면 됩니다.

Disaster Tweet 코드 분석 1편 – 데이터 탐색

이번 포스트에서는 Kaggle의 Real or Not NLP with Disaster Tweet 캐글 컴퍼티션에서 Most Votes를 받은 주피터 노트북 코드를 정리해보려고 합니다. 참고한 코드는 현재 포스트에 표시된 하이퍼링크를 클릭하시면, 보실 수 있습니다. 코드는 그대로 사용하지는 않고, 설명을 위해 약간의 수정을 하였습니다.

이번 포스트의 전체 목차는 크게 4가지로 구성되어 있습니다.

  1. Data Column & Row
  2. Tweet Words Distribution
  3. Tweet Stop Words Distribution
  4. Tweet Most Common Words Distribution

1. Data Column & Row

먼저 데이터를 살펴보도록 하겠습니다.

Columns
  • id – a unique identifier for each tweet
  • text – the text of the tweet
  • location – the location the tweet was sent from (may be blank)
  • keyword – a particular keyword from the tweet (may be blank)
  • target – in train.csv only, this denotes whether a tweet is about a real disaster (1) or not (0)

총 5개의 칼럼으로 이루어져 있는데요, id는 각각의 트위터 레코드의 식별자이고, text는 트윗 텍스트, location은 트위터를 보낸 장소, keyword는 트윗의 특정 키워드, target은 트위터가 실제로 재난인지 (1) 아닌지 (0) 를 표시한 것입니다.

location과 keyword는 경우에 따라 null일 수 있고, target은 트레이닝 데이터에만 있습니다. 참고로 캐글 컴퍼티션의 경우 예측하려는 목표 칼럼은 트레이닝 데이터에만 표시가 되어있고, 테스트 데이터에는 그 부분은 비어있어서 컴퍼티션 참여자가 직접 그 부분을 채워서 제출하면 정답은 알 수 없지만 score를 통해 자신이 제출한 답의 정확성을 가늠할 수 있게 되어있습니다.

tweet = pd.read_csv('../input/nlp-getting-started/train.csv')
test = pd.read_csv('../input/nlp-getting-started/test.csv')
tweet.head(3)

pandas 라이브러리를 통해 상위 3개의 레코드를 살펴보면 다음과 같은 데이터가 보입니다. 여기서 tweet은 트레이닝 데이터이고 test는 테스트 데이터입니다. head()는 디폴트로 상위 5개의 레코드를 보여주는데 예시에서는 괄호 안에 3을 명시함으로써 상위 3개의 데이터를 출력합니다.

keyword, location 정보는 비어있고 target의 값은 모두 1로 재난에 대해서 얘기하고 있는 트윗입니다. 내용을 읽어보아도 earthquake (지진), Forest fire (산불), shelter (대피소) 등 재난과 관련성이 깊은 단어들입니다.

print('There are %d rows and %d columns in train' %(tweet.shape[0],tweet.shape[1]))
print('There are %d rows and %d columns in train' %(test.shape[0],test.shape[1]))

트레이닝 데이터 tweet과 테스트 데이터 test 데이터 프레임에서 각각의 row와 column 수를 출력해보면, 다음과 같이 나옵니다. 트레이닝 데이터의 경우 7613개의 row와 5개의 column으로 이루어져있고, 테스트 데이터는 3263개의 row와 4개의 column 입니다. test 칼럼이 4개인 이유는 target 칼럼이 없기 때문입니다. 즉, 정답지는 트레이닝 데이터에만 있고 테스트 데이터는 없습니다.

value_counts()를 통해 전체 데이터에서 target 칼럼에 있는 1,0의 갯수가 어떻게 되는지 알 수 있고, 이를 barplot으로 그리면 다음과 같습니다.

x = tweet.target.value_counts()
sns.barplot(x.index,x)
plt.gca().set_ylabel('samples')

0 (재난이 아님) 의 경우 1 (재난임) 일 때보다 더 많은데요, 실제 세계에서 트윗 전체를 본다면 0이 1보다는 훨씬 더 많지 않을까 싶습니다. 즉, 재난이라는 비상사태에 대해서 말하는 트윗보다는 다른 주제에 대한 트윗의 비중이 높을 것 같습니다.

2. Tweet Words Distribution

이제 한 트윗당 글자 수의 분포를 살펴보겠습니다.

fig,(ax1,ax2)=plt.subplots(1,2,figsize=(10,5))
tweet_len = tweet[ tweet['target']==1 ]['text'].str.len()
ax1.hist(tweet_len,color='red')
ax1.set_title('disaster tweets')
tweet_len = tweet[ tweet['target']==0 ]['text'].str.len()
ax2.hist(tweet_len,color='green')
ax2.set_title('Not disaster tweets')
fig.suptitle('Characters in tweets')
plt.show()

재난에 관한 트윗이나, 재난과 관련되지 않은 트윗 모두 120~140 글자 수를 주로 갖고 있는 것을 위 분포를 통해 볼 수 있습니다.

이제 한 트윗 안에 단어가 몇 개 들어있는지 살펴보겠습니다.

fig,(ax1,ax2)=plt.subplots(1,2,figsize=(10,5))
tweet_len = tweet[ tweet['target']==1 ]['text'].str.split().map(lambda x: len(x))
ax1.hist(tweet_len,color='red')
ax1.set_title('disaster tweets')
tweet_len = tweet[ tweet['target']==0 ]['text'].str.split().map(lambda x: len(x))
ax2.hist(tweet_len,color='green')
ax2.set_title('Not disaster tweets')
fig.suptitle('Words in a tweet')
plt.show()

코드를 좀 더 설명하자면, tweet==0]['text'].str.split() 은 각 트윗에 있는 단어 스트링을 기준으로 split을 한 리스트입니다. ['I', 'love', 'fruits'] 처럼 I love fruits 라는 원 문장을 단어 string 기준으로 쪼갠 리스트입니다. 여기에 map(lambda x: len(x)) 을 적용하면 한 트윗 안에 단어가 몇 개 있는지 알 수 있습니다. ['I', 'love', 'fruits']의 경우는 한 트윗 안에 단어가 3개 있습니다.

전체적으로 보면, 한 트윗 안에 주로 10 ~ 20개 단어 정도 있는 것을 볼 수 있습니다.

한 트윗 내 개별 단어의 길이를 살펴보겠습니다.

fig,(ax1,ax2)=plt.subplots(1,2,figsize=(10,5))
word = tweet[ tweet['target']==1 ]['text'].str.split().apply(lambda x : [len(i) for i in x])
sns.distplot(word.map(lambda x: np.mean(x)),ax=ax1,color='red')
ax1.set_title('disaster')
word = tweet[ tweet['target']==0 ]['text'].str.split().apply(lambda x : [len(i) for i in x])
sns.distplot(word.map(lambda x: np.mean(x)),ax=ax2,color='green')
ax2.set_title('Not disaster')
fig.suptitle('Average word length in each tweet')

Diaster 트윗과 Not Diasaster의 모두 주로 대략 length가 5~6 정도 되는 단어들이 많은 것을 알 수 있습니다.

3. Tweet Stop Words Distribution

이제 stop word가 얼마나 많은지 살펴보려고 하는데, 그 전에 corpus, 말뭉치 리스트를 만들어주는 함수를 정의하여 사용할 것입니다.

def create_corpus(target):
    corpus=[]
    
    for x in tweet[ tweet['target']==target ]['text'].str.split():
        for i in x:
            corpus.append(i)
    return corpus

이 함수를 살펴보면, 특정 target 칼럼의 트윗을 string 기준으로 split해서 단어 리스트를 만든 후에, 그 리스트 안에 들어있는 개별 단어를 corpus 라는 리스트에 append를 합니다. 그렇게 해서, 예를 들어 target이 0인 트윗들에 들어있는 모든 단어를 corpus라는 리스트에 전부 append를 하여 target이 0일 때의 전체 단어 리스트를 만드는 것입니다. corpus = create_corpus(0) 이 바로 target이 0인 (즉, 재난이 아닌 경우) 트윗들에 들어있는 모든 단어 리스트를 생성하는 것입니다. 여기에다가 dic이라는 딕셔너리를 생성하여, 만약 corpus 안에 있는 word가 stop이라는 nltk.corpus 말뭉치에서 영어 stop words set 안에서 발견되면, dic에서 word 키를 기준으로 value를 1씩 증가시켜서 해당 word가 전체 단어 리스트에서 얼마나 있는지 카운트를 합니다.

corpus=create_corpus(0)

dic = defaultdict(int)
for word in corpus:
    if word in stop:
        dic[word]+=1
        
top=sorted(dic.items(), key=lambda x:x[1],reverse=True)[:10] 

참고로 영어 stop words는 from nltk.corpus import stopwords >> stop=set(stopwords.words('english')) 이렇게 정의해서 얻어지는 set 입니다. Python에서 set이란 중복되는 값이 없고, 정렬되지 않는 자료형입니다. 즉, stop이라는 set에는 중복되지 않고 정렬되지 않은 영어 stop words가 들어있습니다.

여기서 top은 stop words dictionary를 value를 기준으로 내림차순으로 정렬하여, 그 중 위에서 10개를 뽑은 리스트입니다. top을 그래프로 나타내면 다음과 같은데, the, a, to 등 재난 여부를 판단할 때 의미없는 단어들의 분포 수를 알 수 있습니다.

x,y = zip(*top)
plt.bar(x,y)

target 1인 트윗들도 위와 같은 방식을 통해서 stop words의 분포를 살펴볼 수 있습니다.

이제 punctuation 문자의 분포를 살펴보겠습니다.

plt.figure(figsize=(10,5))
corpus = create_corpus(1)

dic = defaultdict(int)
import string
special = string.punctuation
for i in (corpus):
    if i in special:
        dic[i]+=1
        
x,y=zip(*dic.items())
plt.bar(x,y)

이번에는 target이 1인 트윗들의 총 단어 리스트에서 특수 문자 분포를 살펴보았는데요, 보시면 - 라는 특수문자가 제일 많습니다. target이 0인 경우도 비슷한 방식으로 해보면 - 라는 특수문자가 제일 많습니다.

4. Tweet Most Common Words Distribution

이제 가장 흔한 단어를 살펴보겠습니다. 우선 target이 0인 트윗들의 전체 단어 리스트에서 가장 많은 단어 40개를 고르고, 그 중에서 stop word와 punctuation이 아닌 단어만 뽑아서 barplot을 그려보면 다음과 같습니다.

corpus = create_corpus(0)
counter = Counter(corpus)
most = counter.most_common()
x=[]
y=[]
for word,count in most[:40]:
    if (word not in stop and word not in special) :
        x.append(word)
        y.append(count)

주로 재난 여부와 무관한 단어들이 전체 단어에서 많은 비중을 차지하는 것을 알 수 있습니다. 데이터 클렌징 대상으로 파악될 수 있습니다.

여기까지 데이터 탐색을 해보았고, 다음 포스트에서 Ngram 분석을 진행해보도록 하겠습니다. Ngram이란 n개의 연속적인 단어 나열입니다. 예를 들어, “The book is really interesting” 이라는 문장이 있을 때, n=2인 bigrams로 구분하면 “The book”, “book is”, “is really”, “really interesting”이 됩니다. 다음 포스트는 n=2인 Ngram 분석에 대한 내용입니다.

긴 글 읽어주셔서 감사합니다 🙂

Hash Table 해쉬 테이블이란?

Hash Table이란 효율적인 key value lookup을 위해 key를 value에 매핑하는 자료 구조입니다. 찾는 과정을 살펴보면, 먼저 hash function을 사용해서 hash code 값을 계산합니다. key를 변환해서 더 작은 key로 만드는데 사용되는 함수가 hash function 인데요, 그렇게 해서 얻어진 값인 hash(key) 값이 hash code 입니다.

이 hash code를 array length로 나누어 얻어진 나머지를 index로 사용해서 해당 index에 매핑되는 value를 array에 저장하고 찾는 것입니다.

예를 들어, [“apple”, “banana”, “lemon”] 이라는 key 배열이 있다고 가정하면 python에서 hash function을 사용해서 hash code를 얻으면 각각 값이 4431541238040168687, 7306034771644922176, 3404778505129102945 이 됩니다. array의 length는 3이기 때문에 각각을 3으로 나눈 나머지는 0, 1, 1 입니다. 그리고 이 값들이 index가 되어서 해당 index에 있는 value가 원래 key인 “apple”, “banana”, “lemon”에 매핑되는 값입니다.

이 경우에서도 볼 수 있지만 hash code가 다르더라도 동일한 index가 나올 수 있습니다. 또한 서로 다른 key에 대해서 hash code 값이 같을 수도 있어서 이 경우에도 동일한 index가 나올 수 있습니다.

이를 보완하기 위해 Linear Probing 기법에서는 index가 겹치면 그 다음 index를 사용합니다. 예를 들어, 아까처럼 “lemon”의 hash code를 3으로 나눈 나머지가 1로 “banana”의 index와 겹치면 1대신 2를 index로 사용합니다.

이러한 충돌이 매우 높으면 worst case로는 런타임이 O(N)이 됩니다. (여기서 N은 key의 갯수입니다.) 그러나 일반적으로 충돌이 최소한으로 발생한다고 가정하여 look up 타임을 O(1)로 가정합니다.

Binary Search 이진 탐색 알고리즘이란?

Binary Search, 이진 탐색 알고리즘이란 배열의 원소가 순서대로 sorting이 되어 있다는 가정하에 중간에 있는 element와 찾으려는 element의 크기를 비교해서 찾는 방식입니다.

크기를 비교해서 찾으려는 element보다 중간에 있는 element가 작으면 그 이하를 탐색에서 제외하고, 중간에 있는 element가 그보다 크면 그 이상도 탐색에서 제외합니다. 그래서 찾으려는 값과 중간에 있는 값이 같아질 때까지 반복합니다. 이렇게 하면 탐색 범위를 N/2, N/4 … 이런식으로 절반씩 줄여나갈 수 있다는 장점이 있습니다.

예를 들어, [1,2,4,5,6,7,8,9] 라는 배열에서 6을 찾는다고 가정합니다. 전체 8개로 이루어진 리스트의 중간 element는 약 3번째 index를 가진 5입니다. 그러면 5와 6을 비교했을 때 5보다 6이 크기 때문에 중간 element인 5 이하는 탐색에서 제외합니다. 그래서 6부터 9까지 보는데 여기에서 중간 위치에 있는 element는 7입니다. 7보다 6이 작기 때문에 7 이상부터는 탐색에서 제외합니다. 그러면 이제 6만 남기 때문에 찾는 것이 완료되게 됩니다.

다음은 Python으로 구현한 코드입니다. middle에 있는 값을 구해서 찾으려는 값과 비교하여 같으면 middle에 있는 값의 index를 리턴하고 만약 middle에 있는 값이 찾으려는 x보다 작으면 lower를 현재 middle index 값보다 + 1만큼 증가시켜서 middle 보다 큰 값에서부터 x를 찾습니다. 반대로 middle에 있는 값이 찾으려는 x보다 크면 upper를 현재 middle index 값보다 – 1 만큼 감소시켜서 middle보다 낮은 값에서부터 x를 찾습니다.

def binarySearch(L, x):
    lower = 0
    upper = len(L) - 1
    while lower <= upper:
        middle = (lower + upper) // 2
        if L[middle] == x:
            return middle
        elif L[middle] < x:
            lower = middle + 1
        else:
            upper = middle - 1
    return -1

Big O란?

Big O 란 컴퓨터 공학에서 알고리즘의 성능이나 복잡성을 측정하기 위해 사용되는 개념입니다. 주로 worst 시나리오를 가정하는데, input size가 증가함에 따라 알고리즘의 실행 소요시간(Time Complexity) 또는 메모리나 디스크 상에서 차지하는 공간(Space Complexity)을 나타냅니다. 개념에 대한 설명은 Cracking the Coding Interview의 순서를 따랐습니다.

  1. 1. Time Complexity

표기는 O(N), O(N^2) 처럼 표시 됩니다. 예를 들어 O(N)이라는 것은 input size에 “선형적”으로 런타임이 비례하는 것입니다.

기울기가 1인 Y = X 라는 그래프를 생각해보았을 때 아래 그래프처럼 선형적인 모양이 생각나실 텐데요, X 값이 증가함에따라 선형적으로 Y 값도 증가하는 것처럼 O(N)도 input N의 크기에 따라 선형적으로 런타임이 증가한다고 이해할 수 있습니다.

  1. 2. Space Complexity

Space Complexity는 알고리즘이 차지하는 메모리를 나타냅니다. 예를 들어 size가 n인 배열을 생성한다고 하면 O(N) 만큼의 space를 차지한다고 보면 됩니다.

3. Drop the Constants

Big O에서 상수만큼 곱해진 것은 고려하지 않는 것입니다. 예를 들어 O(2N) 으로 보여지는 것도 결국 O(N)과 같습니다.

예를 들어 for loop 하나 안에 if 절 2개가 정의된 것이나 for loop 하나에 if 절 하나, 그 다음 for loop 하나에 if 절 하나인 것이나 같습니다. 다음은 pseudo 코드로 간략하게 로직을 적어본 것입니다.

# O(N)
for loop:
    if 절 첫번째
    if 절 두번째

# O(2N) 이나 결과적으로 O(N)
for loop:
    if 절 첫번째
for loop:
    if 절 두번째

4. Drop the Non-Dominant Terms

Big O를 계산할 때 큰 영향을 끼치지 않는 것은 제외하는 것입니다. 예를 들어, O(N^2 + N)에서 N은 Big O 계산시에 영향력이 있는 값이 아니기 때문에 N을 제외해서 O(N^2) 으로 나타냅니다. 왜냐면 N이 커지면 커질수록 N을 더하는 것의 영향력은 작아지고 N^2의 영향력이 주요하기 때문입니다.

앞서 살펴본 Drop the Constants 원칙과 비슷한 맥락으로 이해할 수 있습니다.

5. Multi-Part Algorithms: Add + Multiply

만약 알고리즘이 A를 먼저하고 그게 끝나면 그 다음에 B를 하라고 하면 O(A+B)입니다. 반면에 A를 할 때마다 B를 하라고 하면 O(A*B) 입니다. 이러한 로직으로 런타임을 더하거나 곱할 수 있습니다. 다음은 pseudo 코드로 간략하게 로직을 적어본 것입니다.

# O(A+B) --> A 끝나고 B
for loop (A):
for loop (B):

# O(A*B) --> A의 element 마다 B 실행
for loop (A):
   for loop (B):

6. Amortized Time

Amortized Time 이라는 개념은 worst case가 가끔 발생하지만 한 번 발생하면 한동안은 발생하지 않는다는 것입니다. 예를 들어 array에 element가 추가되다가 어느 순간 capacity에 한계가 오면 새로운 array를 capacity를 double로 해서 생성한다고 할 때, 그 새로운 array에 모든 element를 복제합니다. 이 경우 element를 insertion 하는데 걸리는 런타임을 어떻게 표시할 수 있을까요?

N개의 element를 포함하는 array의 용량이 꽉 차서 사이즈가 2N인 새로운 array로 옮겨갈 경우, 새로 만들어진 array에 기존 element를 추가하는 시간은 O(N)일 것입니다.

그렇지만 이렇게 꽉차서 새로운 array를 생성해서 element를 insert해야하는 상황은 자주 발생하지 않습니다. 따라서 기존에 있던 array에 element를 추가하는 대부분의 insertion하는 시간은 O(1) 입니다.

따라서 어쩌다 한 번 발생하는 worst case의 경우 O(N), 그리고 평균적으로 insertion 하는 case는 O(1) 입니다.

이렇게 size를 증가시키는 배열을 동적 배열 dynamic array 라고 하는데요 좀 더 자세히 살펴보겠습니다. 예를 들어 element가 1개 있을 때 배열이 꽉 찼다라고 보면 이 배열의 사이즈를 2배 늘리는 것입니다. 그러면 사이즈가 원래 1 이었는데 1*2 해서 2로 늘어납니다. 여기서 element가 새로 추가되면서 size 2가 꽉 차게 됩니다. 그러면 size를 2배 늘려서 2*2 = 4 size인 배열이 만들어집니다. 이 상태에서 element 들이 추가되다가 결국 size 4도 꽉 차게 됩니다. 그러면 또 2배 늘려서 size가 8인 배열이 만들어지고 기존에 있던 element들이 이 새로운 사이즈의 배열로 복제됩니다.

이런식으로 계속 기존 배열에 element를 추가하다가 사이즈가 꽉차서 2배만큼 double로 사이즈를 늘리게 되면 공식으로는 1+ 2+ 3+ 8 + 16 + … + X 만큼 런타임이 소요되게 됩니다.

이 수식을 거꾸로 써보면 X + X/2 + X/4 + X/8 + … + 1 이렇게 되는데요 다시 이 공식을 수정하면 X( 1 + 1/2 + 1/4 + 1/8 + …..) = X*(1+1) = 2X 가 됩니다. 1/2 + 1/4 + … 를 다 더하면 이 값이 아래 위키피디아를 참고한 공식에 의해서 총 1이 되기 때문에 다 더하면 2X가 되는 것입니다.

frac12+frac14+frac18+frac{1}{16}+cdots = sum_{n=1}^infty left({frac 12}right)^n = frac {frac12}{1-frac 12} = 1.

그러면 worst case로 X 만큼 insertion하는 시간은 O(2X) 만큼의 time이 소요됩니다. 여기서 Drop the Constants라는 법칙에 따라서 2를 날려버리게 되면 array 사이즈가 꽉차서 새로 배열을 만들어 기존의 element들을 복제하는데 걸리는 시간은 결과적으로 O(N)이 됩니다.

그러나 이러한 케이스는 드물게 어쩌다 발생하는 것이고, 평소에는 element를 하나씩 추가하기 때문에 O(1) 만큼의 시간이 걸립니다.

7. Log N Runtimes

Binary Search 알고리즘을 통해 Log N 런타임을 이해해보도록 하겠습니다. Binary Search 알고리즘이란 간단하게 말해서 element가 순서대로 sorting이 되어있는 배열에서 원하는 값 x를 찾을 때 배열의 중간에 있는 값과 크기를 비교해서 범위를 축소해나가면서 x를 찾는 알고리즘입니다. 알고리즘의 탐색 범위가 N/2, N/4, N/8 이런식으로 절반씩 줄어들기 때문에 O(log N) 으로 나타낼 수 있습니다. 따라서 탐색 스페이스가 절반씩 줄어드는 알고리즘은 O(log N) 만큼의 complexity를 가진다고 볼 수 있습니다.

예를 들어 [1, 5, 8, 9, 11, 13, 15, 19, 21] 에서 N은 8 >> 4 >> 2 >> 1 이런식으로 탐색 범위가 절반식 줄어든다고 이해할 수 있습니다. 이 순서를 거꾸로 하면 N = 1 >> 2 >> 4 >> 8 이라고 볼 수 있는데 2^3 이 8 이고 log를 씌우면 log 8/log 2 = 3 즉 log N/log 2 = k 여기서 constant인 1/log 2 를 drop 하면 O(log N)이 됩니다.

8. Recursive Runtimes

결론적으로 재귀함수의 space complexity는 O(N) 입니다. 재귀함수는 전체적으로 O(2^N) 만큼의 노드가 있지만 주어진 시간 내에서 차지하는 메모리는 O(N) 입니다.

먼저 재귀함수의 전체 노드를 카운트해 보면 2^0 + 2^1 + 2^2 + … + 2^N 입니다. 수학적으로 다 더하면 2^(N+1) – 1 입니다. 따라서 노드의 수는 O(2^(N+1) – 1) 인데 Constant와 Non Dominant Terms를 제외하면 O(2^N) 이 됩니다. 그러나 주어진 시간에서는 O(N) 만큼의 메모리만 차지합니다. 그 이유는 호출되는 수와 무관하게, 처리되는 것은 depth만큼 누적되기 때문입니다. 예를 들어 다음과 같은 함수가 있을 때,

int f(int n) {
	if (n <= 1) {
	return 1;
	}
	return f(n - 1) + f(n - 1)
}

n = 4일 때 f(4) = f(3) + f(3) 인데 여기서 f(3)이 처리되고 순서상 바로 f(2) >> f(1) 까지 순차적으로 처리 되어야만 그 때부터 누적된 것들이 거슬러 올라가면서 처리됩니다. 즉 가장 먼저 처리되는 순서를 보면 f(4) >> f(3) >> f(2) >> f(1) 이기 때문에 depth인 4만큼이 메모리를 차지합니다. 따라서 O(N) 만큼의 space complexity를 차지한다고 볼 수 있습니다.

Quick Sort 알고리즘이란?

안녕하세요 이번 포스트에서는 Quick Sort 알고리즘의 정의를 알아보고 Quick Sort를 Python으로 구현한 코드까지 같이 살펴보도록 하겠습니다.

Quick Sort 알고리즘은 divide and conquer 방식으로 배열을 나누어 가면서 정렬하는 방식으로 다음과 같이 계산됩니다.

1) 배열에서 pivot(중심점)을 선택합니다.

2) 두 번째로, 선택된 pivot보다 작은 값들은 왼쪽으로 큰 값들은 오른쪽으로 움직입니다.

3) 이 과정은 위의 pivot보다 작은 값들로 이루어진 sub array에서도 반복되고 pivot보다 큰 값들로 이루어진 sub array에서도 반복되어서 배열 전체 값이 정렬될때까지 재귀적으로 이루어집니다. 그렇게해서 결과적으로 순서대로 배열이 정렬되게 됩니다.

자세한 설명은 아래 유투브 영상에서 시각적으로 보여주고 있어서 참고 링크를 첨부드립니다.

이 영상에서는 pivot을 선택하고 그 pivot을 기준으로 맨 왼쪽부터 체크해서 pivot보다 큰 값을 itemFromLeft로 정하고 맨 오른쪽부터 체크해서 pivot보다 작은 값을 itemFromRight로 정합니다.

그렇게 해서 itemFromLeft의 순서가 itemFromRight보다 Left 즉 왼쪽에 위치하면 두 값을 서로 교체하고 반대로 itemFromLeft의 순서가 itemFromRight보다 Right 즉 오른쪽에 위치하면 itemFromLeft 값을 pivot과 교체합니다. index로 표현하면 index(itemFromLeft) < index(itemFromRight) 이면 두 값을 교체하지만 index(itemFromLeft) > index(itemFromRight) 이면 이제itemFromLeft를 pivot과 교체합니다.

그러면 pivot 기준 좌측에 있는 값들은 pivot보다 전부 작고 우측에 있는 값들은 pivot보다 전부 크게 됩니다.

이후 pivot 기준 좌측 sub array와 우측 sub array에서 위와 같은 과정을 반복하면 결과적으로 순서가 sorting이 됩니다.

관련해서 Python 코드를 보겠습니다. Python 코드는 아래 유투브 영상의 댓글에서 Mr. UncleChu 라는 분이 굉장히 깔끔한 코드를 써놓아서 이 코드를 가져왔고 제가 마지막 리턴하는 부분만 수정하였습니다. 원본 코드는 리턴하는 값이 sum([lesser, [a_array[0]], bigger], []) 인데, sum 함수 안에 숫자가 아닌 것을 넣을 경우 성능이 좋지 않기 때문에 그 한 줄만 바꾸었습니다.

from functools import reduce 

def quick_sort(a_array):
    if len(a_array) < 2: return a_array
    lesser = quick_sort([x for x in a_array[1:] if x <= a_array[0]])
    bigger = quick_sort([x for x in a_array[1:] if x >  a_array[0]])
    return reduce(lambda x, y: x+y, [lesser, [a_array[0]], bigger])

보시면 quick_sort 라는 재귀함수로 구성되어 있고 처음에 [6,2,3,5,9,0,1,7,8,10,4] 라는 배열이 있다고 하면, 이 코드에서 a_array[0] 즉 6은 최초의 pivot이 됩니다.

여기에서는 pivot을 선택할 때 전체 배열의 맨 처음, 중간, 끝 중에서 중앙값을 선택하는 방식으로 하지 않고 단순히 배열의 0번을 pivot으로 지정합니다.

재귀함수가 lesser 계산하면서도 있고 bigger 계산하면서도 있기 때문에 순서를 따라가는 것이 복잡하지만 위에 공유드린 코드에서 하나하나 값들을 print로 출력해서 보시면 이 순서를 따라가실 수 있을 것입니다. 하나하나 print 하는 코드는 다음과 같습니다.

from functools import reduce 

def quick_sort(a_array):
    print("start: ", a_array, len(a_array))
    if len(a_array) < 2: return a_array
    print("pivot 1: ", a_array[0], a_array)
    print("total 1: ",a_array[1:], "quick sort 1: ", [x for x in a_array[1:] if x <= a_array[0]])
    lesser = quick_sort([x for x in a_array[1:] if x <= a_array[0]])
    print("lesser: ", lesser)

    print("pivot 2: ", a_array[0], a_array)
    print("total 2", a_array[1:], "quick sort 2", [x for x in a_array[1:] if x >  a_array[0]])
    bigger = quick_sort([x for x in a_array[1:] if x >  a_array[0]])
    print("bigger: ", bigger)
    print(lesser, a_array[0], bigger)
    print("answer: ", reduce(lambda x, y: x+y, [lesser, [a_array[0]], bigger]))
    return reduce(lambda x, y: x+y, [lesser, [a_array[0]], bigger])
 
test_array = [6,2,3,5,9,0,1,7,8,10,4]
quick_sort(test_array)

구두로 풀어서 설명드리면,

전체 배열 [6,2,3,5,9,0,1,7,8,10,4] 에서 0번 index 값인 6을 pivot으로 결정하면 pivot을 제외한 배열 a_array[1:]인 [2,3,5,9,0,1,7,8,10,4] 중에서 6보다 작은 값들을 선택해서 sub array를 만듭니다. 그러면 [2, 3, 5, 0, 1, 4] 가 되는데 여기서 quick_sort 함수가 호출이 됩니다. 그러면 [2, 3, 5, 0, 1, 4] 에 대해서 다시 pivot을 계산합니다. 이번에는 2가 pivot이 되고 2를 제외한 나머지 sub array [3, 5, 0, 1, 4] 에서 2보다 작은 값들로 배열을 만들면 [0, 1] 이 되는데 여기서 또 quick_sort 함수가 호출이 됩니다. 그러면 이번에는 pivot이 0이 되고 0보다 작은 값은 없기 때문에 그 배열은 []이 됩니다. 그러면 []를 가지고 다시 quick_sort가 호출이 되는데 이번에는 배열의 length가 2보다 작기 때문에 배열이 if 절에서 바로 리턴되고 더이상 lesser에서 quick_sort가 호출될 수 없으므로 0이 pivot일 때 lesser가 계산이 되어서 lesser는 [] 가 됩니다. 그러고 나서 pivot이 0인 상태에서 이제 bigger가 계산이 되는데 그 값은 [1]로 여기서 다시 quick_sort가 호출되는데 length가 2보다 작기 때문에 배열이 if 절에서 바로 리턴되고 마저 pivot이 0일 때의 bigger가 [1]로 계산됩니다. 그러면 lesser []. pivot 0, bigger [1] 해서 answer가 [0, 1]이 되고 이제 pivot 0일 때 해야하는 것은 다 끝났기 때문에 마저 pivot 2일 때 lesser를 계산하던 로직으로 가서 lesser가 [0, 1]이 되고 pivot 2일 때 bigger를 계산하는 로직으로 넘어갑니다.이번에는 2보다 큰 값들이 [3, 5, 4] 되면서 이제 이 값을 기준으로 다시 quick_sort가 호출됩니다. 그러면서 꼬리에 꼬리를 물고 계속 더 이상 호출될 quick_sort가 없을 때까지 재귀적으로 진행된다고 보시면 됩니다.

크게 로직을 이해해보면 오히려 더 이해가 쉬워지는데요 pivot 하나를 정해서 (코드 상에서는 array의 0번째 값) 이 pivot보다 작은 값들로 이루어진 배열을 lesser, 큰 값들로 이루어진 배열을 bigger라고 하고 그 안에서도 재귀적으로 새로운 pivot을 기준으로 lesser와 bigger을 계산해주는 것입니다. 이렇게 재귀적으로 반복하다보면 최종적으로 한 pivot을 기준으로 lesser와 bigger가 나눠지는데 lesser 안에서도 순서대로 되어 있고 bigger 안에서도 순서대로 되어있어서 최종적으로 lesser, pivot, bigger 를 보면 전체 배열이 sorting이 되어있습니다.