TigerCow.Door


안녕하세요. 문범우입니다.


이번 포스팅에서는 TensorFlow tutorial의 두번째인, Text classification에 대해서 진행해보았습니다.


In [1]:
# TensorFlow and tf.keras
# 텐서플로우와 keras를 import한다. 이떄 tensorflow는 tf라는 별칭으로 사용할 것임.
import tensorflow as tf
from tensorflow import keras

# Helper libraries
# numpy와 matplotlib을 사용한다.
import numpy as np
import matplotlib.pyplot as plt
# jupyter notebook에서 matplotlib을 사용하기 위한 매직커맨드
%matplotlib inline

print("사용되는 tensorflow의 버전:",tf.__version__)
사용되는 tensorflow의 버전: 1.9.0

ㄱ. 데이터준비

이번 text classification 실습을 위한 데이터는 keras dataset에 있는 imdb를 사용한다.

(해당 데이터는 영화에 대한 review 내용이다.)

아래에서 확인해볼 수 있겠지만 train과 test 데이터 셋은 각각 25,000개 이며 데이터는 review자체로 구성되어 있다.

또한 labels는 0또는 1값으로 해당 review가 긍정적인 것인지 부정적인 것인지를 나타낸다.

따라서 우리는 test데이터를 이용하여 해당 Review가 영화에 대해 긍정적인 것인지, 부정적인 것인지를 예측해본다.

데이터의 자세한 내용은 아래에서 확인해본다.

In [28]:
imdb = keras.datasets.imdb

(train_data, train_labels), (test_data, test_labels) = imdb.load_data(num_words=10000)
In [29]:
# training data 확인
print("Training entries: {}, labels: {}".format(len(train_data), len(train_labels)))
Training entries: 25000, labels: 25000

training data는 위와 같다.

하지만, 실제로 데이터를 하나 찍어보면 string이 아닌 integer 값이 리스트로 들어있다.

In [30]:
print(train_data[0])
[1, 14, 22, 16, 43, 530, 973, 1622, 1385, 65, 458, 4468, 66, 3941, 4, 173, 36, 256, 5, 25, 100, 43, 838, 112, 50, 670, 2, 9, 35, 480, 284, 5, 150, 4, 172, 112, 167, 2, 336, 385, 39, 4, 172, 4536, 1111, 17, 546, 38, 13, 447, 4, 192, 50, 16, 6, 147, 2025, 19, 14, 22, 4, 1920, 4613, 469, 4, 22, 71, 87, 12, 16, 43, 530, 38, 76, 15, 13, 1247, 4, 22, 17, 515, 17, 12, 16, 626, 18, 2, 5, 62, 386, 12, 8, 316, 8, 106, 5, 4, 2223, 5244, 16, 480, 66, 3785, 33, 4, 130, 12, 16, 38, 619, 5, 25, 124, 51, 36, 135, 48, 25, 1415, 33, 6, 22, 12, 215, 28, 77, 52, 5, 14, 407, 16, 82, 2, 8, 4, 107, 117, 5952, 15, 256, 4, 2, 7, 3766, 5, 723, 36, 71, 43, 530, 476, 26, 400, 317, 46, 7, 4, 2, 1029, 13, 104, 88, 4, 381, 15, 297, 98, 32, 2071, 56, 26, 141, 6, 194, 7486, 18, 4, 226, 22, 21, 134, 476, 26, 480, 5, 144, 30, 5535, 18, 51, 36, 28, 224, 92, 25, 104, 4, 226, 65, 16, 38, 1334, 88, 12, 16, 283, 5, 16, 4472, 113, 103, 32, 15, 16, 5345, 19, 178, 32]

이렇게 되어 있는 이유는, 추가적인 dictionary에 각 숫자와 단어가 매칭되어 있기 때문이다.

또한 아래와 같이 각각의 데이터의 길이도 다른 것을 확인할 수 있다.

In [31]:
len(train_data[0]), len(train_data[1])
Out[31]:
(218, 189)

하지만 실제로 우리가 ML모델에 넣어줄때, 입력의 길이는 모두 같아야 한다.

