목차

  • gradio란?
  • 사용법
  • 동작 방식
  • 어디서 든 내 모델을 사용할 수 있게 하기
  • 한계점

Gradio란?

Gradio는 Model을 웹으로 손쉽게 사용할 수 있게 해주는 라이브러리이자 플랫폼입니다.

각종 UI를 쉽게 그릴 수 있게 해주고, input을 받아 서버에서 inference 혹은 predict를 한 후 그 결과를 사용자들에게 돌려줍니다.

다른 웹 어플리케이션 서버들과 차별화된 점은 ML 모델이 자주 다루는 컴포넌트들이 이미 이쁜 UI로 구현이 돼 있다는 점이죠.

복잡한 커스터마이징은 어렵지만, 오디오, 비디오, 챗봇, 이미지, 텍스트, 확률 표시 등 머신러닝에서 자주 사용하는 기능들을 거의 코딩 없이 제공가능합니다.

사용법

먼저 gradio를 설치해 줍니다.

pip install gradio

아래가 기본적인 템플릿입니다.

 

 

이 템플릿을 실행 시켜보면 주소가 나오는데, 그 주소를 웹 브라우저에 복사 붙여넣기를 하면 다음과 같은 웹페이지가 뜹니다.

동작 방식

gradio는 기본적으로 fastapi를 기반으로 돌아갑니다.

복잡한 것들을 설명하기는 지면이 길어지니 주로 사용하는 예시들을 들어드리겠습니다.

12번째 줄은 함수가 들어갑니다. 정확히는 python의 callable이면 모두 들어갈 수 있습니다.

이에 대한 구체적인 구현은 4-7번째 줄에서 확인할 수 있습니다.

여기서 13번째 줄의 inputs 파라미터에는 어떤 종류를 넣을 것인지 결정할 수 있습니다.

여기서 inputs에 들어갈 수 있는 오브젝트들을 컴포넌트라고 합니다.

가장 기본적인 동작은 inference 함수의 parameter 명이 컴포넌트의 label 명이 됩니다.

즉 13번째 줄은 text 컴포넌트를 사용하겠다는 것이고, text의 label은 'my_input'이 됩니다.

조금더 자세히는 gr.components.Text 를 내부적으로 생성하게 되는데 자세한 설정을 하고 싶다면 이 컴포넌트를 직접 넘겨줘도 됩니다.

이왕이면 inference 함수의 parameter의 개수가 inputs의 개수가 일치하는게 좋습니다.

아래 예제를 보시면 더 이해가 쉽습니다.

 

 

이 코드는 아래와 같이 웹에서 랜더링 됩니다.

파라미터 명이 label이 되는 것을 확인할 수 있죠 (각 컴포넌트의 좌측 상단)

여러개의 output을 내보내고 싶다면 ,로 구분해서 (구체적으로는 tuple 형태로) return 해주면됩니다.

각 형의 어떤방식으로 랜더링할지는 outputs에 정해주면 됩니다.

구체적인 설정은 공식 document를 참고하시면 좋습니다.

https://gradio.app/docs/

 

Gradio Docs

Browse Gradio Documentation and Examples

gradio.app

어디서 든 내 모델을 사용할 수 있게 하기

아주 쉽습니다.

17 번 줄을 보시면 share=True 라는 코드가 있습니다.

이 코드를 입력하면 어디서든 접근 가능한 .gradio.live 로 끝나는 public url이 생성됩니다.

구체적으로는 터널링을 통해서 구현돼 있는데, 외부로 접근만 가능하다면 NAT 환경에서도 쉽게 사용이 가능합니다.

복잡한 것은 모르셔도 되지만, 그냥 어디서든 접근 가능하다 정도로 이해하시고 넘어가면 좋습니다.

한계점

유료 plan을 사용하지 않는 이상 저 URL은 3일정도만 유지 됩니다. 

직접 서버를 띄워서 사용하면 3일이상 사용할 수 있습니다.

클라우드에 EC2등에 띄워서 사용할 수 있습니다. 

하지만 EC2는 또 EC2 비용이 나가죠 ㅠㅠ

목차

  • LeetCode의 콘테스트 참여 방법
  • Leet Contest의 난이도
  • BOJ 기준 난이도
  • View와 reputation 쉽게 얻기
  • 리워드는?
  • 랭킹은 언제 갱신 되나요?

LeetCode의 콘테스트 참여 방법

LeetCode에서는 BiWeekly & Weekly 콘테스트가 열립니다.

상단의 Contest 탭을 누르면 Contest를 참여할 수 있습니다.

만약 Contest 에 참여하고 싶다면, Contest 전에 미리 등록해두시는걸 추천드립니다.

처음 컨테스트에 등록하신다면 다소 귀찮은 form을 작성해야 합니다.

게다가 컨테스트가 시작됐다면 시간을 낭비할 수도 있으니 꼭 미리 등록해주세요.

Leet Contest의 난이도

LeetCode의 분류로는 easy, medium, medium, hard 4문제가 순서대로 출제됩니다.

특별히 그것보다 더 어렵거나 하지는 않고, 다만 주어지는 시간이 1시간 30분으로 타이트합니다.

문제의 난이도는 컨테스트 출제자들마다 다소 왔다갔다 거리기는 합니다.

또 당연하지만, 익숙하지 않은 개념들이 출제되면 어렵게 느껴질 수 있습니다.

컨테스트의 출제되는 hard 문제들은 느낌상 특정 알고리즘을 알아야 하는 문제들보다는

조금 더 아이디어를 떠올려야하는 문제들을 자주 출제하는 것 같습니다.

BOJ 기준 난이도

BOJ기준으로 느낌상 최대 골드1 ~ 플레티넘4 정도 되는 것 같습니다.

  • 1번 문제는 브론즈~실버
  • 2번 문제는 골드5~골드2
  • 3번 문제는 골드3~골드1
  • 4번 문제는 골드1~플레티넘4

BOJ의 경우 아이디어적인 것보다 특정 알고리즘을 알고 있어야 풀리는 문제들이 많은 반면 LeetCode

View와 reputation 쉽게 얻기

큰 노력을 들이지 않아도, hard 문제를 풀고나서 직 후 solution을 작성하면 사람들의 관심이 몰립니다.

쉽게 reputation과 View들을 확보할 수 있습니다.

medium 문제로는 큰 관심을 받지는 못하는 것 같습니다. ㅠㅠ

꿀빤 솔루션 링크: https://leetcode.com/problems/rearranging-fruits/solutions/3144124/python-on-log-n-count-sorting-solution/

4문제를 다풀었을 때 ranking은?

간만에 Contest를 참가해서 아슬아슬하게 4문제를 다 풀거나, 4번 문제를 풀다가 끝나는 것 같아요.

4문제를 다풀면 문제 난이도에 따라서 600등에서 1000등 사이에 들 수 있습니다.

그 것보다 더 높은 랭킹을 가기 위해서는 빨리 풀어야 합니다.

LeetCode 의 콘테스트 자체가 난이도가 너무 높아서 못푸는 문제는 잘 내지 않기 때문에 빠른 속도로 풀어야 200등안에 들 수 있습니다.

저는 Contest에서 22000명 중에서 800~900등 정도를 달성 했는데, LeetCode Rating 1700 점을 얻을 수 있었습니다.

리워드는?

내부 코인을 줍니다. 변경될 수도 있으나 거의 같습니다.

그것 외에도 profile에 랭킹이 표시가 됩니다.

있어빌리티가 올라가니 취업에도 도움이 되지 않을까요?

랭킹은 언제 갱신되나요?

갱신되는 시기가 그때 그때 다른 것 같습니다.

제가 봤을 때는 1주일정도 걸립니다.

목차

이 글에서는 다음 사항들을 다룹니다.

  • AWS Lambda란 무엇인가
  • AWS Lambda의 장점과 단점
  • 람다의 기가막히게 저렴한 비용
  • 람다 실행 예제

Lambda 란?

Lambda는 AWS에서 단순한 코드 조각을 손쉽게 실행하게 해주는 Component 중 하나입니다.

AWS상에서 Serverless Architecture를 구현하기 위한 가장 간단한 솔루션으로 볼 수 있죠.

Lambda의 가장 큰 장점은 ms 초당 과금된다는데 있습니다.

따라서 초기에 트래픽이 많이 몰리지 않는 서비스들의 경우 복잡한 인프라 아키텍처를 고려하지 않고도 저렴하게 이용할 수 있습니다.

