Sequence-to-sequence learning with Transducers

Transducer(RNN을 사용할 필요는 없지만 "RNN Transducer" 또는 "RNN-T"라고도 함)는 Alex Graves가 "반복 신경망을 사용한 시퀀스 변환(Sequence Transduction with Recurrent Neural Networks)"에서 제안한 seq2seq 모델입니다. 이 논문은 ICML 2012 Workshop on Representation Learning에서 출판되었습니다. Graves는 Transducer가 음성 인식에 사용하기에 적합한 모델이며 작은 데이터 세트(TIMIT)에서 좋은 결과를 달성했음을 보여주었습니다.

그 이후로 Transducer는 CTC 모델(예: Deep Speech 2) 또는 attention 모델(예: Listen, Attend 및 Spell)에 비해 많이 사용되지 않았습니다. 그러나 2019년에 Transducer는 Google 연구원들이 휴대폰에서 기기 내에서 대기 시간이 짧은 음성 인식(entirely on-device low-latency speech recognition)을 완전히 가능하게 할 수 있음을 보여주면서 큰 주목을 받았습니다. 그리고 최근에는 LibriSpeech 벤치마크에 대한 새로운 SOTA WER을 달성하기 위해 Transducer가 사용되었습니다.

그렇다면 Transducer란 무엇이며 언제 사용하고 싶습니까? 이 게시물에서는 Transducer 모델이 다른 시퀀스-투-시퀀스 모델과 어디에 적합한지 살펴보고 작동 방식에 대한 자세한 설명을 살펴보겠습니다.

이 게시물에는 toy problem에 대한 Transducer의 PyTorch 구현이 포함된 Colab 노트북도 포함되어 있습니다. 여기(here)로 바로 건너뛸 수 있습니다.

Attention Models

여기서 우리가 관심을 갖는 문제는 입력 시퀀스 $x = { x_1, x_2, ..., x_T}$를 출력 시퀀스 $y = { y_1, y_2, ..., y_U}$로 매핑하는 것이 목표인 시퀀스 변환 문제입니다.

시퀀스 변환 문제에 적합한(go-to) 모델은 RNN 인코더-디코더 모델(RNN encoder-decoder models) 또는 Transformer(Transformers)와 같은 Attention 기반 시퀀스-시퀀스 모델입니다.

다음은 Attention 모델의 다이어그램입니다. (아래 다이어그램에서 빨간색은 모듈이 x 에 대한 액세스 권한이 있음을 나타내고, 파란색은 y 에 대한 액세스 권한이 있음을 나타내고, 보라색은 x, y에 대한 액세스 권한이 있음을 나타냅니다.

모델은 입력 x를 일련의 특징 벡터로 인코딩한 후 인코딩된 입력 및 이전 출력의 함수로 다음 출력 $y_U$의 확률을 계산합니다. Attention 메커니즘을 통해 디코더는 각 출력을 예측할 때 입력 시퀀스의 다양한 부분을 볼 수 있습니다. 예를 들어 다음은 번역 작업 중에 디코더가 찾는 위치에 대한 히트맵입니다(from Bahdanau et al.).

Attention 모델은 모든 문제에 적용될 수 있지만 몇 가지 이유로 음성 인식과 같은 특정 문제에 대해 항상 최선의 선택은 아닙니다.

Attention 모델의 문제

• Attention 작업은 긴 입력 시퀀스의 경우 비용이 많이 듭니다. 모든 출력에 대한 전체 입력에 참여하는 복잡성은 $O(TU)$이며 오디오의 경우 $T$ 및 $U$가 큽니다.
• 어텐션 모델은 디코더가 처리하기 전에 전체 입력 시퀀스를 사용할 수 있어야 하기 때문에 온라인(실시간)으로 실행할 수 없습니다.
• Attention 모델은 또한 음성 인식의 경우 입력과 출력 간의 정렬이 단조롭다(monotonic)는 사실을 활용하지 않습니다. 즉, transcript에서 단어 A가 단어 B 뒤에 오는 경우 오디오 신호에서 단어 A는 단어 B 뒤에 와야 합니다(단조 정렬(monotonic alignment)의 예는 Chan et al.의 아래 이미지 참조). Attention 모델에는 이러한 귀납적 편향(inductive bias)이 부족하다는 사실로 인해 음성 인식 훈련이 더 어려워지는 것 같습니다; 훈련을 안정화하기 위해 보조 손실 항(auxiliary loss terms)을 추가하는 것이 일반적입니다.

이는 Attention 모델보다 일부 문제에 더 적합한 연결주의 시간 분류(CTC) 모델로 이어집니다.

CTC Models

CTC 모델은 단조로운(monotonic) 입력-출력 정렬이 있다고 가정합니다. 결과적으로 모델이 훨씬 단순해졌습니다.

정말 간단합니다! CTC 모델을 구현하려면 단일 신경망만 필요하며 값비싼 global Attention 메커니즘은 필요하지 않습니다.

그러나 CTC 모델에는 몇 가지 문제가 있습니다.

CTC 모델의 문제

• Problem 1
  • 출력 시퀀스 길이 U는 입력 시퀀스 길이 T보다 작아야 합니다.
  • 이는 T가 U보다 훨씬 큰 음성 인식에서는 문제가 되지 않는 것처럼 보일 수 있습니다.
  • 그러나 이는 모델을 훨씬 더 빠르게 만들 수 있는 풀링을 수행하는 모델 아키텍처를 사용하지 못하게 합니다.
• Problem 2
  • 출력은 서로 독립적인 것으로 가정됩니다.
  • 그 결과 CTC 모델은 "I ate food" 대신 "I eight food"와 같이 명백히 잘못된 출력을 생성하는 경우가 많습니다.
  • CTC로 좋은 결과를 얻으려면 일반적으로 보조 언어 모델(secondary language model)을 통합하는 검색 알고리즘이 필요합니다.

Transducer Models

Transducer는 Attention 모델에 비해 일부 장점을 유지하면서 CTC와 관련된 두 가지 문제를 모두 우아하게 해결합니다.

Transducer는,

• 각 입력에 대해 여러 출력을 허용하여 Problem 1을 해결합니다.

  • ❓ 이걸로 생기는 trade-off 단점은?

• 예측 네트워크와 Joiner5 네트워크를 추가하여 Problem 2를 해결합니다.

  • ❓ 모델 내부에 LM 기능을 하는 Predictor가 있는거랑, CTC 이후에 추가적으로 LM을 쓰는게 크게 다른건가?

  • 후자는 LM을 독립적으로 학습해야 하는거 가장 큰 차이점인가?

  • 밑에서는 Predictor의 LM도 따로 사전 학습 한다는데?

Predictor는 autoregressive 합니다. Predictor는 표준 언어 모델처럼, 이전 출력을 입력으로 사용하고 다음 출력을 예측하는 데 사용할 수 있는 feature을 생성합니다.

Joiner는 인코더 벡터 $f_t$와 예측 벡터 $g_u$를 결합하고 "null" 출력 ∅을 포함하는 모든 레이블에 대해 소프트맥스 $h_{t,u}$를 출력하는 간단한 피드포워드 네트워크입니다.

입력 시퀀스 x가 주어지면 간단한 탐욕 검색 알고리즘을 사용하여 출력 시퀀스 y를 생성할 수 있습니다.

1. t=1, y=0, y=empty list 로 세팅하고 시작

2. x를 이용하여 $f_t$ 계산, y를 이용하여 $g_u$계산

3. $f_t, g_u$ 를 이용하여 $h_{t, u}$ 계산

4. $h_{t, u}$의 argmax가 labe l이면, u += 1, 라벨을 출력(이를 y에 추가하고 Predictor에 다시 공급)

   $h_{t,u}$의 argmax가 ∅ 이면, t += 1, (즉, 다음 입력 시간 단계로 이동하고 아무것도 출력하지 않습니다.)

5. t=T+1 이면, 끝. 아니면, 2부터 다시 수행

여기서 주목해야 할 트랜스듀서에 대한 몇 가지 멋진 점

• 인코더가 인과적인(causal) 경우(즉, 양방향 RNN과 같은 것을 사용하지 않는 경우) 검색(encoder, predictor, joiner의 일련의 과정을 의미하는 듯)은 온라인/스트리밍 방식으로 실행될 수 있으며 각 $x_t$가 도착하자마자 처리됩니다.
• Predictor는 x와 y를 모두 보는 Attention 모델의 디코더와 달리 y에만 액세스할 수 있고 x에는 액세스할 수 없습니다. 이는 쌍(음성, 텍스트) 데이터보다 훨씬 더 많은 텍스트 전용 데이터에 대해 Predictor를 쉽게 사전 훈련할 수 있음을 의미합니다.

Alignment

$(x,y)$쌍이 주어지면 변환기는 x와 y 사이에 가능한 단조 정렬(monotonic alignments) 집합을 정의합니다. 예를 들어, 길이 T=4의 입력 시퀀스와 길이 U=3의 출력 시퀀스("CAT")를 생각해 보세요. 다음과 같이 그래프를 사용하여 정렬 집합을 설명할 수 있습니다.

정렬 $z= \varnothing,C,A,\varnothing,T,\varnothing,\varnothing$ 에 대한 그래프는 다음과 같습니다.

또 다른 정렬 $z=C, \varnothing, A,\varnothing,T,\varnothing,\varnothing$에 대한 그래프는 다음과 같습니다.

경로를 따라 각 edge 확률의 값을 곱하여 이러한 정렬 중 하나의 확률을 계산할 수 있습니다. 여기서 간선의 값은 $h_{t,u}$의 해당 항목입니다.

$\mathbf{z} = \varnothing, C, A, \varnothing, T, \varnothing, \varnothing$

$p(\mathbf{z} | \mathbf{x}) = h_{1,0}[\varnothing] \cdot h_{2,0}[C] \cdot h_{2,1}[A] \cdot h_{2,2}[\varnothing] \cdot h_{3,2}[T] \cdot h_{3,3}[\varnothing] \cdot h_{4,3}[\varnothing]$

Training

모델을 어떻게 훈련하나요? 실제 정렬 z를 안다면 , 일반 Classifier처럼 h와 z 사이의 교차 엔트로피를 최소화할 수 있습니다. 그러나 우리는 일반적으로 실제 정렬을 알지 못합니다(일부 작업의 경우 “실제” 정렬이 존재하지 않을 수도 있음).

대신, Transducer는 $p(y|x)$를 $x$와 $y$ 사이의 모든 가능한 정렬 확률의 합으로 정의합니다. 우리는 손실함수 $-\log p(y|x)$를 최소화함으로써 모델을 학습합니다.

일반적으로 손실 함수를 모두 직접 추가하여 계산하기에는 가능한 정렬이 너무 많습니다. 합계를 효율적으로 계산하기 위해 "전향 변수(forward variable)" $\alpha_{t,u}$($1 \le t \le T,\ 0 \le u \le U$)를 계산합니다.

$$ \alpha_{t,u} = \alpha_{t-1, u} \times h_{t-1, u} [\varnothing] + \alpha_{t, u-1} \times h_{t, u-1}[y_{u-1}] $$

• $\alpha_{t,u}$ 이전 t, 이전 u에 대해 모두 고려하여, t번째 시점에 u번째 음소가 등장할 확률

• ❓근데 이러면 y축이 CAT으로 고정되는게 맞는데

• ❓학습과정에선 정답레이블이 주어져 있으니까 y축이 고정되는게 맞나?

• ❓그럼 $h_{2,2}[A]$, $h_{2,2}[T]$ 이렇게 공존할 수 없는건가? u번째 음소에 나타날 레이블은 고정되어 있는 건가?

• ❓그럼 $h_{2, 2}[A] + h_{2,2}[\varnothing] = 1$ 이 맞나?

정렬 그래프의 가장자리를 따라 값을 전달하는 것으로 이 계산을 시각화할 수 있습니다.

정렬 그래프의 모든 노드에 대해 $\alpha_{t,u}$를 계산한 후 그래프의 마지막 노드에서 순방향 변수를 사용하여 $p(y|x)$를 얻을 수 있습니다.

$$ p(y|x) = \alpha_{T,U} \cdot h_{T,U}[\varnothing] $$

일반적인 이유로 로그 도메인에서 모든 작업을 수행해야 합니다. 로그 도메인에서 계산은 다음과 같습니다.

$$ \log \alpha_{t,u} = \text{logsumexp}([\log \alpha_{t-1,u} + \log h_{t-1,u}[\varnothing], \ \log \alpha_{t,u-1} + \log h_{t,u-1}[y_{u-1}] ]) $$

• ❓ logsumexp?
  • https://gregorygundersen.com/blog/2020/02/09/log-sum-exp/
  • 읽어보면 도움이 될 것 같다

어쨋든, 위의 식을 적용하면 다음을 도출할 수 있습니다.

$$ \log p(\mathbf{y}|\mathbf{x}) = \log \alpha_{T,U} + \log h_{T,U}[\varnothing] $$

마지막으로 손실의 기울기 $-\log p(y|x)$를 계산하기 위한 두 번째 알고리즘이 있습니다. 이 알고리즘은 $\alpha_{t,u}$와 동일한 계산을 사용하지만 역방향으로 마지막 노드부터 시작하는 후방 변수 $\beta_{t,u}$를 계산합니다.

노트북에서는 순방향 계산만 작성하고 자동 미분을 사용하여 기울기를 계산하는 손실 함수의 간단한 PyTorch 구현을 제공합니다. 이는 하위 수준 구현보다 훨씬 느리지만 프로그래밍하고 읽기가 더 쉽습니다.

Memory usage

일반적으로 Transducer 모델은 좋은 아이디어처럼 보입니다. 그러나 문제는 다음과 같습니다(최근까지 Transducer가 따라잡지 못한 무언의 이유일 수도 있음).

T=1000, U=100, L=1000 라벨, 배치 크기 B=32가 있다고 가정합니다. 그런 다음 모든 (t,u)에 대해 $h_{t,u}$를 저장하여 정방향 알고리즘을 실행하려면 B×T×U× 크기의 텐서가 필요합니다. $B\times T \times U \times L = 3200000000$ 또는 단정밀도 부동소수점을 사용하는 경우 12.8GB입니다. 그리고 그것은 단지 출력 텐서일 뿐입니다. $B \times T \times U \times d_{joiner}$크기의 조이너 네트워크의 숨겨진 단위 활성화도 있습니다.

따라서 당신이 충분한 RAM을 갖춘 TPU를 소유한 특정 기술 회사가 아닌 이상(누가 가장 많은 Transducer 논문을 출판했는지 맞춰보세요!) 훈련 중에 메모리 소비를 줄이는 방법을 찾아야 할 수도 있습니다. 예를 들어 인코더에서 풀링하여 T를 줄이거나 작은 배치 크기 B를 사용하는 것입니다.

아이러니하게도 이는 훈련 중에만 발생하는 문제입니다. 추론하는 동안에는 y에 대한 현재 활성화 및 가설을 저장하는 데 약간의 메모리만 필요합니다.

Search

앞서 우리는 greedy 검색을 사용하여 항상 $h_{t,u}$의 최상위 출력을 선택하여 y를 예측할 수 있다는 것을 보았습니다. 대신 y에 대한 여러 가설을 유지하고 각 입력 시간 단계에서 이를 업데이트하는 빔 검색을 사용하면 더 나은 결과를 얻을 수 있습니다.

Transducer 빔 검색 알고리즘은 원본 논문에서 찾을 수 있습니다. 비록 단순한 Attention 모델 빔 검색보다 다소 거칠고 아직 직접 구현하지 않았음을 고백합니다. (Check out the soon-to-be-released SpeechBrain toolkit for my colleagues’ implementation.)

Code

마지막으로 Transducer용 Colab 노트북은 여기(here)에서 찾을 수 있습니다. 노트북은 장난감 시퀀스 변환 문제(문장에서 누락된 모음 채우기: "hll wrld" –> "hello world")를 위해 PyTorch에서 Transducer 모델을 구현합니다. 여기에는 손실 함수, 탐욕 검색 및 단일 정렬 확률 계산 기능이 포함됩니다.

간단하게 말해서 스테이블 디퓨전은 text-to-image 모델, 즉, 텍스트(문장/단어)로부터 이미지를 뽑아내는 모델입니다. 텍스트 프롬프트를 입력하면, 그 텍스트에 맞는 이미지를 반환하는 것이죠.

Diffusion 모델

Stable Diffusion은 디퓨전 모델이라는 딥러닝 모델의 일종입니다. 디퓨전 모델은 생성형 모델입니다. 즉, 학습받은 것과 비슷한 새로운 데이터를 생성하도록 설계된 모델입니다. 스테이블 디퓨전의 경우 데이터는 이미지를 의미한다. ChatGPT는 문장을 생성하는 것이다. 마찬가지로 생성형 모델은 음악이든 글이든 무엇이든 생성할 수 있다.

그러면 왜 디퓨전 모델이라고 할까? 물리학에서의 확산과 수학적으로 매우 비슷하기 때문이다. 더 자세히 알아보자.

일단 개와 고양이로 구성된 두가지 종류의 이미지들만 사용해 디퓨전 모델을 학습시킨다고 가정해보자. 아래 그림에서 가운데 부분에 있는 두 개의 옆으로 눕혀진 종모양이 각각 고양이 이미지와 강아지 이미지를 대표한다.

순방향 확산(Forward Diffusion)

Stable Diffusion - 순방향 확산은 이미지를 잡음으로 바꾸는 과정

순방향 확산 프로세스에서는 학습용 이미지에 점차적으로 잡음을 추가하여, 점점 아무런 특징이 없는 잡음 이미지로 바꿔간다. 아무리 예쁜 이미지도 순방향 프로세스를 거치면 위 그림 맨 오른쪽에 있는 잡음 이미지가 되어서, 결국 강아지 그림인지 고양이 그림인지도 알 수 없게 된다. 이 사실이 매우 중요하다.

이것은 물컵에 잉크를 한방울 떨어뜨리는 것과 비슷하다. 잉크가 물속에서 “확산”하게 되고, 몇 분이 지나면 물속에 완전히 퍼져버려서 처음에 잉크가 어디에 떨어졌는지 전혀 알 수 없게 되어버린다.

아래는 이미지가 순방향 확산을 거치는 과정이다. 고양이 이미지가 결국 무작위 잡음(random noise)로 바뀌게 굄을 볼 수 있다.

고양이 이미지의 순방향 확산 프로세스

역방향 확산(Reverse Diffusion)

이 확산 과정을 거꾸로 돌리면 어떻게 될까? 물론 물속의 잉크를 다시 잉크로 뽑아내는 방법은 없지만, 컴퓨터 세계에서는 가능하다. 비디오를 거꾸로 돌리는 것과 같이.

Stable Diffusion - 역방향 확산은 잡음에서 이미지를 복구하는 과정

역방향 확산은 잡음, 즉 의미없는 이미지에서 출발해서 강아지 혹은 고양이 이미지를 복구하는 것이다. 잉크물에서 잉크가 떨어진 위치를 알아낼 수 있는 것과 같다.

기술적으로 보았을 때, 확산 프로세스는 (1) 드리프트(drift) 혹은 방향성 이동 (2) 무작위(random) 이동 등 두 부분으로 구성된다. 역방향 디퓨전은 아무것도 없는 곳에서 고양이 또는 강아지 이미지를 향하여 드리프트(떠도는 것)하게 된다. 이렇게 해서 결과가 고양이 또는 강아지가 되게 된다.

학습 방법

역방향 확산은 정말 영리하고 우아하다. 하지만 어떻게 이게 가능할까? 확산을 뒤집기 위해서는 이미지에 얼마나 많은 잡음이 들어있는지 알아야 한다. 그 해답은 신경망 모델에게 추가된 잡음을 예측하도록 시키는 것이다. 이것을 스테이블 디퓨전에서는 잡음 예측기(noise predictor)라고 하며, U-Net 모델을 사용한다. 훈련은 다음과 같이 진행된다.

1. 학습용 이미지(예: 고양이 이미지)를 선택한다.
2. 무작위 잡음 이미지를 생성한다.
3. 학습용 이미지에 정해진 단계만큼 무작위 잡음 이미지를 추가하여 손상시킨다.
4. 잡음 예측기에게 잡음 추가량을 학습시킨다. 가중치를 조정하고 정답을 보여주는 방식으로 작업이 수행된다.

각 단계마다 잡음이 추가된다. 잡음 예측기는 총 잡음을 추정한다.

이렇게 학습이 이루어지면, 이미지에 추가된 잡음을 예측할 수 있는 잡음 예측기(Noise Predictor)를 확보하게 된다. 이 잡음 예측기를 역방향 확산 프로세스에서 사용하여 이미지를 복원하게 된다.

역방향 확산(Reverse Diffusion)

지금까지 잡음 예측기를 사용했다. 이걸 어떻게 사용할까?

먼저 완전한 잡음 이미지를 생성하고, 잡음 예측기에 이 이미지에 잡음이 얼마나 포함되었는지 질문을 던진다. 그 다음 잡음 예측기가 반환한 예측 잡음을 원래의 잡음 이미지에서 제거한다(substract).

역방향 확산은 이미지에서 예측된 잡음을 순차적으로 제거한다.

이 설명에서는 생성되는 이미지에 아무런 제어도 하고 있지 않다. 즉, 조건 없이 이미지가 생성되는데, 컨디셔닝(conditinoing, 조건부여)에 대해서는 아래에서 다룬다. 당분간은 조건부여가 없는(unconditioned) 이미지를 생성한다.

스테이블 디퓨전 모델

이제까지 설명은 개념적인 것에 불과하다. 이대로는 거의 작동이 안되거나, 매우 느리다는 뜻이다. 위의 설명은 이미지 공간에서 직접 설명했는데(이미지 공간이라고 이야기했지만, 그냥 이미지 상태라는 뜻으로 생각하면 된다.), 이렇게 되면 계산이 매우매우 느리게 된다. 이 경우, 현존하는 최고의 GPU를 사용한다고 해도, 하나의 GPU로는 계산이 불가능하다.

이미지 공간은 엄청나게 크기가 크다. 3개의 색채널이 있는 512x512 크기의 이미지라면, 786,462 차원을 차지한다. 이미지 하나마다 이 값을 지정해야 하는 것이다.

구글의 Imagen 또는 OpenAI의 DALL-E는 이러한 이미지 공간에서 작동된다. 모델을 빠르게 돌릴 수 있는 몇가지 기법을 동원하고는 있지만, 워낙 크기가 커서 한계가 있다.

잠재 확산 모델(Latent Diffusion 모델)

스테이블 디퓨전은 이러한 문제를 잠재 확산 모델(latent diffusion model)을 사용하여 해결했습니다. 이상과 같이 고차원의 이미지 공간에서 작동시키는 것이 아니라, 먼저 잠재 공간(latent space)으로 이미지를 압축한 뒤 연산을 시행하는 것이다. 잠재 공간은 이미지 공간에 비해 48배나 작기 때문에 훨씬 연산이 빨라진다.

가변 자동인코더(VAE, Variational AutoEncoder)

이미지를 잠재 공간으로 압축하는 데는 가변 자동 인코더(Variational AutoEncoder)라는 기법을 사용한다. (스테이블 디퓨전 설정할 때의 VAE이다. VAE 파일이 이 역할을 하는 것이다.)

가변 자동 인코더 신경망은 (1) 인코더, (2) 디코더 등 두 부분으로 나누어진다. 인코더는 이미지를 잠재 공간에서 낮은 차원의 표현으로 압축하며, 디코더는 잠재 공간(latent space)으로부터 이미지를 복원하는 역할을 담당한다.

스테이블 디퓨전의 잠재 공간의 크기는 4x64x64(16,384)이다. 이미지 픽셀 공간에 비해 1/48 뿐이 안된다 위에서 이야기한 순방향 디퓨전 및 역방향 디퓨전은 모두 이 잠재 공간상에서 이루어지게 된다.

즉, 다시 말해서, 위에서는 잡음 이미지를 생성한다고 했지만, 실제로는 잠재 공간산에의 무작위 텐서(random tensor, latent noise)를 생성한다. 또한 잡음을 사용해 이미지를 손상시키는 게 아니라, 잠재 공간상의 이미지 표현을 잠재 잡음(latent noise)을 사용해 손상시킨다. 이렇게 하는 이유는 잠재 공간이 작기 때문에 연산이 훨씬 빠르기 때문이다.

이미지 해상도

이미지 해상도는 잠재 이미지 텐서의 크기에 반영된다. 512x512이미지에 대해서만 잠재 이미지의 크기가 4x64x64가 된다. 768x512 이미지의 경우 4x96x64가 된다. 이 때문에 크기가 큰 이미지를 생성하려면 시간이 오래 걸리고 VRAM을 더 많이 차지하는 것이다.

스테이블 디퓨전 v1은 512x512 이미지에 대해서 미세 조정되었다. 따라서 이보다 큰 이미지를 생성하려면 물체가 겹쳐지는 현상이 발생할 수 있다.

이미지 확대(upscaling)

**SD v1 모델(Stable Diffusion v1 모델)**을 사용해 큰 이미지를 생성할 경우, 적어도 한쪽은 512에 맞추고 나중에 AI 확대도구(Upscaler)를 사용하는 것이 좋다.

또는 SDXL 모델을 사용하면 좋다. SDXL은 1024x1024 크기로 학습되었기 때문이다. 또한 이미지 품질도 대부분 뛰어나다.

잠재 공간이 가능한 이유

지금까지의 설명을 보면, VAE를 사용해 이미지를 훨씬 작은 잠재 공간으로 압축한다고 했는데, 어떻게 정보에 손상이 없이 가능한지 궁금할 수 있다. 이는 대부분의 이미지가 무작위가 아니기 때문이다. 즉, 자연적 이미지는 규칙성이 높다는 뜻이다. 얼굴을 예를 들면 눈, 코, 입 사이에는 특정한 공간적 관계가 존재한다. 나무를 그리면 녹색 픽셀 바로 옆에는 녹색 픽셀이 나올 확률이 매우 높다. 이런 것이 공간적 관계이다.

다른 말로 하면, 자연적 이미지는 이러한 정보의 손상없이 잠재 공간으로 압축하는 것이 가능하다는 뜻이다. 이를 머신 러닝에서는 다중체 가설(manifold hypothesis)라고 한다.

잠재 공간에서의 역방향 디퓨전

위에서 이미지 공간에서의 역방향 디퓨전에 대해서 설명했는데, 잠재공간(latent space)에서의 역방향 디퓨전은 다음과 같이 작동한다.

1. 무작위 잠재 공간 행렬을 생성한다.
2. 잡음 예측기(noise predictor)가 잠재 행렬의 잡음을 예측한다.
3. 예측된 잡음을 잠재 행렬에서 제거한다.
4. 지정한 생플링 단계(sampling step)에 이를 때까지 2,3 단계를 반복한다.
5. VAE 디코더가 잠재 행렬로부터 최종 이미지로 변환한다.

VAE 파일

Stable Diffusion v1에서 VAE 파일의 목적은 눈과 얼굴을 향상시키는데 사용되었다. VAE파일이 방금 언급한 자동인코더(AutoEncoder)의 디코더이다. 디코더를 세부 조정하면 훨씬 나은 이미지를 생성할 수 있다.

위에서 가변 자동 인코더로 이미지를 압축하면 정보 손실이 없다고 언급했는데, 사실 잘못된 표현이다. 전체적인 형태는 문제가 없지만, 세세한 부분은 정보가 손실되어 복구하지 못하기 때문이다. 대신 디코더가 미세한 세부 사항을 그려내는 역할을 하게 된다.

조건부여(Conditioning)

이제까지 설명한 것에는 심각한 결함이 있다. 어디에도 텍스트 프롬프트가 들어갈 곳이 없다는 것이다. 즉, 이상의 모델에서는 이미지를 VAE 인코더를 통해 잠재 공간으로 압축하고, 잠재공간에서 이미지를 학습하여 모델을 생성하는 학습과정과, 모델에서 잡음 예측기를 사용해 잡음을 제거하여 잠재공간상의 이미지를 생성하고 이를 VAE 디코더를 통해 이미지를 생성하는 과정으로 나눌 수 있는데, 여기 어디에도 텍스트 프롬프트는 개입되지 않았다는 점이다.

즉, 이 상태로는 잠재공간의 학습 데이터에서 이미지를 뽑으면 그냥 알아서 뽑을 뿐, 어떤 이미지를 뽑으라고 지시할 수 없어서 무작위로 이미지가 튀어 나오게 되는 것이다. 위의 예라면 강아지가 나올 수도 있고 고양이가 나올 수도 있다.

이를 위해 조건부여(conditioning)가 필요하다. 조건부여의 목적은 잡음 제거기를 제어하여 이미지에서 예측된 잡음 제거한 결과가 우리가 원하는 것이 되도록 몰아가는 것이다.

텍스트 조건부여(text-to-image)

아래는 텍스트 프롬프트가 처리되어 잡음 예측기로 들어가는 방법을 대략적으로 나타낸 그림이다. 먼저 프롬프트에 포함된 단어들을 토큰생성기가 토큰이라고 하는 숫자로 변환한다. 각각의 토큰은 임베딩이라고 하는 769개 값의 벡터로 변환된다.(이게 AUTOMATIC1111에서 사용하는 임베딩과 동일하다.) 다음으로 텍스트 변환기(text transformer)가 임베딩을 처리하여 노이즈 예측기(Noise Predictor)가 사용할 수 있는 데이터를 생성하게 된다.

텍스트 프롬프트가 처리되어 잡음 제거기에 제공되는 과정

이제 이 그림에 포함된 각각의 부분에 대해 자세히 살펴보자. 위에 있는 개요만으로 충분하다면 다음 절로 넘어가도 된다.

토큰 생성기(Tokenizer)

먼저 텍스트 프롬프트는 CLIP tokenizer를 통해 토큰으로 바뀌게 된다. CLIP(Contrastive Language-Image Pre-Training)은 OpenAI에서 개발한 딥러닝 모델로서, 이미지에 대한 텍스트 설명을 설명하기 위해 사용된다. Stable Diffusion v1은 CLIP의 토큰 생성기를 사용한다.

토큰화는 컴퓨터가 단어를 이해하는 방법이다. 사람들은 단어를 읽을 수 있지만, 컴퓨터는 숫자를 읽을 뿐이고, 따라서 사람이 입력한 단어들은 토큰화를 통해 숫자로 변환되어야 컴퓨터가 읽을 수 있다.

토큰 생성기는 자신이 학습할 때 보았던 단어들만 토큰으로 변환할 수 있다. 예를 들어 CLIP 모델에 “dream”과 “beach”는 있는데 “dreambeach”는 없다고 가정하면, 토큰 생성기는 dreambeach를 분해해서 “dream”과 “beach”라는 두 개의 토큰으로 변환하게 된다. 이처럼 하나의 단어가 반드시 하나의 토큰에 대응되는 것이 아니다.

또 한 가지 주의할 점은 공백(space)도 토큰의 일부라는 점이다. 위의 예시에서 “dream beach”는 “dream”과 “ beach” 라는 두 개의 토큰으로 변환된다. 이 토큰은 “dreambeach”에서 생성된 “dream”, “beach”와 다르게 된다.

Stable Diffusion 모델은 프롬프트에서 75개의 토큰만 사용하도록 제한하고 있다. 단 75개의 토큰은 75개의 단어가 아니라는 점을 다시한 번 얘기한다.

임베딩(Embedding)

스테이블 디퓨전 v1은 OpenAI의 VoT-L/14 CLIP 모델을 사용한다. 임베딩은 768개의 값을 갖는 벡터이다. 각각의 토큰은 각각의 고유한 임베딩 벡터를 갖고 있다. 임베딩은 CLIP 모델에서 생성되어 고정되어 있다. 다시 말해서 학습과정에서 임베딩이 결정되는 것이다.

왜 임베딩이 필요한 걸까? 임베딩은 일부 단어들이 서로 연괸되어 있기 때문이다. 예를 들어 man, gentleman, guy 등의 단어는 거의 동일하다. 실세계에서 바꿔거며 사용되기 때문이다. 다른 예로 Monet, Manet, Degas는 모두 인상주의 화가이지만, 그림 스타일은 약간씩 다르다. 이들 이른은 밀접하지만 동일하지는 않는 임베딩이다. 결과적으로 임베딩에는 하나의 토큰에 대응되는 768개의 다른 토큰과의 연관성을 담고 있다고 생각하면 될 것 같다.

임베딩을 적절히 사용하면 마술을 부릴 수 있다. 과학자들은 적절한 임베딩을 찾아내면, 임의의 물체와 스타일을 발동시킬 수 있다는 것을 발견했다. 이것이 **텍스트 인버전(Textual Inversion)**이라고 말하는 세밀 조정 기법이다.

임베딩을 잡음 생성기에 넣기

그 다음으로 임베딩은 텍스트 트랜스포머(text transformer)에서 처리된 후 잡음 예측기에 공급된다. 트랜스포머는 조건부여를 위한 범용 어댑터와 같다. 이 예에서 텍스트 트랜스포머의 입력은 텍스트 임베딩 벡터이지만, 클래스 라벨, 이미지 혹은 깊이 맵(depth map)도 트랜스포머의 입력이 될 수 있다. 트랜스포머는 데이터를 추가로 처리할 뿐만 아니라, 다양한 조건부여 방식을 수용할 수 있는 메커니즘도 제공한다.

교차 인지(corss-attention)

U-Net 전체에서 노이즈 예측기는 텍스트 트랜스포머의 출력을 여러 번 사용한다. U-Net은 교차 인지(cross-attention) 메커니즘을 통해 이를 사용한다. 여기가 바로 프롬프트가 이미지와 만나는 지점이다.

“파란 눈을 가진 남자”라는 프롬프트를 예로 들어보자. 스테이블 디퓨전은 “파란색”과 “눈”이라는 두 단어를 함께 짝을 지어(프롬프트 내의 셀프 인지) 파란 눈을 가진 남자를 생성한다. (하지만 파란 셔츠를 입은 남자는 생성하지 않는다.) 그런 다음 이정보를 사용하여 역방향 확산과정에서 파란 눈이 포함된 이미지로 유도된다.(프롬프트와 이미지 간 교차 인지)

참고 : Stable Diffusion 모델에서 미세 조정하는 기술인 하이퍼 네트워크는 교차 인지 네트워크를 가로채어 여러 가지 스타일을 삽입한다. LoRA 모델은 교차 인지 모듈의 가중치를 수정하여 특정한 스타일을 변경한다. 교차 인지 모듈을 수정하는 것만으로도 Stable Diffusion 모델을 미세 조정할 수 있다는 사실로부터, 이 모듈이 얼마나 중요한지 알 수 있다.

기타 조건부여

Stable Diffusion 모델에서 텍스트 프롬프트 이외의 조건부여(conditioning) 기법도 존재한다. depth-to-image 모델의 조건부여는 텍스트 프롬프트와 깊이(depth)이미지를 함께 사용하는 방법이 사용된다. ControlNet의 경우, 외곽선이나 사람의 자세 등으로 잡음 제거기에 조건을 부여함으로써, 이미지 생성시 원하는 구도를 제어할 수 있다.

Stable Diffusion step-by-step

지금까지 스테이블 디퓨전 모델의 내부적인 작동 방식에 대해 알아봤다. 지금부터는 스테이블 디퓨전을 작동할 때 어떠한 일이 일어나는지 몇가지 예를 들어 알아 보자

Text-to-Image

txt2img는 텍스트 프롬프트를 입력해 이미지를 얻는 기능이다.

[1단계]

Stable Diffusion 은 잠재 공간(latent space)에 무작위 텐서(random tensor)를 생성한다. 이때, seed 번호를 사용해 무작위 숫자 생성기를 통해 무작위 텐서를 제어할 수 있다. seed를 특정한 값으로 입력하면 항상 동일한 무작위 텐서가 만들어진다. 무작위 텐서가 바로 잠재 공간에 있는 이미지이다. 다만 이때에는 모든 이미지가 잡음일 뿐이다.

seed 번호로 무작위 텐서를 생성함

[2단계]

잡음 예측기(U-Net)가 잠재 잡음 이미지와 텍스트 프롬프트를 입력받아 잡음을 예측한다. 이 과정도 잠재 공간(4x64x64 텐서)에서 시행된다.

잠재 공간에서 노이즈 예측

[3단계]

잠재 이미지에서 잠재 잡음을 제거한다. 그 결과는 새로운 잠재 이미지다.

잠재 잡음 제거

2단계와 3단계는 정해진 샘플링 단계(예: 20회) 동안 반복된다.

[4단계]

최종적으로 VAE 디코더가 잠재 이미지를 픽셀 공간으로 보내어 이미지를 생성한다. 이것이 스테이블 디퓨전을 돌리면 생성되는 이미지다.

VAE 디코딩과 이미지 생성

아래는 각 샘플링 단계에서 이미지가 변화하는 과정이다.

각 샘플링 단계의 이미지

잡음 스케줄(Noise Schedule)

위에서 보는 것처럼 Stable Diffusion의 이미지는 완전 잡음으로부터 점차 깨끗해진다. 초기 단계에서는 잡음 예측기(noise predictor)가 제대로 작동하지 않는 것처럼 보이는가? 사실 이것은 부분적으로만 사실이다. 진짜 이유는 각 샘플링 단계에서 예상되는 잡음에 도달하려고 노력하기 때문이다. 이를 잡음 스케줄(noise schedule)이라고 한다. 아래는 그 예시이다.

샘플링 단계가 15일 경우의 잡음 스케줄

잡음 스케줄을 우리가 정의한다. 각 단계에서 동일한 양만큼 제거하도록 할 수 있고, 위 그림처럼 많이 제거하도록 할 수도 있다. 샘플링 알고리즘은 다음 단계에서 예상되는 잡음에 도달한 만큼만 잡음을 제거한다. 이 때문에 우리는 단계별 이미지를 볼 수 있다.

Image-to-Image

Image-to-Image는 어떤 이미지를 스테이블 디퓨전을 사용해 다른 이미지로 변환하는 기법이다. Image-to-Image는 SDEdit 방법에서 처음으로 제안된 방법이다. SDEdit은 어떠한 디퓨전 모델에도 적용할 수 있다. 이 때문에 우리는 Stable Diffusion에서 Image-to-Image 기능을 볼 수 있다.

Image-to-Image 에서는 이미지와 텍스트 프롬프트가 입력으로 사용된다. 생성된 이미지는 입력 이미지와 텍스트 프롬프트로 조건부여(conditioning)된다. 예를 들어 아래 첫번째 그림의 아마추어 그림과 프롬프트 “photo of perfect green apple with stem, water droplets, dramatic lighting”를 입력으로 사용하면, 스테이블 디퓨전은 전문가적인 그림으로 바꾸어준다.

[1단계]

입력 이미지가 잠재 공간으로 인코딩된다.

입력 이미지 인코딩

[2단계]

잠재 이미지에 잡음이 추가된다. 이때 잡음 제거 강도(Denoising strength) 값에 따라 추가되는 잡음의 양이 결정된다. 0으로 설정할 경우 잡음이 추가되지 않으며, 1일 경우, 잡음이 최대치로 추가되어, 잠재 이미지가 완전히 무작위 텐서(random tensor)가 된다.

입력 이미지에 잡음 추가

[3단계]

잡음 예측기(Noise Predictor) U-Net이 잠재 잡음 이미지와 텍스트 프롬프트를 입력으로 받아, 잠재 공간(4x64x64 텐서)에서 잡음을 예측한다.

잡음 예측기(Noise Predictor)가 잡음 예측

[4단계]

잠재 이미지에서 잠재 잡음을 제거한다. 그 결과 새로운 잠재 이미지가 생성된다.

새로운 잠재 이미지 생성

[5단계]

마지막으로 VAE(가변 자동 인코더)의 디코더가 잠재 이미지를 픽셀 공간으로 내보낸다. 이렇게 나온 결과가 Image-to-Image의 결과가 된다.

잠재 이미지 디코딩

요약하면, Image-to-Image가 Text-to-Image와 다른 점은, 입력된 이미지에 약간의 잡음을 추가한 초기 잠재 이미지가 입력으로 사용되는 것 뿐이다. 참고로 잡음 제거 강도(denoising strength)를 1로 설정하면, 초기 잠재 이미지가 완전한 무작위 노이즈가 되어버리기 때문에 text-to-image와 동일하게 된다.

인페인트(Inpainting)

인페인트(Inpaing)는 Image-to-Image의 특별한 경우일 뿐이다. 그림 전체가 아니라 인페인트시 적용한 마스크 부분에 대해서만 잡음이 추가된다는 점만 다르다. 추가되는 잡음의 양은 일반 Image-to-Image와 마찬가지로 잡음 제거 강도에 의해 제거된다.

Depth-to-Image

Depth-to-Image는 Image-to-Image를 더욱 진보시킨 것이다. 즉, 깊이 맵(depth map)을 사용하여 추가적인 조건부여(conditioning)를 적용하여 새로운 이미지를 생성한다.

[1단계]

입력 이미지가 잠재 공간으로 인코딩된다.

입력 이미지 인코딩

[2단계]

MiDas(깊이 AI 모델)가 입력된 이미지의 깊이 맵을 추정한다.

깊이 맵(depth map) 추정

[3단계]

잠재 이미지에 잡음을 추가한다. 추가되는 잡음의 양은 잡음 제거 강도(denoising strength)에 의해 결정된다. 잡음 제거 강도가 0이면 잡음이 추가되지 않고, 1이면 잡음이 최대치로 추가되어 잠재 이미지가 무작위 텐서가 된다.

잠재 이미지에 잡음 추가

[4단계]

잡음 예측기가 잠재공간의 잡음을 예측한다. 이때 텍스트 프롬프트와 깊이 맵을 조건부여로 사용한다.

잡음 예측

[5단계]

잠재 이미지에서 잠재 잡음을 제거한다. 그 결과 새로운 잠재 이미지가 생성된다.

잠재 이미지에서 예측된 잡음 제거

[6단계]

VAE(가변 자동 인코더)의 디코더가 잠재 이미지를 디코딩한다. 이렇게 나온 결과가 depth-to-image의 결과가 된다.

잠재 이미지 디코딩

무분류기 안내(CFG, Classifier-Free Guidance)

이미지 생성형 인공지능을 사용하다보면, 분류 자유도 척도를 고민하지 않을 수 없다. CFG가 무엇인지 이해하려면 먼저 분류기 안내(classifier guidance)에 대해 알아볼 필요가 있다.

분류기 안내(classificer guidance)

분류기 안내는 디퓨전 모델에서 이미지 레이블을 통합하는 방법이다. 레이블을 사용하여 확산 프로세스의 방향을 안내할 수 있다. 예를 들어 “cat”이란 레이블은 역방향 확산 프로페스가 고양이 사진을 생성하도록 유도한다.

분류기 안내 척도(classifier guidance scale)이란 디퓨전 프로세스가 얼마나 밀접하게 레이블을 따를 것인지 제어하는 파라미터이다. 아래의 그림은 이 논문에서 나온 예인데, 3개의 그룹의 이미지에 각각 “cat”, “dog”, “human”이라고 레이블이 붙었다고 가정한다. 디퓨전이 아무런 안내/유도를 받지 않는다면, 무작위로 각 그룹의 전체 모집단에서 샘플을 추출하게 된다. 때로는 두개의 레이블에 맞는 이미지 (예: 개를 쓰다듬는 소년)를 추출할 경우도 발생할 수 있다.

분류기 안내 척도를 높은 값으로 설정할 경우, 디퓨전 모델은 극단적으로 모호성이 없는 이미지를 생성합니다. 예를 들어 “cat”을 요청할 경우, 다른 것은 없고 고양이만 있는 이미지가 반환될 수 있다.

분류기 척도. 좌측: 안내 없을 때, 중간: 낮은 값의 안내 척도, 우측: 높은 값의 안내 척도

분류기 안내 척도를 높은 값으로 설정한 경우, 디퓨전 모델은 극단적으로 모호성이 없는 이미지를 생성한다. 예를 들어 “cat”을 요청할 경우, 다른 것은 없고 고양이만 있는 이미지가 반환될 수 있다.

분류기 안내 척도(classifier guidance scale)는 안내(프롬프트)를 얼마나 밀접하게 따를지를 제어한다. 위의 그림에서 CFG를 높게 설정하면 맨 오른쪽에 있는 그림과 같은 상태가 된다. 즉, cat을 요청하면, human이나 dog이 나올 확률은 거의 없게 되는 것이다.

무분류기 안내(Classifier-free guidance)

분류기 안내는 놀라운 성능을 발휘하지만, 이러한 안내를 제공하려면 추가적인 모델이 필요하다. 이로 인해 학습에 약간의 어려움이 존재한다.

무분류기 안내(classifier-free guidance)는 거칠게 말해 “분류기가 없이 분류기 안내”를 달성하는 방법이다. 클래스 레이블과 별도의 모델을 사용하여 안내하는 대신, 이미지 캡션을 사용하고 text-to-image 방식에서 설명한 것과 동일한 조건부여(conditioning) 방식으로 디퓨전 모델을 훈련하는 방법이다.

이들은 분류기 부분을 잡음 예측기인 U-Net의 조건부여(conditioning)로 둠으로써, 이미지 생성에서 소위 “분류기 없는” (즉, 별도의 이미지 분류기가 없는) 안내를 달성했다.

텍스트 프롬프트는 text-to-image에서 이 안내를 제공한다.

CFG 값

이제 조건부여를 통하여 무분류기 디퓨전 프로세스를 확보했는데, 안내를 얼마나 따를지는 어떻게 제어해야 할까? 무분류기 안내(CFG) 척도는 텍스트 프롬프트 조건부여를 디퓨전 프로세스가 얼마나 따를지를 제어하는 값이다. 이 값을 0으로 두면 이미지 생성은 조건부여 없이(즉, 프롬프트가 무시됨) 이루어진다. 높은 값을 부여할 수록 디퓨전은 프롬프트를 따라가게 된다.

스테이블 디퓨전 v1과 v2 비교

모델의 차이

스테이블 디퓨전 블로그에 따르면, 스테이블 디퓨전 v2는 텍스트 임베딩에 OpenClip을 사용한다. (반면, 스테이블 디퓨전 v1은 OpenAI의 CLIPViT-L/14 를 사용한다.) 이유는 아래와 같다.

• OpenClip은 크기가 5배 크다. 텍스트 인코더 모델이 클 수록 이미지의 품질이 올라가게 된다.
• OpenAI의 CLIP 모델이 오픈 소스이기는 하지만, 이 모델은 독점적인 데이터를 사용하여 학습되었다. OpenClip 모델로 바뀌게 됨으로써, 연구자들은 모델을 연구하거나 최적화할 때 더욱 투명하게 진행할 수 있게 되었다. 결과적으로 장기적인 발전에 도움이 될 것이다.

학습 데이터의 차이

스테이블 디퓨전 v1.4 의 학습 데이터는 다음과 같다.

• laion2B-en 데이터셋의 256x256 해상도에서 237k 단계
• laion-high-resolution 데이터셋의 512x512 해상도에서 194k 단계
• laion-aesthetics v2 5+ 의 512x512 에서 225k 단계(텍스트 조건부여에서 10% 감소)

스테이블 디퓨전 v2의 학습 데이터는 다음과 같다.

• 음란물에 대해 필터링된 laion-5B 하위 집합의 해상도 256x256에서 550만 단계. (punsafe=0.1 및 aesthetic score(미적 점수) ≥ 4.5 의 laion-nsfw 분류기를 사용함)
• 동일한 데이터 세트에서 해상도 ≥ 512x512인 이미지에 대해 해상도 512x512로 850만 단계
• 동일한 데이터 세트에서 v-objective을 사용하여 15만 단계
• 768x768 이미지에 대해 140만 단계를 다시 시도

Stable Diffusion v2.1은 v2.0에 대해 다음과 같은 세부조정을 실시했다.

• 동일한 데이터 셋에 대하여 추가로 55k 단계(punsafe=0.1로 설정)
• punsafe=0.98을 설정하여 추가로 155k 단계

즉, 기본적으로 마지막 학습단계에서 NSFW 필터를 사용하지 않았다.

차이 극복 방법

사용자들은 일반적으로 스테이블 디퓨전 v2를 사용할 때 스타일 제어가 힘들고 유명인 생성이 힘들다고 한다. Stability AI 에서 예술가 및 유명인 이름을 명시적으로 필터링하지는 않았지만, v2에서는 그 효과가 훨씬 약해졌다고 한다. 이는 아마도 학습 데이터에 의한 차이 때문으로 보인다. Open AI의 독점 데이터에는 예술 작품과 유명인 사진이 더 많이 포함되어 있을 수 있다. 이러한 사진이 빠져서 발생하는 일로 보인다.

다만 v2 및 v2.1 모델은 그다지 많이 사용되지 않는다. 대부분 미세조정된 v1.5 모델과 SDXL 모델을 더 많이 사용한다.

SDXL 모델

SDXL 모델은 v1 및 v2 모델에 대한 공식적인 업그레이드 모델이다. 이 모델은 오픈소스로 공개되었다.

SDXL은 v1 및 v2에 비해 모델의 크기가 훨씬 크다. AI 세계에서 모델 크기가 크다는 것은 성능이 좋다는 것과 동등하다. v1.5의 경우 파라미터 수는 9.8억개 정도였는데, SDXL 모델의 경우 66억개로 늘어났다.

SDXL 모델은 두개의 모델로 구성되어 있다. 먼저 base 모델을 돌리고나서 refinder 모델을 돌리게 된다. base 모델은 전반적인 구성을 설정하고, refinder 모델은 세밀한 부분을 추가하는 역할을 한다.

물론 base 모델만 돌려도 무방하다.

SDXL base 모델은 이전 버전에 비해 아래와 같은 차이가 있다.

• 텍스트 인코더가 가장 큰 OpenClip 모델 (ViT-G/14)와 OpenAI 독점 모델인 CLIP ViT-L이 결합되어 있다. 이렇게 함으로써 프롬프트를 쉽게 작성할 수 있게 되었고, 강력하면서도 학습 가능한 OpenClip을 유지했다.
• 새로운 이미지 크기 조건부여(conditioning)을 도입하여 256x256 크기의 이미지도 학습시켰다. 이렇게 함으로써 전체 데이터셋 중 39%에 달하는 학습데이터를 버리지 않고 사용하였다.
• U-Net가 v1.5보다 3배 가량 커졌다.
• 기본 이미지 사이즈가 1024x1024가 되었다. 이는 v1.5 모델의 기본 이미지 크기(512x512)에 비해 4배나 커진 것이다.

문제 링크 : https://www.acmicpc.net/problem/1976

문제 설명

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

• 입력 첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다. 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.

• 출력 첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.

예제 입출력

예제 입력 1

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

예제 출력 1

YES

문제 해결 방법

• Union-Find 알고리즘 사용
• 모든 간선의 두 노드에 대해 Union 연산 실행
• 여행하려는 도시들이 전부 같은 집합에 있으면(루트 노드가 같으면) YES 출력
• 그렇지 않으면 NO 출력

CODE

import sys
input = sys.stdin.readline

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, i, j):
    a = find_parent(parent, i)
    b = find_parent(parent, j)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def solution():
    # 입력
    N = int(input())
    M = int(input())

    graph = []
    for _ in range(N):
        graph.append(list(map(int, input().split())))
    cities = set(map(int, input().split()))

    parent = [i for i in range(N)]
    # 도시는 0번도시부터 N-1번 도시까지 있음
    for i in range(N):
        for j in range(i+1, N):
            if graph[i][j] == 1: # i번 도시와 j번 도시가 연결되어 있으면
                union_parent(parent, i, j)

    can_tour = True
    parent_set = set()
    for city in cities:
        parent_set.add(find_parent(parent, city-1))
    if len(parent_set) == 1:
        print("YES")
    else:
        print("NO")

if __name__ == "__main__":
    solution()

시간 복잡도

$$ O(N^2) $$

• Union-Find 알고리즘 시간복잡도는 거의 상수 시간에 수행됨
• 입력된 NxN graph를 돌면서 Union 하는 작업에서 $N^2$ 시간 소요
• 여행 계획 도시들 돌면서 같은 집합의 도시들인지 확인하는 작업에서 $M$시간 소요. 그러나 cities를 집합으로 선언했으므로 $N$시간 소요

문제 링크 : https://www.acmicpc.net/problem/6118

문제 설명

재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 <= N <= 20,000)개이며, 1 부터 샌다고 하자.

재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있다. 모든 헛간은 M(1<= M <= 50,000)개의 양방향 길로 이어져 있고, 그 양 끝을 A_i 와 B_i(1<= A_i <= N; 1 <= B_i <= N; A_i != B_i)로 나타낸다. 또한 어떤 헛간에서 다른 헛간으로는 언제나 도달 가능하다고 생각해도 좋다.

재서기는 발냄새가 지독하기 때문에 최대한 냄새가 안나게 숨을 장소를 찾고자 한다. 냄새는 1번 헛간에서의 거리(여기서 거리라 함은 지나야 하는 길의 최소 개수이다)가 멀어질수록 감소한다고 한다. 재서기의 발냄새를 최대한 숨길 수 있는 헛간을 찾을 수 있게 도와주자!

• 입력
  • 첫 번째 줄에는 N과 M이 공백을 사이에 두고 주어진다.
  • 이후 M줄에 걸쳐서 A_i와 B_i가 공백을 사이에 두고 주어진다.
• 출력
  • 출력은 한줄로 이루어지며, 세 개의 값을 공백으로 구분지어 출력해야한다.
  • 첫 번째는 숨어야 하는 헛간 번호를(만약 거리가 같은 헛간이 여러개면 가장 작은 헛간 번호를 출력한다), 두 번째는 그 헛간까지의 거리를, 세 번째는 그 헛간과 같은 거리를 갖는 헛간의 개수를 출력해야한다.

입출력 예시

예제 입력 1

6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2

예제 출력 1

4 2 3

문제 풀이

이 문제는 특정 노드에서 가장 먼 노드를 찾는 문제이다.

다익스트라 알고리즘을 사용해서 1번 노드와 모든 노드간의 최단거리를 distance 배열에 저장함으로써 문제를 해결할 수 있다.

간선의 가중치는 1로 둔다.

CODE

import heapq
import sys
input = sys.stdin.readline

def solution():
    N, M = map(int, input().split())
    INF = int(1e9)
    graph = [[] for _ in range(N+1)]

    distance = [INF] * (N + 1)
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    queue = []
    heapq.heappush(queue, (0, 1)) # 
    distance[1] = 0
    while queue:
        w, v1 = heapq.heappop(queue)

        for v2 in graph[v1]:
            cost = w + 1
            if cost < distance[v2]:
                distance[v2] = cost
                heapq.heappush(queue, (cost, v2))

    answer_node = 0
    answer_distance = 0
    ansewr_max_num = 0
    for i in range(1, N+1):
        if distance[i] > answer_distance:
            answer_node = i
            answer_distance = distance[i]
            ansewr_max_num = 1
        elif distance[i] == answer_distance:
            ansewr_max_num += 1

    print(answer_node, answer_distance, ansewr_max_num)

if __name__ == "__main__":
    solution()

시간 복잡도

$$ O(MlogN) $$

문제 링크 : https://www.acmicpc.net/problem/4485

문제 설명

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!

젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.

하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다. 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

• 입력
  • 입력은 여러 개의 테스트 케이스로 이루어져 있다.
  • 각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 125) N = 0인 입력이 주어지면 전체 입력이 종료된다.
  • 이어서 N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 공백으로 구분되어 차례대로 주어진다. 도둑루피의 크기가 k면 이 칸을 지나면 k루피를 잃는다는 뜻이다. 여기서 주어지는 모든 정수는 0 이상 9 이하인 한 자리 수다.
• 출력
  • 각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰서 출력한다. 형식은 예제 출력을 참고하시오.

입출력 예제

예제 입력 1

3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
7
9 0 5 1 1 5 3
4 1 2 1 6 5 3
0 7 6 1 6 8 5
1 1 7 8 3 2 3
9 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4
0

예제 출력 1

Problem 1: 20
Problem 2: 19
Problem 3: 36

문제 풀이

이 문제는 특정 점에서 특정 점까지의 최소 거리를 구하는 문제로, $O(ElogV)$ 시간복잡도를 갖는 다익스트라 알고리즘을 이용해 풀 수 있다.

우선순위 큐를 이용해 구현했으며, 특정 칸 K에 대하여 ((0,0)→K 이동하는 최소 가중치, K의 x좌표, K의 y좌표)의 정보가 큐에 들어간다.

그래프의 모든 점들을 노드로 보고, 인접한 칸끼리는 모두 간선으로 연결되어있다고 생각하고 접근했다. 현재까지 해당 좌표까지 도달하기 위한 최소 가중치 값들을 distance 배열에 저장한다.

우선 (0, 0)의 좌표를 큐에 넣어주며 다음의 작업을 반복한다.

1. 우선순위 큐에서 좌표(x, y) 하나를 꺼낸다.
2. 해당 좌표의 상하좌우 좌표(nx, ny)에 대하여
   1. (nx, ny) 좌표가 유효하고
   2. (x, y)를 거쳐 (nx, ny)로 가는 가중치가 기존 distance[nx][ny]보다 작다면
      1. 그 좌표를 우선순위 큐에 집어넣고,
      2. distance를 update 한다.

종료 조건은 큐에서 꺼낸 좌표가 (N-1, N-1)인 경우이다.

이를 코드로 구현하면 아래와 같다.

CODE

import heapq
import sys
input = sys.stdin.readline

def solution():
    T = 0
    INF = 1e9

    while True:
        T += 1
        N = int(input())
        if N == 0:
            break
        graph = []
        for _ in range(N):
            graph.append(list(map(int, input().split())))

        distance = [[INF] * N for _ in range(N)]
        queue = []
        heapq.heappush(queue, (graph[0][0], 0, 0))
        distance[0][0] = graph[0][0]
        while True:
            # queue에서 가장 가중치 적게 드는 노드 V를 뽑고 방문처리
            w, x, y = heapq.heappop(queue)

            # 종료 조건 : (N-1, N-1)에 도달한 경우
            if x == N-1 and y == N-1:
                print(f'Problem {T}: {w}')
                break

            # V의 상하좌우 노드들을 queue에 집어넣는다. (유효한 좌표인지 확인 + )
            for dx, dy in [(1, 0), (-1, 0), (0, -1), (0, 1)]: # 상하좌우
                nx = x + dx
                ny = y + dy

                # 좌표가 그래프 안에 존재해야 한다.
                if nx < 0 or nx >= N or ny < 0 or ny >= N:
                    continue

                # 그냥 넣으면 시간초과 난다. 따라서 비교해야한다.
                cost = w + distance[x][y]
                if cost < distance[nx][ny]:
                    distance[nx][ny] = cost
                    heapq.heappush(queue, (w + graph[nx][ny], nx, ny))

if __name__ == "__main__":
    solution()

시간복잡도

$$ O(N^2 log N) $$

• 다익스트라 알고리즘의 시간복잡도는 $O(ElogV)$이지만 여기서 간선의 수는 $N^2$이고, 노드의 수도 $N^2$이므로 결과적으로 시간복잡도는 $O(N^2logN)$이 된다.

문제 링크 : https://www.acmicpc.net/problem/2458

문제 설명

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

• 입력
  • 첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다.
  • 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 N보다 작거나 같은 서로 다른 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다.
• 출력
  • 자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다.

입출력 예시

예제 입력 1

6 6
1 5
3 4
5 4
4 2
4 6
5 2

예제 입력 2

6 7
1 3
1 5
3 4
5 4
4 2
4 6
5 2

예제 입력 3

6 3
1 2
2 3
4 5

예제 출력 1

1

예제 출력 2

2

예제 출력 3

0

문제 풀이

해당 문제는 노드의 수와 노드들의 우열 관계가 주어지고, 순위가 결정되는 노드의 개수를 출력하는 문제이다.

해당 문제는 플로이드 워셜 알고리즘을 이용해 풀 수 있는데, 이를 위해 NxN 크기의 인접 행렬 그래프를 만든다.

graph[i][j]는 i번째 노드가 j번째 노드보다 우월하다(키가 크다)는 뜻이고 이를 간선의 방향으로 표현한 것이다. a→k, k→b 이면, a→b 가능함을 graph에 표시한다.

이 과정에서 플로이드 워셜 알고리즘을 이용한다. 이렇게 간접적으로 접근이 가능한 간선들도 graph에 표시되면, graph를 통해서 순위가 결정되는지 확인할 수 있다.

V번 노드가 순위가 결정됐는지 확인하기 위해서는, V번 노드를 제외한 다른 모든 노드들과 비교했을 때, 이기거나 진 정보가 확실히 있어야 한다.

즉 V번 노드를 제외한 모든 노드와 간선이 방향에 상관없이 연결이 되어 있다는 뜻이다.

이를 코드로 구현하면 아래와 같다.

CODE

import sys
input = sys.stdin.readline

def solution():
    N, M = map(int, input().split())
    INF = int(1e9)
    graph = [[INF] * (N+1) for _ in range(N+1)]
    for i in range(1, N+1):
        graph[i][i] = 0

    for _ in range(M):
        a, b = map(int, input().split())
        graph[a][b] = 1


    for k in range(1, N+1):
        for a in range(1, N+1):
            for b in range(1, N+1):
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

    answer = 0
    for v in range(1, N+1):
        # v 번 노드가 순위가 정해져있는지 확인
        for i in range(1, N+1):
            if graph[i][v] < INF or graph[v][i] < INF:
                continue
            else:
                break
        else: # 위 for 문을 다 돌았다면
            answer += 1
    print(answer)

if __name__ == "__main__":
    solution()

시간 복잡도

$$ O(N^3) $$

문제 링크 : https://www.acmicpc.net/problem/11404

문제 설명

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

• 입력

  • 첫째 줄에 도시의 개수 n이 주어지고
  • 둘째 줄에는 버스의 개수 m이 주어진다.
  • 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다.
  • 시작 도시와 도착 도시가 같은 경우는 없다. → (a ≠ b)
  • 비용은 100,000보다 작거나 같은 자연수이다. → (1 ≤ c ≤ 100,000)
  • 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. → (a, b, c1), (a, b, c2) 입력이 있을 수 있음

• 출력

  n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

입출력 예시

예제 입력 1

5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4

예제 출력 1

0 2 3 1 4
12 0 15 2 5
8 5 0 1 1
10 7 13 0 3
7 4 10 6 0

문제 풀이

이 문제는 문제 설명에서 플로이드 워셜 알고리즘을 사용하라고 언질을 주고 있다. 첫 번째 힌트로 노드의 최대 개수가 100개라는 점이다. 플로이드 워셜 알고리즘의 시간복잡도는 $O(N^3)$ 이므로, 웬만한 문제에서는 노드의 최대 개수가 세 자리수이다. 두 번째 힌트는 출력 형태이다. 출력에서는 모든 노드간 최단 거리를 출력하라고 한다. 이는 모든 지점에서 다른 모든 지점가지의 최단 경로를 계산하는 플로이드 워셜 알고리즘의 역할과 동일하다.

CODE

import sys
input = sys.stdin.readline

def solution():
    '''
        플로이드 워셜 알고리즘을 사용한 풀이
    '''
    N = int(input())
    INF = int(1e9)
    graph = [[INF] * (N+1) for _ in range(N+1)]
    for i in range(1, N+1):
        graph[i][i] = 0

    M = int(input())
    for _ in range(M):
        a, b, c = map(int, input().split())
        if graph[a][b] > c:
            graph[a][b] = c

    for k in range(1, N+1):
        for a in range(1, N+1):
            for b in range(1, N+1):
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

    for g in graph[1:]:
        for e in g[1:]:
            if e == INF:
                print(0, end=" ")
            else:
                print(e, end=" ")
        print()

if __name__ == "__main__":
    solution()

시간 복잡도

$$ O(N^3) $$

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A($x_A$, $y_A$, $z_A$)와 B($x_B$, $y_B$, $z_B$)를 터널로 연결할 때 드는 비용은 min(|$x_A$-$x_B$|, |$y_A$-$y_B$|, |$z_A$-$z_B$|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

• 입력

  첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.

• 출력

  첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

문제 풀이

모든 행성을 연결한다는 정보에서 크루스칼 알고리즘을 떠올렸다. 그러나 크루스칼 알고리즘은 간선을 가중치 별로 정렬해야 하는데, 문제에서는 간선에 대한 정보가 주어지지 않는다. 그렇다면 간선을 어떻게 만들어야 할까? 문제에서는 행성과 행성의 연결을 min(|$x_A$-$x_B$|, |$y_A$-$y_B$|, |$z_A$-$z_B$|) 로 정의했다. 때문에 x, y, z 축 각각을 기준으로 행성들을 정렬한 다음, 이웃하는 행성과 행성을 하나의 간선으로 취급한다. 각 축 별로 생성된 간선들을 가중치순으로 정렬한 뒤, 크루스칼 알고리즘을 수행하여 최소 신장 트리를 생성하여 문제를 풀 수 있다.

입출력 예시

예제 입력 1

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

예제 출력 1

4

CODE

import sys
input = sys.stdin.readline

def find_parent(parent, x):
    if x != parent[x]:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def solution():
    N = int(input())
    nodes = []
    for i in range(N):
        X, Y, Z = map(int, input().split())
        nodes.append((i+1, X, Y, Z))

    # 1. x, y, z 축으로 정렬하여 이웃한 행성들의 edges 를 얻는다.
    edges = []
    # 1-1 dim축 기준으로 정렬 후 인접한 행성 edges에 추가
    for dim in range(1, 4): # 1:x, 2:y, 3:z
        sorted_list = sorted(nodes, key = lambda x: x[dim])
        for i in range(N-1):
            cost = abs(sorted_list[i][dim] - sorted_list[i+1][dim])
            v1 = sorted_list[i][0]
            v2 = sorted_list[i+1][0]
            edges.append((cost, v1, v2))

    # 2. 얻은 edges를 기반으로 크루스칼 알고리즘을 수행한다.
    parent = [i for i in range(N+1)]
    answer = 0
    for edge in sorted(edges):
        w, v1, v2 = edge

        # 2-1. v1, v2의 루트 노드가 다른 경우에만 Union 작업 실행
        if find_parent(parent, v1) != find_parent(parent, v2):
            union_parent(parent, v1, v2)
            answer += w

    return answer

if __name__ == "__main__":
    answer = solution()
    print(answer)

시간 복잡도

$$ O(N log N) $$

문제 링크 : https://www.acmicpc.net/problem/3665

문제 설명

올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다.

올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.

창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다.

• 입력 조건

  첫째 줄에는 테스트 케이스의 개수가 주어진다. 테스트 케이스는 100개를 넘지 않는다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

  • 팀의 수 n을 포함하고 있는 한 줄. (2 ≤ n ≤ 500)
  • n개의 정수 t를 포함하고 있는 한 줄. (1 ≤ t ≤ n) t는 작년에 i등을 한 팀의 번호이다. 1등이 가장 성적이 높은 팀이다. 모든 ti는 서로 다르다.
  • 상대적인 등수가 바뀐 쌍의 수 m (0 ≤ m ≤ 25000)
  • 두 정수 a와 b를 포함하고 있는 m줄. (1 ≤ a < b ≤ n) 상대적인 등수가 바뀐 두 팀이 주어진다. 같은 쌍이 여러 번 발표되는 경우는 없다.

• 출력

  각 테스트 케이스에 대해서 다음을 출력한다.

  • n개의 정수를 한 줄에 출력한다. 출력하는 숫자는 올해 순위이며, 1등팀부터 순서대로 출력한다. 만약, 확실한 순위를 찾을 수 없다면 "?"를 출력한다. 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

입출력 예시

예제 입력 1

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

예제 출력 1

5 3 2 4 1
2 3 1
IMPOSSIBLE

문제 풀이 1.

최종 순위 문제는 2가지 방법으로 풀었다.

첫 번째 방법은 NxN 인접 행렬 graph를 이용한 풀이다. graph[v1][v2] 의 의미는 v1노드가 v2노드를 이길 수 있는지의 여부이다. 우선 작년 순위 rank 를 순회하면서 지면 1로 초기화되어 있는 graph[v1][v2]를 0으로 수정한다. 그리고 M개의 상대적인 등수가 바뀌는 쌍을 입력받으면서 graph에서 두 노드간의 승패 여부를 수정해준다. 최종적으로 모든 노드가 등수가 정해지려면 다음과 같이 sum(graph[i])값(1 ≤ i ≤ N)이 모두 달라야 한다.

다음과 같이 sum(graph[i])값(1 ≤ i ≤ N)이 같은 것이 생길 경우 두 노드의 등수를 특정할 수 없는 문제가 생기고, 이러한 경우 IMPOSSIBLE을 출력해야 한다.

CODE 1.

import sys
input = sys.stdin.readline
from collections import deque

def solution_1():
    T = int(input())
    for _ in range(T):
        N = int(input()) # 노드 수
        graph = [[1] * (N+1) for _ in range(N+1)] # 모든 노드가 모든 노드를 이긴다고 초기화
        rank = list(map(int, input().split())) # 인덱스 순으로 등수 나열, rank[0] -> 1등

        for i in range(N):
            v = rank[i] # i+1등 노드 v
            for rest_node in rank[i+1:]: # i+2등 노드부터는 v한테 짐
                graph[rest_node][v] = 0

        M = int(input())
        for _ in range(M):
            V1, V2 = map(int, input().split())
            tmp = graph[V1][V2]
            graph[V1][V2] = graph[V2][V1]
            graph[V2][V1] = tmp

        can_rank = [False] * (N+1)
        answer = [0] * N
        for v, g in enumerate(graph): # v는 노드 번호, sum(g)는 이긴 횟수, N-이긴횟수 = answer 인덱스
            if v == 0:
                continue
            g = g[1:]
            s = sum(g)
            can_rank[s] = True
            i = N-s
            answer[i] = v

        # print(f'can_rank : {can_rank}')
        if False in can_rank[1:]:
            print("IMPOSSIBLE")
        else:
            for v in answer:
                print(v, end=' ')
            print()

if __name__ == "__main__":
    solution_1()
    # solution_2() # 위상 정렬 사용한 풀이 

시간 복잡도

$$ O(N^2) $$

문제 풀이 2.

두 번째 방법은 위상 정렬을 이용한 풀이이다. v1 노드가 v2 노드를 이긴다는 것을 v1→v2 로 해석하여, 인접 리스트 graph와 indegree 배열을 만든다. 이 뒤로는 위상 정렬의 핵심 알고리즘대로 코드를 구현한다.

CODE 2. 위상 정렬 사용

import sys
input = sys.stdin.readline
from collections import deque

def solution_2():
    '''
        위상 정렬을 사용항 코드
        - 인덱스는 노드, 값은 해당 노드의 진입차수를 저장하는 indegree 배열을 사용
        - 핵심 알고리즘
            1. 진입 차수가 0인 노드를 큐에 넣는다
            2. 큐가 빌 때까지 다음의 과정을 반복한다.
                2-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
                2-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
    '''
    T = int(input())
    for _ in range(T):
        N = int(input()) # 노드 수
        graph = [[] for _ in range(N+1)]
        rank = list(map(int, input().split())) # 인덱스 순으로 등수 나열, rank[0] -> 1등

        # 1. 위상 정렬을 위한 indegree 생성
        indegree = [0] * (N+1)

        # 등수에 따라 간선 생성, 5번이 1번 이기면 5->1 간선 생성
        lose_nodes = [i for i in range(1, N+1)]
        for win in rank: # 등수별로 v 나옴
            lose_nodes.remove(win)
            # 남은 노드는 다 이기는걸로 간주
            for lose in lose_nodes:
                graph[win].append(lose)
                indegree[lose] += 1

        M = int(input())
        for _ in range(M):
            V1, V2 = map(int, input().split())
            if V2 in graph[V1]: # V1->V2 를 V2->V1 으로 바꿔줌
                graph[V1].remove(V2)
                graph[V2].append(V1)
                indegree[V1] += 1
                indegree[V2] -= 1
            else:
                graph[V2].remove(V1)
                graph[V1].append(V2)
                indegree[V1] -= 1
                indegree[V2] += 1

        # 2. indegree 값이 0인 노드 큐에 추가
        queue = deque([])
        for v in range(1, N+1):
            if indegree[v] == 0:
                queue.append(v)

        # 3. 큐가 빌 때 까지, 
        answer = []
        while queue:
            v1 = queue.popleft()
            answer.append(v1)
            # 3-1. v1에서 나가는 간선 그래프에서 제거 + 진입차수 0인 노드 큐에 추가
            for v2 in graph[v1]:
                indegree[v2] -= 1
                if indegree[v2] == 0:
                    queue.append(v2)
        # 4. 큐가 비었는데 간선이 남아있는 경우 impossible
        if any(indegree):
            print("IMPOSSIBLE")
        else:
            for v in answer:
                print(v, end=' ')
            print()

if __name__ == "__main__":
    # solution_1()
    solution_2() # 위상 정렬 사용한 풀이 

시간 복잡도

$$ O(N^2 + M) $$

• (2 ≤ N ≤ 500)
• E = N(N+1)/2
• (0 ≤ M ≤ 25000)

1. 간선 정보 생성 및 진입 차수 계산: O(N^2) - 순위 정보를 바탕으로 간선 정보를 생성하고, 진입 차수를 설정한다.
2. M번의 상대적인 등수가 바뀐 쌍 처리: O(M) - 경기 결과를 반영하여 간선의 방향을 바꾸고, 진입 차수를 업데이트한다.
3. 위상 정렬 실행: O(N+E) - 모든 노드를 큐에 넣고, 각 노드에서 출발하는 간선을 제거하면서 위상 정렬을 수행한다. 여기서 E는 간선의 총 개수이다. E는 N(N-1)/2이 될 수 있으므로, 이 단계의 시간 복잡도는 O(N^2)으로 볼 수 있다.

문제 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

입력 입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)

이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)

도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.

입력의 끝에서는 첫 줄에 0이 2개 주어진다.

출력 각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.

문제 풀이

크루스칼 알고리즘을 이용해서 최소 신장 트리를 만드는 문제이다.

edges 배열을 선언하여 모든 edges를 저장한 후, 가중치를 기반으로 정렬한다.

비용이 적은 도로부터 연결(Union)하면서 모든 집이 연결되게 만들면 된다.

만약 간선의 두 끝이 Root 노드가 같다면 같은 집합에 속하여 이미 이동할 수 있다는 뜻이므로 넘어간다. 그렇지 않으면 두 집합을 합친다(Union).

최종적으로 절약할 수 있는 최대 금액을 출력하는 것 이므로, 모든 간선의 가중치에서 최소 신장 트리의 가중치를 빼주면 된다.

입력이 조금 특이해서 애먹었는다. 테스트케이스가 한꺼번에 주어지는 것이니, N==0 and M==0 일때 까지 하나의 테스트케이스에 대한 입력을 받고 출력을 해야한다.

입출력 예시

입력 예시 1

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
0 0

출력 예시 1

51

CODE

import heapq
import sys
input = sys.stdin.readline

def find_parent(parent, x):
    if x != parent[x]:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

if __name__ == "__main__":

    while True:
        N, M = map(int, input().split())
        if N == 0 and M == 0:
            break

        parent = [i for i in range(N)]
        edges = []
        answer = 0

        for _ in range(M):
            v1, v2, W = map(int, input().split())
            heapq.heappush(edges, (W, v1, v2))
            answer += W

        while edges:
            W, v1, v2 = heapq.heappop(edges)

            if find_parent(parent, v1) == find_parent(parent, v2): # 간선의 두 노드가 이미 같은 집합에 속해 있다면
                continue
            else:
                union_parent(parent, v1, v2)
                answer -= W

        print(answer)

시간 복잡도

$$ O(MlogM) $$

• M개의 각선에 대하여 힙에 추가하는 데에 각각 $O(logM)$의 시간이 걸리므로 최종적으로 $O(MlogM)$ 시간이 걸린다.
• 크루스칼 알고리즘은 힙에서 꺼내는 데에 $O(logM)$의 시간이 들고, Union-Find 알고리즘을 수행하는 데에 거의 상수시간에 가깝다.

문제 링크 : https://www.acmicpc.net/problem/10775

문제 설명

오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다. 신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

• 입력 조건
  • 첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.
  • 두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.
  • 이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.
• 출력 조건
  • 승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

문제 풀이

이 문제는 Union-Find 알고리즘을 사용해서 풀 수 있다. 탑승구의 정보를 담는 parent 배열을 선언한다. 새로운 비행기가 탑승구에 도킹이 된다고 하면, 해당 탑승구 집합을 왼쪽 탑승구의 집합과 합친다. 단 집합의 루트가 0이면 더 이상 도킹이 불가능하다는 뜻이므로, 운영을 중단한다.

입출력 예시

입력 예시 1

4
3
4
1
1

출력 예시 1

2

입력 예시 2

4
6
2
2
3
3
4
4

출력 예시 2

3

CODE

import sys
input = sys.stdin.readline

def find_parent(parent, x):
    if x != parent[x]:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

if __name__ == "__main__":
    # 입력
    N = int(input()) # 탑승구 수
    M = int(input()) # 비행기 수

    # Union-Find 알고리즘을 이용해 해결
    parent = [i for i in range(N+1)]

    answer = 0
    for i in range(M):
        # g_i 입력 - i번째 비행기의 탑승구 정보
        x = int(input())
        if find_parent(parent, x) == 0: # 비행기 도킹 불가능
            break
        else:
            parent_x = parent[x]
            union_parent(parent, parent_x, parent_x - 1) # 비행기 도킹
            answer += 1
    print(answer)

시간 복잡도

parent 배열을 초기화 : $O(N)$

비행기 도킹 시도 : $O(M)$

$$ O(N+M) $$

풀이 1

어떤 노드 X가 순위가 정해진 노드인지 확인하기 위해서는,

X를 제외한 모든 노드 Y에 대하여 X→Y 혹은 Y→X 가 가능해야 한다.

X→Y가 가능한지 확인하기 위한 함수로 can_A_to_B라는 함수를 정의했으며, bfs 알고리즘을 사용했다.

graph는 인접 리스트로 구현했으며, 이 경우 bfs의 시간복잡도는 $O(N + E)$이다.

만약 인접 행렬로 구현했다면, bfs의 시간 복잡도는 $O(N^2)$이다. 이 문제에서는 노드의 최댓값이 100, 간선의 최댓값이 4500이어서, 인접행렬로 graph를 구현했을 때 더 유리하다.

시간 복잡도

$$ O(N^2 \times(N+E)) $$

• 노드의 개수 $N$의 최댓값이 100, 간선의 개수 $E$의 최댓값이 4500이다.
• 최대 45,000,000 인데, 가능할 것 같은데 안 된다…

CODE

from collections import deque

def can_A_to_B(graph, A, B):
    # 단방향 그래프 graph에서 노드 A에서 B로 이동 가능하면 True, 불가능하면 False 반환
    q = deque([])
    # A, B가 같으면 방문 가능하다 취급
    if A == B:
        return True

    # A->? 모든 노드 q에 저장    
    for Y in graph[A]:
        q.append(Y)

    # bfs 수행 중 B를 만나면 True 반환
    while q:
        X = q.popleft()
        if X == B:
            return True
        for Y in graph[X]:
            q.append(Y)

    # bfs가 끝났는데 B를 못만났으면 False 반환
    return False # A->B 불가능

def solution(n, results):
    # 순위가 정해지는 기준 : 어떤 노드 X를 제외한 모든 노드 V가 (X -> V) or (V -> X) 가능

    # graph 구현
    graph = [[] for _ in range(n+1)]
    for result in results:
        v1, v2 = result
        graph[v1].append(v2)

    answer = 0
    for X in range(1, n+1):
        # 어떤 노드 X를 제외한 모든 노드 V가 (X -> V) or (V -> X) 가능한지 확인
        for V in range(1, n+1):
            if not can_A_to_B(graph, V, X) and not can_A_to_B(graph, X, V):
                break
        else: # X는 순위가 정해진 노드이다.
            answer += 1

    return answer

풀이 2

(N+1)x(N+1) 크기의 인접 행렬 graph를 준비해준다.

편의상 index 0 은 무시하고 1부터 저장해준다.

graph[a][b] 의 의미는 a가 b를 이겼다는 의미이다.

results 원소들을 기반으로 직접적인 승리들을 graph에 기록해준다.

그리고 플로이드-워셜 알고리즘을 이용하여 a→b and b→c 이면 a→c인 것 처럼 간접적인 승리를 graph에 기록해준다.

그럼 최종적으로 graph[a][b] 값은 직접적으로든 간접적으로든 a가 b를 이길 수 있는지가 저장된다.

어떤 노드 X가 순위가 정해져있는지 확인하기 위해서는, X를 제외한 모든 노드들 Y가 graph[X][Y]=True 이거나 graph[Y][X]=True 여야 한다. 즉, X는 모든 노드들에 대하여 승패 여부를 알 수 있어야 한다. 하나라도 승패 여부를 모르는 노드 Y가 있다면, 순위를 지정할 수 없다는 뜻이다.

시간 복잡도

$$ O(N^3) $$

• 노드의 개수 $N$의 최대 크기가 100인 점에서 플로이드-워셜 알고리즘을 떠올리면 좋다.
• 플로이드-워셜 알고리즘은 최대 크기가 1000이 되면 쓸 수 없다.

CODE

def solution(n, results):
    graph = [[False] * (n+1) for _ in range(n+1)]

    for result in results:
        win, lose = result
        graph[win][lose] = True

    for k in range(1, n+1):
        for w in range(1, n+1):
            for l in range(1, n+1):
                if graph[w][k] and graph[k][l]:
                    # print(f'{w} -> {k}, {k} -> {l} so {w} -> {l}')
                    graph[w][l] = True

    answer = 0
    for x in range(1, n+1):
        # x가 순위가 정해져있는지 확인
        for y in range(1, n+1):
            if x == y:
                continue
            # x->y 이거나 y->x 이면 
            if not graph[x][y] and not graph[y][x]:
                break
        else: # for문을 다 돌았으면
            answer += 1

    return answer

문제 링크 : https://www.acmicpc.net/problem/11692

풀이

약수와 관련된 문제여서 소인수분해를 해보며 접근했습니다. 약수의 합이 짝수가 되기 위해서는 약수 중 홀수의 개수가 짝수개 있어야 합니다. 대부분 학창시절 약수의 개수를 구하는 문제를 접해봤을 듯 합니다. 약수의 개수를 구하는 방법은 아래 표를 보면 유추할 수 있습니다.

출처 : https://mathbang.net/201#gsc.tab=0

소인수분해를 하여 소수 거듭제곱들의 곱 꼴로 만들고, 지수들에 +1 한 값들을 곱하면 약수의 개수를 구할 수 있습니다. 그렇다면 약수 중 홀수인 것들의 개수는 어떻게 구할까요? 소인수분해 결과에서 홀수인 소인수들만 고려해주면 됩니다. 홀수인 소인수들의 지수에 1을 더해서 곱해주면, 홀수인 약수의 개수를 구할 수 있습니다. 예를 들면, $2^x \times 3^y \times 5^z$ 이 숫자에서는 $(y+1)(z+1)$개의 홀수인 약수가 존재합니다.

이제, 이 값(소인수분해한 결과에서 홀수인 소인수의 지수에 1을 더해서 모두 곱한 값)이 홀수가 되는 경우에 대해서 생각해봅시다. 어떤 수들을 곱해서 홀수가 되려면 어떤 수들이 전부 홀수여야 합니다.

• 홀수 x 홀수 → 홀수
• 짝수 x 홀수, 짝수 x 짝수 → 짝수

지수에 +1 해서 약수의 개수를 구하기 때문에, 홀수인 소인수들의 지수가 전부 짝수여야 한다는 뜻이 됩니다. 이말은 곧 제곱수라는 의미입니다. 예를 들면, $2^2 \times 3^2, ~ 3^4, ~2\times 3^4\times 5^2, ~3^4 \times 5^2$ 이런 수들이 있습니다.

소인수분해 결과에 2가 포함되어 있는지에 대한 여부는 시그마 함수의 값이 짝수가 되는 데에 영향을 끼치지 않습니다. 따라서 우리는 모든 제곱수를 빼주면 됩니다. 다만 소인수 2의 지수가 홀수개인지 짝수개인지 알 수 없으므로, 두 가지 경우를 모두 빼줘야합니다.

• 제곱수
• 제곱수 $\times ~2$

1~m(입력값) 사이의 제곱수의 개수는 int(sqrt(m)) 개 입니다. 제곱수 $\times ~2$ 의 개수는 int(sqrt(m/2)) 개 입니다.

최종적으로, 구하고자 하는 값은 m - int(sqrt(m)) - int(sqrt(m/2)) 으로 구할 수 있습니다.

Code

if __name__ == "__main__":
    N = int(input())

    print(N - int(sqrt(N)) - int(sqrt(N/2)))

dfs를 이용해서 풀었습니다. 재귀적으로 dfs를 호출할 때 r_visited, b_visited 에 deepcopy 함수를 사용하면 테스트12가 시간초과나서 재귀에서 탈출하면 visited 원소를 삭제하는 방식으로 구현했습니다.

테스트8, 9에서는 시간초과가 나는데, 원인을 차지 못했습니다. 혹시 아시는분은 알려주시면 감사하겠습니다.

from typing import Tuple, Set
import copy

def get_pos(maze):
    for i in range(len(maze)):
        for j in range(len(maze[0])):
            if maze[i][j] == 1:
                r_pos = (i, j)
            elif maze[i][j] == 2:
                b_pos = (i, j)
            elif maze[i][j] == 3:
                r_target_pos = (i, j)
            elif maze[i][j] == 4:
                b_target_pos = (i, j)
            else:
                pass
    return r_pos, b_pos, r_target_pos, b_target_pos

def solution(maze):
    global answer 
    answer = 2^32
    r_visited = list()
    b_visited = list()
    r_pos, b_pos, r_target_pos, b_target_pos = get_pos(maze)
    lx = len(maze)
    ly = len(maze[0])
    dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]


    # dfs의 역할
    # 전달 받은 위치에 대하여 방문처리 + 상하좌우 방향으로 다음 칸 전달(4번 호출)
    # r_maze, b_maze 에서 각 수레가 한칸씩 움직인다

    def dfs(r_pos: Tuple[int, int], b_pos: Tuple[int, int], r_visited: Set[Tuple[int, int]], b_visited: Set[Tuple[int, int]], depth):
        global answer
        # 종료 조건
        # 둘 다 타겟에 도달한 경우
        if r_pos == r_target_pos and b_pos == b_target_pos:
            if depth < answer:
                answer = depth
            return

        # 방문 처리
        r_visited.append(r_pos)
        b_visited.append(b_pos)

        # 다음 이동. 다음과 같은 제한사항 주의
        # 0. 벽이 아니어야함
        # 1. 수레는 벽이나 격자 판 밖으로 움직일 수 없습니다.
        # 2. 수레는 자신이 방문했던 칸으로 움직일 수 없습니다.
        # 3. 자신의 도착 칸에 위치한 수레는 움직이지 않습니다. 계속 해당 칸에 고정해 놓아야 합니다.
        # 4. 동시에 두 수레를 같은 칸으로 움직일 수 없습니다.
        # 5. 수레끼리 자리를 바꾸며 움직일 수 없습니다.
        for dx1, dy1 in dir:
            if r_pos == r_target_pos: # 조건 3
                n_r_pos = r_pos
            else:
                n_r_pos = (r_pos[0] + dx1, r_pos[1] + dy1)
            # 조건 1, 0, 2
            if (0 > n_r_pos[0] or n_r_pos[0] >= lx  or 0 > n_r_pos[1] or n_r_pos[1] >= ly) \
                or (maze[n_r_pos[0]][n_r_pos[1]] == 5)\
                or (n_r_pos in r_visited and n_r_pos != r_target_pos):
                continue
            for dx2, dy2 in dir:
                if b_pos == b_target_pos:
                    n_b_pos = b_pos
                else:
                    n_b_pos = (b_pos[0] + dx2, b_pos[1] + dy2)
                # 조건 1, 0, 2, 4, 5
                if (0 > n_b_pos[0] or n_b_pos[0] >= lx  or 0 > n_b_pos[1] or n_b_pos[1] >= ly) \
                    or  (maze[n_b_pos[0]][n_b_pos[1]] == 5)\
                    or (n_b_pos in b_visited and n_b_pos != b_target_pos) \
                    or (n_r_pos == n_b_pos) \
                    or (n_r_pos == b_pos and n_b_pos == r_pos):
                    continue
                dfs(n_r_pos, n_b_pos, r_visited, b_visited, depth + 1)

        r_visited.pop()
        b_visited.pop()
    dfs(r_pos, b_pos, r_visited, b_visited, 0)

    if answer == 2^32:
        answer = 0
    return answer

input : 시작 시점의 시간, 끝 시점의 시간 output : 시작 시간부터 끝나는 시간까지 아날로그 시계가 동작하는 동안 초침이 분침 혹은 시침과 만나는 횟수 반환

문제 분석

초침 > 분침 > 시침 순으로 움직이는 속도가 다릅니다. 초침이 제일 빠르고 1분에 한바퀴 도니까 그냥 1분에 2번씩 울리는거 아닌가? 라고 생각할 수 있지만, 다음을 주의해야 합니다.

• 주의 1. 12시 정각으로, 시침, 분침, 초침 모두 겹치는 경우 -> 2번이 아니라 1번 울립니다.
• 주의 2. 시침과 분침이 1분동안 초침의 초기 각도를 추월한 경우 -> 울리지 않습니다.
  • 이는 시침은 12시간에 1번, 분침은 1시간에 1번 꼴로 일어납니다.

초침, 분침, 시침이 시간단위별로 몇도씩 움직이는지 확인해봅시다.

• 초침은
  • 1분 -> 360도
  • 1초 -> 6도
• 분침은
  • 1분 -> 6도
  • 1초 -> 0.1도
• 시침은
  • 1시간 -> 30도
  • 1분 -> 0.5도
  • 1초 -> 1/120도

문제 해결

시간, 분, 초가 input으로 주어졌을 때, 12시를 기준으로 시침, 분침, 초침이 몇도를 이루고 있는지 구하여 반환하는 함수를 이용했습니다.

• ex) 12시 6분 30초
  • s_ang = 180.0
  • m_ang = 39.0
  • h_ang = 390/120

이 함수를 이용해 매초마다 각도를 계산해서, 초침이 분침 혹은 시침의 각도를 추월한 경우 alarm_count를 1씩 증가하는 방식으로 문제를 해결했습니다.

코드

from typing import Tuple

def find_angles(h: int, m: int, s: int) -> Tuple[float, float, float]:
    s_ang = float(s * 6)
    m_ang = float(m * 6 + s * 0.1)
    h_ang = float((h % 12) * 30 + m * 0.5 + s / 120)

    return (h_ang, m_ang, s_ang)

def solution(h1, m1, s1, h2, m2, s2):
    alarm_count = 0
    p_h_ang, p_m_ang, p_s_ang = find_angles(h1, m1, s1)
    p_h, p_m, p_s = h1, m1, s1
    if p_h_ang == p_m_ang == p_s_ang: # 시작 시점이 12시 정각인 경우
        alarm_count += 1

    # 초와 각도를 증가시키는 while 문    
    while True:
        # 1초씩 증가
        n_s = (p_s + 1) % 60
        n_m = (p_m + (p_s + 1) // 60) % 60
        n_h = (p_h + (p_m + (p_s + 1) // 60) // 60) % 24
        n_h_ang, n_m_ang, n_s_ang = find_angles(n_h, n_m, n_s)

        # 초의 각도가 분의 각도를 추월하는 순간 알림 카운트
        if (p_s_ang < p_m_ang and n_s_ang >= n_m_ang) or (p_s_ang < p_m_ang and n_s_ang == 0.0):
            alarm_count += 1

        # 초의 각도가 시의 각도를 추월하는 순간 알림 카운트
        if (p_s_ang < p_h_ang and n_s_ang >= n_h_ang) or (p_s_ang < p_h_ang and n_s_ang == 0.0):
            alarm_count += 1

        # 12시 정각인 경우 count -= 1
        if n_h_ang == n_m_ang == n_s_ang: # 시작 시점이 12시 정각인 경우
            alarm_count -= 1

        if n_h == h2 and n_m == m2 and n_s == s2:
            break

        p_h, p_m, p_s = n_h, n_m, n_s
        p_h_ang, p_m_ang, p_s_ang = n_h_ang, n_m_ang, n_s_ang

    return alarm_count



input_1 = [0, 5, 30, 0, 7, 0]
input_2 = [12, 0, 0, 12, 0, 30]
input_3 = [0, 6, 1, 0, 6, 6]
input_4 = [11, 59, 30, 12, 0, 0]
input_5 = [11, 58, 59, 11, 59, 0]
input_6 = [0, 0, 0, 23, 59, 59]

print(f'answer : {solution(*input_5)}')


'''
입출력 예시
h1    m1    s1    h2    m2    s2    result
0    5    30    0    7    0    2
12    0    0    12    0    30    1
0    6    1    0    6    6    0
11    59    30    12    0    0    1
11    58    59    11    59    0    1
1    5    5    1    5    6    2
0    0    0    23    59    59    2852
'''

2023/09 ~ 2023/12 기간동안 음성인식 기술력을 갖춘 회사인 리턴제로에서 지냈던 기간들을 회고하고자 포스팅을 한다. ICT 인턴십이라는 학기중에 인턴을 하면서 학점을 받을 수 있는 제도가 있다. 나는 4학년 1학기 과정으로 학점도 받으면서 AI 관련 실무경험을 쌓고자 리턴제로에 지원했다. 직무는 총 ML Engineer, 프론트엔드, 백엔드 3개의 직무로 지원할 수 있었는데, 나는 AI 분야로 취업을 준비하고 있었기 때문에 ML Engineer로 지원했다. 다행히 합격해서 4개월간 인턴 생활을 했고, 아래부터는 4개월을 회고하는 내용이다.

어떤 업무를 했는가?

1. 블로그 포스팅
2. 리서처팀 채용 전환 과제
   1. espnet 성능 향상 실험
   2. CTC 논문 세미나

1. 블로그 포스팅

9월 4일 첫 입사를 하고 첫 업무가 주어졌다. 회사에 적응하는 차원에서 회사 음성인식 API 를 사용해보고, 이에 대한 블로그를 작성하는 것이다. 내용은 VITO 음성인식 API를 타사 API와 성능을 비교하는 내용이었다. 나중에 알았지만 내가 포스팅한 내용과 정확히 같은 기능을 하는 사내 라이브러리가 이미 만들어져 있었다. 다시보니 글을 좀 다듬고 싶다… 급하게 쓰다 보니 내용이 많이 산만하다. 성능 비교 부분만 보려면 전사결과(6)부터 보면 된다. 블로그 링크

2. 리서처팀 채용 전환 과제 - espnet 성능 향상 실험

인턴 1개월 남았을 때 즈음, 사수분께서 채용 전환에 관심이 있냐고 물어봐주셨고 관심이 있다면 남은 기간은 채용 전환 과제를 진행하면 된다고 했다. 나는 관심이 있다고 했고, 채용 전환 과제를 진행하기로 했다. 과제는 총 2개였고 병행해서 진행해야 했다. 하나는 espnet 이라는 음성인식 툴킷 오픈소스를 이용해 직접 End-to-End 음성인식 모델을 학습해보고 다양한 실험을 진행하는 과제였다. 또 다른 과제는 CTC(Connectionist Temporal Classification)논문에 대한 세미나를 진행하는 것이었다. espnet 과제는 1500줄로 된 bash shell 스크립트를 읽어야 했는데, 약 4일만에 학습을 돌리는 데에 성공했다. espnet 오픈소스에서는 다양한 데이터셋 각각에 레시피를 제공해준다. 나는 ksponspeech 데이터셋에 대한 레시피로 학습을 진행해야 했다. 레시피를 이용해 직접 학습한 결과 github에 제시되어 있는 성능을 재현하는 데에 성공했고, 더불어 evaluation 데이터셋에 대한 성능(CER, WER)은 이를 뛰어 넘었다. config를 건드리면서 encoder, optimizer, fine-tuning 등 다양한 실험들을 진행했으며 각 실험에 대한 보고서를 노션 페이지에 정리했다.

3. 리서처팀 채용 전환 과제 - CTC 논문 세미나

CTC 논문 세미나 과제로는 회사 리서처분들(약 10명, 이런 분들…) 앞에서 CTC 논문 세미나를 진행해야 했다. 논문 세미나는 처음 해보고, 음성인식 분야는 인턴을 하면서 첫 입문을 했기에 더 떨리는 자리였다. 이 논문은 음성인식 분야에서 매우 중요하면서도 2006년에 나온 논문이어서 리서처분들은 이미 빠삭하게 알고 계시는 논문이다. 그래서 질문이 매우 날카로웠고, 나는 질문의 의도조차 파악하지 못하는 질문들이 대부분이었다. 나중에 한 리서처분이 어려운 질문이었다고 답하지 못하는게 정상이라고 말씀해주셔서 조금은 위안이 됐지만, 그래도 ML 지식의 부족함을 뼈저리게 느끼는 자리였다. 그래도 어려웠던 만큼 얻은게 많은 경험이었다. 논문 세미나를 어떻게 준비해야 하는지와 이 논문이 해당 산업에 끼친 영향과 의의가 무엇인지 명확하게 아는 것이 중요하다는 점을 깨달았다. CTC 논문 세미나 발표 자료

배운점

1. 내가 뭘 하는지 공유하는 능력

   어떤 Task가 주어졌을 때, 그것의 결과물은 공유가 되지만 과정에 대한 공유가 잘 안되는 경우가 있었다. 내가 뭘 하고있는지 잘 알리는 것도 junior의 중요한 역량이라는 것을 깨달았다.

2. 소통의 중요성

   whisper 모델을 다루면서 AI 관련 업무들이 많아지게 됐고, 이 과정에서 업무 분담에 불균형이 생겼었다. 모두가 알고 있었지만 그냥 넘어가다 어느날 이런 문제에 대해서 소통을 했고, 사수분의 적극적인 도움 덕에 모두가 만족하는 Task를 배정받았다.

   프론트, 백엔드 인턴분들은 데이터셋을 만드는 업무를 크게 의미있지 않은 프로젝트로 생각하고 있었고, 그들은 프로젝트에 점점 의욕이 없어지고 있었다. 안타까웠고 그들의 입장에서 생각해봤다. 요구사항들 정리해서 DB 설계하고 웹 디자인하는 그런 업무들을 하다가 크롤링하는 것은 잡무라고 생각할 수 있겠다고 조금은 이해되기 시작했다. 나는 안일해지는 분위기에 영향받기 싫었고 그럴바엔 그들이 만족할 수 있는 새로운 업무를 받아서 다같이 화이팅하는 분위기를 원했다. 여기까지 생각하고 나서 나는 새로운 업무를 달라고 요청해보는게 어떻겠냐고 소통을 시도했고, 사수분의 매우 적극적인 도움 덕에 모두가 만족하는 업무를 맡게 되었다. 결과적으로 프론트, 백엔드 인턴분들은 사내 프론트, 백엔드 개발자분들과 교류가 더 잦아지면서 모두가 화이팅 넘치게 남은 기간동안 보낼 수 있었다.

3. AI 최신 동향 Follow-up

   사내 메신저로 slack을 사용하는데, GeekNews를 가져오는 봇이 있었다. 엄청 유용한 내용들이 많았고, 특히 매주 이주의 ML논문을 번역해서 가져와주는 글을 항상 눈여겨 보았다. GeekNews만 틈틈이 챙겨보더라도 AI 산업의 움직임과 더불어 개발 트렌드를 따라갈 수 있겠다고 생각이 들었다.

마무리

ICT 인턴십을 준비할 때부터 AI와 관련없는 업무를 하게 되면 어떡하지라는 걱정을 했었는데, 다행히 리턴제로 인턴 기간 동안은 대부분은 내가 생각했던 업무들을 맡아서 만족스럽다. 채용 전환이 된다면 음성인식 분야를 제대로 공부해 볼 생각이다. 전환이 되지 않는다면, 전반적인 ML 지식과 요즘 생성 AI에 관심이 생겨 이쪽으로 공부해볼까 생각중이다.

학사 수준으로 AI 분야로 취직하는 것은 특히 요즘같은 취업난에서는 매우 힘든 것 같다. 나같아도 석사와 학사를 비교해서 뽑는다면 당연히 석사를 뽑을 것 같다. 석사가 되면서 갖추는 능력으로는 다양한 논문들을 읽고 분석해본 경험, 이를 통해 갖춘 ML 관련 지식 등이 있을 것 같다. 채용 전환이 되지 않는다면 이런 능력들을 키울 수 있도록 방학과 남은 학기동안 잘 계획을 해야겠다.

리턴제로에서의 인턴 경험은 오랫동안 좋은 기억으로 남을 것 같다. 음료와 닭가슴살, 핫도그 등을 맘대로 먹을 수 있도록 준비되어 있고, 라운지에서 각종 악기들을 원할 때 칠 수 있었다. 업무 환경, 복지 같은 것들을 통틀어 따져보자면, ICT 인턴십을 진행하는 기업 중에서는 상위 5% 안에는 들 것 같다. 게다가 리턴제로는 사람이 제일 중요한 회사라는 점을 자주 느꼈다. 정말 좋으신 분들이 많았다. + 엄청난 분들(CTO분이 ICPC world final 17위)이 많다… 배울 것들이 천지… 마지막날 출근날이 회사 송년회였는데, 많은 분들이 명함을 주셨고, 편하게 연락하라고 말씀해주셨다. 정말 좋은 경험이었다!

❓ model 의 반환값 (yaw, pitch)의 의미? ❓ 모델에서 사용한 데이터셋의 label 형식

model 의 반환값 (yaw, pitch)의 의미?

Aircraft principal axes 용어이다.

• pitch → 위아래 시선 각도
• yaw → 좌우 시선 각도

L2CS-Net Architecture

모델 이름이 L2CS-Net 인 이유

2 loss 를 사용하고 loss function 은 cross-entropy loss 와 softmax layer 을 사용해서 생긴 이름

모델 특징

• 모델의 Input : 사람 얼굴 Bbox (RGB 이미지)
• 모델의 Output : (yaw angle, pitch angle)
• CNN-based model
• yaw 축, pitch 축 loss 계산을 따로 하여 독립적으로 학습 → 가중치 미세 조정 + 일반화 성능 증가
• face_detection 모델로는 RetinaFace 사용.

Introduction

• Eye gaze 는 다양한 분야에 많이 쓰임.

  ex) 인간-로봇 상호작용, 개방형 대화 시스템, 증강 현실 등…

• Eye gaze 예측에는 두 가지 방법이 있음

  • Model-based method

    • 눈동자의 위치와 머리의 회전 등과 같은 사람의 물리적인 특징과 모양을 모델링하여 시선을 예측하는 방식
    • 사람의 머리와 눈에 대한 3D 모델을 사용하고, 머리와 눈의 움직임에 따른 눈동자의 이동 벡터를 계산
    • 일반적으로 전용 하드웨어가 필요하며, 이는 제한된 환경에서만 사용 가능

  • Appearance-based method

    • 이미지에서 얼굴 특징점, 즉 눈, 코, 입, 귀 등의 위치를 인식하고, 눈 주위 픽셀에서 특징을 추출하여 시선을 예측
    • 일반적으로 머신러닝 알고리즘을 사용하여 이미지 특징을 학습
    • 저렴한 기성품 카메라로 캡처한 이미지에서 직접 사람의 시선을 회귀시켜 제약 없는 설정으로 다양한 위치에서 쉽게 생성

  • 차이점

    Model-based method가 물리적 특징을 기반으로 하고, Appearance-based method는 이미지에서 특징을 추출하여 예측을 수행

    Model-based method는 사람의 물리적 특징이 변경되면 시선 추적이 어렵고, Appearance-based method는 조명, 얼굴 각도 등의 영향을 덜 받지만 이미지에서 특징을 잘 추출할 수 있는 디자인이 필요

• Appearance-based method 에서는 CNN 기반 모델들이 등장하고 있음. pinball loss도 생기면서 정확도를 올림. 그러나 아직 제한된 환경에서와 일반화 성능이 부족함.

• 이 논문에서는 multi-loss approach 를 통해 RGB 이미지에서 3D 시선 각도를 추정함.

3.3 Datasets

• Gaze360 and MPIIGaze 사용해서 train, evaluate
• Gaze360
  • 광범위한 360도 범위의 3D gaze annotations
  • 연령, 성별, 민족이 다른 238명의 피실험자
  • 조명 조건 및 배경과 같은 다양한 실내 및 실외 환경 설정에서 Ladybug 다중 카메라 시스템을 사용하여 이미지를 캡처 (unconstrained setting)
• MPIIGaze
  • 213.659개의 이미지
  • 15명의 피실험자가 몇 달 동안 일상 생활에서 캡처
  • 다양한 배경, 시간, 조명의 이미지를 포함(unconstrained setting)
  • 참가자들에게 랩톱에서 무작위로 움직이는 점을 보도록 요청하는 소프트웨어를 사용하여 수집

4.2 Training and results

• backbone 으로 ImageNet-pretrained ResNet-50 사용
• Adam optimizer (lr = 0.00001)
• 50 epoch, batch size = 16