따라서 우리는 추후에 입력의 길이가 다른 것에 대한 컨트롤을 진행한다.

먼저 데이터를 보다 자세히 확인해보기 위해 각 데이터의 숫자를 단어로 치환해본다.

In [51]:
# 숫자로 된 값을 단어로 바꾸기 위한 dictionary를 가져온다
word_index = imdb.get_word_index()
#word_index #블로그 길이때문에 주석처리함
In [52]:
#word_index.items() #블로그 길이때문에 주석처리함.

word_index라는 dictionary는 단어가 key, 숫자가 value로 되어있다.

추가적으로, pad, start, unknown, unused 값을 나타내기 위해 각 value에 3을 더하고 비어있게 되는 0~3에 각각을 할당한다.

In [34]:
# The first indices are reserved
word_index = {k:(v+3) for k,v in word_index.items()} 
word_index["<PAD>"] = 0
word_index["<START>"] = 1
word_index["<UNK>"] = 2  # unknown
word_index["<UNUSED>"] = 3

또한 실제로 우리가 필요한 dictionary는 숫자가 key이고, 단어가 value인 dictionary이기 때문에,

reverse_word_index 라는 dictionary를 구성하고 숫자로 이루어진 입력데이터를 단어로 치환해주며 문장으로 출력하는는 decode_review함수를 만든다.

In [35]:
reverse_word_index = dict([(value, key) for (key, value) in word_index.items()])

def decode_review(text):
    return ' '.join([reverse_word_index.get(i, '?') for i in text])
In [36]:
# 하나의 입력데이터를 문장으로 확인해보자
decode_review(train_data[0])
Out[36]:
"<START> this film was just brilliant casting location scenery story direction everyone's really suited the part they played and you could just imagine being there robert <UNK> is an amazing actor and now the same being director <UNK> father came from the same scottish island as myself so i loved the fact there was a real connection with this film the witty remarks throughout the film were great it was just brilliant so much that i bought the film as soon as it was released for <UNK> and would recommend it to everyone to watch and the fly fishing was amazing really cried at the end it was so sad and you know what they say if you cry at a film it must have been good and this definitely was also <UNK> to the two little boy's that played the <UNK> of norman and paul they were just brilliant children are often left out of the <UNK> list i think because the stars that play them all grown up are such a big profile for the whole film but these children are amazing and should be praised for what they have done don't you think the whole story was so lovely because it was true and was someone's life after all that was shared with us all"

앞에서 추가해주었던 start, unk 등이 추가되어 보여지는 것을 확인할 수 있다.

ㄴ. 데이터 전처리

실제로 우리의 데이터를 ML모델에 입력하기 위해 데이터 전처리를 진행한다.

먼저 위에서 언급했던 각 데이터의 길이가 상이한 것을 처리한다.

keras에서 제공하는 preprocessing 함수를 이용하여 모든 데이터를 최대길이로 늘려주면서 빈공간에는 위에서 dictionary에 추가적으로 넣어주었던 pad값을 이용한다.

In [37]:
train_data = keras.preprocessing.sequence.pad_sequences(train_data,
                                                        value=word_index["<PAD>"],
                                                        padding='post',
                                                        maxlen=256)

test_data = keras.preprocessing.sequence.pad_sequences(test_data,
                                                       value=word_index["<PAD>"],
                                                       padding='post',
                                                       maxlen=256)

train데이터와 test데이터를 같이 작업하였고, 이를 통한 입력데이터를 확인해본다.

In [38]:
print("길이가 동일한가? => 0번째 데이터 길이:",len(train_data[0]),"1번째 데이터 길이",len(train_data[1]))
tmp_len_check = 0
tmp_len = 256
for data in train_data:
    if(tmp_len == len(data)): tmp_len_check += 1
if(tmp_len_check == len(train_data)):
    print("모든 데이터의 길이가 256으로 동일합니다!")
else:
    print("데이터의 길이가 동일하지 않습니다!")