AWS에서 pre-tier 라고해서, 최소 사용량만큼 사용하면 과금을 하지 않는 정책을 피고 있는데,

이를 잘만 구성하면 공짜로 서비스를 만들 수도 있습니다.

Lambda의 장단점

장점

  • 아주 기초적인 단계까지는 한 function을 실행시키는데 복잡한 지식이 필요하지 않습니다.
  • 과금은 사용한만큼 1ms단위로 재서 과금됩니다.
  • 아주 직관적으로 동작합니다.

단점

  • 꽤 크리티컬한 제한 사항을 가지고 있습니다.
    • 최대 실행시간이 5분을 넘어가서는 안됩니다.
    • 사용할 수 있는 메모리가 최대 10GB입니다. 이 이상의 메모리를 사용할 수 없습니다.
    • 프로젝트의 용량이 제한됩니다.
  • 의외로 모니터링 및 디버깅하기가 까다롭습니다.
    • 제대로 이해하기 위해서는 Lambda와 다른 컴포넌트가 어떤방식으로 trigger되는지 이해할 필요합니다.

Lambda의 비용

비용의 정확한 값을 outdate 될 수 있습니다.

AWS에서는 매번 비용을 내리고 있습니다. 기술혁신에 따라 효율화되면 가격을 내리고, 고객을 모으는 방식을 선택하고 있죠.

그래서 이 정보는 outdate 될 수 있음을 미리 말씀드립니다.

GB-초

근데 이해하기 어렵죠? GB 초라는 건 메모리 * 사용 시간(초)입니다.

그 밑에 있는 가격표를 보시는편이 더욱 이해하기 쉽습니다.

메모리를 저만큼 쓰는 코드조각이 1ms초 실행 될 때 요금이 저렇다는 겁니다.

1GB 초 = 1,024 메모리에 1,000ms = 0.0000167 달러입니다.

기가막히게 저렴한 Lambda의 사용 가격 Simulation

한 함수의 호출당 100ms가 걸린다고 하면 100만번 api가 호출되면 16.7달러가 과금된다는 겁니다.

아 그리고 100만 요청당 0.2달러가 추가로 붙죠. 그러니 100만 요청당 16.9달러 정도 청구된다고 볼 수 있습니다.

Lambda의 pre-teir

저도 매번 까먹어서 적어놓겠습니다. pre-tier는 월별 적용이며, 1년이 지나도 계속 무료로 사용할 수 있다는 장점이 있습니다.

  • 100만건의 무료 요청
  • 월별 400,000GB-초의 컴퓨팅 시간

400,000GB-초가 계산이 잘 안되네요.

1GB-초는 메모리 1GB짜리 어플리케이션을 1,000ms 사용했을 때 charging 됩니다.

우리가 가정한 어플리케이션은 1GB당 10회의 처리를 할 수 있겠네요.

4,000,000 번 호출할 수 있네요! 대충 400만번입니다.

메모리는 4G로 올리거나, 한 API당 실행 시간을 400ms로 넉넉히 사용할 수 있겠네요.

이제 최소 100만회의 요청을 보내거나 넉넉한 메모리를 사용해서 서비스를 구성할 수 있겠네요!

그것도 무료로 말이죠!

AWS Lambda 비용 계산기



 

 

간단한 Lambda Service 만들어보기

⚠️ 이 파트는 AWS의 계정이 있음을 가정하고 진행됩니다.

AWS콘솔에서 Lambda를 검색합니다. 그리고 함수 생성을 누릅니다.

버전에 따라 다르겠지만 아래와 같은 창이 뜰겁니다.

저는 python을 좋아하니 python3.9로 런타임을 지정하고, 실행합니다.

함수 이름을 짓는것도 잊지마세요.

저는 간단하게 테스트하는 함수를 작성해 봤습니다.

import json

def lambda_handler(event, context):
    # TODO implement
    return {
        'statusCode': 200,
        'body': '테스트 '
    }

그럼 다음과 같은 에디터 창이 뜰텐데 에디터에 원하는 코드를 삽입하고 deploy 버튼을 눌러봅시다.

그러면 lambda 함수가 업데이트 됐다고 뜰텐데 이제 테스트 탭에가서 테스트를 해봅시다.

잘 동작하나요?

아주 기초적인 lambda 사용법이었습니다.

마무리

람다는 매우 고수준으로 추상화된 서비스입니다.

사실 서버라는 것이 무엇인지 모른다고 하더라도, json정도만 알면 누구나 서버를 구축할 수 있죠.

왠만한 EC2를 사용하는 것보다 더 저렴하게 서비스를 구성할 수 있을 겁니다.

다만 진짜 production으로 나가게되면 고려해야할 점들이 몇가지 있습니다.

Lambda 자체가 안정성이 떨어지는 편이기도 하고,

디버깅이 정말 까다롭기도 하죠.

다음에는 lambda로 제대로된 웹 어플리케이션 서버를 작성해 보겠습니다.

'개발 > AWS' 카테고리의 다른 글

aws IAM  (0) 2017.08.17
aws 시작하기  (0) 2017.08.17
aws에서 결제 알람 받기  (0) 2017.01.23
AWS 준비하기  (0) 2016.10.23

문제 링크: https://leetcode.com/problems/sum-of-distances-in-tree/

 

Sum of Distances in Tree - LeetCode

Sum of Distances in Tree - There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are given the integer n and the array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the

leetcode.com

 

문제

문제를 요약하자면 tree가 주어질 때 모든 정점으로부터의 거리가 최소가 되는 정점에서의 모든 정점으로까지의 길이의 합을 출력하는 문제가 되겠습니다.

직관

tree기 때문에 Cycle이 없습니다. 따라서 한 edge를 제거했을 때,  그래프로 나눠집니다.

A와 B를 잇는 edge가 있다고 가정해봅시다. 그리고, A쪽 그래프에있는 모든 노드로부터 A까지의 거리를 알 수 있다고 가정해봅시다.

그럼 B쪽 노드의 관점에서 봤을 때는 우리는 모든 A쪽 그래프의 노드로부터 B까지의 거리의 총합을 다음 수식으로 구할 수 있습니다. 

$$TotalDist_{A side} + NodeCnt_{A side}$$

왜냐하면 A쪽 노드로부터 B쪽 노드로 오는 모든 길은 edge A->B를 지날 수 밖이 없기 때문이죠.

접근법

그러므로 우리는 DP를 계산할 수 있습니다. 

노드 N과 S가 있을 때, edge (N,S)에 의해서 N쪽 graph와 S쪽 graph 로 나뉘게됩니다.

그리고
$cnt[n][s] = $ $n$ 쪽 그래프에 있는 노드의 수
$dist[n][s] =$ N쪽 그래프에서 S로 가는 총 거리의 합

라고 정의할 때 우리는 이 두 배열을 다음과 같은 방식으로 업데이트할 수 있습니다.

$G[n]$ 을 노드 N과 이어진 모든 이웃 노드들을 포함하고 있을 때


$$ dp[n][s] = sum_{i \in G[n], i \neq s}(dp[n][i] + cnt[n][i])$$
$$ cnt[n][s] = sum_{i \in G[n], i \neq s}(cnt[n][i])$$

로 계산되게 됩니다. 

복잡도

이 풀이는 시간복잡도와 공간복잡도가 오직 edge의 개수의 영향받으며, edge는 총 N-1개 존재합니다.

시간 복잡도: $O(N)$

공간 복잡도:  $O(N)$

코드

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        self.G = [[] for i in range(n)]
        
        for e in edges:
            self.G[e[0]].append(e[1])
            self.G[e[1]].append(e[0])
        
        ans = []
        for i in range(n):
            ans.append(self.dp(i, -1)[0])
        return ans
    
    @cache
    def dp(self, pnode, source):
        dist = 0
        cnt = 0
        for n in self.G[pnode]:
            if n == source:
                continue
            n_dist, n_cnt = self.dp(n, pnode)
            dist += n_dist + n_cnt
            cnt += n_cnt
        cnt += 1
        return dist, cnt

 

영문 솔루션

https://leetcode.com/problems/sum-of-distances-in-tree/discuss/2939374/Python-Super-Simple-O(N)-DP-Solution 

요즘 아침 출근할 때마다 스마트폰으로 문제 푸는 재미가 쏠쏠합니다.

 leetcode 문제들이 부담없이 한문제씩 매일 풀 수 있는 정도 난이도라서 아침에 하나씩 머리 깨우는 겸 풉니다. 

