1. 곱셈, 거듭제곱

Pass

2. 리스트 확장

list_1 = [0]*5 # [0, 0, 0, 0, 0]
tuple_1 = (0,)*5 # (0, 0, 0, 0, 0)

3. 가변인자

가변인자 : 길이가 변할 수 있는 인자(argument), 함수에 입력이 얼마나 들어오게 될지 모르는 경우에 사용 *args : args라는 tuple로 저장됨 **kwargs : kwargs라는 dict에 저장됨

def args_func(*args):
    print(args)

def kwargs_func(**kwargs):
    print(kwargs)

args_func(1, 2) # (1, 2)
kwargs_func(a = 1, b = 2) # {'a':100, 'b':200}

4. 언패킹(Unpacking)

container 타입의 데이터를 unpacking하는 경우에 사용됨. (**로 딕셔너리형태에서도 활용가능함.)

from functools import reduce

primes = [2, 3, 5, 7, 11, 13]

def product(*numbers):
    p = reduce(lambda x, y: x * y, numbers)
    return p

product(*primes)
# 30030

product(primes)
# [2, 3, 5, 7, 11, 13]

• clear

• ls : 디렉토리 안에 있는 파일 list

  • ls -l(우분투 : l) : 좀 더 자세하게(권한, 수정 일자, 용량 등)
  • ls -al(우분투 : ll) : 모든 파일 list(.으로 시작하는 파일까지 포함)
    • a는 보통 전체를 의미
  • ls -alt : 시간순으로 정렬

• alias : 단축키(직접 만들 수도 있음)

• touch : 파일 만들기

• mv 파일 경로 : move(파일을 옮기고 싶다, 이름 바꾸기도 가능)

  • . : 현재 경로를 의미
  • .. : 이전 경로를 의미

• mkdir : 폴더 만들기(make directory)

• cd 경로 : 폴더 위치 바꾸기(change directory)

  • cd : Home 폴더
  • cd - : 이전 폴더로 이동
  • 상대경로 / 절대경로

• cp 파일1 파일2 : 파일1을 파일2의 이름으로 복사(copy), 경로를 바꿀수도 있다.

• rm 파일 : 파일 삭제(remove), 휴지통 이런거 없음!, 폴더는 지울 수 없음!

  • rm -i 파일 : 지워도 되는지 한번 더 물어봄
  • rm -f 파일 : 강제로(force)로 지운다.
  • rm -rf 파일/폴더 : 폴더도 지울수 있다.

• top : 내 컴퓨터의 상태를 보여줌(CPU 등), q로 끌 수 있음

• htop : 좀 더 예쁘게 보여줌

• ps : 프로세스, 현재 실행하고 있는 프로그램을 볼 수 있다는 것이 의미 있음

• df : 디스크 정보를 보여줌(램 등)

• du : 용량을 얼마나 가지고 있는지 보여줌

• find : 현재 폴더에 들어있는 모든 파일을 검색

  • find | grep 파일/폴더 : 파일/폴더의 위치를 찾음

• man : 명령어의 기능을 알려줌(manual), 거의 급할때..?

• which : 명령어의 위치(환경?)를 보여줌

  which python3

• tail : 파일의 변화를 실시간 트래킹, 파일의 끝부분 몇개를 보여줌

• echo : 입력한거 그대로 출력

• echo > 파일 : 출력에 대한것을 파일에 덮어씀

• echo >> 파일 : 출력에 대한것을 파일에 추가

• cat 파일 : 파일에 입력된 것 출력

• tail -f 파일 : 다른 서비스에서 파일이 변형되는 것을 모니터링할 수 있다!

  • 빠져나오려면 Ctrl + z

• 다중 명령어 세미콜론(;) : 명령어;명령어;명령어 + Enter

  • 중간에 잘못된 명령어가 있어도 끝까지 실행함(주의!!!)

• 다중 명령어 &&, ||

  • 명령어1 && 명령어2 : 명령어 1을 실행하고 문제가 없다면 명령어 2도 실행, 문제있으면 명령어 2 실행 안함
  • 명령어1 || 명령어2 : 명령어 1을 실행하고 문제가 있다면 명령어 2를 실행, 문제가 없으면 명령어 1만 실행

• 다중 명령어 파이프(|) : 명령어의 결과에 대해 2차적으로 처리하고 싶음.

  • grep, awk등과 많이 사용됨.
  • cat 파일 | grep "text" -n : -n은 넘버링, 파일 속에 "text"가 포함된 줄을 출력
  • 로그에서 필요한 것만 정규표현식등으로 가져올 수 있다!!

• vi 파일 : 터미널 환경에서 쓸 수 있는 텍스트 편집기, 정규표현식도 가능,

  • Command Mode, Editor Mode, Last Line Mode

• Redirection(> : 덮어쓰기, >> : 추가) : 표준 출력으로 발생한 결과를 파일로 저장

  • ps -ef > ./process list.txt
  • echo abc >> 파일
  • 어떤 프로그램의 output을 로그 파일로 저장
  • ps -ef | awk ' { print $2 }

• File Descriptor : 표준 입출력, 에러를 숫자로 나타낼수 있음

  • 0 : stdin : 명령어의 표준 입력
    • fjgfgkd 1> err_test
  • 1 : stdout : 명령어의 표준 출력
    • dfajfkf 2> err_test
  • 2 : stderr : 명령어의 표준 오류

Tool

• apt-get : 필요한 패키지, 프로그램을 설치 할 수 있는 패키지 관리 도구
• htop : top을 좀 더 예쁘게 꾸며서 보여줌ㅎ
• nohup : 내 스크립트가 터미널을 끄더라도 계속 실행시키고 싶을 때 &와 함께 백그라운드로 실행
• screen(tmux) : nohup을 백그라운드로 가버린 프로세스는 다시 볼 수 없지만 screen을 띄워서 실행하면, 해당 세션을 다시 복원할 수 있음

계정과 권한

• drwx 소유자의 권한, 그룹의 권한, 소유자가 아닌 사람의 권한을 구분 root 계정 : 모든 권한을 가진 계정

• chmod 777 : 권한을 각각 다르게 줄 수 있음!

• sudo : 시스템의 중요한 부분을 변경하거나 업데이트해야 할 때, Root 계정 접속을 남발하면 귀찮기도 하고, 보안상 좋지 않으니 일시적으로 Root의 권한을 위임 받을 수 있는 방법

  • sudo가 가능한 계정이 있음
  • sudo apt-get install ~~

• 환경변수 $PATH : 프로그램을 실행할 때 자동으로 참조하는 절대경로의 모음, 왼쪽으로 갈수록 우선 순위가 높으며, 발견 즉시 바로 실행 됨

  • /bin : 일반사용자, 기본적인 명령어
  • /sbin : 슈퍼유저(root), 시스템 관리를 위한 명령어
  • /usr/bin : 일반사용자, /bin에 있는 명령을 제외한 기본적인 명령어
  • /usr/sbin : 슈퍼유저(root), sbin에 있는 명령을 제외한 시스템 관리를 위한 명령어
  • export 명령어로 환경변수를 추가(일시적)

쉘 스크립트