print("데이터 형태는?\n",train_data[0])
길이가 동일한가? => 0번째 데이터 길이: 256 1번째 데이터 길이 256
모든 데이터의 길이가 256으로 동일합니다!
데이터 형태는?
 [   1   14   22   16   43  530  973 1622 1385   65  458 4468   66 3941
    4  173   36  256    5   25  100   43  838  112   50  670    2    9
   35  480  284    5  150    4  172  112  167    2  336  385   39    4
  172 4536 1111   17  546   38   13  447    4  192   50   16    6  147
 2025   19   14   22    4 1920 4613  469    4   22   71   87   12   16
   43  530   38   76   15   13 1247    4   22   17  515   17   12   16
  626   18    2    5   62  386   12    8  316    8  106    5    4 2223
 5244   16  480   66 3785   33    4  130   12   16   38  619    5   25
  124   51   36  135   48   25 1415   33    6   22   12  215   28   77
   52    5   14  407   16   82    2    8    4  107  117 5952   15  256
    4    2    7 3766    5  723   36   71   43  530  476   26  400  317
   46    7    4    2 1029   13  104   88    4  381   15  297   98   32
 2071   56   26  141    6  194 7486   18    4  226   22   21  134  476
   26  480    5  144   30 5535   18   51   36   28  224   92   25  104
    4  226   65   16   38 1334   88   12   16  283    5   16 4472  113
  103   32   15   16 5345   19  178   32    0    0    0    0    0    0
    0    0    0    0    0    0    0    0    0    0    0    0    0    0
    0    0    0    0    0    0    0    0    0    0    0    0    0    0
    0    0    0    0]

위와 같이 데이터 길이가 서로 동일한 것을 확인할 수 있고, 실제로 0번째 데이터를 확인해보았을때 맨 뒤에 0값, 즉 pad값이 포함된 것을 확인할 수 있다.

ㄷ. 모델 구성하기

이제 text classification을 수행할 ML모델을 만들어보자.

먼저 vocab_size 는 영화리뷰에 사용되는 단어의 개수이다.

실제로 위에서의 단어와 숫자를 매칭하는 dictionary의 사이즈는 보다 크지만, 해당 데이터에서는 10000개의 단어 이내에로 리뷰가 작성되었다.

각 레이어에 대한 설명은 다음과 같다.

  1. embedding 해당 레이어는 숫자로 인코딩 되어있는 각 단어를 사용하며 각 단어 인덱스에 대한 벡터를 찾는다.

이러한 벡터는 추후 model이 학습하는데 사용된다.

  1. GlobalAveragePooling1D 해당 레이어에서는 각 예시에 대해 sequence 차원을 평균하여 고정된 길이의 벡터를 출력한다.

이를 통해 가변적인 길이의 입력을 간단하게 처리할 수 있다.

  1. Dense_1, Dense_2 첫번째 Dense 레이어를 통해서, 고정길이로 출력된 vector 값을 통해 16개의 hidden unit을 가진 fully-connected layer를 통과시킨다.

이후 두번째 Dense 레이어는 단일 출력 노드를 가짐고 시그모이드 활성화 함수를 사용함으로써 결과에 대해 0 ~ 1 사이의 값을 가지도록 한다.

In [40]:
# input shape is the vocabulary count used for the movie reviews (10,000 words)
vocab_size = 10000

model = keras.Sequential()
model.add(keras.layers.Embedding(vocab_size, 16))
model.add(keras.layers.GlobalAveragePooling1D())
model.add(keras.layers.Dense(16, activation=tf.nn.relu))
model.add(keras.layers.Dense(1, activation=tf.nn.sigmoid))

