문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.
김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.
행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 $\rightarrow$ 1, 1 $\rightarrow$ 0)

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

Hicsonmez, Samet, et al. “GANILLA: Generative adversarial networks for image to illustration translation.” Image and Vision Computing 95 (2020): 103886.

Introduction

• 생산적 적대 신경망 (Generative Adversarial Network, GAN) 기반 아동도서의 삽화 (illustration) 스타일 이미지 변환
  • 일반적인 그림과 만화와 다르게 사물이 포함되지만 추상화 수준이 매우 높음
  • 기존 모델 (CycleGAN, DualGAN)을 통해 추상화 스타일과 삽화의 내용 간 균형을 다루는데 한계점 존재
• Goal: 주어진 일러스트 작가의 스타일을 전달하며 주어진 이미지의 콘텐츠를 보존하는 생성기 개발
  • 정렬되지 않은 두 개의 개별 image dataset $\rightarrow$ Unpaired approach
    • Source domain (natural images)
    • Target (illustrations)
  • 스타일과 콘텐츠의 불균형 문제
    • Residual layer에서 특징 맵을 다운 샘플링하여 새로운 생성기 네트워크 제시
    • 콘텐츠를 더 잘 전송하기 위해 skip connection 및 upsampling 사용 $\rightarrow$ 낮은 수준의 feature을 높은 수준의 feature와 병합
• Unpaired style transfer approach의 evaluation
  • 일반적으로 image-to-image translation 모델의 평가는 정성적
  • 생성된 이미지에 대해 짝지어진 ground-truth가 존재하지 않아 직접적으로 정량적 평가 불가
  • 콘텐츠 및 스타일 분류기 기반 정량적 평가 프레임워크 제안
• Highlights
  • Image-to-image style and content transfer의 새로운 연구
  • 24명의 아티스트에 대한 약 9500개의 illustration으로 구성된 dataset 제공
  • 스타일과 콘텐츠의 균형이 맞는 새로운 generator network 제안
  • 콘텐츠와 스타일 측면에서 이미지 생성 모델의 새로운 정량적 평가 프레임워크 제안

Natural Language Processing

• 자연어 처리 (Natural Language Processing, NLP): 컴퓨터와 사람의 언어 사이의 상호작용에 대해 연구하는 컴퓨터 과학과 어학의 한 분야
  • 문자 단위 RNN (character RNN): 문장에서 다음 글자를 예측하도록 훈련

1
2
3
4
5
6
7
8
9

from tensorflow.compat.v2 import keras

shakespeare_url = "https://homl.info/shakespeare"
filepath = keras.utils.get_file("shakespeare.txt", shakespeare_url)
with open(filepath) as f:
    shakespeare_text = f.read()

tokenizer = keras.preprocessing.text.Tokenizer(char_level = True)
tokenizer.fit_on_texts(shakespeare_text)

• 셰익스피어 작품을 다운로드 이후 Tokenizer를 통해 모든 글자를 정수로 인코딩

CycleGAN

• pix2pix
  • Self-supervised
  • Loss: Minimize the difference between output $G(x)$ and ground truth $y$
    • $\underset{(x,y)}{\Sigma}||y-G(x)||_1$
  • Ex) 흑백 $\rightarrow$ 컬러
• GAN
  • Loss: Another deep network point out the difference
    • $\arg\underset{G}{\min}\underset{D}{\max}\mathbb{E}_{x,y}[\log{D(G(x))}+\log(1-D(y))]$
  • $D$ tries to identify the fakes
  • $G$ tries to synthesize fake images that fool $D$