• 쉘 위에서 실행 가능한 명령어를 조합해서 작업을 자동화 하기 위해 사용
• 똑같은 작업을 자동으로 해버리자!
• 셔뱅 : `#! 인터프리터 위치, 쉘 스크립트를 시작할 때 맨 처음에 기입, 스크립트를 해석하는 인터프리터를 지정하는 것
  • ex) : #!/usr/bin/python3
  • 인터프리터 : 쉘 명령어를 해석하는 것

변수

• 선언 : var = ?
• 사용 : $var
• 특수한 경우 : ${var}
• 매개변수 : $0, $1.., $*, $@, 스크립트를 제어
• 산술 덧셈은 추가 처리 필요 : $((1+2)), 입력 매개변수는 기본적으로 스트링

조건문, 비교 연산자

• if then ~ eilf then ~ fi
• 정수 -eq, -ne, -gt, -lt, -ge, -le
• 문자열 ==, !=, -z, -n
• 정수와 문자열의 비교방식이 다름, 괄호를 두개 넣는다거나 문자열로 인식되도록 변환하는 방법이 있음.

반복문

• while 조건
• for 지정된 범위
• break, continue, exit으로 제어

유의사항

1. space가 필요한 곳은 확실히 넣어줘야 함
2. 중간에 에러가 나더라도 계속 진행
3. 엔터 잘못 쳤다가 전부 날려먹을 수도...ㄷㄷ

이점

1. 민첩성과 즉각적인 탄력성(On-Demand)
2. 비용 절감 효과
3. 개방성 및 유연성(API)
4. 보안
5. 높은 기술 노하우

대표 솔루션

1. 어플리케이션 호스팅 : 서버 자원 제공
2. 웹 사이트 : 서버 자원 제공(CPU, Memory, Storage 등)
3. 백업 및 스토리지(S3 등)
4. 데이터베이스
5. 엔터프라이즈 IT

2. AWS 서비스 레이어

1. AWS Global Physical Infrastructure
2. Compute(EC2) / Storange(S3) / Network(RDS) / Database(VPC) : Low-Level Building Blocks

3. Paralled Processing(Elastic MapReduce) / Transfer / Content Delivery / App Services / Search : High-Level Building Blocks
4. Auth, Authorization, Federation/ Monitoring / Deployment and Automation : Cross Service Features
5. Libraries and SDKs / Web Interface / Tools / Command Line : Tools to access services
6. Application

3. AWS 책임 분담 모델

Infrastructure 서비스 모델

• Managed By AWS(EC2, S3, RDS, VPC 등)
• Managed By Customers, Apache같은것 설치 가능

Abstracted 서비스 모델

• 해당 플랫폼을 빌려쓰는 느낌

4. EC2(Elastic Compute Cloud)

• EC2는 AWS에서 가장 기본이 되는 low-level 빌딩 블럭에 속하는 컴퓨팅 서비스이며, 원하는 만큼 가상 서버를 구축하고 보안 및 네트워크 구성과 스토리지 관리가 가능.
• OS를 EC2에 연결되어 있는 AMI(Amazon Machine Image)에 올릴 수 있음
• InfraStructure 책임 모델

구성요소

1. 인스턴스 : 가상 컴퓨팅 환경
2. AMI(아마존 머신이미지), 인스턴스에 필요한 OS와 소프트웨어가 구성된 템플릿(골드 이미지)
3. 인스턴스 타입 : 가상 서버의 CPU, 메모리 사이즈 용량
4. EIP(Elastic IP) : 가상의 컴퓨팅 서버에 할당되는 고정 공인 IP
5. VPC : 가상의 컴퓨팅 서버가 속하는 독립된 네트워크 블럭

5. Lambda

• 이벤트에 응답하여 코드를 실행하고 자동으로 기본 컴퓨팅 리소스를 관리하는 서버리스 컴퓨팅 서비스
• 백엔드 서버와 운영 체제 유지 관리, 용량 프로비저닝 및 자동 조정, 코드 및 보안 패치 배포, 코드 모니터링, 로깅 등 모든 컴퓨팅 리소스 관리를 수행한ㄷ.
• Abstracted 책임 모델

New Data -> Batch Layer / Serving Layer / Speed Layer -> 'Merge' -> Query

6. 컴퓨트 서비스 장애에 대한 디자인

1. 확장성 : AZ(가용영역) 단위로 확장 가능하며, Autoscailing을 통해 요구되는 트래픽들을 수용한다.
2. 모니터링 및 운영 관리 : API와 대시보드를 통해 손쉽게 관리
3. 이중화 : 여러 AZ에 DB를 구성하여 단일요소의 장애 제거, 하나의 AZ에 장애가 났을 때 서비스를 지속할 수 있도록
4. Failover : EIP와 Disk를 별도로 관리 가능하여 정상적인 상태의 서버로 대체

7. AWS 데이터베이스 서비스

• 데이터베이스의 용량과 성능에 맞게 조정 가능 -> 시간 소모적인 관리 작업들(패치, 백업, 확장)등으로부터 자유롭게 해줌
• 관계형 데이터베이스 : RDS : Mysql, MsSQL, Oracle, PostgreSql 등 사용 가능
• 비관계형 데이터베이스 : DynamoDB : key-value 형식

관계형 데이터베이스

• 키 값에 의해 서로 관련되는 테이블로 구성하는 가장 일반적인 데이터베이스
• 각 테이블/관계는 하나의 엔티티 타입(고객이나 제품)을 대표
• 효율적이고 정확하게 운용되기 위해서 ACID 트랜잭션 특징을 가짐 ACID 트랜잭션 : 데이터는 학상 원자성, 일관성, 지속성, 고립성을 가져야 함

NoSQL

• 스키마가 없으며 저장하고 싶은 값을 무제한으로 저장하는 DB
• 각 데이터 항목으로 고유하게 식별하는 기본 키는 있어야 하지만 다른 속성값에 대해서는 제한이 없음
• DynamoDB는 JSON 문서를 비롯한 정형 또는 반정형 데이터를 관리할 수 있으며 BASE의 특징을 가짐 BASE : Basically Available, Soft-State, Eventually Consistency(ACID에 비해서는 조금 느슨함)

데이터베이스 장애에 대한 디자인

1. 확장성 : AZ 단위로 확장 가능, 다른 AZ로의 두번째 구성 가능
2. 백업 및 운영 관리 : API와 대시보드를 통해 손쉽게 관리
3. 이중화 : 여러 AZ에 DB를 구성하여 단일요소의 장애 제거
4. Failover : 데이터가 소결합으로 저장되어 있어 대체작동 가능

확장성 있는 어플리케이션

1. 리소스 증가에 비례한 성능의 증가
2. 회복력(확장성과 일맥상통)
   • 얼마나 탄력적으로 서비스 트래픽에 따라 자원을 줄이고 늘일 수 있는지
3. 분산된 시스템의 관리 능력
4. 효율적인 운영 방법
5. 비용의 효율적인 관리

Scale Up/ Scale Down(수직적인 확장)

2 X 4 <> 4 X 8

Scale Out/ Scale in(수평적인 확장)

병렬적으로 확장(1개의 서버 <> 3개의 서버)

Scale Up/Down을 하게 되면 down time이 생길수 밖에 없으므로 scale out이 권장됨.

2.탄력성에 대한 이해

• 탄력성 : 최소한의 마찰로 리소스를 스케일링 가능하게 하는 특징.
• 어플리케이션 구조에 클라우드 이점을 충분히 적용할 수 있도록 탄력성의 개념을 가지고 설계한다.
• 클라우드 환경에서 전통적인 방식(품질 저하 & 용량 낭비)과 다르게 필요한 자원들만 활용하도록 간소화한 시스템 설계 및 프로세스의 관점의 변화가 필요
• on-demand한 특성(리소스를 서비스 양에 맞게 즉각적으로 변화)

3. 제약에 대한 극복

• 시스템의 요구사항들이 클라우드에서 충분히 제공되는지 고민해야함.
• On-Premise 환경과 동일한 하드웨어 혹흔 솔루션을 활용하기 어렵다. 클라우드 환경에서 제공하는 추상화된 자원들을 활용하여 서비스를 딜리버리할 수 있도록 관점의 변화가 필요함.
• Redis : 인메모리 데이터베이스, key-value 데이터 저장소

4. 가상화 시스템 관리자

• 시스템 관리자는 가상화 시스템 관리자의 역할을 수행해야 한다.
• 데이터베이스 관리자
  1. DB 설치 및 운영
  2. 규칙적인 DB 관리 작업(백업, 패치, 이중화 구성 등)
  3. DB 인스턴스(가상화 인스턴스) 이미지(MySQL, Postgresql 등) 관리 4. 분산 DB 환경의 관리

트리 기반 Gradient Boosting 방식 알고리즘이 모델 성능의 우수성은 인정되지만 학습 시간이 너무 오래 걸림

• XGBoost : 모델 성능도 좋고 병렬 학습이 가능, 하지만 대용량 데이터에 대해서 학습 시간이 오래걸림
• LightGBM : 모델 학습 시간을 대폭 향상 시키기 위해 개발된 방식(마이크로소프트에서 개발!), 랜덤 포레스트보다는 느림ㅎ

학습 시간이 오래걸리면 여러가지 방법을 쓰는 것에 제한이 있음, 캐글같은 데이터경진대회에서 베이스라인으로 많이 쓰임.

LightGBM

• level-wise 방식은 균형을 맞추며 트리를 생성해나감
• Leaf-wise 방식(균형을 맞추지 않으며 Tree를 생성해나가는 방식)으로 Tree를 생성하면 빠르게 트리를 생성해갈 수 있음
• 이러한 방식은 Overfitting되기 쉬움. 하지만 LightGBM은 내부 하이퍼 파라미터 등으로 그 문제를 잘 해결해냄

주요 특징

1. 히스토그램 기반으로 Feature Binning
2. GBDT 외에 GOSS, DART 방식 제공
3. 오버피팅을 극복하기 위한 다양한 하이퍼 파라미터

1. 히스토그램 기반 Feature Binning

Best split gain을 찾기 위해 모든 leaf node의 데이터들을 대상으로 해야함. 오랜 수행 시간 필요 -> lightGBM : 연속형 feature들을 특정한 개수의 bin으로 할당하여 개별 피처들의 범위를 급격히 줄임!

2. Boosting Type

• default : gbdt(gradient boosting descision tree)
• goss, dart, rf(랜덤포레스트, 배깅(부스팅X))

2.1 Goss(Gradient Based One-side Sampling)

• Gradient 값이 상대적으로 큰 값에 대해서만 선택적으로 필터링하여 반복적으로 재 학습
• Gradient 값이 작을 경우 이미 상당한 수준으로 학습이 진행되었다고 가정함.

  2.2 Dart(Dropout meet Multiple Additive Regressing Trees)

• Iteration을 지속적으로 수행하면서 추가적인 트리가 만들어 질 때 마지막에 만들어 지는 트리들이 일부 데이터 세트 조건만을 만족시키기 위해 만들어지는 경우가 발생. 이런 Tree들에 Drop out 적용

3. 하이퍼 파라미터

LightGBM : leaf-wise 방식이므로 조절해주지 않으면 depth가 끝없이 깊어져서 오버피팅에 취약해짐.

• 가장 중요한 파라미터 max_depth : 최대 depth num_leaves : leaf node의 개수 num_iterations(n_estimators) : 약한 학습기의 개수 learning_rate : 학습률

• 과적합 제어 bagging_fraction(subsample) : 데이터를 샘플링하는 비율(행) feature_fraction(colsample_bytree) : 트리 생성에 사용하는 피처(열) lambda_l2 : L2 Regularization lambda_l1 : L1 Regularization max_bin : 연속형 변수들 binning할 때 최대 bin의 개수

하이퍼 파라미터 튜닝

1. Grid Search
2. Random Search
3. Bayesian Optimization
4. 수동 튜닝

Issue

너무 많은 하이퍼 파라미터 gridsearch : 개별 하이퍼 파라미터들을 grid 형태로 지정하는 것은 한계가 존재(데이터가 크면 답이 없다).

Bayesian Opt.

미지의 함수가 반환하는 값의 최대값을 매우 짧은 반복을 통해 찾아내는 최적화 방식!

• Gaussian Process를 통해 함수의 사후 분포를 생성하고, 이를 기반으로 최적화하려는 함수를 재구성

• 점차 많은 입력 값을 받아서 수행하면서 사후 분포가 점점 개선되고, 함수 반환 값을 최대되는 입력 파라미터 영역을 보다 확실하게 찾게 됨.

  함수 입력 인자의 범위를 설정 & 함수 선언 함수를 잘 선언하는 것이 중요(loss function이 return 값)

• AutoML !

추천 시스템 방식

1. Contents Based Filtering
   • 컨텐츠의 요소들을 기반으로 개인의 취향을 매칭
2. Collaborative Filtering
   • 성향이 비슷한 다른 사람들의 선택을 기반으로 매칭
3. Hybrid(Contents Based + Collaborative Filtering)

컨텐츠 기반 필터링

(Contents Based Filtering)

감독, 배우, 영화 설명, 장르 등 영화를 구성하는 다양한 컨텐츠들을 텍스트 기반 문서 유사도로 비교하여 추진함

1. 컨텐츠에 대한 텍스트 정보들을 피처 벡터화
2. 코사인 유사도로 컨텐츠별 유사도 계산
3. 컨텐츠 별로 가중 평점을 계산
4. 유사도가 높은 컨텐츠 중에 평점이 좋은 컨텐츠 순으로 추천

TMDB 5000 Movie Dataset

1. 컨텐츠에 대한 텍스트 정보들을 피처 벡터화

🔔ast Abstract Syntax Trees의 약자인데 말 그대로 문자를 자동으로 parsing해서 파이썬 문법에 맞는 구조로 구조화(객체화)해줍니다. Tree형의 자료구조이며, 각각의 노드를 갖게 됩니다. 실제로 1.2 + 3.4의 AST를 뜯어보면 다음과 같습니다.

>> import python
>> ast.dump(ast.parse('1.2 + 3.4'))
Module(body=[Expr(value=BinOp(left=Num(n=1.2), op=Add(), right=Num(n=3.4)))])

🔔ast.literal_eval eval함수와 비슷하게 문자그대로(literal) 계산을 실행해주는 함수입니다. eval함수와 다른 점은 파이썬 문법에 맞지 않으면 함수를 실행하지 않는 다는 것입니다. 따라서, 둘 중에 사용을 고민한다면 literal_eval을 사용한 것이 더 안전합니다. 그 이유는, eval 함수를 사용한 프로그램을 배포하면 사용자가 의도적으로 틀린 파이썬 문법을 사용하여 공격할 수 있기 때문입니다.

import pandas as pd
import numpy as np
import warnings; warnings.filterwarnings('ignore')

movies =pd.read_csv('./tmdb_5000_movies.csv')
movies_df = movies[['id','title', 'genres', 'vote_average', 'vote_count',
                 'popularity', 'keywords', 'overview']]

pd.set_option('max_colwidth', 100)
movies_df[['genres']][:1]

genres
[{"id": 28, "name": "Action"}, {"id": 12, "name": "Adventure"}, {"id": 14, "name": "Fantasy"}, {...    

텍스트 문서 1차 가공, 파이썬 딕셔너리 변환 후 리스트 형태로 변환

from ast import literal_eval

movies_df['genres'] = movies_df['genres'].apply(literal_eval)
print(movies_df['genres'].head(1))

movies_df['genres'] = movies_df['genres'].apply(lambda x : [ y['name'] for y in x])
print(movies_df[['genres']][:1])

0    [{'id': 28, 'name': 'Action'}, {'id': 12, 'name': 'Adventure'}, {'id': 14, 'name': 'Fantasy'}, {...
Name: genres, dtype: object

genres
[Action, Adventure, Fantasy, Science Fiction]

2. 코사인 유사도로 컨텐츠별 유사도 계산

from sklearn.feature_extraction.text import CountVectorizer

# CountVectorizer를 적용하기 위해 공백문자로 word 단위가 구분되는 문자열로 변환. 
movies_df['genres_literal'] = movies_df['genres'].apply(lambda x : (' ').join(x))
count_vect = CountVectorizer(min_df=0, ngram_range=(1,2))
genre_mat = count_vect.fit_transform(movies_df['genres_literal'])

from sklearn.metrics.pairwise import cosine_similarity

genre_sim = cosine_similarity(genre_mat, genre_mat)
# 유사도가 높은 영화의 index를 얻음
genre_sim_sorted_ind = genre_sim.argsort()[:, ::-1]
print(genre_sim_sorted_ind[:1])

유사도가 높은 순으로 영화의 index를 추출

[[   0 3494  813 ... 3038 3037 2401]]

특정 영화와 장르별 유사도가 높은 영화를 반환하는 함수 생성

def find_sim_movie(df, sorted_ind, title_name, top_n=10):

    # 인자로 입력된 movies_df DataFrame에서 'title' 컬럼이 입력된 title_name 값인 DataFrame추출
    title_movie = df[df['title'] == title_name]

    # title_named을 가진 DataFrame의 index 객체를 ndarray로 반환하고 
    # sorted_ind 인자로 입력된 genre_sim_sorted_ind 객체에서 유사도 순으로 top_n 개의 index 추출
    title_index = title_movie.index.values
    similar_indexes = sorted_ind[title_index, :(top_n)]

    # 추출된 top_n index들 출력. top_n index는 2차원 데이터 임. 
    #dataframe에서 index로 사용하기 위해서 1차원 array로 변경
    print(similar_indexes)
    similar_indexes = similar_indexes.reshape(-1)

    return df.iloc[similar_indexes]

similar_movies = find_sim_movie(movies_df, genre_sim_sorted_ind, 'The Godfather',10)
similar_movies[['title', 'vote_average']]

    title    vote_average
2731    The Godfather: Part II    8.3
1243    Mean Streets    7.2
3636    Light Sleeper    5.7
1946    The Bad Lieutenant: Port of Call - New Orleans    6.0
2640    Things to Do in Denver When You're Dead    6.7
4065    Mi America    0.0
1847    GoodFellas    8.2
4217    Kids    6.8
883    Catch Me If You Can    7.7
3866    City of God    8.1

3. 가중 평점(Weighted Rating) 계산

$가중 평점(Weighted Rating) = \frac{v}{v+m}R + \frac{m}{v+m}C$

• v: 개별 영화에 평점을 투표한 횟수
• m: 평점을 부여하기 위한 최소 투표 횟수
• R: 개별 영화에 대한 평균 평점.
• C: 전체 영화에 대한 평균 평점

C = movies_df['vote_average'].mean()
m = movies_df['vote_count'].quantile(0.6)

def weighted_vote_average(record):
    v = record['vote_count']
    R = record['vote_average']

    return ( (v/(v+m)) * R ) + ( (m/(m+v)) * C )   

movies_df['weighted_vote'] = movies_df.apply(weighted_vote_average, axis=1) 

4. 유사도가 높은 컨텐츠 중, 평점이 좋은 컨텐츠 순으로 추천

앞의 find_sim_movie함수를 수정 후보군을 더 많이(2배) 뽑고 (가중)평점 순으로 top_n만큼 선택

def find_sim_movie(df, sorted_ind, title_name, top_n=10):
    title_movie = df[df['title'] == title_name]
    title_index = title_movie.index.values

    # top_n의 2배에 해당하는 쟝르 유사성이 높은 index 추출 
    similar_indexes = sorted_ind[title_index, :(top_n*2)]
    similar_indexes = similar_indexes.reshape(-1)
# 기준 영화 index는 제외
    similar_indexes = similar_indexes[similar_indexes != title_index]

    # top_n의 2배에 해당하는 후보군에서 weighted_vote 높은 순으로 top_n 만큼 추출 
    return df.iloc[similar_indexes].sort_values('weighted_vote', ascending=False)[:top_n]

similar_movies = find_sim_movie(movies_df, genre_sim_sorted_ind, 'The Godfather',10)
similar_movies[['title', 'vote_average', 'weighted_vote']]

    title    vote_average    weighted_vote
2731    The Godfather: Part II    8.3    8.079586
1847    GoodFellas    8.2    7.976937
3866    City of God    8.1    7.759693
1663    Once Upon a Time in America    8.2    7.657811
883    Catch Me If You Can    7.7    7.557097
281    American Gangster    7.4    7.141396
4041    This Is England    7.4    6.739664
1149    American Hustle    6.8    6.717525
1243    Mean Streets    7.2    6.626569
2839    Rounders    6.9    6.530427

협업 필터링(Collaborative Filtering)

취향이 비슷한 친구에게 물어보자!

1. 최근접 이웃 기반(Nearst Neighbor), 일반적으로 아이템 기반이 선호됨

   • 사용자 기반
     • 특정 사용자와 비슷한 고객들을 기반으로 비슷한 고객들이 선호하는 다른 상품을 추천
     • 비슷한 상품을 구매해온 고객들은 비슷한 고객으로 간주

       당신과 비슷한 고객들이 이 상품도 구매했습니다!

   • 아이템 기반
     • 특정 상품과 유사한 좋은 평가를 받은 다른 비슷한 상품을 추천
     • 사용자들로부터 특정 상품과 비슷한 평가를 받은 상품들은 비슷한 상품으로 간주

       이 상품을 선택한 다른 고객들은 다음 상품도 구매했습니다!

2. 잠재 요인 기반(Latent Factor)

   • 행렬 분해 기반 (ex. SVD)

• User Behavior에만 기반하여 추천
• 상품, 영화 등 사용자가 아직 평가하지 않은 item에 대한 평가를 예측하는 것이 중요한 문제
• 사용자 - 아이템 평점 데이터 행렬 형태가 필요(희소 행렬)
  • 사용자 기반 : 사용자(행) X 아이템(열)
  • 아이템 기반 : 아이템(행) X 사용자(열)

아이템 기반 협업 필터링

1. 사용자-아이템 행렬 데이터를 아이템-사용자 행렬 데이터로 변환
2. 아이템간의 코사인 유사도로 아이템 유사도 산출
3. 사용자가 관람하지 않은 아이템들 중에서 아이템간 유사도를 반영한 예측 점수 계산
4. 예측 점수가 가장 높은 순으로 아이템 추천

Weighted Rating Sum $$\hat{R}{u,i} = \frac{\sum\limits^{N}{S{i,N}}R_{u,N}}{\sum\limits^{N}{|S_{i,N}|}}$$

• $\hat{R}_{u,i}$ : 사용자 u, 아이템 i의 개인화된 예측 평점 값
• $S_{i,N}$ : 아이템 i와 가장 유사도가 높은 Top-N개 아이템의 유사도 벡터
• $R_{u,N}$ : 사용자 u의 아이템 i와 가장 유사도가 높은 TOP-N개 아이템에 대한 실제 평점 벡터

MovieLens Latest Dataset

1. 아이템-사용자 행렬 데이터

import pandas as pd
import numpy as np

movies = pd.read_csv('./ml-latest-small/movies.csv')
ratings = pd.read_csv('./ml-latest-small/ratings.csv')

#로우레벨 사용자 평점 데이터를 사용자-아이템 평점 행렬로 변환
ratings = ratings[['userId', 'movieId', 'rating']]
ratings_matrix = ratings.pivot_table('rating', index='userId', columns='movieId')

# title 컬럼을 얻기 이해 movies 와 조인 수행
rating_movies = pd.merge(ratings, movies, on='movieId')

# columns='title' 로 title 컬럼으로 pivot 수행. 
ratings_matrix = rating_movies.pivot_table('rating', index='userId', columns='title')

# NaN 값을 모두 0 으로 변환
ratings_matrix = ratings_matrix.fillna(0)

ratings_matrix_T = ratings_matrix.transpose()
print(ratings_matrix_T.shape)

(9719, 610)

2. 영화들 간 유사도 산출

from sklearn.metrics.pairwise import cosine_similarity

item_sim = cosine_similarity(ratings_matrix_T, ratings_matrix_T)

# cosine_similarity() 로 반환된 넘파이 행렬을 영화명을 매핑하여 DataFrame으로 변환
item_sim_df = pd.DataFrame(data=item_sim, index=ratings_matrix.columns,
                          columns=ratings_matrix.columns)

print(item_sim_df.shape)
item_sim_df["Inception (2010)"].sort_values(ascending=False)[1:6]

(9719, 9719)

title
Dark Knight, The (2008)          0.727263
Inglourious Basterds (2009)      0.646103
Shutter Island (2010)            0.617736
Dark Knight Rises, The (2012)    0.617504
Fight Club (1999)                0.615417
Name: Inception (2010), dtype: float64

3. 아이템 기반 인접 이웃 협업 필터링으로 개인화된 영화 추천(가중 평점합 기반)

# Weighted Rating Sum(행렬 연산, 내적)
def predict_rating(ratings_arr, item_sim_arr ):
    ratings_pred = ratings_arr.dot(item_sim_arr)/ np.array([np.abs(item_sim_arr).sum(axis=1)])
    return ratings_pred

ratings_pred = predict_rating(ratings_matrix.values , item_sim_df.values)
ratings_pred_matrix = pd.DataFrame(data=ratings_pred, index= ratings_matrix.index,
                                   columns = ratings_matrix.columns)
print(ratings_pred_matrix.shape)

(610, 9719)

top-n 유사도를 가진 데이터들에 대해서 예측 평점 계산

def predict_rating_topsim(ratings_arr, item_sim_arr, n=20):
    # 사용자-아이템 평점 행렬 크기만큼 0으로 채운 예측 행렬 초기화
    pred = np.zeros(ratings_arr.shape)

    # 사용자-아이템 평점 행렬의 열 크기만큼 Loop 수행. 
    for col in range(ratings_arr.shape[1]):
        # 유사도 행렬에서 유사도가 큰 순으로 n개 데이터 행렬의 index 반환
        top_n_items = [np.argsort(item_sim_arr[:, col])[:-n-1:-1]]
        # 개인화된 예측 평점을 계산
        for row in range(ratings_arr.shape[0]):
            pred[row, col] = item_sim_arr[col, :][top_n_items].dot(ratings_arr[row, :][top_n_items].T) 
            pred[row, col] /= np.sum(np.abs(item_sim_arr[col, :][top_n_items]))        
    return pred
ratings_pred = predict_rating_topsim(ratings_matrix.values , item_sim_df.values, n=20)
user_rating_id = ratings_matrix.loc[9, :]
user_rating_id[ user_rating_id > 0].sort_values(ascending=False)[:10]

title
Adaptation (2002)                                                                 5.0
Austin Powers in Goldmember (2002)                                                5.0
Lord of the Rings: The Fellowship of the Ring, The (2001)                         5.0
Lord of the Rings: The Two Towers, The (2002)                                     5.0
Producers, The (1968)                                                             5.0
Citizen Kane (1941)                                                               5.0
Raiders of the Lost Ark (Indiana Jones and the Raiders of the Lost Ark) (1981)    5.0
Back to the Future (1985)                                                         5.0
Glengarry Glen Ross (1992)                                                        4.0
Sunset Blvd. (a.k.a. Sunset Boulevard) (1950)                                     4.0
Name: 9, dtype: float64

사용자가 관람하지 않은 영화 중에서 아이템 기반의 인접 이웃 협업 필터링으로 영화 추천

def get_unseen_movies(ratings_matrix, userId):
    # userId로 입력받은 사용자의 모든 영화정보 추출하여 Series로 반환함. 
    # 반환된 user_rating 은 영화명(title)을 index로 가지는 Series 객체임. 
    user_rating = ratings_matrix.loc[userId,:]

    # user_rating이 0보다 크면 기존에 관람한 영화임. 대상 index를 추출하여 list 객체로 만듬
    already_seen = user_rating[ user_rating > 0].index.tolist()

    # 모든 영화명을 list 객체로 만듬. 
    movies_list = ratings_matrix.columns.tolist()

    # list comprehension으로 already_seen에 해당하는 movie는 movies_list에서 제외함. 
    unseen_list = [ movie for movie in movies_list if movie not in already_seen]

    return unseen_list

4. 사용자가 관람하지 않은 영화들 중 예측 평점이 가장 높은 영화를 추천

def recomm_movie_by_userid(pred_df, userId, unseen_list, top_n=10):
    # 예측 평점 DataFrame에서 사용자id index와 unseen_list로 들어온 영화명 컬럼을 추출하여
    # 가장 예측 평점이 높은 순으로 정렬함. 
    recomm_movies = pred_df.loc[userId, unseen_list].sort_values(ascending=False)[:top_n]
    return recomm_movies

# 사용자가 관람하지 않는 영화명 추출   
unseen_list = get_unseen_movies(ratings_matrix, 9)

# 아이템 기반의 인접 이웃 협업 필터링으로 영화 추천 
recomm_movies = recomm_movie_by_userid(ratings_pred_matrix, 9, unseen_list, top_n=10)

# 평점 데이타를 DataFrame으로 생성. 
recomm_movies = pd.DataFrame(data=recomm_movies.values,index=recomm_movies.index,columns=['pred_score'])
recomm_movies

    pred_score
title    
Shrek (2001)    0.866202
Spider-Man (2002)    0.857854
Last Samurai, The (2003)    0.817473
Indiana Jones and the Temple of Doom (1984)    0.816626
Matrix Reloaded, The (2003)    0.800990
Harry Potter and the Sorcerer's Stone (a.k.a. Harry Potter and the Philosopher's Stone) (2001)    0.765159
Gladiator (2000)    0.740956
Matrix, The (1999)    0.732693
Pirates of the Caribbean: The Curse of the Black Pearl (2003)    0.689591
Lord of the Rings: The Return of the King, The (2003)    0.676711

잠재 요인 협업 필터링

• 사용자-아이템 평점 행렬 속에 숨어 있는 잠재 요인을 추출해 추천
• 대규모 다차원 (희소) 행렬을 SVD 같은 행렬 분해를 통해 잠재 요인을 추출하는데, 이 잠재 요인을 기반으로 평점 행렬을 재구성하면서 추천을 구현합니다.
• 잠재 요인이 무엇이라고 정확히 특정짓기는 매우 어렵다.
• 사용자 레벨의 잠재요인 ~ 아이템 레벨의 잠재요인
• 목표는 희소 행렬 형태의 사용자-아이템 평점 행렬을 밀집 행렬 형태의 _사용자-잠재요인 행렬과 잠재 요인-아이템 행렬로 분해해서 이를 밀집 형태의 사용자-아이템 평점 행렬을 생성해 추천에 사용하는 것

  $$R \cong PQ^T$$ = (사용자-잠재요인 행렬)*(잠재요인 - 아이템 행렬)'

Singular Value Decomposition(SVD)

• Factor의 개수 K는 분석가가 정해주어야함
• P의 개별 행은 개별 사용자에 대한 잠재요인을 반영
• Q의 개별 열은 개별 아이템에 대한 잠재요인을 반영

  아직 사용자가 평점을 매개지 않은 아이템 [i, j]에 대한 예측평점 = (P의 i 행 벡터)*(Q의 j열 벡터)'

행렬 분해 이슈

• SVD는 결측값이 없는 행렬에 적용 가능함, 일반적인 SVD방식으로 분해 불가
• 경사하강법을 이용해 P와 Q에 기반한 예측 R값이 실제 R값과 가장 최소의 오차를 가질 수 있도록 비용함수 최적화를 통해 P와 Q 최적화

1. P와 Q를 임의의 값을 가진 행렬로 설정
2. P와 Q를 곱해 예측 R 행렬을 계산하고 실제 R 행렬에 해당하는 오류값 계산
3. 이 오류값이 적절히 최소화할 수 있도록 업데이트

   $$Cost = min\sum{(r_{u,i}-p_uq_i^t)^2}+\lambda(\lvert q_i^2\rvert+\lvert p_u^2\rvert)$$ (실제값과 예측값의 오류 최소화) + (과적합 개선을 위한 L2 규제)

경사하강을 이용한 행렬 분해 예제

원본 행렬 R 및 R을 분해할 P와 Q를 임의의 정규분포를 가진 랜덤값으로 초기화

import numpy as np

# 원본 행렬 R 생성, 분해 행렬 P와 Q 초기화, 잠재요인 차원 K는 3 설정. 
R = np.array([[4, np.NaN, np.NaN, 2, np.NaN ],
              [np.NaN, 5, np.NaN, 3, 1 ],
              [np.NaN, np.NaN, 3, 4, 4 ],
              [5, 2, 1, 2, np.NaN ]])

num_users, num_items = R.shape
K=3

# P와 Q 매트릭스의 크기를 지정하고 정규분포를 가진 random한 값으로 입력합니다. 
np.random.seed(1)
P = np.random.normal(scale=1./K, size=(num_users, K))
Q = np.random.normal(scale=1./K, size=(num_items, K))

비용계산 함수를 생성. 분해된 행렬 P와 Q.T를 내적하여 예측 행렬 생성하고 실제 행렬에서 널이 아닌 값의 위치에 있는 값만 예측 행렬의 값과 비교하여 RMSE값을 계산하고 반환

from sklearn.metrics import mean_squared_error

def get_rmse(R, P, Q, non_zeros):
    error = 0
    # 두개의 분해된 행렬 P와 Q.T의 내적으로 예측 R 행렬 생성
    full_pred_matrix = np.dot(P, Q.T)

    # 실제 R 행렬에서 널이 아닌 값의 위치 인덱스 추출하여 실제 R 행렬과 예측 행렬의 RMSE 추출
    x_non_zero_ind = [non_zero[0] for non_zero in non_zeros]
    y_non_zero_ind = [non_zero[1] for non_zero in non_zeros]
    R_non_zeros = R[x_non_zero_ind, y_non_zero_ind]
    full_pred_matrix_non_zeros = full_pred_matrix[x_non_zero_ind, y_non_zero_ind]

    mse = mean_squared_error(R_non_zeros, full_pred_matrix_non_zeros)
    rmse = np.sqrt(mse)

    return rmse

경사하강법에 기반하여 P와 Q의 원소들을 업데이트 수행

# R > 0 인 행 위치, 열 위치, 값을 non_zeros 리스트에 저장. 
non_zeros = [ (i, j, R[i,j]) for i in range(num_users) for j in range(num_items) if R[i,j] > 0 ]

steps=1000
learning_rate=0.01
r_lambda=0.01

# SGD 기법으로 P와 Q 매트릭스를 계속 업데이트. 
for step in range(steps):
    for i, j, r in non_zeros:
        # 실제 값과 예측 값의 차이인 오류 값 구함
        eij = r - np.dot(P[i, :], Q[j, :].T)
        # Regularization을 반영한 SGD 업데이트 공식 적용
        P[i,:] = P[i,:] + learning_rate*(eij * Q[j, :] - r_lambda*P[i,:])
        Q[j,:] = Q[j,:] + learning_rate*(eij * P[i, :] - r_lambda*Q[j,:])

    rmse = get_rmse(R, P, Q, non_zeros)
    if (step % 250) == 0 :
        print("### iteration step : ", step," rmse : ", rmse)

### iteration step :  0  rmse :  3.2388050277987723
### iteration step :  250  rmse :  0.029248328780879088
### iteration step :  500  rmse :  0.01697365788757103
### iteration step :  750  rmse :  0.01657420047570466

pred_matrix = np.dot(P, Q.T)
print('예측 행렬:\n', np.round(pred_matrix, 3))

예측 행렬:
 [[3.991 0.897 1.306 2.002 1.663]
 [6.696 4.978 0.979 2.981 1.003]
 [6.677 0.391 2.987 3.977 3.986]
 [4.968 2.005 1.006 2.017 1.14 ]]

파이썬 추천 패키지 Surprise

! 주의할 점 Input 데이터의 형식이 정해져 있습니다. user_id(1열), item_id(2열), rating(3열) 열들이 사용자를 기준으로 한 row레벨의 평점 데이터 세트만 입력 가능(네 번째 열 이후부터는 아에 사용하지않음) test() : 사이킷런의 predict()와 같습니다. predict() : 개별 사용자 한명에 대한 예측(전체X)

Reader클래스로 파일의 포맷팅 지정하고 Dataset의 load_from_file()을 이용하여 데이터셋 로딩

from surprise import accuracy 
from surprise.model_selection import train_test_split
from surprise import Reader

reader = Reader(line_format='user item rating timestamp', sep=',', rating_scale=(0.5, 5))
data=Dataset.load_from_file('./ml-latest-small/ratings_noh.csv',reader=reader)

학습과 테스트 데이터 세트로 분할하고 SVD로 학습후 테스트데이터 평점 예측 후 RMSE평가

trainset, testset = train_test_split(data, test_size=.25, random_state=0)

# 수행시마다 동일한 결과 도출을 위해 random_state 설정
# SVD 학습은 TrainSet 클래스를 이용해야 함
algo = SVD(n_factors=50, random_state=0)

# 학습 데이터 세트로 학습 후 테스트 데이터 세트로 평점 예측 후 RMSE 평가
algo.fit(trainset) 
predictions = algo.test( testset )
accuracy.rmse(predictions)

# Cross-Validation
from surprise.model_selection import cross_validate 
cross_validate(algo, data, measures=['RMSE', 'MAE'], cv=5, verbose=True) 

# GridSearchCV
from surprise.model_selection import GridSearchCV

# 최적화할 파라미터들을 딕셔너리 형태로 지정. 
param_grid = {'n_epochs': [20, 40, 60], 'n_factors': [50, 100, 200] }

# CV를 3개 폴드 세트로 지정, 성능 평가는 rmse, mse 로 수행 하도록 GridSearchCV 구성
gs = GridSearchCV(SVD, param_grid, measures=['rmse', 'mae'], cv=3)
gs.fit(data)

0. 데이터베이스 서버

데이터베이스 서버 접속 $ mysql -u 사용자명 -p dbname

1. 데이터베이스

CREATE DATABASE database

• 데이터베이스 생성

DROP DATABASE database

• 데이터베이스 삭제

USE database

• 데이터베이스 선택

SHOW DATABASES

• 데이터베이스 목록 조회

문제

1. 프로그래머스, 3단계, N으로 표현

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

문제 풀이

• 이 문제는 상향식 방법(Bottom-up, Tabulation)의 다이나믹 프로그래밍 방법으로 풀이했습니다.
• 다이나믹 프로그래밍을 사용한 가장 큰 이유는 괄호의 존재때문입니다.
• 괄호가 없다면 단순히 앞에서부터 사칙연산을 모두 구해가며 number와 일치하는지만 확인하면 쉽게 풀이가 가능합니다.
• 괄호의 존재때문에 i개의 N으로 이루어진 숫자들의 모음은
  1. j개의 N으로 이루어진 사칙연산 결과 모음과
  2. i-j개의 N으로 이루어진 모음의 조합으로 이루어져 있다고 생각하고 문제에 접근해보겠습니다.(1=<j<4)

1. 우선 N이 number와 같다면 N 하나만 필요하므로 1을 리턴하고 dp는 list를 값으로 가지는 딕셔너리로 지정해둡니다. 여기서 dp[i]는 i개의 N으로 이루어진 사칙연산의 결과값들의 list입니다.

    if N == number:
        return 1
    dp = collections.defaultdict(list)
    dp[1].append(N)

2. 33, 555같이 N이 사칙연산없이 이어붙어진 형태의 수들을 처리해줍니다.

    for i in range(2,9):
        dp[i].append(int(str(N)*i))

3. 이제 중복된 하위 문제들(Overlapping Subproblems)을 갖는 DP의 특징을 이용합니다. dp[j]의 요소들과dp[i-j]를 사칙연산한 결과를 순서대로 dp[i]에 넣어줍니다.

   • for문을 줄이기 위해 extend와 map, lambda로 각 사친연산의 결과를 한번에 처리합니다.

   • 0으로 나누는 경우 Error가 뜨는데 try,except 처리해줍니다.

   • 매 i번째 탐색마다 연산 결과에 타겟인 number가 존재한다면 i를 리턴합니다.

   • i=8까지 탐색했음에도 일치하는 결과값이 없다면 -1을 리턴합니다.

     for i in range(2,9):
       dp[i].append(int(str(N)*i))
       for j in range(1,5):
           # dp[i]는 dp[i-j]와 dp[j]의 조합
           for d_i in dp[i-j]:
               dp[i].extend(list(map(lambda x:x+d_i, dp[j])))
               dp[i].extend(list(map(lambda x:x-d_i, dp[j])))
               dp[i].extend(list(map(lambda x:x*d_i, dp[j])))
               try:
                   dp[i].extend(list(map(lambda x:x//d_i, dp[j])))
               except:
                   continue
       if number in dp[i]:
           return i
     return -1

     최종 제출 코드

     import collections
     def solution(N, number):
     if N == number:
       return 1
     dp = collections.defaultdict(list)
     dp[1].append(N)
     
     for i in range(2,9):
       dp[i].append(int(str(N)*i))
       for j in range(1,5):
           # dp[i]는 dp[i-j]와 dp[j]의 조합
           for d_i in dp[i-j]:
               dp[i].extend(list(map(lambda x:x+d_i, dp[j])))
               dp[i].extend(list(map(lambda x:x-d_i, dp[j])))
               dp[i].extend(list(map(lambda x:x*d_i, dp[j])))
               try:
                   dp[i].extend(list(map(lambda x:x//d_i, dp[j])))
               except:
                   continue
       if number in dp[i]:
           return i
     
     return -1

최종 제출 코드

def solution(n, computers):
    answer = 0
    bfs = []
    visited = [0]*n

    while 0 in visited:
        x = visited.index(0)
        bfs.append(x)
        visited[x] = 1

        while bfs:
            node = bfs.pop(0)
            visited[node] = 1
            for i in range(n):
                if visited[i] == 0 and computers[node][i] == 1:
                    bfs.append(i)
                    visited[i] = 1
        answer += 1
    return answer

문제

DFS

1. 프로그래머스, 3단계, 여행경로

   BFS

2. 프로그래머스, 3단계, 네트워크

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력

문제풀이

• collcetion 내장 모듈에는 defaultdict라는 함수가 있습니다. 이 문제의 경우 list로 입력 형식을 지정해주면 별다른 추가 조치없이 append 명령어를 쓸 수 있습니다.
• 여행 일정을 그래프로 구성해 DFS 방식으로 풀이했습니다.

1. 우선 그래프를 구성해줍니다. 알파벳이 앞서는 경로부터 방문해야하기 때문에 sorted해줍니다.

   graph = collections.defaultdict(list)
   for a , b in sorted(tickets):
    graph[a].append(b)

2. dfs함수를 만들어줄겁니다. 알파벳 순으로 정렬했기 때문에 맨 앞의 공항부터 재귀적으로 pop(0)을 사용해 추출해서 path에 추가해줍니다. 모든 티켓이 graph에서 추출될때까지 while문이 유지되며 마지막으로 방문한 도시부터 path에 차곡차곡 쌓이게 됩니다. 모든 도시를 방문할 수 있도록 문제가 주어졌기 때문에 중간에 끊기는 경우는 고려하지 않습니다.

   path = []
   def dfs(a):
    while graph[a]:
        dfs(graph[a].pop(0))
    path.append(a)
   

dfs("ICN")

3. 재귀를 사용했기 때문에 path는 마지막 공항부터 차곡차곡 쌓여있습니다. 리스트를 거꾸로 뒤집어 줍니다. `[::-1]`
```python
return path[::-1]

최종 제출 코드

import collections
def solution(tickets):
    graph = collections.defaultdict(list)

    for a , b in sorted(tickets):
        graph[a].append(b)
    path = []
    def dfs(a):
        while graph[a]:
            dfs(graph[a].pop(0))
        path.append(a)

    dfs("ICN")

    return path[::-1]

보완

• pop(0) 연산은 시간복잡도가 $O(n)$이지만 pop()은 $O(1)$입니다.
• Stack으로 구현해서 pop()을 사용하도록 하면 더 효율적인 코드가 될 것 같습니다.

문제

1. 프로그래머스, 3단계, 이중우선순위큐

문제 설명

• 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
• 원소는 “명령어 데이터” 형식으로 주어집니다.
• 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

입출력

문제풀이

• heapq모듈을 사용합니다
• 파이썬의 heapq는 최소힙만을 지원합니다. 따라서 최소값은 heappop으로 바로 추출할 수 있지만 최대값은 다른 처리를 해주어야합니다.
  

1. 입력값인 operations 리스트의 element들을 순서대로 받아 공백을 기준으로 op1, op2로 분리합니다.

   answer = []
   for op in operations:
    op1, op2 = op.split(" ")
    ...

2. "I"을 받으면 op2를 int로 변환해(for 값 비교) answer에 추가해줍니다.

    if op1 == "I":
        heapq.heappush(answer, int(op2))