model.summary()
_________________________________________________________________
Layer (type)                 Output Shape              Param #   
=================================================================
embedding_1 (Embedding)      (None, None, 16)          160000    
_________________________________________________________________
global_average_pooling1d_1 ( (None, 16)                0         
_________________________________________________________________
dense_2 (Dense)              (None, 16)                272       
_________________________________________________________________
dense_3 (Dense)              (None, 1)                 17        
=================================================================
Total params: 160,289
Trainable params: 160,289
Non-trainable params: 0
_________________________________________________________________

모델 구성에 대한 마지막으로 loss function과 optimizer를 설정한다.

In [41]:
model.compile(optimizer=tf.train.AdamOptimizer(),
              loss='binary_crossentropy',
              metrics=['accuracy'])

ㄹ. 모델 훈련하기

모델을 훈련하기에 앞서 우리는 10,000개의 데이터를 따로 떼어 validation set을 만든다.

이렇게 하는 이유는 모델이 새롭게 접하는 데이터에 대한 accuracy와 loss 등을 확인해보기 위해서이다.

In [43]:
x_val = train_data[:10000]
partial_x_train = train_data[10000:]

y_val = train_labels[:10000]
partial_y_train = train_labels[10000:]

history = model.fit(partial_x_train,
                    partial_y_train,
                    epochs=40,
                    batch_size=512,
                    validation_data=(x_val, y_val),
                    verbose=1)
Train on 15000 samples, validate on 10000 samples
Epoch 1/40
15000/15000 [==============================] - 1s 55us/step - loss: 0.7099 - acc: 0.5045 - val_loss: 0.6942 - val_acc: 0.5106
Epoch 2/40
15000/15000 [==============================] - 0s 32us/step - loss: 0.6920 - acc: 0.5147 - val_loss: 0.6911 - val_acc: 0.5132
Epoch 3/40
15000/15000 [==============================] - 0s 32us/step - loss: 0.6901 - acc: 0.5292 - val_loss: 0.6897 - val_acc: 0.5391
Epoch 4/40
15000/15000 [==============================] - 0s 31us/step - loss: 0.6882 - acc: 0.5435 - val_loss: 0.6878 - val_acc: 0.5510
Epoch 5/40
15000/15000 [==============================] - 0s 32us/step - loss: 0.6859 - acc: 0.5797 - val_loss: 0.6856 - val_acc: 0.5742
Epoch 6/40
15000/15000 [==============================] - 0s 32us/step - loss: 0.6832 - acc: 0.6010 - val_loss: 0.6827 - val_acc: 0.6093
Epoch 7/40
15000/15000 [==============================] - 0s 29us/step - loss: 0.6797 - acc: 0.6424 - val_loss: 0.6793 - val_acc: 0.6413
Epoch 8/40
15000/15000 [==============================] - 0s 30us/step - loss: 0.6750 - acc: 0.6792 - val_loss: 0.6742 - val_acc: 0.6842
Epoch 9/40
15000/15000 [==============================] - 0s 30us/step - loss: 0.6651 - acc: 0.6916 - val_loss: 0.6613 - val_acc: 0.7029
Epoch 10/40
15000/15000 [==============================] - 0s 31us/step - loss: 0.6505 - acc: 0.7511 - val_loss: 0.6468 - val_acc: 0.7495
Epoch 11/40
15000/15000 [==============================] - 0s 30us/step - loss: 0.6331 - acc: 0.7627 - val_loss: 0.6294 - val_acc: 0.7663
Epoch 12/40
15000/15000 [==============================] - 1s 34us/step - loss: 0.6123 - acc: 0.7869 - val_loss: 0.6095 - val_acc: 0.7746
Epoch 13/40
15000/15000 [==============================] - 0s 33us/step - loss: 0.5888 - acc: 0.7942 - val_loss: 0.5889 - val_acc: 0.7767
Epoch 14/40
15000/15000 [==============================] - 0s 33us/step - loss: 0.5639 - acc: 0.8051 - val_loss: 0.5646 - val_acc: 0.7939
Epoch 15/40
15000/15000 [==============================] - 0s 32us/step - loss: 0.5371 - acc: 0.8123 - val_loss: 0.5396 - val_acc: 0.8027
Epoch 16/40
15000/15000 [==============================] - 0s 32us/step - loss: 0.5103 - acc: 0.8221 - val_loss: 0.5156 - val_acc: 0.8051
Epoch 17/40
15000/15000 [==============================] - 0s 32us/step - loss: 0.4830 - acc: 0.8359 - val_loss: 0.4920 - val_acc: 0.8205
Epoch 18/40
15000/15000 [==============================] - 0s 30us/step - loss: 0.4569 - acc: 0.8460 - val_loss: 0.4691 - val_acc: 0.8285
Epoch 19/40
15000/15000 [==============================] - 0s 33us/step - loss: 0.4321 - acc: 0.8541 - val_loss: 0.4478 - val_acc: 0.8363
Epoch 20/40
15000/15000 [==============================] - 1s 36us/step - loss: 0.4092 - acc: 0.8621 - val_loss: 0.4285 - val_acc: 0.8411
Epoch 21/40
15000/15000 [==============================] - 1s 34us/step - loss: 0.3876 - acc: 0.8697 - val_loss: 0.4108 - val_acc: 0.8463
Epoch 22/40
15000/15000 [==============================] - 1s 40us/step - loss: 0.3683 - acc: 0.8753 - val_loss: 0.3951 - val_acc: 0.8515
Epoch 23/40
15000/15000 [==============================] - 0s 30us/step - loss: 0.3511 - acc: 0.8818 - val_loss: 0.3817 - val_acc: 0.8559
Epoch 24/40
15000/15000 [==============================] - 0s 28us/step - loss: 0.3351 - acc: 0.8862 - val_loss: 0.3695 - val_acc: 0.8596
Epoch 25/40
15000/15000 [==============================] - 0s 29us/step - loss: 0.3211 - acc: 0.8901 - val_loss: 0.3590 - val_acc: 0.8641
Epoch 26/40
15000/15000 [==============================] - 0s 27us/step - loss: 0.3084 - acc: 0.8931 - val_loss: 0.3500 - val_acc: 0.8669
Epoch 27/40
15000/15000 [==============================] - 0s 27us/step - loss: 0.2972 - acc: 0.8952 - val_loss: 0.3420 - val_acc: 0.8691
Epoch 28/40
15000/15000 [==============================] - 0s 29us/step - loss: 0.2864 - acc: 0.9001 - val_loss: 0.3349 - val_acc: 0.8715
Epoch 29/40
15000/15000 [==============================] - 0s 28us/step - loss: 0.2768 - acc: 0.9029 - val_loss: 0.3291 - val_acc: 0.8725
Epoch 30/40
15000/15000 [==============================] - 0s 27us/step - loss: 0.2685 - acc: 0.9053 - val_loss: 0.3237 - val_acc: 0.8754
Epoch 31/40
15000/15000 [==============================] - 0s 27us/step - loss: 0.2598 - acc: 0.9087 - val_loss: 0.3191 - val_acc: 0.8757
Epoch 32/40
15000/15000 [==============================] - 0s 27us/step - loss: 0.2526 - acc: 0.9093 - val_loss: 0.3150 - val_acc: 0.8767
Epoch 33/40
15000/15000 [==============================] - 0s 27us/step - loss: 0.2451 - acc: 0.9123 - val_loss: 0.3114 - val_acc: 0.8763
Epoch 34/40
15000/15000 [==============================] - 0s 27us/step - loss: 0.2382 - acc: 0.9151 - val_loss: 0.3080 - val_acc: 0.8771
Epoch 35/40
15000/15000 [==============================] - 0s 30us/step - loss: 0.2322 - acc: 0.9164 - val_loss: 0.3051 - val_acc: 0.8787
Epoch 36/40
15000/15000 [==============================] - 0s 27us/step - loss: 0.2257 - acc: 0.9189 - val_loss: 0.3026 - val_acc: 0.8794
Epoch 37/40
15000/15000 [==============================] - 0s 27us/step - loss: 0.2200 - acc: 0.9213 - val_loss: 0.3007 - val_acc: 0.8799
Epoch 38/40
15000/15000 [==============================] - 0s 26us/step - loss: 0.2145 - acc: 0.9227 - val_loss: 0.2980 - val_acc: 0.8813
Epoch 39/40
15000/15000 [==============================] - 0s 29us/step - loss: 0.2089 - acc: 0.9254 - val_loss: 0.2962 - val_acc: 0.8815
Epoch 40/40
15000/15000 [==============================] - 0s 27us/step - loss: 0.2038 - acc: 0.9268 - val_loss: 0.2944 - val_acc: 0.8822
In [44]:
results = model.evaluate(test_data, test_labels)

print(results)
25000/25000 [==============================] - 1s 21us/step
[0.3078416971683502, 0.87396]

위를 통해 우리의 모델은 test데이터 기반, 약 87%의 정확도를 가짐을 볼 수 있다.

실제로 더 진보된 모델이라고 하기 위해서는 약 95%이상의 정확도를 필요로 한다.

일단 이정도로 하고, 위에서 결과로 확인한 정확도와 오차 등을 그래프로 확인해보고 마무리한다.

In [48]:
history_dict = history.history
history_dict.keys()
Out[48]:
dict_keys(['val_loss', 'val_acc', 'loss', 'acc'])
In [49]:
acc = history.history['acc']
val_acc = history.history['val_acc']
loss = history.history['loss']
val_loss = history.history['val_loss']

epochs = range(1, len(acc) + 1)

# "bo" is for "blue dot"
plt.plot(epochs, loss, 'bo', label='Training loss')
# b is for "solid blue line"
plt.plot(epochs, val_loss, 'b', label='Validation loss')
plt.title('Training and validation loss')
plt.xlabel('Epochs')
plt.ylabel('Loss')
plt.legend()

plt.show()
In [50]:
plt.clf()   # clear figure
acc_values = history_dict['acc']
val_acc_values = history_dict['val_acc']

plt.plot(epochs, acc, 'bo', label='Training acc')
plt.plot(epochs, val_acc, 'b', label='Validation acc')
plt.title('Training and validation accuracy')
plt.xlabel('Epochs')
plt.ylabel('Accuracy')
plt.legend()

plt.show()


블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요 .문범우입니다.

이번 포스팅에서는 hackerrank의 The Grid Search 문제를 풀어보았습니다.

난이도는 Medium, rate는 약 75%입니다.

문제 개념이나 이해자체는 크게 어렵지 않다고 생각되나 몇가지 고려할 부분들이 존재합니다.


제가 중요시 생각한 점은,

먼저 탐색하고자 하는 P배열에 대해 그 첫번째 행이 G배열에서 존재할때만 실질적인 탐색문을 반복하는 것과

그 첫번째 행이 G배열의 특정행에서 반복하여 존재할 수 있기 때문에 인덱스를 고려해가며 탐색하는 것 입니다.


보다 자세한 설명은 코드에 주석으로 달아 놓았습니다.

궁금하시거나 코드를 보다 효율적으로 개선할 방법에 대해서는 댓글 및 카카오톡, 이메일을 통해 말씀해주시면 감사하겠습니다 :)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
 
