음성 데이터를 resampling 해야 할 경우가 있다. 

예를 들어 44.1kHz 에서 16000으로 변경을 해준다던지, 16000에서 22050으로 변경하여 음성 처리를 해줄 때가 있다.(Downsampling)

python에서 librosa 라이브러리를 이용하여 resampling을 간단히 해줄 수 있는데, 이 때 우분투에서 작업하던 음성 파일이 resampling 되고나서 librosa를 이용하여 그대로 저장을 하고 윈도우에서 그 음성을 다운받아서 확인해볼 때 읽히지 않을때가 있다.

결론적으로 말하자면, librosa 로 resample 이후에 soundfile의 write를 사용하여 저장하면 이 문제를 해결할 수 있다.

librosa.output.write_wav(output_dir+'.wav', data, sr) # 깨지는 현상 존재
sf.write(output_dir, data, sr, format='WAV', endian='LITTLE', subtype='PCM_16') # 깨지지 않음

위의 soundfile write내의 내용을 librosa write_wav의 내용을 그대로 넣어주면 된다.

음성 데이터(Speech, Sound 등)를 python을 이용하여 처리하여(sampling rate나 일정 부분을 자는 것 등) 저장하는 것을 해보려 한다.

사용하는 라이브러리는 librosa

우선 음성을 저장된 디렉토리로부터 불러온다. 

아래의 코드를 사용하여 불러오면 file_dir와 file_id가 출력이 된다.

wav = '/data/dataset/IEMOCAP_wavonly/IEMOCAP_Wavonly/Wav/Ses01F_impro01/Ses01F_impro01_F005.wav'
(file_dir, file_id) = os.path.split(wav)
print("file_dir:", file_dir)
print("file_id:", file_id)

- 결과

file_dir: /data/dataset/IEMOCAP_wavonly/IEMOCAP_Wavonly/Wav/Ses01F_impro01

file_id: Ses01F_impro01_F005.wav

Process finished with exit code 0

그 다음 이 음성 파일을 librosa로 불러올 것이다.

librosa는 별도로 sr(sampling rate)를 설정하지 않으면 default sr이 22500으로 되어있다.

내가 불러올 음성 파일은 이미 16000 sr이므로 반드시 sr=16000을 붙여주도록 한다.

y, sr = librosa.load(wav, sr=16000)
time = np.linspace(0, len(y)/sr, len(y)) # time axis

fig, ax1 = plt.subplots() # plot
ax1.plot(time, y, color = 'b', label='speech waveform')
ax1.set_ylabel("Amplitude") # y 축
ax1.set_xlabel("Time [s]") # x 축
plt.title(file_id) # 제목
plt.savefig(file_id+'.png')
plt.show()

이 음성 파일을 plot하여 그린 그림은 아래와 같다.

약 4초정도의 길이를 갖는 음성파일이다.

이 음성 파일의 절반만을 가져오고 다시 저장하는 단계를 해보겠다.

우선 아래의 코드를 통해 음성 신호를 절반만을 가져오고, 절반을 그려보도록 하자.

half = len(y)/2
y2 = y[:round(half)]
time2 = np.linspace(0, len(y2)/sr, len(y2))
fig2, ax2 = plt.subplots()
ax2.plot(time2, y2, color = 'b', label='speech waveform')
ax1.set_ylabel("Amplitude") # y 축
ax1.set_xlabel("Time [s]") # x 축
plt.title('cut '+file_id)
plt.savefig('cut_half '+file_id+'.png')
plt.show()

이 부분의 결과는 아래의 그림과 같다. 약 절반정도가 잘렸다.

이제 이 음성을 저장할건데, librosa 라이브러리를 사용하여 쉽게 저장할 수 있다. 

librosa.output.write_wav('cut_file.wav', y2, sr)

아래에서 기존 음성과 자른 부분의 음성을 비교해볼 수 있다.

Original 음성:  

절반 Cut 한 음성: 

전체 코드

import librosa
import os
import numpy as np
import matplotlib.pyplot as plt


wav = '/data/dataset/IEMOCAP_wavonly/IEMOCAP_Wavonly/Wav/Ses01F_impro01/Ses01F_impro01_F005.wav'
(file_dir, file_id) = os.path.split(wav)
print("file_dir:", file_dir)
print("file_id:", file_id)

# original
y, sr = librosa.load(wav, sr=16000)
time = np.linspace(0, len(y)/sr, len(y)) # time axis
fig, ax1 = plt.subplots() # plot
ax1.plot(time, y, color = 'b', label='speech waveform')
ax1.set_ylabel("Amplitude") # y 축
ax1.set_xlabel("Time [s]") # x 축
plt.title(file_id) # 제목
plt.savefig(file_id+'.png')
plt.show()
librosa.output.write_wav('original_file.mp3', y, sr) # original wav to save mp3 file

# cut half and save
half = len(y)/2
y2 = y[:round(half)]
time2 = np.linspace(0, len(y2)/sr, len(y2))
fig2, ax2 = plt.subplots()
ax2.plot(time2, y2, color = 'b', label='speech waveform')
ax1.set_ylabel("Amplitude") # y 축
ax1.set_xlabel("Time [s]") # x 축
plt.title('cut '+file_id)
plt.savefig('cut_half '+file_id+'.png')
plt.show()
librosa.output.write_wav('cut_file.mp3', y2, sr) # save half-cut file

오늘은 Keras로 구축해놓은 모델을 png나 jpg인 그림 포멧으로 저장하는 법에 대해 써볼까 한다.

우선 Keras 공식 홈페이지를 들어가서 plot_model library를 검색해본다.

https://keras.io/visualization/

들어가보면 맨 윗창에 Model Visualization이라고 나와 있다. 뜻 그대로 모델을 시각화 하겠다라는 뜻일듯.

예제에 나와 있는 것 처럼 그림으로 보고 싶은 모델을 불러온 뒤 예제처럼 코딩을 하면 저장이 된다.

나의 코드는 다음과 같다.

from keras.utils import plot_model


from keras.models import load_model
from keras_self_attention import SeqSelfAttention

model = load_model('/data/Auditory_Emotion_Recognition/model_attention/4emotions_auditory_cnn_model_self_GAP_pati50_epoch200_dropout0.2,relu_lr1e-05_8conv5dim+1GRU2FC_Zscore_lrdecay5.4e-08_acc:0.5498_test:_57.42.h5',custom_objects={'SeqSelfAttention':SeqSelfAttention})
plot_model(model, to_file='./model.png')

from keras.utils import plot_model: keras에서 모델을 그리기 위해 필요한 라이브러리 import

from keras.models import load_model: 저장된 모델을 불러오기 위한 라이브러리 import

from ~ SeqSelfAttention: SelfAttention을 보기 위한 라이브러리 import

model ~ -> 불러올 모델의 위치를 load_model을 통해 불러온 뒤 model로 선언

plot_model(model, to_file='./model.png'): model 을 그림으로 그리는 건데, 이 때 ./ 는 코드상의 디렉토리에 model.png 로 저장하겠다는 뜻이다.

저장된 모델은 다음과 같다.

Listen, Attend and Spell : A Neural Network for Large Vocabulary Conversational Speech Recognition 리뷰

이번에 읽은 논문은 Listen, Attend and Spell: A Neural Network for Large Vocabulary Conversational Speech Recognition 이다.

Carnegie Mellon 대학의 William Chan과 Google Brain팀에서 출간한 논문이며, 해당 논문은 https://arxiv.org/pdf/1508.01211.pdf 에서 볼 수 있다.

ICASSP2016에 제출 된 논문이다.

1. Abstract

 이 논문은 LAS(Listen, Attend and Spell) model을 소개하고 있다. LAS는 기존의 DNN-HMM모델과는 다른 스피치 발화를 문자로 변경해주는 뉴럴넷이다. 기존의 DNN-HMM모델과 다르다고 주장하는 이유는, 모든 것을 End-to-End로 학습하기 때문이라고 한다. 시스템은 크게 2개의 구성요소로 되어있는데 1개는 Encoder Part의 Listener, 1개는 Decoder Part의 Speller이다. Listener는 피라미드 모양의 RNN을 사용하고 있으며, 이 때 input 데이터로는 filter bank를 통과한 Spectrum들을 사용하고 있다. Speller는 Attention-Based RNN이며 Listener의 output을 input으로 받아 글자로 내뱉어주는 역할을 한다. 

 논문은 2015년 8월에 쓰여졌고, 이때 당시 state-of-the-art 였던 CLDNN-HMM 모델의 WER은 8.0% 였지만, 이 논문에서 제안하는 WER은 14.1%였다. 이 때, 14.1%는 사전이나 언어 모델 없이 학습하였을 때의 결과이고, 언어 모델을 사용할 때의 WER은 10.3%라고 한다.

2. Introduction

 (논문이 쓰여진 2015년 8월 즈음) State-of-the-art 음성인식 모델은 음향 모델(Acoustic Model), 언어 모델(Language Model), 명사 모델(Pronunciation), 언어 정규화(Text normalization) 등 다양한 구성 요소로 이루어진 복잡한 시스템이었다. 예를 들어 n-gram 언어 모델과 Hidden Markov Models (HMMs)은 문장 내의 단어/기호간 strong한 Markovian independence 추정을 만든다. CTC (Connectionist Temporal Classification)와 DNN-HMM 시스템은 뉴럴 네트워크가 독립된 예측을 다른 시간에서 하게끔 하고, HMM이나 언어 모델은 시간 경과에 따라 이러한 예측 간의 종속성을 도입하게 해준다.

 이렇듯, 2개 이상의 구성 요소를 합쳐서 음성 인식 시스템을 만들었지만, 이 논문에서 제안하는 바로는 End-to-End로 음성을 문자로 변경하는 시도를 보인다. 즉, input으로 음성을 받아서 언어 모델이나 명사 모델, Hmm 등을 쓰지 않고 output으로 character로 내보내는 것을 말한다. 이 방법은 Seq2Seq 학습 framework에 에 Attention 기법을 도입하는 것을 참고로 한다. Encoder로 Listener라는 이름을 갖는 RNN을 사용하고, decoder로 Speller라는 이름을 갖는 RNN을 사용한다.