3. 중요한 부분입니다. heapq에는 nlargest라는 힙에서 상위 n개의 값을 리스트 형식으로 추출합니다. 여기서는 op2=="1"일 때, nlargest의 인자를 1로 하여 answer의 상위 1개, 즉, 최대값을 얻어 제거합니다. op2 == "-1"이면, 최소힙의 기능을 이용해 쉽게 answer의 최소값을 제거합니다.

    elif answer:
        if op2 == "1":
            answer.pop(answer.index(heapq.nlargest(1,answer)[0]))
        else:
            heapq.heappop(answer)
        ...

4. answer에 값이 남아 있다면 최대값, 최소값을 return하고 남아 있지 않으면 [0,0]을 return합니다.

    if answer:
        return [max(answer), min(answer)]
    else:
        return [0,0]

최종 제출 코드

import heapq
def solution(operations):
    answer = []
    for op in operations:
        op1, op2 = op.split(" ")
        if op1 == "I":
            heapq.heappush(answer, int(op2))
        elif answer:
            if op2 == "1":
                answer.pop(answer.index(heapq.nlargest(1,answer)[0]))
            else:
                heapq.heappop(answer)
    if answer:
        return [max(answer), min(answer)]
    else:
        return [0,0]

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입력

1. nums : [1,2,3,4]
2. nums : [1,2,7,6,4]

   출력