public class Solution {
 
    // Complete the gridSearch function below.
    static String gridSearch(String[] G, String[] P) {
        // G를 입력배열, P를 목표배열이라 하겠음
        int G_width = G[0].length(); // 입력배열의 가로길이 -> 목표배열 한줄씩 탐색시 사용됨. 
        int G_height = G.length// 입력배열의 세로길이 -> 목표배열 탐색 중에 입력배열의 높이를 넘어가면 NO를 반환
        int P_width = P[0].length(); // 목표배열의 가로길이
        int P_height = P.length// 목표배열의 세로길이 -> 목표배열 탐색 중에 목표배열의 높이를 넘어가면 YES를 반환
        int start_num = -1
        // 탐색중인 목표배열의 1 행이 13일떄, 입력배열에 01300130 과 같이 중복되서 나타날 수 있음
        // 이때 입력배열의 한줄에 대해 각각 검사하기 위해 사용하기도 하며
        // 목표배열의 1행이 위와 같이 13이고, 2행이 27일때, 입력배열이 다음과 같을 수 있음
        // 01300130
        // 99992799
        // 이러한 경우를 위해 각 입력배열의 각줄에 목표배열의 행이 포함되는지 여부뿐아니라,
        // 그 시작 인덱스가 일치하는지 알아야 하기 때문에 이때 start_num이 사용됨
        int count_from = -1;
        int count = 0;
        // count_from과 count변수는 입력배열의 탐색하고자 하는 목표배열의 행에 대해
        // 입력배열의 한 행에 몇개나 같은 문자열이 포함되어있는지를 저장함.
        // 즉, 위와 같이 01300130 같은 경우 count가 2가 되어서
        // 각각에 대해서 탐색을 진행해야 하기 때문에 탐색문을 2번 실행하게함
        for(int j=0;j<G_height;j++){ // 입력배열의 한 행씩 탐색을 진행함
            if(G[j].contains(P[0])){ // 어찌되었는 목표배열의 첫번째 행이 입력배열에 존재할때 탐색을 시작해야함
                count = 0
                start_num = -1;
                // count와 start_num 초기화, count_from은 아래 while문을 통해서 자동적으로 초기화가 됨
                while((count_from = G[j].indexOf(P[0], count_from + 1))>=0){
                    // G[j]에 P[0]가 어느 인덱스에서 시작되는지 확인, 이때 그 뒤에 count_from+1 인자를 줌으로써
                    // G[j]의 count_from+1 인덱스 이후로 부터 확인을 하는 것,
                    // 존재한다면 양수값을 주기때문에 count 값을 하나 증가,
                    // 존재하지 않는다면 -1을 반환하므로 count_from이 초기화 되는 기능이 됨
                    count++;
                }
                // 실질적인 탐색문 시작
                for(int i=0;i<count;i++){
                    start_num = G[j].indexOf(P[0], start_num+1); // G[j]에서 P[0]가 포함된 인덱스를 구함
                    for(int k=0;k<P_height;k++){ // 이제 모든 목표배열행에 대해 탐색할 것
                        if((G[j+k].contains(P[k]))&(start_num == G[j+k].indexOf(P[k],start_num))){
                            // 목표배열의 다음행이 입력배열의 다음행에 포함되어있는지 확인하면서
                            // 그 시작위치가 동일한지 확인 -> else: 즉, 그게 아니면 목표배열의 첫행에 대해 재탐색
                            if(k+1 == P_height){
                                // k가 증가하다가 목표배열의 높이를 넘어가면 모든 목표배열에 대해 탐색이 된 것이므로
                                // YES를 반환
                                return "YES";
                            }else if(j+k+1 == G_height){
                                // k가 증가하다가 목표배열의 높이를 넘어가기 전에 입력배열의 높이를 넘어가면
                                // 입력배열에 목표배열이 완전하게 존재하지 않는 것이기 때문에 NO를 반환
                                return "NO";
                            }
                        }else{
                            break;
                        }
                    }
                }
            }
        } // 해당 for문이 끝난 것은 입력배열에 목표배열이 포함되어 있지 않다는 뜻이기에 NO를 반환함
        return "NO";
    }
 