계속 할 수 있을까 싶었는데 부담도 안되고 꾸준히 풀게 되네요.

https://leetcode.com/choiking10/

 

윤호 최 - LeetCode Profile

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

1월 Badge도 받았습니다 ㅎㅎ 

시간이 나면 Contest도 참가해볼까 합니다.

leetcode 문제

틈틈히 재밌는 문제가 나오면 문제풀이도 블로그에 올리겠습니다.

왜 디버깅하면서 이미지를 봐야하지?

제가 예전에 담당했던 업무중에 사람 얼굴의 특징점 (눈, 코, 입 등이라고생각하면 편하다) 가지고 기능을 짜야했던 적이 있었습니다. 지금도 그렇지만 그때는 텐서감수성이 떨어질 때라서, 현재 짜고 있는 코드가 맞게 동작하는지 잘 이해가 안가는 경우가 굉장히 많았습니다. 🙂

이미지 출처: https://towardsdatascience.com/facial-keypoints-detection-deep-learning-737547f73515?gi=529af36da233

이미지 출처: https://towardsdatascience.com/facial-keypoints-detection-deep-learning-737547f73515?gi=529af36da233

특히, 이게 단순 산술연산이 아니라 이미지상에서 어느 부분을 짜르거나, 어느 부분을 기준으로 뭔짓을 가해야하는 종류라면 정말 디버깅에 많은 시간이 걸립니다. (예를 들면 얼굴 부분만 자르기!)

짜도 그 이미지에 알맞게 적용됐는지, 머리속으로 상상은 해도 실제로 그렇게 짜졌는지 실행하기 전까지 불안에 떨어야 했죠.

따라서 디버깅 하면서 이미지를 보는 건 디버깅 시에 확실히 이점이 있습니다. 보면서 실수를 그때 그때 잡을 수 있으니까요. 특히 저 같은 뉴비 머신러닝러는 더더더더더더욱 그렇습니다.

이처럼 머신러닝, 특히 비전관련한 테스크를 하다보면 디버깅을 할 때 이미지 파일을 보면서 할 때 더편한 경우가 왕왕 있습니다.

대안들

중간중간 이미지를 보는 작업은 생각보다 편하지만, 단순하게 이미지를 로그처럼 찍는 방법은 생각보다 불편합니다. 이렇게 할 경우 폴더를 열어서 이미지를 켜봐야 하고, 코드에 삽입해서 작성함으로 그때 그때 모델을 실행해야하죠.

특히 후처리를 해야할 경우 매 실행마다 모델을 로드해야하기 때문에 더 오랜 시간이 걸리게 됩니다. 이것 때문에 코드하나 고치고 다시 재시작하고, 모델을 로드하는데 많은 시간을 소모하게 됩니다. 😢

다른 방법으로는 plt.show() 같은 짓을 코드에 삽입하는 겁니다. 그러면 scientific mode로 pycharm을 사용하면 되죠. 하지만 전 이 scientific mode를 좋아하지 않습니다. 솔직히 창도 번거롭게 많아지고 생각보다 기능이 불편했습니다. 제가 잘 사용하지 못하는걸까요.

플러그인

그래서 저는 주로 pycharm의 디버거를 사용하는데, 이 디버거에서 사용하기 매우 좋은 플로그인을 소개하고자 합니다.

바로 디버깅 중에 이미지를 보여주는 플러그인입니다.

https://plugins.jetbrains.com/plugin/14371-opencv-image-viewer

여기 들어가서 pycharm에 추가하면 파이참에서 dialog가 뜨는데 수락을하면 바로 pycharm에서 이 플러그인을 사용할 수 있습니다.

사용법

플러그인이 정상적으로 설치됐다면 디버깅을 원하는 지점에 break point를 등록 후 디버깅 모드로 실행합니다.

Watch에 등록된 image 형태의 numpy 배열을 우클릭했을 때, View as Image 라는 메뉴가 등록됐을 거에요.

image 형태의 numpy 배열이란 H x W x 1, H x W x 3 (BGR), H x W x 4 (BGRA) 형태의 배열입니다. $256 \times 256 \times 3$ 형태가 되겠죠.

근데 이 메뉴를 디버깅때마다 클릭하는 것은 좀 귀찮으니까 전 주로 단축키 alt+i 를 사용해서 디버깅합니다.

이미지 출처:  https://en.wikipedia.org/wiki/Image

그러면 이렇게 창이 뜨면서 디버깅중에 이미지를 볼 수 있습니다! 이렇게 이미지를 보면 그때 그때 이미지에 조작을 가하면서 프로그램이 정상동작하는지 볼 수 있습니다. 프로그램을 다시실행하지 않고도요!

기타 꿀팁

Color 변환

그런데 프레임워크별로 color format이 다릅니다. 예를들자면 matplotlib와 pillow의 경우, RGBA 형태로 로드하게됩니다. (PNG의 경우)

그러니까 이걸 그냥 그대로 보면 이렇게 원본 얼굴과 전혀 다른 형태로 이미지가 나오게 됩니다. pytorch도 RGB 형태로 BGR 형태로 바꿔줘야 올바른 색으로 볼 수 있죠.

즉 이런 경우 color foramt을 변경해줘야 하는데, cv2.cvtColor로 한줄코딩해주면 쉽게 변경해줄 수 있습니다.

matplotlib 으로 load한 경우

cv2.cvtColor(mat_image, cv2.COLOR_RGBA2BGRA) # matplotlib로 load한 경우

cv2 모듈의 색형식 변환 함수인 cvtColor를 통해서 변환해준 것입니다.

만약 Alpha channel이 필요없다면 cv2의 색형식 상수에서 A들을 빼주시면 됩니다.

pillow 로 load한 경우

cv2.cvtColor(np.array(pil_image), cv2.COLOR_RGBA2BGRA)  # pillow로 load한 경우

pillow가 return하는 image의 경우 numpy 형태가 아닙니다.

따라서 np.array로 변환해줘야 정상적으로 보입니다.

그리고 색변환을 수행해줘야하죠.

마무리

이게 뭐라고 상당히 글이 길어졌네요.

도움이 되셨으면 좋겠습니다.

다른 꿀팁이 있다면 공유해주시면 감사하겠습니다!

자 다시 GAN 포스팅을 작성할 시간이네요.

아 GAN은 쓸게 많아서 너무 괴로워요... PS쪽이 확실히 더 작성하기 편하네요.

익숙한 개념이라서 그런걸까요?

오늘 알아볼 내용은 GAN의 증명과 한계 그리고 해결법에 관한 내용입니다. 오늘 내용은 WGAN을 들어가기 앞서 필요한 GAN에 대한 증명과 한계들을 다뤄볼 예정입니다.

수학적인 내용을 최소한으로 준비했지만, 도저히 못덜어낸 수학들이 좀 많이 남았습니다.

작성한 글에 오류가 있다면 코멘트 달아주세요! 그럼 바로 시작하겠습니다.

복습

역시 복습을 안하고 갈수는 없겠죠?

복습에서는 이전 포스팅의 내용을 요약하도록 하겠습니다.

 

[논문 정리] GAN에 대해서 알아보자 (1) - 개념, 알고리즘, 소스코드 분석

GAN에 대해서 알아보자 - 개념, 알고리즘, 소스코드 최근에 GAN에 관해서 이것저것 많이 찾아볼 기회가 있어서 이것을 정리하고 블로깅하고자 합니다. 이번 블로깅에서는 최대한 수학적인 내용없

lifeignite.tistory.com

GAN의 Component

GAN은 두가지 component로 구성되어 있습니다. Generator와 Discriminator입니다. Generator는 실제 데이터와 유사한 분포의 데이터를 생성하기 위해 노력하는 Component죠. Discriminator는 Generator가 만든 가짜 데이터와 실제 Data를 구별해주는 Component였습니다. Discriminator로 머신러닝 네트워크를 사용하는 이유는 generator가 생성하는 분포와 실제 데이터 분포를 수식화 하기 힘든 매우 어려운 분포이기 때문입니다.

GAN의 Sampling

그리고, GAN은 latent space에서 latent vector z를 sampling합니다. 초기의 latent space는 아무런 의미를 가지지 않기 때문에 여기서 sampling된 latent vector z도 아무런 의미를 가지지 않습니다만, 학습을 통해서 latent vector와 특정 데이터를 연결하게 되면서 latent space가 의미를 가지도록 바꿔줍니다. 마치 사람들이 아무의미없는 것들에 의미를 부여하는것처럼 네트워크도 경험적으로 latent space에 의미를 부여하기 시작할겁니다. ㅎㅎ

GAN의 학습 Algorithm

GAN의 학습은 2가지 step으로 이루어졌었죠. 첫번째 스텝에서는 Generator를 고정시키고, Discriminator를 학습시킵니다. 두번째 스텝에서는 Discriminator를 고정시키고, Generator를 학습시킵니다. 그리고 고정시킴에 따라 Loss Function이 일부 변경되었었습니다.

전체를 요약해보자면

GAN의 전체 구조를 요약해보자면 GAN은 latent space에서 sampling 한 z로부터 Generator는 어떠한 데이터 분포를 만듭니다. 그리고 이렇게 생성한 Generator의 분포와 실제 데이터 분포를 Discriminator로부터 비교하게 함으로서 G가 잘생성하면 D를 혼내주고, D가 잘 구분하면 G를 혼내주는 방법으로 학습을 수행합니다.

아래와같은 구조를 가지고 있죠.

GAN과 JS Divergence

직관적으로 GAN이 왜 동작하는지는 쉽게 이해가 됩니다. 그런데 직관적으로만 ㅇㅋ 하고 가면 조금 찝찝하죠. 그래서 GAN이 동작하는 이유에 대해서 증명을 하나하고 넘어가겠습니다.

이 내용은 이 후 WGAN으로 넘어가기 위해서 반드시 필요하다고 생각해서 넣었는데, 생략하시고 싶으시면 바로 WGAN으로 넘어가시면 됩니다.

한줄 요약

최초 제안된 GAN의 Loss function은 JSD를 계산하게 되는데, JSD는 두 분포가 겹치지 않았을 때, 상수 값을 가져서 gradient 계산으로 optimal을 찾는 것이 쉽지 않다.

GAN의 동작 조건

GAN의 목표는 실제 데이터 분포인 $P_{data}$ 와 Generator 가 만든 가짜 데이터 분포인 $P_{g}$ 가 같아지는 것을 목표로 합니다.

즉 GAN의 Loss Function인 아래 식이 최적일 때, $P_{data}=P_g$ 임을 만족해야한다는 뜻이죠.

$$\min_{G} \max_{D} V(G, D)=\mathbb{E}_{x \sim P_{data}(x)}[\log D(x)]+\mathbb{E}_{z \sim P_{z} (z)}[\log (1-D(G(z))]$$

일단, 최적의 G에 대해서 생각할 거니까, G를 고정한 것과 같죠? 저번 시간에 봤던 식이 튀어나올 겁니다.

$$\max_{D} V(G, D)=\mathbb{E}_{x \sim P_{data}(x)}[\log D(x)]+\mathbb{E}_{x \sim P_g (x)}[\log (1-D(x)]$$

 


Term 정리

자 변수가 너무 많으니까 좀 정리해볼께요.

  • $x$: 이미지 ( high-dimensional vector)
  • $G$: generator 함수입니다.
  • $D$: discriminator 함수입니다.
  • $P_{data}$: 실제 데이터 셋의 분포입니다.
  • $P_g$: generator가 생성한 가짜 데이터의 분포입니다.
  • $\mathbb{E}$: 기대값이에요. 의외로 이 기호를 잘모르시는 분들이 많더라구요.
  • 기대값은 $p(x)$의 확률로 나타나는 어떤 함수 $f(x)$의 평균으로써 $$\mathbb{E}_{x \sim p}[f] = \int p(x)f(x)dx$$로 계산될 수 있습니다.

 


Loss Function 이 최적일 때의 D

자 변수를 정리해놓고 봤는데, 저희의 목적을 잊지 말죠.

저희가 확인하고 싶은 것은 이 Loss Function이 최적일 때, $P_{data}=P_g$ 가 되는지 확인하는 것이에요.

그럼, Loss Function이 최적일 때는 어떨까요? 바로 Loss Function $V$ 를 최대화하는 것입니다.

Loss Function을 최대화하는 최적의 (optimal) $D$를 $D^*$ 라고 할께요 . 이를 수식으로 나타내면 아래와 같은 거에요.

$$D^*=arg\underset {D}{\max}V(D,G)$$

그리고 우리의 Loss Function $V$의 식이 아래와 같았습니다.

$$\max_{D} V(G, D)=\mathbb{E}_{x \sim P_{data}(x)}[\log D(x)]+\mathbb{E}_{x \sim P_g (x)}[\log (1-D(x)]$$

$\mathbb{E}$ 를 풀어볼게요. 기대값은 $\mathbb{E}_{x \sim p}[f] = \int p(x)f(x)dx$ 로 풀리니까,

$$\begin{aligned}V &=\mathbb{E}_{x \sim P_{ data }}[\log D(x)]+\mathbb{E}_{x \sim P_{g}}[\log (1-D(x))] \\&=\int_{x} P_{data }(x) \log D(x) d x+\int_{x} P_{g}(x) \log (1-D(x)) d x \\&=\int_x\left[P_{\text {data }}(x) \log D(x)+P_{g}(x) \log (1-D(x))\right] d x\end{aligned}$$

단순하게 식에 대입하고, 적분 기호안쪽으로 모아둔 것 밖에 없는 식입니다! 정말 단순한 식이에요.

자 이제 저 식에서 $a=P_{data}$ 이고, $b=P_G(x)$ 라고 했을 때 위식을 정리해보면,

$$f(x) = alogx+blog(1-x)$$

꼴이 되게 됩니다. 이 함수를 그래프로 그려보시면, 위로 볼록한 모양이 되게 되는데, 0과 1 사이에서 미분 가능합니다. 저희는 이 식의 최대값을 구하고 싶은 거니까 이 식을 미분해볼께요.

그러면 아래와 같이 미분이 가능합니다. (고등학교 로그 미분 입니다!)

$$\begin{aligned} \frac{f(x)}{dx} = \frac{a}{x} - \frac{b}{1-x}&=0 \\ a(x-1)+bx &=0\\ (b+a)x-a &=0 \\ \therefore x =\frac{a}{a+b} \\ \end{aligned}$$

즉, $x$가 $\frac{a}{a+b}$ 일 때, 최대 값을 가진다는 뜻이죠.

최적의 D에 다시 $a=P_{data}$ 이고, $b=P_G(x)$ 를 넣고 정리해보자면,

$$optimal \space D^*= \frac{P_{data}(x)}{P_{data}(x)+P_G(x)}$$

이 되게 됩니다.

D가 최적일 때, Loss Function의 의미는?

그럼 $D^*$ 일 때, 식은 어떻게 될까요?

한번 $a=P_{data}$ 이고, $b=P_G(x)$ , $D^*=\frac{a}{a+b}$ 로 넣고 정리 해볼께요.

$$\begin{aligned} &\max _{D} V(G, D)=V\left(G, D^{*}\right) \\ &=\int_x\left[P_{\text {data }}(x) \log D^*(x)+P_{G}(x) \log (1-D^*(x))\right] dx\\&=\int_x[\text{log}(a\frac{a}{a+b}) + \text{log}(b(1-\frac{a}{a+b}))]dx \\&=\int_x[\text{log}(\frac{1}{2}a\frac{a}{(a+b)/2}) + \text{log}(\frac{1}{2}b\frac{b}{(a+b)/2})]dx\\&=-2\text{log}2 + \int_x\text{log}a\frac{a}{(a+b)/2}dx + \int_x\text{log}b\frac{b}{(a+b)/2}dx \end{aligned}$$

자! 여기서 KLD와 JSD가 등장하게 됩니다. KLD에 대해서는 아래 포스팅을 참고하세요!

 

Entropy, Cross Entropy, KL-Divergence에 대해 알아보자

Entropy 엔트로피는 머신러닝에서 정보량을 나타내는 방법으로 사용된다. 정보의 량이라는게 되게 추상적으로 들리는데, 생각해보면 되게 간단한 개념이다. ML상에서 굉장히 많이 사용되는 개념

lifeignite.tistory.com

어쨌든 KL Divergence는 아래와 같이 정의됩니다.

$$KL(P \parallel Q)= \sum_xP(x)log\frac{P(x)}{Q(x)}$$

이식을 사용해서 풀어보자면,

$$\max _{D} V(G, D)=V\left(G, D^{*}\right) \\ =-2\text{log}2 + \int_x\text{log}a\frac{a}{(a+b)/2}dx + \int_x\text{log}b\frac{b}{(a+b)/2}dx\\ =-2 \log 2+\int_{x} P_{\text {data }}(x) \log \frac{P_{\text {data }}(x)}{\left(P_{\text {data }}(x)+P_{G}(x)\right) / 2} d x \\ +\int_{x} P_{G}(x) \log \frac{P_{G}(x)}{\left(P_{\text {data }}(x)+P_{G}(x)\right) / 2} d x \\ =-2 \log 2+\mathrm{KL}\left(\mathrm{P}_{\text {data }} \| \frac{\mathrm{P}_{\text {data }}+\mathrm{P}_{\mathrm{G}}}{2}\right)+\mathrm{KL}\left(\mathrm{P}_{\mathrm{G}} \| \frac{\mathrm{P}_{\text {data }}+\mathrm{P}_{\mathrm{G}}}{2}\right)$$

그리고, Jensen-Shannon Divergence(JSD)는 아래와 같이 정의가 됩니다.

$$\begin{aligned}\operatorname{JSD}(P \| Q)=\frac{1}{2} KL(P \| M) &+\frac{1}{2} KL(Q \| M) \\M &=\frac{1}{2}(P+Q)\end{aligned}$$

JSD는 KL의 개량형 버전이라고 생각하셔도되는데, KL이 대칭성이 성립하지 않아 거리로 사용할 수 없던 것을 대칭적으로 만들어줘 거리로 사용할 수 있게 됩니다.

모양이 JSD 처럼 변했죠? 그럼 아래와 같이 정리 할수 있게 됩니다.

$$\max _{D} V(G, D)=V\left(G, D^{*}\right)\\=-2 \log 2+\mathrm{KL}\left(\mathrm{P}_{\text {data }} \| \frac{\mathrm{P}_{\text {data }}+\mathrm{P}_{\mathrm{G}}}{2}\right)+\mathrm{KL}\left(\mathrm{P}_{\mathrm{G}} \| \frac{\mathrm{P}_{\text {data }}+\mathrm{P}_{\mathrm{G}}}{2}\right) \\=-2 \log 2+2 J S D\left(P_{\text {data }} \| P_{G}\right)$$

오우 정신 사납습니다. 결론은 저희의 Loss function은 JSD로 귀결되게 됩니다.

그리고 JSD는 두 분포사이의 거리로 사용할 수 있음으로, 따라서 위의 수식을 최소로 만드는 것은 두 분포사이의 거리를 최소로 만드는 것이란 거죠!

WGAN의 등장

자 이제부터 쉬워져요. 왜냐면 여기서 수학을 다뺏거든요.

한숨돌리시고 갑시다!

JS Divergence는 학습에 적합하지 않다!

WGAN에서 주장하길 좋은친구아저씨가 제안한 loss의 JSD는 학습에 적합하지 않다는 것이었습니다. 이걸 이해하기 위해서는 SUPP를 이해하셔야하는데, 간단히 설명할께요.

지지 집합 SUPP

SUPP는 support라고 읽는데, 한국어로는 지지집합이라고 합니다. 멋진 위키를 참고하자면

수학에서, 함수의 지지집합(支持集合, 영어: support 서포트[*]) 또는 받침은 그 함수가 0이 아닌 점들의 집합의 폐포이다.

X가 위상 공간이고, ${\displaystyle f\colon X\to \mathbb {R} }$이 함수라고 하자. 그렇다면 ${\displaystyle f}$의 지지집합 ${\displaystyle \operatorname {supp} f}$는 다음과 같다.
${\displaystyle \operatorname {supp} f=\operatorname {cl} {x\in X\colon f(x)\neq 0}}$
여기서 ${\displaystyle \operatorname {cl} }$ 폐포 연산자다.

인데, 사실 어려운말 다 쳐내고, 이해하시면 좋은 것 단하나 바로 0이 아닌 점들의 집합 입니다. 콤펙트하고 머시기하고 유계 집합 머시기 이런것들이 있는데 사실 저도 잘모릅니다. 수학과가아니라서요. 개념상 0이 아닌 점들의 집합으로 이해하고 넘어가셔도 큰문제가 없습니다.

그림으로 표현해보겠습니다. 두 분포 $\mathbb{P}_r$ 과 $\mathbb{P}_g$ 가 있다고 하겠습니다. 그 분포가 아래와 같이 있다고 가정해볼께요.

여기서 $SUPP \space \space \mathbb{P}_r$ 는 B 공간이 되고, $SUPP \space \space \mathbb{P}_g$ 는 A공간이 된다는 겁니다. 그야말로 0이 아닌 점들의 집합입니다.

이 때, $\mathbb{P}_r(A)=0, \mathbb{P}_r (B)=1$ 이 될 것입니다. 반대로, $\mathbb{P}_g(A)=1, \mathbb{P}_g (B)=0$ 이 되겠죠?

분포의 거리 측정

자 그럼 조금더 직관적인 설명을 위해서, 두 확률 변수를 2차원상의 분포라고 가정해서 생각해보겠습니다.

두 분포가 겹치지 않는다는 사실은 명확하죠. 서로 $0$ 과 $\theta$ 사이에서만 움직이니까요.

여기서 $\theta$ 는 다양한 값을 가질 수 있습니다.

하지만, $\theta \neq0$ 인 경우를 제외한 어떤 경우에도 두 분포가 겹칠 수는 없습니다. 이 경우 두 분포 중 하나가 0이 아닌 값을 가질 때는 다른 분포에서는 무조건 0인 값을 가지게 될 것입니다.

식으로 나타내면

$$\left\{\begin{array}{ll}P_{0}(x) \neq 0 & \Rightarrow P_{\theta}(x)=0 \\P_{\theta}(x) \neq 0 & \Rightarrow P_{0}(x)=0\end{array}\right.$$

이 떄 이상적으로 분포의 거리를 측정하는 지표라면 이 때 두 분포사의 거리는 어떻게 측정되는 것이 좋을까요?

직관적으로 두 분포사이의 최단거리(직선거리) $\theta$ 에 따른 값을 가지는 것이 적합할 것입니다. 예를들면 $\text{distance}(\mathbb{P}_0,\mathbb{P}_\theta)=\theta$ 와 같이 나타낼 수 있으면 좋겠네요.

KL의 경우

자, 그럼 KL divergence는 어떻게 두 분포사이의 거리를 측정할까요?

$$\mathrm{KL}\left(\mathbb{P}_{\theta} \| \mathbb{P}_{0}\right)=\int_{\left\{x: P_{\theta}(x) \neq 0\right\}} \log \left(\frac{P_{\theta}(x)}{P_{0}(x)}\right) P_{\theta}(x) \mu(d x)$$

$P_\theta>0$ 인 곳에서, $P_{0}(x)=0$ 이 되니까 아래와 같이 쓸수 있겠네요.

$$\log \left(\frac{P_{\theta}(x)}{P_{0}(x)}\right)=\infty$$

그럼 KL은 아래와 같이 계산됩니다.

$$\mathrm{KL}\left(\mathbb{P}_{\theta} \| \mathbb{P}_{0}\right)=\int \infty \cdot P_{\theta}(x) \mu(d x)=\infty$$

즉, $KL$ 값은 무한대의 값을 가지게 됩니다.

$\theta$ 가 0 이아닌 어떤 값이든, 모든 상황에서 무한대의 값을 가지게 되죠.

$$\mathrm{KL}\left(\mathbb{P}_{0}\|  \mathbb{P}_{\theta} \right)=\mathrm{KL}\left(\mathbb{P}_{0} \| \mathbb{P}_{\infty}\right)=\left\{\begin{array}{ll}\infty & : \theta \neq 0 \\0 & : \theta=0\end{array}\right.$$

JSD의 경우

이 경우는 매우 간단합니다. 한번 보시죠.

$$\begin{aligned}\mathrm{KL}\left(\mathbb{P}_{0} \| \mathbb{P}_{m}\right)=\int_{P_{0} \neq 0} \log \left(\frac{P_{0}(x)}{P_{0}(x) / 2}\right) P_{0}(x) \mu(d x)=\log 2 \\\mathrm{KL}\left(\mathbb{P}_{\theta} \| \mathbb{P}_{m}\right)=\int_{P_{\theta} \neq 0} \log \left(\frac{P_{\theta}(x)}{P_{\theta}(x) / 2}\right) P_{\theta}(x) \mu(d x)=\log 2\end{aligned}$$

그러므로 $\theta\neq0$ 이면 JS는 $\text{log}2$ 의 값을 가지게 됩니다. 따라서

$$\operatorname{JS}\left(\mathbb{P}_{\theta}, \mathbb{P}_{0}\right)=\left\{\begin{array}{ll}\log 2 & : \theta \neq 0 \\0 & : \theta=0\end{array}\right.$$

가 된다는 것이죠. 따라서 마찬가지로 $\theta$ 의 값과 상관없이 상항 같은 상수값을 나타내게됩니다.

GAN에서의 의미

이는 GAN을 학습하는데 큰 문제가 됩니다. Loss Function은 가까우면 가깝다고, 멀면 멀다고 명확히 말을 해주어야 이에 따른 gradient를 계산할 수 있습니다. 하지만 두 분포의 SUPP이 겹치지 않는다면 '두 분포가 완전히 다르다.' 라는 정보만 줄 뿐 어떻게 가깝게 만들지에 대한 정보 즉 gradient를 계산할 수 없다는 뜻입니다.

즉, D가 너무 깐깐하게 두 분포를 판단해서, 만약 두 분포가 겹치지 않는다면 두분포를 어떻게 가깝게 만들지에 대한 gradient를 계산할 수 없게 된다는 거죠.

이는 사실 일만적으로 이미지 생성과 같은 높은 dimension의 문제를 푸는 GAN에서는 이러한 분포가 겹치지 않는 문제가 더 심하게 발상할 것이기 때문에 GAN의 학습 성능이 떨어지는 등 꽤 크리티컬한 문제로 다가올 것이었습니다.

이 문제를 해결하러 왔다.

이 문제를 해결하기 위해서 2가지 방법을 소개해드리도록 하겠습니다.

  • 분포를 건드리는 방법
  • 분포의 거리 측정 방식을 개선하는 방법

당연히 우리가 앞으로 할 짓은 후자입니다만, 전자 쪽은 매우 간단하고 직관적으로 이해가 쉬우니까 한번 보고 가실께요.

노이즈를 통한 해결

Support가 겹치지 않는 것이 문제였습니다. 때문에 기존의 이미지에 노이즈 n을 추가해주면서 아래 그림처럼 두 분포의 Support영역을 넓혀 겹칠수 있도록 만들어주는 것입니다. 이렇게 두 분포를 겹치게 만들어주면 JSD를 사용해서 문제를 해결할 수 있습니다.

하지만 이러한 해결방법은 생성된 이미지가 굉장히 흐릿하게 나오는 등 문제가 발생하는 등 성능이 좋지 않게 나왔다고 합니다.

JSD가 아닌 다른 형태의 거리 측정 방식 사용

JSD는 두 분포가 겹치지 않을 때 상수가 나와 gradient를 계산하기 힘든 문제가 있었습니다.

따라서 저자는 분포가 겹치지 않아도 두 분포의 거리를 측정할 수 있는 방법인 Earth Mover Distance를 사용할 것을 제안합니다. 그리고 이제부터가 WGAN의 시작이죠.

WGAN은 다음 포스팅에서 다루도록 하겠습니다. 길이 너무 길어져서 여기서 한번 끊고 가도록 하겠습니다.

Reference

Codejam 문제 풀이

sub Title: (1) Round1

구글 code jam은 일반적으로 난이도 순으로 나오기때문에 순서대로 풀면된다.

순위

2000등 밖으로 밀려나서, 1A 라운드 통과는 못했다.

거의 4년만에 제대로된 대회에 참가하는것 같은데 그래서 그런지 정말 머리가 안돌아간다.

1B는 통과할만한 것같은데, 간만에 문제를 풀어서 그런가 문제 푸는속도도 코드도 영 맘에들지 않는다.

무엇보다 아이디어 떠오르는 속도가 정말 너무 많은 trial-and-error을 필요로한다.

Append Sort

문제는 아래에서 자세히 읽을 수 있다.

 

 

Code Jam - Google’s Coding Competitions

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

codingcompetitions.withgoogle.com

문제 설명

정수가 N개가 주어진다.

정수 N개를 정렬하고 싶은데, 정수끼리의 순서를 바꿀수 없다.

우리가수행할 수 있는 연산은 각 정수에다가 숫자들을 더하는 건데 예를 들면 123이 있다면 여기다가 4를 더해서 1234로만드는 이런연산이가능하다.

123 → 1234

이런 연산을 최소한으로 수행해서 strictly increasing order로 만들어라.

sample Input

4
3
100 7 10
2
10 10
3
4 19 1
3
1 2 3

Sample Output

Case #1: 4
Case #2: 1
Case #3: 2
Case #4: 0

설명:

첫번째는 아래처럼 추가하면 100, 700, 1000 으로 오름차순으로 만들수 있다.

100

7 → 700

10 → 1000

총 0을 4번 추가했고, 이거보다 적게 추가해서 오름차순으로 만들 수 없기 때문에 답은 4다 

솔루션 코드

for tc in range(int(input())):
    N = int(input())
    X = list(map(int, input().split(" ")))

    ans = 0
    for i in range(1, N):
        if X[i] > X[i-1]:
            continue
        s_b = list(str(X[i-1]))
        s_p_max = list(str(X[i]))
        s_p_min = list(str(X[i]))
        count = 0
        ori_len = len(s_p_max)
        while int("".join(s_b)) >= int("".join(s_p_max)):
            s_p_max += "9"
            s_p_min += "0"
            count += 1
        ans += count
        if int("".join(s_b)) < int("".join(s_p_min)):
            X[i] = int("".join(s_p_min))
        else:
            # same
            X[i] = X[i-1]+1

    print(f"Case #{tc+1}: {ans}")

그지처럼 풀었다.

첫번째 원소는 건드리지 않아도 되니까 range(1, N) 으로 시작한다. 시작부터 크다면 신경쓸필요없으니까 그리고 뒤를 9로 일단 채워나가면서(그 자리수에서 체울 수 있는 가장 큰 수) 될때까지 자리수를 늘려나간다.

그리고 늘려나간 최종 값중에서 가장 작은 값 (예를들자면, 10에서 2개의 digit을 추가했다면, 1099이 최대값, 1000이 최솟값이 된다.)이 배열의 이전 값 (s_b, X[i-1]) 보다 크다면 그게 답이 되기 때문에 X[i]에 그 값 자체를 넣어준다. int("".join(s_p_min))

만약 최솟값이 같다면, X[i-1]의 값에 +1해주면 된다. 이부분은 +1해줌으로서 다른자리까지 전부 변화시켜주려면 9여야하는데, 모두 9로 되어있는 경우는 14번 째 줄의

while int("".join(s_b)) >= int("".join(s_p_max))

에서 컷팅당한다. 즉 +1만해줘도된다. 

이해가 안가시면 질문주세요. 대충 설명드립니다.

Prime Time

 

문제는 아래에서 자세히 읽을 수 있다.

 

Code Jam - Google’s Coding Competitions

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

codingcompetitions.withgoogle.com

소수가 주어진다. (중복된 소수들도 주어진다.)

소수를 두 그룹으로 만들 것인데, 한 그룹은 덧셈으로, 한 그룹은 곱셈으로 모든 연산을 수행할것이다. 이 때 합을 한 그룹과 곱을 한 그룹의 계산 값이 같아야 한다.

예를 들자면

2 - 2개

3 - 1개

5 - 2개

7 - 1개

11 - 1개

가 주어졌을 때,

2+ 2 + 3 + 7 + 11 == 5 * 5

가 되고 두 그룹의 합은 25로 같다. 이렇게 만들 수 있는 가장 큰 값을 구하라.

중요한 인풋 설명

소수는 499 이하의 것들로만 주어진다.

소수는 서로다른 소수 95개 까지 주어질 수있으며, 각 소수는 여러개 존재할 수 있다.

Sample Input

4
5
2 2
3 1
5 2
7 1
11 1
1
17 2
2
2 2
3 1
1
2 7

Sample Output

Case #1: 25
Case #2: 17
Case #3: 0
Case #4: 8

설명:

첫번째 input은 2가 2개, 3이 1개, 5가 2개, 7이 1개 11이 1개다.

이 때, 더하기 그룹은 2, 2, 3, 7, 11을 선택하고, 나머지 곱하기 그룹은 5 5를 선택하면 최대값 25가 뽑인다. 그래서 답은 25

Test Set 1 솔루션 소스코드

$2≤N_1+N_2+⋯+N_M≤10$. (소수의 총 개수가 10개 이하)

from functools import reduce
for tc in range(int(input())):
    N = int(input())
    P = []
    for i in range(N):
        p_i, n_i = map(int, input().split())
        P += [p_i for j in range(n_i)]
    ans = 0
    for i in range(1 << len(P)):
        arr = list(enumerate([1 if i & (1 << j) else 0 for j in range(len(P))]))
        arr_mul = reduce(lambda x, y: x * y, [P[i] if v == 0 else 1 for i, v in arr])
        arr_sum = sum([P[i] if v == 1 else 0 for i, v in arr])
        if arr_mul == arr_sum:
            ans = max(ans, arr_mul)
    print(f"Case #{tc+1}: {ans}")

소수의 총 개수가 10개 이하다.

잘모를 땐 다해보자. 모든 소수를 분해한다. 0번그룹 1번그룹

그래서 두개의 곱과 합을 구한 후 두개가 같다면 ans로 출력한다.

Test Set 2 솔루션 소스코드

$2≤N_1+N_2+⋯+N_M≤100$. (소수의 총 개수가 100개 이하)

from functools import reduce

for tc in range(int(input())):
    N = int(input())
    P = []
    UP = {}
    for i in range(N):
        p_i, n_i = map(int, input().split())
        UP[p_i] = n_i
        P += [p_i for j in range(n_i)]
    all_sum = sum(P)
    ans = 0
    unique_p = UP.keys()
    for t in range(all_sum, 0, -1):
        is_fail = False
        may_ans = t
        tot = 0
        for p in unique_p:
            p_count = UP[p]
            while t % p == 0:
                t //= p
                p_count -= 1
                tot += p
                if p_count < 0:
                    is_fail = True
                if is_fail:
                    break
            if is_fail:
                break
        if t != 1:
            is_fail = True
        if not is_fail and all_sum - tot == may_ans:
            ans = may_ans
            break
    print(f"Case #{tc+1}: {ans}")

소스코드가 개판이다.

자 이제 어떻게 줄일 수 있을 지 생각해보자. 100개니까 모두를 해보는 건 불가능하다. ($2^{100}$ 은 안봐도 TLE)

합과 곱중 하나를 고정시켜야하는데, 생각해보면 모든 수의 합은 매우 작다. 그러니까 곱하는걸 선택할 때 많은 수를 곱할 수 없다.

100개를 다합쳐보면 최대 얼마가나올까?

$499 * 100 = 49900$ 밖에 안나온다.

그럼 모든 소수를 다더하고, 1씩 빼가면서 그 수를 만들 수 있는지 확인한다. 만약 만드는 것을 실패하면, 불가능하다는 것이고, 만드는 것을 성공하면 만드는데 든 소수의 합을 뺀 것이 지금의 수인지 체크하면 된다. 그 코드는 아래와 같다.

        if not is_fail and all_sum - tot == may_ans:
            ans = may_ans
            break

시간복잡도는 대충 49900 * len(unique_p) * log (49900) 정도 될껀데, 뒤에껀 대충 빼고, 계산해도 49,90,000 정도다. 매우적으니까 당연히 통과다. 문제는 테스트 셋 3인데...

Test Set 3 솔루션 소스코드

$2≤N_1+N_2+⋯+N_M≤10^{15}$. (소수의 총 개수가 $10^{15}$개 이하)

이거 보고 솔직히 아 당연히 수학문제겠지 하고 제꼈다. 구글 수학문제좋아하니까 그럴꺼라고 생각했다.

그런데 멍청했다.

from functools import reduce
for tc in range(int(input())):
    N = int(input())
    P = []
    UP = {}
    all_sum = 0
    for i in range(N):
        p_i, n_i = map(int, input().split())
        UP[p_i] = n_i
        all_sum += p_i * n_i
    ans = 0
    unique_p = UP.keys()
    for t in range(all_sum, max(0, all_sum-8982), -1):
        is_fail = False
        may_ans = t
        tot = 0
        for p in unique_p:
            p_count = UP[p]
            while t % p == 0:
                t //= p
                p_count -= 1
                tot += p
                if p_count < 0:
                    is_fail = True
                if is_fail:
                    break
            if is_fail:
                break
        if t != 1:
            is_fail = True
        if not is_fail and all_sum - tot == may_ans:
            ans = may_ans
            break
    print(f"Case #{tc+1}: {ans}")

거의 메인 로직은 똑같고 중요하게 추가된게 아래 이거 하나다.

for t in range(all_sum, max(0, all_sum-8982), -1):

생각해보면, 곱셈으로 아무리 빼고싶어도 소수를 빼는데 한계가 있다. 곱셈이 너무 커지니까. 그러니까 곱셈측에도 컷팅같은 느낌을 줄 수 있다.

잘 생각해보면 499를 $10^{15}$ 더해봤자 $499*10^{15}$ 이다. 아니 엄청 큰 숫자아니냐고? 곱셈의 세계에서는 매우 작은 숫자다.

그럼 소수 최대 몇개를 뺄 수 있을까. 를 계산해보면

$$\text{log}_2(499*10^{15})=17.xx$$

이긴한데, 사실 계산하기 귀찮으니까 아무리그래도 $499^{18}$ 보다는 작을거라고 생각할 수 있다. 그러니까 아무리 빼고싶어도 499를 18번보다 많이 뺄수없으며, 어떤 소수든 18개이상 빼면 전체합을 넘어가게된다.

즉 뺄수있는 것의 범위가 $499*18=8982$보다는 작게된다는 것이다.

그래서 정말 뺄수있는최소값을 range(all_sum-8982, all_sum) 로 잡으면 되는데, all_sum-8982 가 0보다 작을수있으니까 max를 씌워준것일 뿐이다.

이건 대회중에 떠올리지 못한 아이디어다. 답안지보고 아 수학아니었는데... 하고 너무 아쉬워서 딱 저 아이디어 추가하고 메모리문제좀개선해서 제출했떠니 바로 답이 뜨더라.

아쉽다아쉬워...

Hacked Exam

문제 해석을 잘못하고있다가 10분전에 해석을 완료했다;

테스트셋 1번은 그냥 긁을만했는데 긁었으면 비벼볼만했을텐데 아쉽다.

마무리

아쉽네. 다음번엔 더잘해야징. 1B에는 다음라운드갈수있지않을까.

논문을 검색하고, 성능을 찾아보고, 또 비교하고 하는 작업은 사실 굉장히 피곤한 작업입니다.

특히 인력을 갈아 넣지 않는이상 혼자서 한 분야의 모든 논문을 서베이하고, 성능을 비교분석하는 것은 정말 어려운 일이죠. 

거기다 각종 지표들, 그리고 데이터셋들에 대해서 검색하고 읽을 만한 논문을 선정하는 작업자체가 굉장히 번거롭고 어렵습니다.

ML 계열에서 이런 것을 대신해줄 수 있는 사이트가 있습니다. 

 

 

Papers with Code - The latest in Machine Learning

Papers With Code highlights trending Machine Learning research and the code to implement it.

paperswithcode.com

해당 사이트에서는 각 영역별로 세부 task를 나누고

 

사이트에서 여러 데이터셋, 지표등을 활용해서 논문의 성능을 보여줍니다. 

뿐만아니라 여기 등록된 대부분의 paper는 코드까지 포함하고 있어서 쉽게 코드를 참고할 수 있어서 더욱 좋죠.

각 데이터셋 별로 최고의 SOTA를 달성한 논문과 코드를 리스트업해줍니다.

논문을 찾기 막막하거나, 완전히 새로운 도메인의 연구를 시작했다면 정말 큰 도움이 될 사이트입니다.

사실 이런사이트가 없었다면 서베이부터 읽어야 했을 것이고, 심지어 서베이가 나오지 않는다면 매번 새 논문들을 뒤적거려야 했겠죠... 

알맞는 지표나 데이터셋 차즌ㄴ데에도 활용할 수 있습니다.

다들 연구 화이팅

자 오늘을 마지막으로... 하려고 했는데 생각보다 길어져서 다시 나누게 되었습니다.

생각 날때마다, 여러가지 잡기술들을 모아서 알려드리도록 할께요.

오늘은 python에서 기본적으로 제공해주는 정렬을 활용해서 조금이라도 코드를 편하고, 가독성있게 (나에게만 일지도...) 짤 수 있는 비법들을 알려드리도록 하겠습니다.

오늘 배울 내용들을 간단히 나열해드리자면,

  • sort, sorted 함수
  • enumerate 함수
  • for문에서 이름으로 원소 꺼내오기
  • 이들을 활용한 정렬처리 잡기 술

입니다.

정렬 트릭

정렬은 문제를 풀때 굉장히 자주 사용하게 되는 라이브러리입니다.

단순히 오름차순으로 정렬할 때 python에서 제공하는 sorted 라이브러리나 sort라이브러리를 사용합니다. 간단한 정렬 문제를 해보도록 할께요.

정렬 기초

이번에 풀어볼 문제는 수 정렬하기 입니다.

https://www.acmicpc.net/problem/2750

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력

5
5
2
3
4
1

예제 출력

1
2
3
4
5

문제가 간단해서 좋군요. 뭐가 문제겠어요? 정렬을 알아보는 가벼운 예제니까 빠르게 후딱처리하고 넘어갑시다.

사실 이 문제는 2가지 해법이 있어요. 크게 어려운 해법은 아니고, 원본 배열을 건드리냐 안건드리냐에 따라서 달라지게 되죠. 일단 먼저 보실까요?

답 코드1 - sorted

N = int(input())
D = [int(input()) for i in range(N)]
sorted_D = sorted(D)
for num in sorted_D:
    print(num)

답 코드2 - sort

N = int(input())
D = [int(input()) for i in range(N)]
D.sort()
for num in D:
    print(num)

sorted는 D를 건드리지 않고 새롭게 정렬된 배열을 return합니다.

그에 비해서 sort는 D의 배열 자체를 정렬된 상태로 바꿔버리죠.

이정도면 기본은 되었습니다. 이제 트릭을 알아보러 가시죠.

복잡한 정렬 수행하기

기본적으로 제공되는 함수는 여러가지 조건으로 복잡한 정렬을 수행하기위해서는 비교하기 위한 함수를 넘겨줘야하는 불편한 점이 있죠.

특히 많은 문제에서 여러가지 조건에 따라 비교를 수행해야하는 경우가 왕왕있습니다.

알고리즘은 정확하게 짜는 것도 중요하지만, 빠르게 짜는게 중요한 역할을 합니다. 그때 복잡한 비교구문을 일일이 작성해서 정렬하는 것은 시간낭비입니다.

빠르게 정렬하기 위한 꿀팁을 알려드릴께요. 바로 python 내장 정렬을 이용하는 방법입니다.

python 내장정렬은 다음과 같은 특징을 가지고 있습니다.

  1. 정렬은 오름차순으로 수행한다. (위의 예제에서 보여드렸죠?)
  2. 만약 정렬의 내용물이 tuple이라면 tuple의 낮은 인덱스에 있는 원소를 기준으로 정렬한다.

2번 항목이 잘 이해가지 않으실꺼에요. 간단한 예제를 드릴께요.

a = [
    (2, 4),
    (2, 3),
    (1, 4),
    (1, 3),
]
a.sort()

print(a)

이 코드의 출력은 무엇일까요? 바로

[(1, 3), (1, 4), (2, 3), (2, 4)]

가 됩니다.

첫번 째 원소 1과 2를 비교해서 오름차순으로 정렬을 수행하죠.

만약 첫번째 원소가 같다면 두번째 원소 3과 4를 비교해서 오름차순으로 정렬을 수행합니다.

직관적으로 당연히 그렇게 되어야 맞겠죠?

바로 이 트릭을 이용해서 복잡한 정렬을 추가적인 함수를 작성하지 않고 수행할 수 있습니다.

바로 문제로 가실께요.

https://www.acmicpc.net/problem/1181

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

  1. 길이가 짧은 것부터
  2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

예제 입력

13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

예제 출력

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

자 다소 복잡하죠? 하지만 코드는 문제보다 짧고, 쉽습니다.

바로 보시면서 이해하시죠.

정답 코드

N = int(input())
D = [input() for i in range(N)]
D = set(D)
D = [(len(s), s) for s in D]
D.sort()

for l, s in D:
    print(s)

1~2: 첫 두줄은 늘상 같은 인풋받는 방식입니다.

3~3: 중복을 없애주기 위해서 set 함수를 사용합니다.

4~5: 이게 바로 제가 말하고자하는 정렬트릭입니다.

python의 정렬은 첫번째 것을 먼저 정렬하고, 그다음 우선순위를 두번째 원소로 둡니다.

따라서 정렬의 첫번째 조건을 첫번째 원소에 두번째 조건을 두번째 원소에 넣는 방식으로 넣어두고 정렬을 할 수 있습니다.

만약 길이가 긴 것순으로 정렬하라고 했다면 어떻게 하면 될까요?

N = int(input())
D = [input() for i in range(N)]
D = set(D)
D = [(-len(s), s) for s in D]
D.sort()

for l, s in D:
    print(s)

라고 하시면 됩니다.

이처럼 오름차순, 내림차순도 안에 넣는 원소를 바꾸기만 해서 구현해낼 수 있습니다.

기본정렬에서 추가적인 함수를 호출하지 않고도 처리할 수있어요.

자잘한 꿀팁

사실 이보다 간단하게 처리할 수 있어요.

list뿐 아니라 set도 list처럼 입력을 받으면서 초기화할 수 있습니다.

N = int(input())
D = {input() for i in range(N)}
D = sorted([(len(s), s) for s in D])

for l, s in D:
    print(s)

당연히 더 줄일수도 있죠.

하지만 이 이상부터는 숏코딩의 영역입니다.

착한 어른이들은 따라하지 마세요!

정렬 트릭의 활용

https://www.acmicpc.net/problem/10814

눈에 보이는 조건들만이 조건이 아닙니다. 들어온 순서나, 길이, 입력받은 상수값 같은 것들도 이에 활용할 수 있습니다. 위 문제에도 이를 활용할 수 있습니다.

문제 설명은 지면이 길어져서 생략하도록 할게요.

입력 예제 1

3
21 Junkyu
21 Dohyun
20 Sunyoung

정답 코드

N = int(input())
D = [input().split(" ") for i in range(N)]
D = sorted([(int(age), order, name) for order, (age, name) in enumerate(D)])

for age, order, name in D:
    print(age, name)

이 코드에도 몇가지 보여드릴께 있습니다. 이 코드에서 배울 것은 크게 3가지입니다.

  1. enumerate
  2. for문의 unpack 트릭
  3. order를 정렬의 조건으로 넣기

enumerate

enumerate는 반복문을 돌 때, 배열의 인덱스, 배열의 원소 두가지를 활용할 수 있게 해줍니다.

3개라구요? 아닙니다 잘 보세요! 2개입니다.

order, (age, name) 2개라구요.

for문에서 이름 붙여서 가져오기

이것이 바로 python에서 for문에서 container를 unpack할 시에 제공하는 문법입니다.

아마 컨테이너 안에 있는 tuple에서 몇가지 원소를 이름을 붙여서 가져올 때 사용해보셨을 텐데, 컨테이너 안에 컨테이너에서 이름을 붙여서 가져올 수 있다는 사실은 사람들이 잘 모르시는 경우가 많았습니다.

이 경우에는 괄호를 생략하실수 없습니다! 바로 container에서 가져옴과 동시에 이름을 붙일 수 있기 때문에 코드의 가독성이 더 올라가게 되죠.

순서를 정렬의 기준으로 만들기

enumerate에서 가져온 배열의 인덱스는 곧 input을 받은 순서입니다. 문제의 조건에서

  1. 나이
  2. 들어온 순서 (가입한 순서)

라고 했기 때문에 (int(age), order) 순으로 만든 것이죠.

엇 그런데 name이 추가로 들어가 있네요?

맞습니다. 실제로 출력을 할 때에는 이름 정보가 필요합니다.

정렬시에 사용하기위해서가 아니라 그 데이터 자체를 보존하기 위해서 넣어 준거에요.

연습 문제

https://www.acmicpc.net/problem/10825

마무리

사실 오늘로 끝내려고 했는데, 정렬처리 잡기술이 조금 주저리 주저리가 길어졌네요.

다음에 시간이되면 다른 잡기술들도 소개하도록 하겠습니다.

생각보다 제가 사용하는 잡기술들이 많네요...

graph 알고리즘에서 사용하는 것들도 많고, 슬라이싱을 이용한 잡기술들도 굉장히 많은데

흠... 언제 다쓰지 이거

+ Recent posts