3. result : 1
4. result : 4

문제 풀이

• 우선 소수는 2를 제외하면 무조건 홀수이기 때문에 세 숫자를 더해서 홀수가 되는 경우만 고려했습니다.
• (숫자 셋을 더하면 무조건 2이상이므로 2를 예외처리 하지 않았습니다.)
• 소수 판별은 내장 함수를 추가해 판별합니다.

  def is_prime(x):
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
               return False
    return True

• 주어진 nums를 홀수 odds와 짝수 even으로 구분합니다. 방법의 개수를 저장할 변수 count도 지정해줍니다.

  odds = [n for n in nums if n%2 != 0]
  even = [n for n in nums if n%2 == 0]
  count = 0

• (1) 홀수 + 홀수 + 홀수

itertools의 combinations를 이용하여 홀수 3개로 만들 수 있는 모든 조합을 구해 그 중 숫자 셋을 더해 소수가 되는 경우 count를 올립니다.

if len(odds) >= 3:
    for three_odd in itertools.combinations(odds, 3):
        if is_prime(sum(three_odd)):
            count += 1

• (2) 홀수 + 짝수 + 짝수 even에서 2개의 짝수를 뽑아 그 둘의 조합의 합과 odds의 홀수 1개와 순차적으로 더해가며 소수를 판별합니다.

  if len(odds) >= 1 and len(even) >= 2:
    for odd in odds:
        for two_even in itertools.combinations(even,2):
            if is_prime(sum(two_even)+odd):
                count += 1

최종 제출 코드

import itertools
import math
def solution(nums):

    def is_prime(x):
        for i in range(2, int(math.sqrt(x))+1):
            if x % i == 0:
                return False
        return True

    odds = [n for n in nums if n%2 != 0]
    even = [n for n in nums if n%2 == 0]

    #홀 홀 홀
    count = 0
    if len(odds) >= 3:
        for three_odd in itertools.combinations(odds, 3):
            if is_prime(sum(three_odd)):
                count += 1
    #홀 짝 짝
    if len(odds) >= 1 and len(even) >= 2:
        for odd in odds:
            for two_even in itertools.combinations(even,2):
                if is_prime(sum(two_even)+odd):
                    count += 1

    return count

2보다 큰 자연수 중 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 수

import math
def is_prime_number(x):
    for i in range(2, int(math.sqrt(x))+1): # 2부터 x의 제곱근까지 확인
        if x % i == 0:
            return False
    return True

에라토스테네스의 체

2부터 N까지의 모든 자연수에 대한 소수 판별

1. 2부터 N까지의 모든 자연수를 나열한다.

2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.

3. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다.)

4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

   def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n
   
    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False
   
    return [i for i in range(2, n) if sieve[i] == True]

   아래는 프로그래머스에서 본 풀이인데, 시간은 더 오래걸리지만 간결하고 이해하기 쉽습니다.

   def solution(n):
    num=set(range(2,n+1))
   
    for i in range(2,n+1):
        if i in num:
            num-=set(range(2*i,n+1,i))
    return list(num)

문제

1. 프로그래머스, 2단계, 소수만들기

List

Tuple

Dict

그외 내장 모듈

파이썬의 내장 모듈(ex. collections, heapq)은 C로 작성되어 그 속도가 파이썬보다 훨씬 빠릅니다.

getattr

d = deque
getattr(d, "append")(1)

위 코드는 d.append(1)과 완벽하게 동일한 코드입니다. 일반적으로는 굳이 귀찮게 getattr을 쓸 필요가 없이 .을 사용하는게 더 낫습니다. getattr의 특징은 두 번째 인자를 str 자료형으로 받는다는 것인데 다음 예시를 확인해주세요.

HackerRank, Collections.deque() 첫 줄은 후에 나올 명령의 개수입니다. 두번째 줄부터는 어떤 명령을 수행할 지를 나타냅니다.

Input : 

6
append 1
append 2
append 3
appendleft 4
pop
popleft

다음과 같이 코드를 매우 간소화할 수 있습니다. getattr을 사용하면서 if문으로 하나하나 수작업해야하는 수고를 덜었습니다.

from collections import deque
d = deque()
for _ in range(int(input())):
    cmd, *args = input().split()
    getattr(d, cmd)(*args)

코드와 매일 매일 한 것들을 정리하기 위해 블로그를 찾아봤다. Github Blog랑 티스토리도 만들어봤지만(아주 오래걸려서..) 코드가 깔끔하게 보이고 내가 다시 찾아보기에 편한 Velog로 정착! 잘 부탁드립니다.