    private static final Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
 
        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
 
        for (int tItr = 0; tItr < t; tItr++) {
            String[] RC = scanner.nextLine().split(" ");
 
            int R = Integer.parseInt(RC[0]);
 
            int C = Integer.parseInt(RC[1]);
 
            String[] G = new String[R];
 
            for (int i = 0; i < R; i++) {
                String GItem = scanner.nextLine();
                G[i] = GItem;
            }
 
            String[] rc = scanner.nextLine().split(" ");
 
            int r = Integer.parseInt(rc[0]);
 
            int c = Integer.parseInt(rc[1]);
 
            String[] P = new String[r];
 
            for (int i = 0; i < r; i++) {
                String PItem = scanner.nextLine();
                P[i] = PItem;
            }
 
            String result = gridSearch(G, P);
 
            bufferedWriter.write(result);
            bufferedWriter.newLine();
        }
 
        bufferedWriter.close();
 
        scanner.close();
    }
}
 
cs


'Algorithm > Java 풀이' 카테고리의 다른 글

JAVA #3_ The Grid Search  (0) 2018.08.08
JAVA #2_ Lily's Homework  (0) 2018.08.05
Java #1_ 가장 긴 팰린드롬 길이 구하기  (0) 2018.07.12
블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요. 문범우입니다.