3. Model and Methods

x = (x1, x2, ...., xt) 를 필터 뱅크를 통과한 스펙트럼 특징들인 입력 시퀀스로 두고, y = (<sos>, y1, ...., ys, <eos>)문자의 출력 순서라고 가정하자. 이 때, yi는 {a, ...., z, 0, ...., 9, <space>, <comma>, <period>, <apostrophe>, <unk>) 를 포함하는데, sos는 sentence의 시작 토큰이고, eos는 sentence의 종료 토큰이다.(start-of-sentence: sos, end-of-sentence: eos) 또한 <unk>는 악센트 문자와 같이 unknown token으로 가정하고 있으며, <space>, <comma>, <apostrophe> 같은 경우는 스페이스, 콤마, ' 와 같은 문자이다. 즉 알파벳 a~z, 숫자 0~9, 그리고 위에서 언급한 것들이 모두 y에 포함된다는 것이다.

LAS 모델은 각각의 출력 문자 yi를 이전 문자 y<i에 대한 조건부 분포로 모델링하고, 확률에 대한 Chain Rule을 사용하여 입력 신호 x를 y로 모델링 한다. 이때의 공식은 다음과 같다.

즉 주어진 음성 x에 대하여 출력문자 y가 될 확률은, 전체 문자 y < i(위에서의 a~z, 0~9, 등)에 대한 x의 조건부 분포(Conditional Distribution)로 모델링한다고 볼 수 있다. 위의 식은 음향 신호가 입력으로 들어오면, 문자 시퀀스의 조건부 확률을 직접 예측할 수 있기 때문에 모델을 차별화 된 End-to-End로 만들어 준다.

아래의 그림은 Paper에 개재된 그림으로 LAS 모델의 구조인 Listener(Encoder)와 Speller(Decoder)를 설명해주고 있다.

1) 먼저 Listener는 Encoder로서 음성 신호를 high level feature들로 변환하는 역할을 LAS내에서 맡고 있다. Listener는 BLSTM을 Pyramidal 형식으로 3개를 붙여서 사용하고 있다. 논문에서는 이를 pBLSTM으로 부르고 있으며, pyramidal 하게 사용하는 이유는 pBLSTM 1개당 연산속도를 2배로 줄여주기 때문이다. 

h를 Listen Encoder라 하고, i를 i-th time step이라하고, j를 from the j-th layer라 하였을 때,

3개의 BLSTM의 top of the bottom에 쌓은 pBLSTM은 time resolution을 2의 3승만큼, 즉 8 배만큼 줄여준다고 한다. 

2) Speller는 Decoder로서, attention-based LSTM 변환기 역할을 맡고 있다. 즉, 모든 출력 단계에서 변환기는 이전에 본 모든 문자를 조건으로 한 다음 문자에 대한 확률 분포를 생성한다. yi에 대한 분포는 디코더 상태 si 및 컨텍스트 ci의 함수이다. 디코더 상태 si는 이전 상태 si-1, 이전에 출력 된 문자 yi-1 및 컨텍스트 ci-1의 함수이다. 컨텍스트 벡터 ci는 attention-mechanism에 의해 생성된다.

여기서 CharacterDistribution은 charcter 위로 softmax 출력이있는 MLP이고 RNN은 2계층 LSTM이다.

매 time step마다, attention mechanism인 AttentionContext ci는 컨텍스트 벡터를 생성하고, 다음 문자를 생성하는데 필요한 음향 신호의 정보를 캡슐화한다. attention 모델은 내용 기반이며, 디코더 상태 si의 내용은 attention 벡터 ai를 생성하기 위해 h의 time step u를 나타내는 hu의 내용과 일치한다. 벡터 hu는 ai를 사용하여 linear하게 블렌딩되어 AttentionContext를 생성한다.

3) 이 모델의 학습은, 입력 음성에 대해 알맞는 sequence의 log probability를 maximize한다.  공식은 아래와 같다.

4) 디코딩 관련하여, test 시에 가장 근접한 character sequence를 주어진 음향에 대해 찾는다. 공식은 아래와 같다.

4. Experiments and results

 저자는 3백만개의 Google Voice Search utterances(2000시간의 데이터셋)를 이용했다. 거의 10시간의 발화들이 랜덤으로 선택되어 validation set으로 사용되었다. room simulator를 이용하여 Data Augmentation를 진행하였고, 이 때 기존 녹음된 것과 같은 reverberation과 noise를 추가했다.

 음성 데이터 input은 Mel-Spectrogram을 사용하여 number of mel을 40으로 주고 10ms마다 features들을 뽑았다 (40 dimensional log-mel filter bank). 

 Text Normalization은 모든 캐릭터들을 lower case English alphanumerics로 일반화 해주었다. 알파벳, 숫자, space, comma, period, apostrophe는 그대로 유지해주고 나머지들을 <unk> token으로 치환해주었다. 또한 맨 앞쪽에 언급한 것처럼, 모든 발화의 앞쪽에는 <sos>를, 끝쪽에는 <eos>를 패딩해주었다. 

논문이 쓰여진 당시의 State-of-the-art의 CLDNN-HMM의 Clean WER는 8.0이고, Noisy WER는 8.9였다. 논문 실험 결과인 LAS는 그보다 미치진 못하였다.

저자는 Listen Function에서(Encoder part) 3개의 pBLSTM을 쓰기 때문에 시간을 2^3= 8times 만큼 줄여준다고 주장하고 있다. weights들은 uniform distribution (-0.1, 0.1)로 초기화 하였다. Gradient는 Asynchronous Stochastic Gradient Descent (ASGD)를 train 하는데에 사용했다. learning rate는 0.2로 시작하여 20 에폭마다 0.98씩 decay를 하였다. 모델 학습하는 데에 거의 2주간의 시간이 걸렸다고 한다. 마지막으로 모델은 N-best list decoding으로 decode하였다. 

아래의 그림은 paper에 실린 그림으로, 문자와 입력 음성간의 할당 (Alignment)를 보여준다.

"how much would a woodchuck chuck" 라는 음성 input에 따른 character alignment를 보여주고 있다. Content based attention mechanism은 첫 번째 문자에 대한 오디오 시퀀스의 시작 위치를 올바르게 식별할 수 있었다고 한다. 생성 된 alignment(그림)은 일반적으로 위치 기반 prior가 없이도 단조로운걸 주장하고 있다. 

 Content based Attention Mechanism은 문자와 오디오 신호 사이의 명확한 정렬을 만들고 있다. 모든 문자의 output 시간 단계에서 audio 시퀀스에 attention distribution을 기록하여 attention mechanism을 visualization 할 수 있었다고 한다.

 이 논문에 쓰여진 2015년 8월 기준으로, 저자는 여러가지 end-to-end trained speech models이 폭발적으로 증가했다고 한다. 그러나 이 모델(

- A. Graves and N. Jaitly, “Towards End-to-End Speech Recognition with Recurrent Neural Networks,” in International Conference on Machine Learning, 2014. 

- Y. Miao, M. Gowayyed, and F. Metze, “EESEN: End-to-End Speech Recognition using Deep RNN Models and WFSTbased Decoding,” in Http://arxiv.org/abs/1507.08240, 2015.

- D. Bahdanau, J. Chorowski, D. Serdyuk, P. Brakel, and Y. Bengio, “End-to-end attention-based large vocabulary speech recognition,” in Http://arxiv.org/abs/1508.04395, 2015. 

- A. Hannun, C. Case, J. Casper, B. Catanzaro, G. Diamos, E. Elsen, R. Prenger, S. Satheesh, S. Sengupta, A. Coates, and A. Ng, “Deep Speech: Scaling up end-to-end speech recognition,” in Http://arxiv.org/abs/1412.5567, 2014. 

- A. Maas, Z. Xie, D. Jurafsky, and A. Ng, “Lexicon-free conversational speech recognition with neural networks,” in North American Chapter of the Association for Computational Linguistics, 2015. 

)들은 고유의 단점을 갖고 있고, 그 단점을 해결하기 위해 이 논문을 제안했다고 한다.

 논문에서 주장하는 이 단점이라 함은, 좋은 정확도를 얻기 위해서는 use of a strong language model during beam search decoding 이라고 표현되어 있따. 즉, 언어 모델 사용은 CTC 목적에 독립적으로 고정되어 훈련되기 때문이다.

 CTC는 또한 FST를 사용하여 음소 표적 및 n-gram 언어 모델을 사용하는 종단 간 교육에 적용되었지만, FST에서는 발음 사전과 언어 모델을 사용하기 때문에 LAS와는 다르다. 

- 여기에서 FST는 Finite-state Transducer 로서, 한국말로는 유한 상태 변환기이다.

- FST 관련 자료는 아래의 사이트에서 잘 나와있으니 참고해보면 될 듯.

1) https://m.blog.naver.com/PostView.nhn?blogId=taehun3718&logNo=140162190370&proxyReferer=https%3A%2F%2Fwww.google.com%2F

2) https://shleekr.github.io/2016/06/30/introducing-rouzeta/

 즉, CTC는 end-to-end 음성 인식에서 엄청난 가능성을 보여 주었지만, 1개의 frame의 output은 다른 frame의 출력에 영향을 미치지 않기 때문에 프레임 간 독립성의 가정에 의해 제한된다. 그리하여 CTC는 이 문제를 개선하기 위한 유일한 방법이 강력한 언어 모델을 사용 하는데, LAS의 저자는 이 점을 뽑아서 단점이라고 주장하고 있다.

 그렇다면 LAS는? 

 LAS는 시퀀스-시퀀스: Seq2Seq2 아키텍처를 기반으로하며 위의 단점을 겪지 않는다고 한다. LAS는 CTC의 단점을 해결하기 위해 첫 번째 문자에서 시작하여(sos) Chain Rule Decomposition을 사용하여 input sequence 가 주어진 경우 output sequence를 모델링 한다고 주장하고 있다. 또한 이 end-to-end LAS 모델은 음성 인식 시스템의 모든 측면 - 음향, 발음, 언어 모델 모두 해당 인코딩 - 을 포함한다고 주장한다. 따라서 저자는 LAS가 end-to-end 훈련 시스템이 아니라 end-to-end 모델이 될 수 있다고 주장한다. 굉장히 powerful 하다고 마지막에 주장하고 있다.

5. Conclusion

 저자는 Listen, Attend and Spell = LAS를 제안하고 있고, 음향 신호를 직접적으로 문자로 표현해줄 수 있는 모델인 LAS를 제안하고 있다. 이 모델에는 전통적인 음성인식 기법인 HMM(Hidden Markov Model), 언어 모델, 음향, 사전적인 구성 요소가 없이도 음성 인식이 가능한 것을 제안하고 있다. 이 LAS는 end-to-end trained system일 뿐만 아니라, 자체적으로 end-to-end 모델이라고 주장한다. LAS는 Seq2Seq framework를 사용하여 출력 sequence에 대한 조건부 독립 가정을 설정하지 않고 음성 인식이 가능하며, 이것은 CTC, DNN-HMM 및 end-to-end 훈련을 받을 수 있는 다른 모델과는 다르다고 주장한다.(조건 독립)

6. 간단 요약 및 느낀점

- Propose End-to-End Encoder-Decoder Model

- This model can End-to-End model (Not using HMMs, language model, etc)

- Transcribing Speech Utterances to Characters Task

- 14.1% WER w/o dictionary or language model, and 10.3% with language model. The Compare model is State-of-the-art CLDNN-HMM model achieves 8.0%

- 이 논문을 찾아보게 된 건 음성 인식 및 dialect 관련하여 자료를 찾다가 오래되었지만 LAS라는 모델을 기반으로 논문이 발행된 것이 있어서 찾게 되었다. 기존의 음성인식은 CTC에 언어모델을 접합하거나 GMM, HMM을 이용하여 하였지만, 이 논문 같은 경우 언어모델을 사용하지 않고도 어느정도의 WER를 뽑은 것을 확인할 수 있었다. 

- 다음에는 Dialect 인식 및 Attention Mechanism을 이용한 접근 법에 대해 찾아 볼 계획이다.

- 대학원생의 주관적인 생각이 들어있으므로 관련 논문에 대해 잘못된 부분이나 comment는 언제나 환영합니다.

문제 설명

1. 오픈채팅방

• 정답률: 59.91%
• 문제 풀러 가기

카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다.

신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다.

“[닉네임]님이 들어왔습니다.”

채팅방에서 누군가 나가면 다음 메시지가 출력된다.

“[닉네임]님이 나갔습니다.”

채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다.

• 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다.
• 채팅방에서 닉네임을 변경한다.

닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다.

예를 들어, 채팅방에 “Muzi”와 “Prodo”라는 닉네임을 사용하는 사람이 순서대로 들어오면 채팅방에는 다음과 같이 메시지가 출력된다.

“Muzi님이 들어왔습니다.” “Prodo님이 들어왔습니다.”

채팅방에 있던 사람이 나가면 채팅방에는 다음과 같이 메시지가 남는다.

“Muzi님이 들어왔습니다.” “Prodo님이 들어왔습니다.” “Muzi님이 나갔습니다.”

Muzi가 나간후 다시 들어올 때, Prodo 라는 닉네임으로 들어올 경우 기존에 채팅방에 남아있던 Muzi도 Prodo로 다음과 같이 변경된다.

“Prodo님이 들어왔습니다.” “Prodo님이 들어왔습니다.” “Prodo님이 나갔습니다.” “Prodo님이 들어왔습니다.”

채팅방은 중복 닉네임을 허용하기 때문에, 현재 채팅방에는 Prodo라는 닉네임을 사용하는 사람이 두 명이 있다. 이제, 채팅방에 두 번째로 들어왔던 Prodo가 Ryan으로 닉네임을 변경하면 채팅방 메시지는 다음과 같이 변경된다.

“Prodo님이 들어왔습니다.” “Ryan님이 들어왔습니다.” “Prodo님이 나갔습니다.” “Prodo님이 들어왔습니다.”

채팅방에 들어오고 나가거나, 닉네임을 변경한 기록이 담긴 문자열 배열 record가 매개변수로 주어질 때, 모든 기록이 처리된 후, 최종적으로 방을 개설한 사람이 보게 되는 메시지를 문자열 배열 형태로 return 하도록 solution 함수를 완성하라.

제한사항

• record는 다음과 같은 문자열이 담긴 배열이며, 길이는 1 이상 100,000 이하이다.
• 다음은 record에 담긴 문자열에 대한 설명이다.
  • 모든 유저는 [유저 아이디]로 구분한다.
  • [유저 아이디] 사용자가 [닉네임]으로 채팅방에 입장 - “Enter [유저 아이디] [닉네임]” (ex. “Enter uid1234 Muzi”)
  • [유저 아이디] 사용자가 채팅방에서 퇴장 - “Leave [유저 아이디]” (ex. “Leave uid1234”)
  • [유저 아이디] 사용자가 닉네임을 [닉네임]으로 변경 - “Change [유저 아이디] [닉네임]” (ex. “Change uid1234 Muzi”)
  • 첫 단어는 Enter, Leave, Change 중 하나이다.
  • 각 단어는 공백으로 구분되어 있으며, 알파벳 대문자, 소문자, 숫자로만 이루어져있다.
  • 유저 아이디와 닉네임은 알파벳 대문자, 소문자를 구별한다.
  • 유저 아이디와 닉네임의 길이는 1 이상 10 이하이다.
  • 채팅방에서 나간 유저가 닉네임을 변경하는 등 잘못 된 입력은 주어지지 않는다.

입출력 예

입출력 예 설명

입출력 예 #1 문제의 설명과 같다.

문제 풀이

첫 번째 문제답게 큰 고민 없이 연관 배열(맵)을 이용해서 쉽게 풀 수 있습니다.

record 를 순회 하면서

• Enter, Leave 인 경우 유저 아이디와 함께 정답에 출력될 메시지의 종류를 기록을 해둡니다. 이렇게 기록해둔 것을 events 라고 합시다.
• Enter, Change 인 경우 연관 배열을 이용하여 각 유저 아이디를 키로, 닉네임을 값으로 저장해 둡니다. 이렇게 해서 최종 닉네임을 유저 아이디별로 유지합니다.

이제 events 를 순회하면서 채팅방에 출력할 메시지를 생성할 때, 연관 배열에 저장된 아이디별 최종 닉네임을 이용하면 됩니다.

2. 실패율

• 정답률: 55.57%
• 문제 풀러 가기

슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.

이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

• 실패율은 다음과 같이 정의한다.
  • 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

제한사항

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• stages의 길이는 1 이상 200,000 이하이다.
• stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
  • 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
  • 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

입출력 예

입출력 예 설명

입출력 예 #1

1번 스테이지에는 총 8명의 사용자가 도전했으며, 이 중 1명의 사용자가 아직 클리어하지 못했다. 따라서 1번 스테이지의 실패율은 다음과 같다.

• 1번 스테이지 실패율 : 1/8

2번 스테이지에는 총 7명의 사용자가 도전했으며, 이 중 3명의 사용자가 아직 클리어하지 못했다. 따라서 2번 스테이지의 실패율은 다음과 같다.

• 2번 스테이지 실패율 : 3/7

마찬가지로 나머지 스테이지의 실패율은 다음과 같다.

• 3번 스테이지 실패율 : 2/4
• 4번 스테이지 실패율 : 1/2
• 5번 스테이지 실패율 : 0/1

각 스테이지의 번호를 실패율의 내림차순으로 정렬하면 다음과 같다.

• [3,4,2,1,5]

입출력 예 #2

모든 사용자가 마지막 스테이지에 있으므로 4번 스테이지의 실패율은 1이며 나머지 스테이지의 실패율은 0이다.

• [4,1,2,3]

문제 풀이

문제를 읽어보면 알 수 있듯이 이 문제는 정렬을 이용해서 풀 수 있습니다.

먼저 주어진 배열의 길이를 이용하여 전체 사용자 수를 구하고, stages 를 순회하며 각 스테이지에 몇 명의 사용자가 도달했는지 세줍니다. 이렇게 만들어둔 배열(각 스테이지별 사용자 수가 들어있는)을 순회하면서 stages 를 참고하여 스테이지별 실패율을 계산합니다. 이때, 스테이지에 도달한 사용자가 0명인 경우 예외 처리를 해야 합니다. 스테이지별 실패율을 구했다면, 각 스테이지 번호와 묶어서 실패율 내림차순으로 정렬합니다. 실패율이 같은 경우는 스테이지 번호가 작은 것을 먼저 오도록 정렬하면 됩니다.

3. 후보키

• 정답률: 16.09%
• 문제 풀러 가기

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.

후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

• 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
  • 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
  • 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.

위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 “학번”을 가지고 있다. 따라서 “학번”은 릴레이션의 후보 키가 될 수 있다. 그다음 “이름”에 대해서는 같은 이름(“apeach”)을 사용하는 학생이 있기 때문에, “이름”은 후보 키가 될 수 없다. 그러나, 만약 [“이름”, “전공”]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다. 물론 [“이름”, “전공”, “학년”]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다. 따라서, 위의 학생 인적사항의 후보키는 “학번”, [“이름”, “전공”] 두 개가 된다.

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

제한사항

• relation은 2차원 문자열 배열이다.
• relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
• relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

입출력 예

입출력 예 설명

입출력 예 #1 문제에 주어진 릴레이션과 같으며, 후보 키는 2개이다.

문제 풀이

가능한 모든 어트리뷰트의 조합을 만들고, 이 조합에서 조건을 만족시키는 조합만 추려야 하는 문제입니다.

dfs 또는 bit 를 이용한 집합 표현을 이용하여 어트리뷰트의 모든 부분 집합을 만들어냅니다.
만들어지는 각 부분 집합을 이용해서 중복 튜플이 있는지 검사합니다. 만약 중복 튜플이 없다면, 이 부분 집합을 슈퍼 키 집합(유일성을 만족하는 키들의 집합)에 포함시킵니다.

슈퍼 키 집합을 구한 후, 여기서 최소성을 만족하는 키들을 선택하여 후보 키 집합을 만들 수 있습니다.
만약 어떤 슈퍼 키 X에 대해 X의 부분집합인 슈퍼 키 Y가 없다면 (X ⊃ Y인 슈퍼 키 Y가 없다면) X는 후보 키로 선택될 수 있습니다.

예를 들어 어떤 릴레이션의 어트리뷰트가 ABCDE 이고, 슈퍼 키 집합이 {A, AB, BC, BCE, BDE, …} 라고 해봅시다.

• A 는 후보 키로 선택될 수 있습니다.
• AB 는 AB ⊃ A 이므로 후보 키가 될 수 없습니다.
• BC 는 부분집합이 되는 다른 슈퍼 키가 없으므로 후보 키로 선택됩니다.
• BCE 는 BCE ⊃ BC 이므로 후보 키가 될 수 없습니다.
• BDE 는 부분집합이 되는 다른 슈퍼 키가 없으므로 후보 키로 선택됩니다.
• …

따라서 이 경우 후보 키 집합은 {A, BC, BDE, …} 가 됩니다.

가능한 모든 조합을 만드는 부분 때문인지 앞쪽에 배치된 문제임에도 많은 지원자들이 어려움을 겪은 것으로 보입니다.

4. 무지의 먹방 라이브

• 정답률: 정확성 42.08% / 효율성 5.52%
• 문제 풀러 가기

* 효율성 테스트에 부분 점수가 있는 문제입니다.

평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.

그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.

회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다.

• 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
• 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
• 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
  • 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
• 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.

무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다. 무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다. 각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.

제한사항

• food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
• k 는 방송이 중단된 시간을 나타낸다.
• 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.

정확성 테스트 제한 사항

• food_times 의 길이는 1 이상 2,000 이하이다.
• food_times 의 원소는 1 이상 1,000 이하의 자연수이다.
• k는 1 이상 2,000,000 이하의 자연수이다.

효율성 테스트 제한 사항

• food_times 의 길이는 1 이상 200,000 이하이다.
• food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
• k는 1 이상 2 x 10^13 이하의 자연수이다.

입출력 예

입출력 예 설명

입출력 예 #1

• 0~1초 동안에 1번 음식을 섭취한다. 남은 시간은 [2,1,2] 이다.
• 1~2초 동안 2번 음식을 섭취한다. 남은 시간은 [2,0,2] 이다.
• 2~3초 동안 3번 음식을 섭취한다. 남은 시간은 [2,0,1] 이다.
• 3~4초 동안 1번 음식을 섭취한다. 남은 시간은 [1,0,1] 이다.
• 4~5초 동안 (2번 음식은 다 먹었으므로) 3번 음식을 섭취한다. 남은 시간은 [1,0,0] 이다.
• 5초에서 네트워크 장애가 발생했다. 1번 음식을 섭취해야 할 때 중단되었으므로, 장애 복구 후에 1번 음식부터 다시 먹기 시작하면 된다.

문제 풀이

이 문제를 완전히 해결하려면 효율성 테스트를 통과해야 합니다.
효율성 테스트의 제한 사항은 정확성 테스트보다 까다롭기 때문에 정확성 테스트를 통과한 풀이를 그대로 적용하면 시간 초과가 발생합니다. 따라서, 실행 시간을 줄일 수 있는 아이디어가 필요합니다.

정확성 풀이

시간이 1초 지날 때마다 다음 먹을 음식을 반복문을 이용해 하나하나 찾아가며 시뮬레이션하면 됩니다.

효율성 풀이

먼저 음식별 필요 시간을 오름차순으로 정렬합니다. 시간의 오름차순으로 정렬해두면 음식을 먹는 데 소요되는 시간을 한꺼번에 지울 수 있습니다. 예를 들어 정렬한 시간이 T = [1, 3, 3, 4, 5]라면 처음에 T[0] * 5 = 5만큼의 시간을 한꺼번에 지울 수 있습니다. 다음으로 T[1]부터 남은 시간을 한꺼번에 제거합니다. 즉, (T[1] - T[0]) * 4 = 8 만큼의 시간을 한꺼번에 지웁니다. 마찬가지로 (T[2] - T[1]) * 3 = 0 만큼의 시간을 한꺼번에 지울 수 있습니다.

위와 같은 방법으로 시간을 지워가다가, 지운 시간의 합이 K 보다 커지게 되면 남은 시간의 개수로 나눈 나머지를 이용해 K 초 후 다시 먹기 시작해야 될 음식의 번호를 바로 구할 수 있습니다. 이때, 남은 시간을 다시 원래 음식의 번호 순서대로 재정렬해야 합니다.

꼭 이 방법이 아니라도 K에 도달하는 시점을 빠르게 구할 수만 있으면 실행 시간을 줄일 수 있습니다.

5. 길 찾기 게임

• 정답률: 7.40%
• 문제 풀러 가기

전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다.

라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다.

그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다.

라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.

• 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
• 모든 노드는 서로 다른 x값을 가진다.
• 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
• 자식 노드의 y 값은 항상 부모 노드보다 작다.
• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

아래 예시를 확인해보자.

라이언의 규칙에 맞게 이진트리의 노드만 좌표 평면에 그리면 다음과 같다. (이진트리의 각 노드에는 1부터 N까지 순서대로 번호가 붙어있다.)

이제, 노드를 잇는 간선(edge)을 모두 그리면 아래와 같은 모양이 된다.

위 이진트리에서 전위 순회(preorder), 후위 순회(postorder)를 한 결과는 다음과 같고, 이것은 각 팀이 방문해야 할 순서를 의미한다.

• 전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3
• 후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7

다행히 두 팀 모두 머리를 모아 분석한 끝에 라이언의 의도를 간신히 알아차렸다.
그러나 여전히 문제는 남아있다. 노드의 수가 예시처럼 적다면 쉽게 해결할 수 있겠지만, 예상대로 라이언은 그렇게 할 생각이 전혀 없었다.

이제 당신이 나설 때가 되었다.

곤경에 빠진 카카오 프렌즈를 위해 이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때, 노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return 하도록 solution 함수를 완성하자.

제한사항

• nodeinfo는 이진트리를 구성하는 각 노드의 좌표가 1번 노드부터 순서대로 들어있는 2차원 배열이다.
  • nodeinfo의 길이는 1 이상 10,000 이하이다.
  • nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다.
  • 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수이다.
  • 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다.
  • 모든 노드의 좌표는 문제에 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.

입출력 예

입출력 예 설명

입출력 예 #1

문제에 주어진 예시와 같다.

문제 풀이

트리를 순회하는 방법은 검색을 통해 쉽게 알 수 있으므로 문제가 되지 않습니다. 이 문제의 핵심은 좌표 값으로 주어지는 노드들을 트리로 구성하는 부분입니다.

트리를 만들기 위해 y 값을 이용해서 각 노드의 level 을 분리하고, 현재 노드의 자식 노드가 가질 수 있는 x값을 이용하여 현재 노드의 왼쪽, 오른쪽 자식을 정확히 찾는 것이 중요합니다.

각 노드의 왼쪽, 오른쪽 자식 노드는 다음과 같이 찾을 수 있습니다.

먼저 현재 노드 P의 x값을 Px, 현재 노드의 자식 노드가 가질 수 있는 x 범위를 Lx, Rx (Lx < Px < Rx)라고 하겠습니다. 또 어떤 노드 K의 x값을 Kx 라고 하겠습니다. 만약 현재 노드의 바로 다음 레벨에 Lx ≤ Kx < Px를 만족하는 노드 K가 있다면 K는 노드 P의 왼쪽 자식이 됩니다. 이때, 노드 K의 자식 노드가 가질 수 있는 x값의 범위는 Lx ≤ x ≤ Px - 1 (x ≠ Kx)가 됩니다.

마찬가지로 현재 노드의 바로 다음 레벨에 Px < Kx ≤ Rx를 만족하는 노드 K가 있다면 K는 노드 P의 오른쪽 자식이 되며, 노드 K의 자식 노드가 가질 수 있는 x의 범위는 Px + 1 ≤ x ≤ Rx (x ≠ Kx)가 됩니다.

위 과정을 재귀적으로 반복하면서 각 노드의 왼쪽, 오른쪽 자식을 찾아주면 트리를 구성할 수 있습니다.

노드별 왼쪽, 오른쪽 자식을 찾는 방법은 여러 가지가 있을 수 있습니다. 그중 하나로, 재귀적으로 순회하며 트리를 만들면 같은 level의 노드는 x값이 작은 노드부터 방문하게 되므로, 큐를 트리의 레벨만큼 만들어 두고, x축 기준으로 오름차순 정렬된 노드들을 y축 값이 같은 노드끼리 각 큐에 넣어두면 큐의 front를 확인하는 방법으로 O(1)에 찾을 수 있습니다.

이렇게 하면 노드의 수가 N일 때, 트리를 구성하는 데는 O(N) 시간이 소요되며, 시간 복잡도는 전체 노드를 정렬하는데 걸리는 시간인 O(NlogN)이 됩니다.

6. 매칭 점수

• 정답률: 6.12%
• 문제 풀러 가기

프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다. 그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.

• 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
• 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
• 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
• 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
• 한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.

예를 들어, 다음과 같이 A, B, C 세 개의 웹페이지가 있고, 검색어가 hi라고 하자.

이때 A 웹페이지의 매칭점수는 다음과 같이 계산할 수 있다.

• 기본 점수는 각 웹페이지에서 hi가 등장한 횟수이다.
  • A,B,C 웹페이지의 기본점수는 각각 1점, 4점, 9점이다.
• 외부 링크수는 다른 웹페이지로 링크가 걸린 개수이다.
  • A,B,C 웹페이지의 외부 링크 수는 각각 1점, 2점, 3점이다.
• A 웹페이지로 링크가 걸린 페이지는 B와 C가 있다.
  • A 웹페이지의 링크점수는 B의 링크점수 2점(4 ÷ 2)과 C의 링크점수 3점(9 ÷ 3)을 더한 5점이 된다.
• 그러므로, A 웹페이지의 매칭점수는 기본점수 1점 + 링크점수 5점 = 6점이 된다.

검색어 word와 웹페이지의 HTML 목록인 pages가 주어졌을 때, 매칭점수가 가장 높은 웹페이지의 index를 구하라. 만약 그런 웹페이지가 여러 개라면 그중 번호가 가장 작은 것을 구하라.

제한사항

• pages는 HTML 형식의 웹페이지가 문자열 형태로 들어있는 배열이고, 길이는 1 이상 20 이하이다.
• 한 웹페이지 문자열의 길이는 1 이상 1,500 이하이다.
• 웹페이지의 index는 pages 배열의 index와 같으며 0부터 시작한다.
• 한 웹페이지의 url은 HTML의 <head> 태그 내에 <meta> 태그의 값으로 주어진다.
  • 예를들어, 아래와 같은 meta tag가 있으면 이 웹페이지의 url은 https://careers.kakao.com/index 이다.
  • <meta property=”og:url” content=”https://careers.kakao.com/index” />
• 한 웹페이지에서 모든 외부 링크는 <a href=”https://careers.kakao.com/index”>의 형태를 가진다.
  • <a> 내에 다른 attribute가 주어지는 경우는 없으며 항상 href로 연결할 사이트의 url만 포함된다.
  • 위의 경우에서 해당 웹페이지는 https://careers.kakao.com/index 로 외부링크를 가지고 있다고 볼 수 있다.
• 모든 url은 https:// 로만 시작한다.
• 검색어 word는 하나의 영어 단어로만 주어지며 알파벳 소문자와 대문자로만 이루어져 있다.
• word의 길이는 1 이상 12 이하이다.
• 검색어를 찾을 때, 대소문자 구분은 무시하고 찾는다.
  • 예를들어 검색어가 blind일 때, HTML 내에 Blind라는 단어가 있거나, BLIND라는 단어가 있으면 두 경우 모두 해당된다.
• 검색어는 단어 단위로 비교하며, 단어와 완전히 일치하는 경우에만 기본 점수에 반영한다.
  • 단어는 알파벳을 제외한 다른 모든 문자로 구분한다.
  • 예를들어 검색어가 “aba” 일 때, “abab abababa”는 단어 단위로 일치하는게 없으니, 기본 점수는 0점이 된다.
  • 만약 검색어가 “aba” 라면, “aba@aba aba”는 단어 단위로 세개가 일치하므로, 기본 점수는 3점이다.
• 결과를 돌려줄때, 동일한 매칭점수를 가진 웹페이지가 여러 개라면 그중 index 번호가 가장 작은 것를 리턴한다
  • 즉, 웹페이지가 세개이고, 각각 매칭점수가 3,1,3 이라면 제일 적은 index 번호인 0을 리턴하면 된다.

입출력 예 #1

• word : blind

• pages :

  ["<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://a.com\"/>\n</head>  \n<body>\nBlind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. \n<a href=\"https://b.com\"> Link to b </a>\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://b.com\"/>\n</head>  \n<body>\nSuspendisse potenti. Vivamus venenatis tellus non turpis bibendum, \n<a href=\"https://a.com\"> Link to a </a>\nblind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut.\n<a href=\"https://c.com\"> Link to c </a>\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://c.com\"/>\n</head>  \n<body>\nUt condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind\n<a href=\"https://a.com\"> Link to a </a>\n</body>\n</html>"]
  

• pages는 다음과 같이 3개의 웹페이지에 해당하는 HTML 문자열이 순서대로 들어있다.

<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta charset="utf-8">
  <meta property="og:url" content="https://a.com"/>
</head>  
<body>
Blind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. 
<a href="https://b.com"> Link to b </a>
</body>
</html>

<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta charset="utf-8">
  <meta property="og:url" content="https://b.com"/>
</head>  
<body>
Suspendisse potenti. Vivamus venenatis tellus non turpis bibendum, 
<a href="https://a.com"> Link to a </a>
blind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut.
<a href="https://c.com"> Link to c </a>
</body>
</html>

<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta charset="utf-8">
  <meta property="og:url" content="https://c.com"/>
</head>  
<body>
Ut condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind
<a href="https://a.com"> Link to a </a>
</body>
</html>

위의 예를 가지고 각각의 점수를 계산해보자.

• 기본점수 및 외부 링크수는 아래와 같다.
  • a.com의 기본점수는 3, 외부 링크 수는 1개
  • b.com의 기본점수는 1, 외부 링크 수는 2개
  • c.com의 기본점수는 1, 외부 링크 수는 1개
• 링크점수는 아래와 같다.
  • a.com의 링크점수는 b.com으로부터 0.5점, c.com으로부터 1점
  • b.com의 링크점수는 a.com으로부터 3점
  • c.com의 링크점수는 b.com으로부터 0.5점
• 각 웹 페이지의 매칭 점수는 다음과 같다.
  • a.com : 4.5 점
  • b.com : 4 점
  • c.com : 1.5 점

따라서 매칭점수가 제일 높은 첫번째 웹 페이지의 index인 0을 리턴 하면 된다.

입출력 예 #2

• word : Muzi

• pages :

  ["<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://careers.kakao.com/interview/list\"/>\n</head>  \n<body>\n<a href=\"https://programmers.co.kr/learn/courses/4673\"></a>#!MuziMuzi!)jayg07con&&\n\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://www.kakaocorp.com\"/>\n</head>  \n<body>\ncon%\tmuzI92apeach&2<a href=\"https://hashcode.co.kr/tos\"></a>\n\n\t^\n</body>\n</html>"]
  

• pages는 다음과 같이 2개의 웹페이지에 해당하는 HTML 문자열이 순서대로 들어있다.

<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta charset="utf-8">
  <meta property="og:url" content="https://careers.kakao.com/interview/list"/>
</head>  
<body>
<a href="https://programmers.co.kr/learn/courses/4673"></a>#!MuziMuzi!)jayg07con&&

</body>
</html>

<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta charset="utf-8">
  <meta property="og:url" content="https://www.kakaocorp.com"/>
</head>  
<body>
con%	muzI92apeach&2<a href="https://hashcode.co.kr/tos"></a>

	^
</body>
</html>

• 기본점수 및 외부 링크수는 아래와 같다.

  • careers.kakao.com/interview/list 의 기본점수는 0, 외부 링크 수는 1개
  • www.kakaocorp.com 의 기본점수는 1, 외부 링크 수는 1개

• 링크점수는 아래와 같다.

  • careers.kakao.com/interview/list 의 링크점수는 0점
  • www.kakaocorp.com 의 링크점수는 0점

• 각 웹 페이지의 매칭 점수는 다음과 같다.

  • careers.kakao.com/interview/list : 0점
  • www.kakaocorp.com : 1 점

따라서 매칭점수가 제일 높은 두번째 웹 페이지의 index인 1을 리턴 하면 된다.

문제 풀이

점수를 계산하는 로직 자체는 복잡하지 않지만, 점수 계산에 필요한 요소들을 잘 추출해야 하는 문제입니다.

정규표현식을 이용하거나 문자열 처리 로직을 구현해서 a 태그와 meta 태그를 찾아 현재 페이지의 URL 과 외부 링크의 URL 을 찾습니다. 또한, 전체 HTML 문서를 대상으로 검색어가 몇 번 등장하는지 찾습니다. 이때, 제시된 조건에 맞게 단어를 찾을 수 있도록 적절히 split 하여 비교합니다. 각 HTML 문서별 기본 점수, 외부 링크 수를 구하고, 해당 웹페이지로 링크가 걸린 다른 웹페이지들을 찾아 링크 점수를 계산합니다.

마지막으로 각 페이지의 매칭 점수를 구하고, 최댓값을 갖는 문서의 인덱스를 구하면 됩니다.

7. 블록 게임

• 정답률: 5.85%
• 문제 풀러 가기

프렌즈 블록이라는 신규 게임이 출시되었고, 어마어마한 상금이 걸린 이벤트 대회가 개최 되었다.

이 대회는 사람을 대신해서 플레이할 프로그램으로 참가해도 된다는 규정이 있어서, 게임 실력이 형편없는 프로도는 프로그램을 만들어서 참가하기로 결심하고 개발을 시작하였다.

프로도가 우승할 수 있도록 도와서 빠르고 정확한 프로그램을 작성해 보자.

게임규칙

아래 그림과 같이 1×1 크기의 블록을 이어 붙여 만든 3 종류의 블록을 회전해서 총 12가지 모양의 블록을 만들 수 있다.

1 x 1 크기의 정사각형으로 이루어진 N x N 크기의 보드 위에 이 블록들이 배치된 채로 게임이 시작된다. (보드 위에 놓인 블록은 회전할 수 없다). 모든 블록은 블록을 구성하는 사각형들이 정확히 보드 위의 사각형에 맞도록 놓여있으며, 선 위에 걸치거나 보드를 벗어나게 놓여있는 경우는 없다.

플레이어는 위쪽에서 1 x 1 크기의 검은 블록을 떨어뜨려 쌓을 수 있다. 검은 블록은 항상 맵의 한 칸에 꽉 차게 떨어뜨려야 하며, 줄에 걸치면 안된다. 이때, 검은 블록과 기존에 놓인 블록을 합해 속이 꽉 채워진 직사각형을 만들 수 있다면 그 블록을 없앨 수 있다.

예를 들어 검은 블록을 떨어뜨려 아래와 같이 만들 경우 주황색 블록을 없앨 수 있다.

빨간 블록을 가로막던 주황색 블록이 없어졌으므로 다음과 같이 빨간 블록도 없앨 수 있다.

그러나 다른 블록들은 검은 블록을 떨어뜨려 직사각형으로 만들 수 없기 때문에 없앨 수 없다.

따라서 위 예시에서 없앨 수 있는 블록은 최대 2개이다.

보드 위에 놓인 블록의 상태가 담긴 2차원 배열 board가 주어질 때, 검은 블록을 떨어뜨려 없앨 수 있는 블록 개수의 최댓값을 구하라.

제한사항

• board는 블록의 상태가 들어있는 N x N 크기 2차원 배열이다.
  • N은 4 이상 50 이하다.
• board의 각 행의 원소는 0 이상 200 이하의 자연수이다.
  • 0 은 빈 칸을 나타낸다.
  • board에 놓여있는 각 블록은 숫자를 이용해 표현한다.
  • 잘못된 블록 모양이 주어지는 경우는 없다.
  • 모양에 관계 없이 서로 다른 블록은 서로 다른 숫자로 표현됩니다.
  • 예를 들어 문제에 주어진 예시의 경우 다음과 같이 주어진다.

입출력 예

입출력 예 설명

입출력 예 #1 문제에 주어진 예시와 같음

문제 풀이

문제를 이해하는 것은 어렵지 않지만 제거해야 할 블록을 찾기 위한 아이디어가 필요합니다.

문제에서는 검은 블록을 떨어뜨린다고 되어있으나, 실제로 검은 블록을 떨어뜨리지 않고 순서대로 검은 블록으로 채워 나가기만 해도 삭제될 블록을 찾을 수 있습니다. 먼저 게임 보드의 왼쪽 위(혹은 오른쪽 위)부터 가로 방향으로 한 줄씩 순서대로 진행하면서 빈칸에 검은 블록을 채울 수 있는지 확인합니다. 현재 칸이 빈칸이라면 위쪽으로 삭제되지 않은 블록이 있는지 확인합니다. 만약 다른 블록이 없다면 검은 블록으로 채우고, 그렇지 않으면 그대로 빈칸으로 둡니다.

칸 하나를 확인한 후에는 해당 칸을 포함하는 칸 중에서 삭제할 수 있는 블록이 있는지 확인합니다. 블록이 사라질 수 있는지 판단은 검은 블록 두 개와 같은 색 블록 4개가 2x3, 3x2의 직사각형 안에 들어있는지 확인하면 됩니다.

블록을 지운 경우에 지워진 칸을 그대로 둘지, 혹은 검은 블록으로 채울지 확인하는 과정이 필요합니다. 블록이 삭제된 칸이어도 검은 블록으로 채울 수 없는 경우가 있기 때문입니다. 지워진 칸을 기준으로 위쪽에 삭제되지 않은 블록이 있는지 확인하여 검은 블록을 적절히 채웁니다(삭제되는 블록을 찾는 방향에 따라 조금 다를 수도 있습니다).

블록이 삭제되면 카운트를 1 증가시키고, 게임 보드의 모든 칸에 대해 삭제될 블록을 찾은 후 카운트된 값을 반환하면 됩니다.

또 다른 방법으로, 문제의 설명대로 위에서 블록을 떨어뜨려서 없앨 수 있는 블록을 차례대로 찾아서 제거하는 것을 생각해 볼 수 있습니다.

도형의 모양을 자세히 보면, 제거할 수 있는 도형은 채워야 할 공간이 위쪽으로 열려있는 5가지뿐임을 알 수 있습니다. 최상단 좌측부터 검사를 시작해 도형이 있는 칸(0보다 큰 값)을 만나면, 주변 값들을 확인해서 제거 가능한 도형 중 하나인지를 체크합니다. 만약, 제거 가능한 도형 중 하나라면 도형에서 채워야 하는 공간부터 최상단까지 모든 값이 비어있는지를 체크합니다. 모두 비어있다면 이는 없앨 수 있다는 뜻이므로 이 도형을 0으로 채워 제거합니다.

제거 가능한 도형을 모두 찾을 때까지 이 과정을 반복하고, 도형을 제거할 때마다 카운트를 증가시켜주면 됩니다.

마무리하며

지금까지 1차 코딩 테스트 문제와 풀이에 대해 살펴봤습니다.

아마 문제를 풀어본 분이라면 고개가 끄덕여지는 부분도 있을 것이고, 자신의 풀이와 차이점도 확인할 수 있었을 것 같네요. 모쪼록 이 글이 도움이 되었으면 좋겠습니다.

마지막으로, 5시간 동안 테스트에 응해주신 지원자분들께 감사드립니다. 모두 고생 많으셨고 2차 오프라인 테스트에서 만날 수 있길 바라봅니다. : )

출처: http://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

Machine을 이용 후 CUDA가 초기화가 되지 않거나, 잔여 메모리가 nvidia-smi 할 때 GPU에 남아 있는 현상이 가끔 일어나는데,

아래와 같이 python으로 하나 짜둔 뒤 실행해보면 처리가 된다.

initialized_machine.py

먼저 pip란 Python으로 작성된 package software를 install & uninstall 하는 package management system이다.

Python Package Index (PyPI)에서 많은 Python package를 찾을 수 있다.

package 설치 및 제거를 쉽게 할 수 있는데,

이 때 pip와 pip3가 존재하는데, 두 개의 차이를 간단하게 설명하면 다음과 같다.

pip : python2 버전

pip3 : python3 버전

가령, python3 버전으로 tensorflow-gpu를 설치하고 싶으면 다음과 같이 하면 된다.

Python package 중 pip3 install ~~ 만 해도 되는 것들이 많지만,

tensorflow-gpu는 반드시 sudo 로 설치를 추천한다.

수정합니다. pip3 install --user tensorflow-gpu 로 10대 이상의 server에 설치하여 사용해보아도 아무문제 없습니다. 공용으로 사용하실 것이면 sudo 설치를 피해주세요.

일반적으로 우분투를 설치하자마자 커맨드창에 python을 입력하면

python2.7 버전이 뜬다.

이를 3버전으로 바꾸고 싶으면

1. vi ~/.bashrc 입력

2. 맨 아래에 

입력

3. 저장 후 source ~/.bashrc 입력

커맨드 창에 python 입력하면 python3.5로 변경 됨

python3이 설치되어 있지 않다면 설치해준 뒤 위의 작업 진행

출처 : http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

‘블라인드’ 전형으로 실시되어 시작부터 엄청난 화제를 몰고 온 카카오 개발 신입 공채. 그 첫 번째 관문인 1차 코딩 테스트가 지난 9월 16일(토) 오후 2시부터 7시까지 장장 5시간 동안 온라인으로 치러졌습니다. 지원자들의 개발 능력을 잘 검증하기 위해 출제 위원들이 한 땀 한 땀 독창적이고 다양한 문제들을 만들어 냈고 문제에 이상은 없는지, 테스트케이스는 정확한지 풀어보고 또 풀어보며 만반의 준비를 기했습니다.

먼저, 가장 궁금해하실 1차 합격 기준부터 알려드립니다. 1차 합격 기준은 총 7 문제 중 4 문제 이상을 풀이한 분들입니다. 참고로 각 문제는 배점이 동일하므로 어떤 문제를 풀었던지 간에 관계는 없습니다.

문제는 쉬운 난이도에서 어려운 난이도 순으로 풀 수 있도록 차례대로 배치했는데요. 앞서 얘기했듯 모든 문제는 배점이 동일하며 부분 점수는 없습니다. 즉, 채점 테스트케이스를 하나만 틀려도 오답으로 처리가 됩니다. 하지만 입출력 예제에 대부분의 예외 사항을 포함했고 따라서 입출력 테스트를 정상적으로 통과했다면 채점도 무리 없이 통과할 수 있도록 구성했습니다. 아울러 이번 코딩 테스트는 대회가 아니라 채용을 위한 시험인 만큼 ACM-ICPC 같은 어려운 알고리즘 설계 능력을 겨루는 문제가 아닌 업무에서 있을만한 상황을 가정하여 독창적이고 다양한 분야의 문제를 출제했고, 난이도 또한 비교적 쉬운 수준으로 조정하였습니다. 일반적으로 자료구조, 알고리즘 등의 전산학 기초에 대해 충분히 학습하였다면 누구나 풀 수 있을만한 문제들로 구성했습니다.

언어별 통계

참가 언어별로는 자바가 전체의 43%로 가장 많았습니다. 그다음이 C++ 36%, 파이썬 11%, 자바스크립트 8% 순이었는데요. 스위프트는 0.7%의 참가자만이 선택하여 아직 스위프트가 주류로 성장하기엔 좀 더 시간이 필요해 보였습니다.

• 참가 언어: 자바 > C++ > 파이썬 > 자바스크립트 > 스위프트

4문제 이상을 풀이한 합격자의 비율은 C++이 25%로 가장 높았습니다. 그다음으로 파이썬이 24%로 근소한 차이로 뒤를 쫓고 있고, 참가자가 매우 적었던 스위프트도 20%로 합격률은 비교적 높았습니다. 그러나, 참가자가 가장 많았던 자바는 11%의 합격률 밖에 보여주지 못했으며 아쉽게도 자바스크립트의 경우 합격률이 9%에 불과했습니다.

• 합격 비율: C++ > 파이썬 > 스위프트 > 자바 > 자바스크립트

풀이한 언어의 평균 코드 라인 수를 알아볼까요?
C++이 평균적으로 가장 긴 라인 수를 자랑했습니다. 4번과 6번 문제는 78라인이나 필요했네요. 그다음은 근소한 차이로 자바입니다. 크게 차이가 나진 않지만 C++에 비해 평균적으로 5 ~ 6라인 정도가 짧았습니다. 그런데 재밌게도 가장 긴 코드는 자바가 차지했네요. 6번 문제의 경우 자바는 무려 80라인을 기록했습니다!

그다음은 자바스크립트입니다. 자바에 비해 10라인 이상이 짧습니다. 역시나 파이썬이 가장 짧은 라인 수를 기록했는데요. 1번 문제는 고작 22라인 밖에 필요하지 않았습니다. 게다가 가장 긴 코드가 필요했던 6번 문제도 48라인으로 자바의 60% 수준에 불과합니다.

• 코드 라인 수: C++ > 자바 > 자바스크립트 > 파이썬

이외에도 여러 언어를 섞어서 풀이한 분들이 전체의 5%나 되었으며, ‘C++ + 자바 + 자바스크립트 + 파이썬’ 이 4가지 언어를 동시에 섞어서 풀이한 분도 계셨네요.

긴 시간 동안 시험을 치르고, 문제를 풀이하느라 다들 고생 많이 하셨습니다.
자, 그렇다면 많은 분들이 궁금해하실 코딩 테스트 문제를 하나씩 짚어보도록 할까요?

문제 설명

1. 비밀 지도(난이도: 하)

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 “공백”(“ “) 또는 “벽”(“#”) 두 종류로 이루어져 있다.
2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 “지도 1”과 “지도 2”라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
3. “지도 1”과 “지도 2”는 각각 정수 배열로 암호화되어 있다.
4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

입력 형식

입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.

• 1 ≦ n ≦ 16
• arr1, arr2는 길이 n인 정수 배열로 주어진다.
• 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2^n - 1을 만족한다.

출력 형식

원래의 비밀지도를 해독하여 "#", 공백으로 구성된 문자열 배열로 출력하라.

입출력 예제

문제 해설

이 문제는 비트 연산Bitwise Operation을 묻는 문제입니다. 이미 문제 예시에 2진수로 처리하는 힌트가 포함되어 있고, 둘 중 하나가 1일 경우에 벽 #이 생기기 때문에 OR로 처리하면 간단히 풀 수 있습니다. 아주 쉬운 문제였던 만큼 if else로 풀이한 분들도 많이 발견되었는데요. 정답으로는 간주되지만 이 문제는 비트 연산을 잘 다룰 수 있는지를 묻고자 하는 의도였던 만큼 앞으로 이런 유형의 문제를 풀 때는 비트 연산을 꼭 기억하시기 바랍니다.

이 문제의 정답률은 81.78%입니다. 첫 번째 문제이고 가장 쉬운 문제였던 만큼 많은 분들이 잘 풀어주셨습니다.

2. 다트 게임(난이도: 하)

카카오톡에 뜬 네 번째 별! 심심할 땐? 카카오톡 게임별~

카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다.
갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다.

1. 다트 게임은 총 3번의 기회로 구성된다.
2. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
3. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수^1 , 점수^2 , 점수^3 )으로 계산된다.
4. 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
5. 스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고)
6. 스타상(*)의 효과는 다른 스타상(*)의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상(*) 점수는 4배가 된다. (예제 4번 참고)
7. 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
8. Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
9. 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.

0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.

입력 형식

“점수|보너스|[옵션]”으로 이루어진 문자열 3세트.
예) 1S2D*3T

• 점수는 0에서 10 사이의 정수이다.
• 보너스는 S, D, T 중 하나이다.
• 옵선은 *이나 # 중 하나이며, 없을 수도 있다.

출력 형식

3번의 기회에서 얻은 점수 합계에 해당하는 정수값을 출력한다.
예) 37

입출력 예제

문제 해설

문자열 처리String Manipulation를 묻는 문제입니다. 앞에서부터 한 글자씩 잘라서 처리할 수 있고, 또는 간단한 컴파일러를 만들듯이 토큰화Tokenizing와 의미 분석Semantic Analysis을 통해 어렵지 않게 계산할 수 있습니다.

점수 중에는 한 자리뿐만 아니라 두 자리인 10점도 포함되어 있기 때문에 한 글자씩 잘라서 처리할때는 그 부분에 유의해야겠네요. 토큰화로 처리할 때는 정규식을 사용하면 비교적 쉽게 잘라낼 수 있습니다. S, D, T는 각각 원점수, 제곱, 세제곱으로 처리하고 스타상은 두 배로 계산하면 됩니다. 참, 아차상은 마이너스 점수라는 점에 유의하세요.

이 문제의 정답률은 73.47%입니다. 앞서 비밀지도 보다는 낮지만 그래도 많은 분들이 잘 풀어주셨습니다.

3. 캐시(난이도: 하)

지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.
어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

입력 형식

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력 형식

• 입력된 도시이름 배열을 순서대로 처리할 때, “총 실행시간”을 출력한다.

조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

입출력 예제

문제 해설

여기서부터 문제가 좀 어려워졌던 거 같습니다. 정답률이 많이 낮은데요. 이 문제는 ‘조건’에도 나와있지만 LRU 캐시 교체 알고리즘을 구현하는 문제이고, 이미 잘 알고 있다면 또는 검색해봤다면 잘 구현된 LRU 알고리즘 코드는 많이 찾을 수 있습니다.

단, 이 문제에는 입출력 예제에 캐시 사이즈 0이 포함되어 있습니다. 공개된 대부분의 LRU 구현 코드는 0일 때의 비정상적인 상황은 가정하지 않고 있기 때문에 생각 없이 그냥 가져와 붙인다면 에러가 나서 많이 고생했을 거 같네요. 하지만 사이즈 0을 처리하는 예외 처리 자체는 어렵지 않게 구현할 수 있으므로 입출력 예제가 왜 자꾸 틀리는지를 유심히 살펴봤다면 쉽게 풀 수 있는 문제입니다.

아울러 검색해서 가져온 코드는 반드시 사용 가능한지 라이센스를 확인하고, 가져올때는 꼭 출처를 명시해야 한다는 점 잊지 마세요.

이 문제의 정답률은 45.26%입니다.

4. 셔틀버스(난이도: 중)

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 ‘크루’라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.

일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.

입력 형식

셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.

• 0 ＜ n ≦ 10
• 0 ＜ t ≦ 60
• 0 ＜ m ≦ 45
• timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM형식으로 이루어져 있다.
• 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.

출력 형식

콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.

입출력 예제

문제 해설

쉬워 보이는데 어려운 문제가 바로 이 문제였던 거 같네요. 당초 난이도를 ‘중’으로 두고 문제를 중간 즈음에 배치하였는데, 시간을 계산하는 부분에서 많은 분들이 어려워하셨던 거 같습니다.

예를 들어 2번 입출력 예제의 경우 ["09:10", "09:09", "08:00"]인데 이 경우 두 번째 버스는 9:10분에 출발하기 때문에 9:10분에 오면 되지 않느냐 많이들 혼동하셨을 거 같아요. 하지만 9:00에 오는 버스는 8:00에 대기하는 크루 1명만 탑승할 수 있고, 따라서 9:10 버스에는 남아 있는 두 명이 모두 타게 됩니다. 따라서 좀 더 이른 9:09에 와야 탑승할 수 있습니다.

전체 계산은 어렵지 않지만 이처럼 정확하게 시간 계산을 해야 하는 부분이 많고 마지막 버스 시간까지 빈틈없이 계산해야 해서 많은 분들이 실수를 한 거 같습니다. 이 문제는 정답률이 두 번째로 낮은 26.79%입니다.

5. 뉴스 클러스터링(난이도: 중)

여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 사용자들이 편리하게 다양한 뉴스를 찾아볼 수 있도록 문제점을 개선하는 업무를 맡게 되었다.

개발의 방향을 잡기 위해 튜브는 우선 최근 화제가 되고 있는 “카카오 신입 개발자 공채” 관련 기사를 검색해보았다.

• 카카오 첫 공채..’블라인드’ 방식 채용
• 카카오, 합병 후 첫 공채.. 블라인드 전형으로 개발자 채용
• 카카오, 블라인드 전형으로 신입 개발자 공채
• 카카오 공채, 신입 개발자 코딩 능력만 본다
• 카카오, 신입 공채.. “코딩 실력만 본다”
• 카카오 “코딩 능력만으로 2018 신입 개발자 뽑는다”

기사의 제목을 기준으로 “블라인드 전형”에 주목하는 기사와 “코딩 테스트”에 주목하는 기사로 나뉘는 걸 발견했다. 튜브는 이들을 각각 묶어서 보여주면 카카오 공채 관련 기사를 찾아보는 사용자에게 유용할 듯싶었다.

유사한 기사를 묶는 기준을 정하기 위해서 논문과 자료를 조사하던 튜브는 “자카드 유사도”라는 방법을 찾아냈다.

자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.

예를 들어 집합 A = {1, 2, 3}, 집합 B = {2, 3, 4}라고 할 때, 교집합 A ∩ B = {2, 3}, 합집합 A ∪ B = {1, 2, 3, 4}이 되므로, 집합 A, B 사이의 자카드 유사도 J(A, B) = 2/4 = 0.5가 된다. 집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.

자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 A는 원소 “1”을 3개 가지고 있고, 다중집합 B는 원소 “1”을 5개 가지고 있다고 하자. 이 다중집합의 교집합 A ∩ B는 원소 “1”을 min(3, 5)인 3개, 합집합 A ∪ B는 원소 “1”을 max(3, 5)인 5개 가지게 된다. 다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로, 자카드 유사도 J(A, B) = 3/7, 약 0.42가 된다.

이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다. 문자열 “FRANCE”와 “FRENCH”가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다.

입력 형식

• 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
• 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 “ab+”가 입력으로 들어오면, “ab”만 다중집합의 원소로 삼고, “b+”는 버린다.
• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. “AB”와 “Ab”, “ab”는 같은 원소로 취급한다.

출력 형식

입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

예제 입출력

문제 해설

이 문제는 자카드 유사도를 설명해주고 자카드 유사도를 직접 계산하는 프로그램을 작성하는 문제입니다. 자카드 유사도는 실무에서도 유사한 문서를 판별할 때 주로 쓰이는데요, 몰랐더라도 문제에서 자세히 설명해주기 때문에 이해하는데 어려움은 없었을 거 같습니다. 공식은 매우 간단한데요, 교집합을 합집합으로 나눈 수입니다. 다만, 이 값은 0에서 1 사이의 실수가 되는데, 여기서는 이를 다루기 쉽도록 65536을 곱한 후 소수점 아래를 버리고 정수부만 취하도록 합니다.

문제 설명은 원소의 중복을 허용하는 다중집합multiset으로 되어 있는데, 자주 접하는 자료구조가 아니고, 일부 언어에서는 기본으로 제공하는 자료구조가 아니라 어려워하는 분들이 있었습니다. 하지만 다중집합 자료구조를 쓰지 않더라도, 각 원소를 정렬된 배열에 넣은 후 병합 정렬Merge sort에서 배웠던 코드를 응용, 어렵지 않게 합집합과 교집합 함수를 직접 구현할 수도 있습니다.

다중집합의 교집합, 합집합만 잘 구해낸다면 이 문제는 어렵지 않게 풀 수 있으며, 다만 집합 A와 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으므로division by zero 따로 J(A,B) = 1로 정의합니다. 즉, 65536을 곱하면 이 경우 1 * 65536 = 65536이 정답이 됩니다. 예제 입출력에도 합집합이 공집합인 경우가 포함되어 있으므로 이 경우만 주의한다면 쉽게 풀 수 있는 문제입니다.

이 문제의 정답률은 41.84%입니다.

6. 프렌즈4블록(난이도: 상)

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 “프렌즈4블록”.
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

입력 형식

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
• 2 <= n, m <= 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

출력 형식

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

입출력 예제

예제에 대한 설명

• 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
• 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

문제 해설

게임 요구 사항을 구현해보는 문제입니다. 같은 모양의 카카오프렌즈 블록이 2x2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임인데요. 인접한 모든 블록이 사라지는 실제 게임들과 달리 계산을 쉽게 하기 위해 2x2로 제한하고, 사라진 블록 자리에는 새로운 블록이 채워지지 않습니다. 그럼에도 불구하고 인접한 블록을 모두 스캔해야 하는 문제라 짧지 않은 코드가 필요했을 것 같네요. 이번 시험에서 가장 긴 코드가 필요한 문제였습니다. 자바의 경우 무려 80라인이나 필요했네요. 블록 매트릭스를 생성하여 스캔하고 제거해 나가는 작업을 반복하면서 더 이상 제거되지 않을 때 사라진 블록 자리의 수를 계산하면 됩니다.

이 문제의 정답률은 48.01%입니다.

7. 추석 트래픽(난이도: 상)

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.

입력 형식

• solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.
• 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.
• 처리시간 T는 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다.
• 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 “2016년 9월 15일 오전 3시 10분 33.010초”부터 “2016년 9월 15일 오전 3시 10분 33.020초”까지 “0.011초” 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)
• 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다.
• lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

출력 형식

• solution 함수에서는 로그 데이터 lines 배열에 대해 초당 최대 처리량을 리턴한다.

입출력 예제

예제 1

• 입력: [ “2016-09-15 01:00:04.001 2.0s”, “2016-09-15 01:00:07.000 2s” ]
• 출력: 1

예제 2

• 입력: [ “2016-09-15 01:00:04.002 2.0s”, “2016-09-15 01:00:07.000 2s” ]
• 출력: 2
• 설명: 처리시간은 시작시간과 끝시간을 포함하므로 첫 번째 로그는 01:00:02.003 ~ 01:00:04.002에서 2초 동안 처리되었으며, 두 번째 로그는 01:00:05.001 ~ 01:00:07.000에서 2초 동안 처리된다. 따라서, 첫 번째 로그가 끝나는 시점과 두 번째 로그가 시작하는 시점의 구간인 01:00:04.002 ~ 01:00:05.001 1초 동안 최대 2개가 된다.

예제 3

• 입력: [ “2016-09-15 20:59:57.421 0.351s”, “2016-09-15 20:59:58.233 1.181s”, “2016-09-15 20:59:58.299 0.8s”, “2016-09-15 20:59:58.688 1.041s”, “2016-09-15 20:59:59.591 1.412s”, “2016-09-15 21:00:00.464 1.466s”, “2016-09-15 21:00:00.741 1.581s”, “2016-09-15 21:00:00.748 2.31s”, “2016-09-15 21:00:00.966 0.381s”, “2016-09-15 21:00:02.066 2.62s” ]
• 출력: 7
• 설명: 아래 타임라인 그림에서 빨간색으로 표시된 1초 각 구간의 처리량을 구해보면 (1)은 4개, (2)는 7개, (3)는 2개임을 알 수 있다. 따라서 초당 최대 처리량은 7이 되며, 동일한 최대 처리량을 갖는 1초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.

문제 해설

이번 테스트의 마지막 문제이고, 가장 어려운 문제입니다. 초당 최대 처리량이 되는 구간 윈도우를 찾아야 하는 문제인데요. 당연히 처음부터 끝까지 스캔하기에는 범위가 너무 크고, 게다가 ms 단위로 되어 있기 때문에 첫 로그 시각부터 마지막 로그 시각까지 1ms씩 증가시키면서 1000ms 단위의 슬라이딩 윈도우로 풀면 24 * 3600 * 1000 * n * 1000ms 만큼의 연산이 필요하기 때문에 이렇게는 풀 수가 없습니다.

그렇다고 각 로그의 시작 시각부터 마지막 시각까지 1ms 씩 움직이면 time(ms) * n^2 이 되며, time(ms)의 값은 대부분 천 단위 이상이기 때문에 마찬가지로 타임아웃이 발생하여 풀 수가 없습니다. 그런데 자세히 살펴보면 요청량이 변하는 순간은 각 로그의 시작과 끝뿐임을 알 수 있습니다. 따라서, 각 로그 별 2번의 비교 연산만 수행하면 되며 2 * n^2, 빅오로 정리하면 O(n^2)에 풀 수가 있습니다. 빅오에서 제거된 상수항도 매우 작기 때문에 이 경우 무리 없이 문제를 풀 수 있게 되며 C++ 기준으로 10ms를 넘지 않습니다.

물론, 이 문제는 윈도우를 사용하지 않고도 풀 수 있는 방법이 있습니다. 효율적인 알고리즘을 쓴다면, O(n log n)으로 풀 수 있는 방법도 있으니 한 번 고민해보세요. 이 문제는 가장 어려운 문제였던 만큼 정답률은 가장 낮은 17.99%입니다.

마무리하며

이렇게 모든 문제를 돌아보고 간략한 해설을 곁들여 봤습니다. 어떠신가요?

참여하신 분들 중 미처 풀지 못한 문제가 있었다면 문제 해설을 보면서 ‘조금만 더 시간이 있었더라면…‘라며 안타까움을 느끼는 분들이 많으실 거라 생각합니다. 여타의 코딩 대회와 달리 채용을 위한 시험인 만큼 재밌게 즐기기는 힘들었을 것입니다. 하지만, “천재는 노력하는 사람을 이길 수 없고, 노력하는 사람은 즐기는 사람을 이길 수 없다.”는 말이 있듯이, 끝까지 즐기는 마음 잊지 않고 코딩을 즐긴다면 언젠가 좋은 결과 있으리라 확신합니다. 마지막까지 잘 마무리하여 꼭 카카오에서 여러분들을 만나 뵙게 되길 기대하겠습니다.

그럼, 2차 시험에서 다시 만나도록 할게요. 마지막까지 파이팅!

출처 : http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

연구실 GPU 쿠다 마무리 작업 중,

나는 분명 cuda8, cuda9를 설치하였는데, nvcc --version 과 nvcc -V 를 쳤을 때 V7.5로 뜨는 것을 확인했다.

계속 이상하게 생각하던 도중...

torch를 설치 하고 있는데, 다음과 같은 에러가 떴다.

nvcc fatal   : Unsupported gpu architecture 'compute_61'

CMake Error at THC_generated_THCHalf.cu.o.cmake:207 (message):

  Error generating

  /home/lee/torch/extra/cutorch/build/lib/THC/CMakeFiles/THC.dir//./THC_generated_THCHalf.cu.o

lib/THC/CMakeFiles/THC.dir/build.make:560: recipe for target 'lib/THC/CMakeFiles/THC.dir/THC_generated_THCHalf.cu.o' failed

make[2]: *** [lib/THC/CMakeFiles/THC.dir/THC_generated_THCHalf.cu.o] Error 1

make[2]: *** Waiting for unfinished jobs....

nvcc fatal   : Unsupported gpu architecture 'compute_61'

CMake Error at THC_generated_THCTensorSortChar.cu.o.cmake:207 (message):

  Error generating

  /home/lee/torch/extra/cutorch/build/lib/THC/CMakeFiles/THC.dir/generated/./THC_generated_THCTensorSortChar.cu.o 블라블라...

nvcc fatal 문제 이다. nvcc 문제로 보는게 맞겠다.

나는 서버에서 거리가 좀 되고, 모니터는 무한 리부팅 문제를 해결하지 않아서, 원격으로 하기 때문에 display 로 보는 것이 힘들기 때문에 

vi ~/.profile 을 입력

맨 아랫줄에 다음과 같이 경로 설정을 해줬다.

export PATH=/usr/local/cuda-8.0/bin:$PATH
export LD_LIBRARY_PATH=/usr/local/cuda-8.0/lib64:$LD_LIBRARY_PATH

닫고 난 뒤, source ~/.profile 을 해준다.

그러면 이제 경로 설정이 되어서 nvcc --version 을 할 경우 cuda 8 버전으로 잘 잡힌다.

연구실 서버 같은 경우 계정이 약 10개 정도 되는데, 일일이 다 해주기는 번거로운 일이다.

그 때, root 계정(superuser)로 접속하여

vi /etc/profile 을 입력

export PATH=/usr/local/cuda-8.0/bin:$PATH
export LD_LIBRARY_PATH=/usr/local/cuda-8.0/lib64:$LD_LIBRARY_PATH

그 후 source /etc/profile 해주면 된다.

이렇게 되면 모든 계정에 대해 쿠다를 8로 잡아준다.

cuDNN 같은 경우에는 워낙 자료가 많으므로 생략

bashrc 로 하는 경우도 있는데, 마찬가지로 해주면 된다.

처음에 cuda9를 설치하고, 9 지원 안해주는 프레임워크가 있어서 uninstall 하지 않고 바로 설치했는데, 문제 없이 되는 것 같다.

cuDNN 도 7에서 6으로 바꿔서 설치했다. 마찬가지로 삭제하지 않고, 메뉴얼대로 따라 했을 뿐인데 잘 된다.

결론 : 굳이 삭제할 필요 없음