이번에는 Hackerrank의 문제를 풀어보았습니다.

문제 이름은 Lily's Homework이며 Medium 난이도에 속해있습니다.

생각외로 rate가 47% 정도로 좀 낮은편 입니다.

해당 문제는 아래 주소에서 풀어보실 수 있습니다.


https://www.hackerrank.com/challenges/lilys-homework/problem


코드에 주석을 통해 설명을 덧붙여 놓았기 때문에 추가적인 설명은 생략하겠습니다.

해당 코드는 아래 github 주소에서도 확인할 수 있습니다.


https://github.com/doorBW/algorithm_practice


보다 궁금한 점이 있으신 분들은 댓글 및 이메일, 카카오톡을 통해 연락주시면 바로 답변드리도록 하겠습니다 :)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
 
public class Solution {
    static int lilysHomework(int[] arr) {
        // arr을 오름차순 또는 내림차순의 형태로 만들어야 한다.
        // 그때가 문제에서 말한 cost가 가장 적은 경우기 때문에,
        // 이때 문제는, arr을 오름차순으로 만드는데 필요한 swap횟수와
        // arr을 내림차순으로 만드는데 필요한 swap횟수가 다르다.
        // 따라서 오름차순 및 내림차순 두 방법 모두 시행하고 그 중 작은 값을 반환한다.
 
        int answer_asc = 0;
        int answer_desc = 0;
        int idx,temp;
        int arr_length = arr.length;
        // 기존 arr은 오름차순에서 사용될 것
        // 내림차순에서 사용될 arr_desc을 만들고 기존 arr을 복사해서 넣는다.
        int[] arr_desc = new int[arr_length];
        System.arraycopy( arr, 0, arr_desc, 0, arr_length );
 
        // 오름차순으로 정렬된 sorted_arr
        int[] sorted_arr = new int[arr_length];
        System.arraycopy( arr, 0, sorted_arr, 0, arr_length );
        Arrays.sort(sorted_arr);
        
        // 내림차순으로 정렬된 reversed_arr
        int[] reversed_arr = new int[arr_length];
        for(int i=0;i<arr_length;i++){
            reversed_arr[i] = -1 * arr[i];
        }
        Arrays.sort(reversed_arr);
        for(int i = 0; i < arr_length; i++){
            reversed_arr[i] *= -1;
        }
        
        // 오름차순을 위한 hash map
        HashMap<Integer, Integer> idxMap_asc = new HashMap();
        for(int i=0;i<arr_length;i++){
            idxMap_asc.put(arr[i],i);
        }
 
        // 내림차순을 위한 hash map
        HashMap<Integer, Integer> idxMap_desc = new HashMap();
        for(int i=0;i<arr_length;i++){
            idxMap_desc.put(arr_desc[i],i);
        }
        
        // 오름차순을 통한 cost 계산
        for(int i=0;i<arr_length;i++){
            if(sorted_arr[i] != arr[i]){
                idx = idxMap_asc.get(sorted_arr[i]);
                idxMap_asc.put(arr[i],idx);
                temp = arr[i];
                arr[i] = sorted_arr[i];
                arr[idx] = temp;
                answer_asc++;
            }
        }
 
        // 내림차순을 통한 cost 계산
        for(int i=0;i<arr_length;i++){
            if(reversed_arr[i] != arr_desc[i]){
                idx = idxMap_desc.get(reversed_arr[i]);
                idxMap_desc.put(arr_desc[i],idx);
                temp = arr_desc[i];
                arr_desc[i] = reversed_arr[i];
                arr_desc[idx] = temp;
                answer_desc++;
            }
        }
        
        // 더 작은값을 반환한다.
        return answer_asc > answer_desc ? answer_desc : answer_asc;
    }
 
    private static final Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
 
        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
 
        int[] arr = new int[n];
 
        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
 
        for (int i = 0; i < n; i++) {
            int arrItem = Integer.parseInt(arrItems[i]);
            arr[i] = arrItem;
        }
 
        int result = lilysHomework(arr);
 
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();
 
        bufferedWriter.close();
 
        scanner.close();
    }
}
 
cs


'Algorithm > Java 풀이' 카테고리의 다른 글

JAVA #3_ The Grid Search  (0) 2018.08.08
JAVA #2_ Lily's Homework  (0) 2018.08.05
Java #1_ 가장 긴 팰린드롬 길이 구하기  (0) 2018.07.12
블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc