no image
02. 딥러닝 발전의 밑거름, MLP
이전 포스팅으로 XOR 문제를 해결할 수 없는 SLP와 이를 극복한 MLP에 대해 간략하게 설명했다. 이번 포스팅 부터는 딥러닝을 구현한 파이썬 코드와 개념, 그리고 베이스라인에 대해 설명하면서 진행할 예정이다. | 퍼셉트론을 이용한 딥러닝의 학습 과정딥러닝 학습 과정은 먼저 아주 크게 두 갈래로 나눌 수 있다. 1) feed forward (순전파)- 말 그대로 전진하는 것이다, 계산을 input → neuron → output 방향으로 진행되고 이 계산의 목적은 임의의 예측값인 y_hat을 도출하는 것이다.- 모델이 학습되기 전에는 이 y_hat이 제멋대로인 값을 출력할 수 있다. (정답 레이블 또는 기대값이 100인데 15억을 출력한다거나) 2) Backpropagation (역전파)- 역전파는 설..
2024.11.17
no image
01. 퍼셉트론의 이해, SLP
| 퍼셉트론이 뭘까?대학교에서 인공지능개론 수업을 들을 때, 퍼셉트론을 뉴런이라고 했다가, 알고리즘이라고 했다가 이런 식으로 설명하시는걸 그대로 필기해서 나중에 정말 헷갈렸던 경험이 있다. 퍼셉트론은 Input(x)에서부터 weight(w)를 바탕으로 계산된 output(y_hat)을 도출하는 일련의 수학적인 과정 전체를 의미한다.이 연산 과정은 인간 뇌 속에 있는 뉴런의 동작 방식과 유사하기 때문에 artificial neuron이라고도 한다고..(뇌의 뉴런도 시냅스에 입력된 정보를 전기신호(출력형태)로 축삭돌기를 통해 보내는 어쩌구..) 이런 저런 아티클들을 찾아보니, 뉴런과 퍼셉트론에 대한 이해는 아래와 같이 여러 갈래로 정리하고 있었다. 1. 퍼셉트론과 뉴런의 차이는 artifical 이냐 bio..
2024.11.04
no image
인공지능에 대한 이해
※참고: 파이썬으로 시작하는 머신러닝+딥러닝  인공지능(AI, Artificial Intelligence)이란, 기계가 사람의 학습 형태를 모방하여 지능을 가진 것 처럼 행동하도록 만든 것을 의미한다.최근 해당 분야가 각광받기 시작하면서 머신러닝, 딥러닝 등의 용어를 쉽게 접할 수 있는데 결국은 AI안에 포함된 개념이다.   머신러닝은 인공지능 객체가 데이터에 대한 규칙 또는 정보를 학습할 수 있도록 설계하는 알고리즘이며, 딥러닝은 이런 머신러닝 기법의 일종으로 신경망 알고리즘을 적용해 인간과 유사하게 판단하는 프로그램을 구현한 기계 학습 방법이다. 인공지능이라는 개념이 등장한건 17~18세기 경이고, 직접 구현되기 시작한건 컴퓨터가 등장한 후 1900년대 중반부터이지만, 정보 처리 방법과 당시 컴퓨터의..
2024.11.02
no image
[프로그래머스] 문자열 압축 (파이썬)
문제 출처: 프로그래머스 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 🔎 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "..
2023.03.05
no image
[프로그래머스] 가장 긴 팰린드롬 (파이썬)
문제 출처: 프로그래머스 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 🔎 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다. 시간을 고려해야 한다는 점을 제외하고는 그렇게 어려운 문제는 아니었다. 또 팰린드롬이라는 주제는 이미 다른 문제들에서도 많이 다뤘기 때문에 접..
2023.03.05
no image
[프로그래머스] 입국심사 (파이썬)
문제 출처: 프로그래머스 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 🔎 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다. 입국심사를 기다리는 사람..
2023.03.04
no image
[프로그래머스] 순위 (파이썬)
문제 출처: 프로그래머스 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다. 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 retur..
2023.03.02
no image
[백준] 6603, 로또 (파이썬)
문제 출처: 백준 온라인 저지 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,2..
2023.02.22

이전 포스팅으로 XOR 문제를 해결할 수 없는 SLP와 이를 극복한 MLP에 대해 간략하게 설명했다.

 

이번 포스팅 부터는 딥러닝을 구현한 파이썬 코드와 개념, 그리고 베이스라인에 대해 설명하면서 진행할 예정이다.

 

| 퍼셉트론을 이용한 딥러닝의 학습 과정

딥러닝 학습 과정은 먼저 아주 크게 두 갈래로 나눌 수 있다.

대충의 과정

 

1) feed forward (순전파)

- 말 그대로 전진하는 것이다, 계산을 input → neuron → output 방향으로 진행되고 이 계산의 목적은 임의의 예측값인 y_hat을 도출하는 것이다.

- 모델이 학습되기 전에는 이 y_hat이 제멋대로인 값을 출력할 수 있다. (정답 레이블 또는 기대값이 100인데 15억을 출력한다거나)

 

2) Backpropagation (역전파)

- 역전파는 설명의 편의성을 위해서, 순전파의 반대방향으로 연산을 진행하는 것이라고 한다.  (맞는 말이긴 하지만 곱하기를 나누기로 하는게 반대다! 라고 생각하는 나 같은 사람한테는 맞지 않는 설명이라고 생각하며 아래만 보는게 더 와닿는 느낌이다.)

- 역전파는 순전파를 통해서 결정된 y_hat에 대해서 ①정답 레이블로부터 오차 크기를 계산해서 ② 순전파 계산에 활용되는 weight와 같은 파라미터들을 조정해 나가는 과정이다.

 

- 파라미터를 조정하는 방향은 파라미터가 total Loss에 미치는 영향에 대해 알아야 하므로, 편미분형식으로 진행이 되는데 상세히 설명되어 있는 wikidocs 문서를 참고하면 좋을 것 같다.

대충 이런 느낌

* learning_rate : 역전파 한 스텝 당, 얼마나 weight를 조절할 지에 대한 비율

 

 

| MLP 구현을 통한 딥러닝 학습 방법에 대한 이해

- 준비물 : 파이썬 3.6 버전 이상, numpy, pandas, matplotlib, seaborn, torch, scikit-learn

 

오늘은 가볍게 MLP를 통해 "tips" 라는 데이터 셋을 학습하도록 구성해본다.

tips 데이터셋은 seaborn라이브러리에서 제공해주는 어떤 식당에서의 결제/팁/결제자 정보를 담은 데이터셋이다.

 

1. 데이터셋 불러오기 및 확인

import pandas as pd
import numpy as np
import seaborn as sns

data = sns.load_dataset('tips')

data.info()
'''
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 244 entries, 0 to 243
Data columns (total 7 columns):
 #   Column      Non-Null Count  Dtype   
---  ------      --------------  -----   
 0   total_bill  244 non-null    float64 
 1   tip         244 non-null    float64 
 2   sex         244 non-null    category
 3   smoker      244 non-null    category
 4   day         244 non-null    category
 5   time        244 non-null    category
 6   size        244 non-null    int64   
dtypes: category(4), float64(2), int64(1)
memory usage: 7.4 KB
'''

data.head()
'''
total_bill	tip	sex	smoker	day	time	size
0	16.99	1.01	Female	No	Sun	Dinner	2
1	10.34	1.66	Male	No	Sun	Dinner	3
2	21.01	3.50	Male	No	Sun	Dinner	3
3	23.68	3.31	Male	No	Sun	Dinner	2
4	24.59	3.61	Female	No	Sun	Dinner	4
'''

 

데이터셋을 불러오는 법과 구성은 위와 같고,

데이터셋을 통해 tip을 제외한 6개의 컬럼을 이용해서 tip을 얼마나 주었을 지 예측하는 MLP모델을 작성해보려한다.

 

2. 데이터 전처리

import torch
import torch.nn as nn
import torch.optim as optim
from torch.utils.data import DataLoader, TensorDataset

from sklearn.model_selection import train_test_split
from sklearn.preprocessing import LabelEncoder

device = torch.device("mps" if torch.cuda.is_available() else "cpu")

def categorical_encoding(col):
    encoder = LabelEncoder()
    data[col] = encoder.fit_transform(data[col].to_numpy())


for i in data.columns:
    if data[i].dtype == 'category':
        categorical_encoding(i)


x = data.iloc[:, [0,2,3,4,5,6]].values
y = data.iloc[:, [1]].values

x = torch.tensor(x, dtype=torch.float32).to(device)
y = torch.tensor(y, dtype=torch.float32).to(device)
print(x.shape, y.shape)

x_train, x_val, y_train, y_val = train_test_split(x, y, test_size=0.3, random_state=42)
print(x_train.shape, x_val.shape)

train = TensorDataset(x_train, y_train)
validation = TensorDataset(x_val, y_val)
print(train)

train_loader = DataLoader(train, batch_size=16, shuffle=True)
val_loader = DataLoader(validation, batch_size=16)
print(train_loader, val_loader)

 

* 맥북 M1 에어 모델에서 작성되어, mps로 매핑하였으나 cpu를 사용하려면 device구문을 제거하면 된다.

 

1) total_bill과 tip을 제외한 나머지 value들은(성별, 흡연 여부, 요일, 방 크기 등) 모두 categorical 데이터이므로, 레이블링 작업을 통해 모델이 학습 가능한 형태로 수정한다.

 

2) 그 다음 독립변수(x)와 예측할 종속변수(y)로 데이터셋을 구분해준 뒤, 사이킷런을 통해 학습에 사용될 trainset과 모델 검증에 사용될 validation set으로 데이터를 분할해준다. (비율은 통상적으로 7:3)

 

3) 모델 학습에 용이하도록 데이터의 형태를 변경해준다. 
- 텐서 데이터셋은 train set인 x_train, y_train 두 쌍을 하나의 데이터 셋으로 저장하고 인덱싱이 가능한 형태로 변경한다

- 데이터로더는 batch size를 조정해 추후 학습을 진행할 때 배치 단위로 전달할 수 있으며, augmentation, shuffle 등 다양한 기능을 지원하기에 수동으로 해야 하는 작업들을 보다 편하게 사용할 수 있도록 변경한다.

 

더보기

* 참고

dataset = next(iter(train))
x_sample, y_sample = dataset
print("x sample: ", x_sample)
print("x sample shape: ", x_sample.shape)
print("y sample: ", y_sample)
print("y sample shape: ", y_sample.shape)

print('\n----- dataloader ----- \n')
# 첫 번째 배치 가져오기
first_batch = next(iter(train_loader))
X_batch, y_batch = first_batch
x_last, y_last = list(train_loader)[-1]

print("X_batch shape:", X_batch.shape)  # 입력 데이터(batch) 크기
print("y_batch shape:", y_batch.shape)  # 레이블(batch) 크기
print("X_batch example:", X_batch[:5])  # X의 일부 예제
print("y_batch example:", y_batch[:5])  # y의 일부 예제

print("last batch shape: ", x_last.shape, y_last.shape)


'''
x sample:  tensor([15.5300,  1.0000,  1.0000,  1.0000,  0.0000,  2.0000])
x sample shape:  torch.Size([6])
y sample:  tensor([3.])
y sample shape:  torch.Size([1])

----- dataloader ----- 

X_batch shape: torch.Size([16, 6])
y_batch shape: torch.Size([16, 1])
X_batch example: tensor([[ 9.7800,  1.0000,  0.0000,  3.0000,  1.0000,  2.0000],
        [25.7100,  0.0000,  0.0000,  2.0000,  0.0000,  3.0000],
        [24.0600,  1.0000,  0.0000,  1.0000,  0.0000,  3.0000],
        [34.3000,  1.0000,  0.0000,  3.0000,  1.0000,  6.0000],
        [10.2900,  0.0000,  0.0000,  2.0000,  0.0000,  2.0000]])
y_batch example: tensor([[1.7300],
        [4.0000],
        [3.6000],
        [6.7000],
        [2.6000]])
last batch shape:  torch.Size([10, 6]) torch.Size([10, 1])
'''

 

tensordataset, dataloader 모두 iterable한 객체로, 그냥 호출하면 객체 타입정보가 떠서 iter형식으로 불러오면 어떻게 생겼는지 확인할 수 있다.

 

3. 모델 정의 및 평가/최적화 함수 로딩

class MLP(nn.Module):
    def __init__(self):
        super(MLP, self).__init__()
        self.fc1 = nn.Linear(6, 64)
        self.fc2 = nn.Linear(64, 32)
        self.fc3 = nn.Linear(32, 1)
        self.relu = nn.ReLU()
    
    def forward(self, x):
        x = self.relu(self.fc1(x))
        x = self.relu(self.fc2(x))
        x = self.fc3(x)

        return x
        
        
model = MLP().to(device)
criterion = nn.MSELoss().to(device)
optimizer = optim.Adam(model.parameters(), lr = 0.001)

 

1) pytorch 기반의 MLP 모델을 작성한다.

- 모델은 forward 함수를 통해 학습이 진행되며, 최초 입력인 x가 모델 내부의 fc1 ~ fc3 레이어를 거쳐서 최종 Output을 생산한다.

 

2) 평가함수인 MSE (Mean Squared Error) 와 역전파를 진행할 때 최적화 알고리즘으로 Adam을 사용하도록 세팅

- adam 알고리즘은 GD 방식에서 여러 개선점을 거쳐 나온 알고리즘으로 자세한 설명은 기회가 닿을 때 다시 설명할 예정..

- learning rate는 0.001 (너무 작으면 local minimum, 너무 크면 minimum을 찾지 못할 수 있으므로 적당히 조절)

 

4. 학습 및 평가 진행 함수 구성

from sklearn.metrics import mean_absolute_error, r2_score

def train(model, train_loader, criterion, optimizer):
    model.train()
    total_loss = 0

    for x_batch, y_batch in train_loader:
        x_batch, y_batch = x_batch.to(device), y_batch.to(device)
        y_batch = y_batch.view(-1, 1)

        optimizer.zero_grad()
        outputs = model(x_batch)
        loss = criterion(outputs, y_batch)
        loss.backward()
        optimizer.step()

        total_loss += loss.item()
    
    return total_loss / len(train_loader)

def evaluate(model, val_loader, criterion):
    model.eval()
    total_loss = 0
    y_true = []
    y_pred = []

    with torch.no_grad():
        for x_val, y_val in val_loader:
            x_val, y_val = x_val.to(device), y_val.to(device)
            y_val = y_val.view(-1, 1)

            pred = model(x_val)

            loss = criterion(pred, y_val)
            total_loss += loss.item()

            y_true.extend(y_val.cpu().numpy())
            y_pred.extend(pred.cpu().numpy())
    
    avg_loss = total_loss/len(train_loader)

    y_true = np.array(y_true)
    y_pred = np.array(y_pred)

    mae = mean_absolute_error(y_true, y_pred)
    r2 = r2_score(y_true, y_pred)

    return avg_loss, mae, r2

 

1) train 데이터셋이 학습을 진행할 train 함수와 validation 데이터셋이 적용될 evaluate 함수를 구성

- train 데이터셋에는 역전파를 진행해 파라미터를 조절해 나가지만, validation에는 역전파하지 않는다.

+ 혹시나 궁금할까봐 다른 평가함수들도 추가해봤다 (MAE, R2_score)

 

5. 학습 진행

epochs = 1000
for epoch in range(epochs):
    train_loss = train(model, train_loader, criterion, optimizer)
    val_loss, mae, r2 = evaluate(model, val_loader, criterion)
    if (epoch + 1) % 100 == 0:
        print(f"Epoch [{epoch+1}/{epochs}], Train Loss: {train_loss:.4f}, Validation Loss: {val_loss:.4f}")
        print(f"Matric Eval MAE: {mae:.3f}, R2_score: {r2:.3f}")

'Epoch [1000/1000], Train Loss: 0.4394, Validation Loss: 0.5791 Matric Eval MAE: 0.862, R2_score: 0.017'

    # es(val_loss)
    # if es.early_stop:
    #     print(f"===== Early Stopped triggered. =======")
    #     print(f"Epoch [{epoch+1}/{epochs}], Train Loss: {train_loss:.4f}, Validation Loss: {val_loss:.4f}")

    #     break

# 예측 테스트
with torch.no_grad():
    sample = torch.tensor(data.iloc[1, [0,2,3,4,5,6]].values, dtype=torch.float32)
    predicted = model(sample).numpy()
    print(f"Predicted tip: {predicted[0]:.2f}\nActual tip: {data.iloc[1, 1]}")
    print(data.iloc[1, [0]])
    
'''
Predicted tip: 1.50
Actual tip: 1.66
total_bill    10.34
'''

 

1) 에폭수를 지정하고 학습을 진행한다.

- epoch : 모든 train 데이터셋을 활용해서 학습을 한번 진행하는 카운트 단위

- 한 에폭에서는 DataLoader에서 지정한 배치사이즈(미니배치)를 기준으로 순차적으로 전달해 학습이 진행된다.

- early stopping rule을 적용시켰었는데, 너무 일찍 종료돼서 제외했다.

ex) batch_size가 16이면, 한 배치마다 16셋의 train 데이터가 전달된다.

 

2) 모든 학습이 완료되었으면, validation 셋을 가지고 모델 검증을 진행한다.

- 원본 데이터에서 tip은 평균 2.99, 중앙값 2.90, 표준편차가 1.3인데 최종 에폭에서 MSE가 0.5791로 측정되었다.

- 예측 단계에서는 실제 팁이 1.66달러인데, 모델이 1.5달러로 예측하는 모습을 보였다.

 

*결론: 실제 팁이 대충 4~5000원인데, 모델의 MSE가 8~900원 정도이면 생각보다 예측을 잘 하진 못한 것 같다.

 

 

'인공지능 > 딥러닝' 카테고리의 다른 글

01. 퍼셉트론의 이해, SLP  (2) 2024.11.04

출처: IT위키

 

| 퍼셉트론이 뭘까?

대학교에서 인공지능개론 수업을 들을 때, 퍼셉트론을 뉴런이라고 했다가, 알고리즘이라고 했다가 이런 식으로 설명하시는걸 그대로 필기해서 나중에 정말 헷갈렸던 경험이 있다.

 

퍼셉트론은 Input(x)에서부터 weight(w)를 바탕으로 계산된 output(y_hat)을 도출하는 일련의 수학적인 과정 전체를 의미한다.

이 연산 과정은 인간 뇌 속에 있는 뉴런의 동작 방식과 유사하기 때문에 artificial neuron이라고도 한다고..

(뇌의 뉴런도 시냅스에 입력된 정보를 전기신호(출력형태)로 축삭돌기를 통해 보내는 어쩌구..)

 

이런 저런 아티클들을 찾아보니, 뉴런과 퍼셉트론에 대한 이해는 아래와 같이 여러 갈래로 정리하고 있었다.

 

1. 퍼셉트론과 뉴런의 차이는 artifical 이냐 biological 이냐로 본다.

2. 퍼셉트론은 딥러닝 동작 방식의 기초가 되는 인풋->아웃풋의 일련의 과정이며,

    인풋과 아웃풋 그 사이 중간의 연산을 통해 활성화 되는 하나의 셀을 뉴런이라고 한다.

대충 이런 느낌

 

### Whole step = perceptron

def call_me_perceptron(input=None):
    # 1.inputs
    if not input:
    	input = np.array([1, 2, 3])

    # 2.weights
    w = np.array([.5, .5, .5])

    # 3.bias 
    bias = -.7

    # 4.calculate output
    output = np.sum(w*input)+b
    
    return output

 

SLP (Single Layer Perceptron) 는 그림과 똑같기 때문에 뉴런? 이랑 아웃풋이랑 무슨 차이지.. 하는 느낌이 강하게 들지만, MLP (Multiple Layer Perceptron) 에서는 확실히 여러 레이어가 존재하기 때문에 뉴런의 존재를 더욱 뚜렷하게 느낄 수 있다.

 

SLP, 즉 하나(한번?)의 퍼셉트론으로는 XOR (두 입력 값의 이진 분류가 다르면 1, 같으면 0 반환) 의 문제: 선형으로 풀 수 없는 복잡한 문제는 풀 수 없기에, MLP의 개념이 등장했고 이것이 딥러닝 발전을 이끌기 시작했다.

 

SLP는 위에 작성한 간단한 코드처럼 복잡한 라이브러리 연산 없이도 구현할 수 있으므로 코드는 생략한다.

'인공지능 > 딥러닝' 카테고리의 다른 글

02. 딥러닝 발전의 밑거름, MLP  (0) 2024.11.17

인공지능에 대한 이해

pluralmajor
|2024. 11. 2. 14:34

※참고: 파이썬으로 시작하는 머신러닝+딥러닝

 

 

인공지능(AI, Artificial Intelligence)이란, 기계가 사람의 학습 형태를 모방하여 지능을 가진 것 처럼 행동하도록 만든 것을 의미한다.

최근 해당 분야가 각광받기 시작하면서 머신러닝, 딥러닝 등의 용어를 쉽게 접할 수 있는데 결국은 AI안에 포함된 개념이다.

 

출처: 지디넷 코리아

 

 

머신러닝은 인공지능 객체가 데이터에 대한 규칙 또는 정보를 학습할 수 있도록 설계하는 알고리즘이며, 딥러닝은 이런 머신러닝 기법의 일종으로 신경망 알고리즘을 적용해 인간과 유사하게 판단하는 프로그램을 구현한 기계 학습 방법이다.

 

인공지능이라는 개념이 등장한건 17~18세기 경이고, 직접 구현되기 시작한건 컴퓨터가 등장한 후 1900년대 중반부터이지만, 정보 처리 방법과 당시 컴퓨터의 성능의 한계로 크게 발전하지 못했다.

 

그러다 파라미터의 학습 과정을 역으로 전파하며 파라미터 값을 조정하는 역전파(Backpropagation) 알고리즘과 퍼셉트론(Perceptron)이 등장하면서 딥러닝 기반의 인공지능 개념이 성장하기 시작했다.

 

딥러닝에 대한 간단한 소개

출처: SK하이닉스 뉴스룸

 

딥러닝 모델은 단순한 퍼셉트론의 배치와 순전파 과정으로만 학습되는 것이 아닌, 상기 사진에서 확인할 수 있는 것 처럼 여러 개의 퍼셉트론과 여러 은닉층(Hidden Layer)를 추가함으로써 복잡한 데이터에서 학습하고 문제를 해결할 수 있다.

 

은닉층(Hidden Layer)란, 인풋에서 특정 계산식을 통해 도출된 결과를 임시로 저장하는 층으로 생각할 수 있고,

특정 계산식은 구현하고자 하는 모델에 따라 달라질 수 있고, 계산식에 포함된 파라미터값을 조정하여 가장 정답 레이블과 가까운 답을 찾아가는 과정이 딥러닝 학습 과정이라고 볼 수 있다.

 

계산식에 포함된 파라미터값을 조정하는 과정은 앞서 언급했던 역전파 알고리즘을 통해 Loss 값이 최소가 되도록 찾아가는 과정이다.

 

다양한 딥러닝 모델들의 가장 기초적인 부분부터 공부를 하고 블로그에 기재하고 있으며, 최종 목표인 멀티모달까지의 과정을 최대한 자세히 이해할 수 있도록 노력할 예정이다.

문제 출처: 프로그래머스

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제 설명

🔎 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

출처: 프로그래머스

설명의 길이가 길어 문제 이해에 도움이 되는 일부만 발췌하였습니다. 상세한 내용은 프로그래머스 페이지에서 확인하실 수 있습니다.


내 기준에서 이 문제는 문제를 정확히 파악하는 것이 해결의 관건이었다.

 

처음에는 문자열 내부에 있는 중복되는 문자열로 압축했을 때 가장 짧은 길이가 나오면 되는 줄 알았다.

(ex. 'abbbccc' ➡'a3b3c')

 

하지만, 마지막 예시에 '문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.'  이라는 문구가 있는데 이를 기준으로 'abbbccc'를 다시 3개씩 자르면 'abb, bcc, c'가 되므로 자를 수 없다.

 

아래 사진은 "xababcdcdababcdcd" 를 압축하는 법에 대해 설명한다.

출처: 프로그래머스

 

이를 이해한 후 문제를 푸니 간단하게 풀렸다.

 

<정답 코드>

def solution(s):
    n = len(s)
    answer = n
    
    for i in range(1, n//2+1):
        before = s[:i]
        same = 1
        new = ''
        for j in range(i, n, i):
            temp = s[j:j+i]
            if before == temp:
                same += 1
            else:
                if same == 1:
                    new += before
                else:
                    new += str(same) + before
                
                before = temp
                same = 1
        
        if same == 1:
            new += temp
        else:
            new += str(same) + temp

        answer = min(answer, len(new))
    
    return answer

접근은 아래와 같다.

  1. 문자열은 최대 len // 2 만큼 자를 수 있으므로, 1개씩 자르는 것부터 len//2개 자를 때 까지를 반복문으로 순회한다.
  2. 이를 기준으로 문자열을 잘랐을 때, 반복이 되는 경우를 찾기 위해 이전 문자 값을 저장하는 before을 생성해 중복되는 문자열을 count해준다.
  3. 중복되는 문자열이 있다면 count한 값을 앞에 붙여 새로운 문자열을 만든다.
  4. 문자열 자르기를 탈출했을 때 마지막으로 잘린 문자열은 new에 붙지 않으므로 붙여준다.
  5. answer에 더 작은 값을 업데이트 해준다.

문제 자체는 그렇게 어렵지 않았으나, 잘못 읽으면 나처럼 시간을 빼앗길 수 있으므로 신중하게 문제를 읽는 습관을 들이는 것이 좋을 것 같다.

문제 출처: 프로그래머스

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제 설명

🔎 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

출처: 프로그래머스


시간을 고려해야 한다는 점을 제외하고는 그렇게 어려운 문제는 아니었다. 또 팰린드롬이라는 주제는 이미 다른 문제들에서도 많이 다뤘기 때문에 접근도 어렵지 않았다. 사실 문자열의 길이를 줄인다면 더 낮은 레벨을 부여 받지 않았을까 생각이 드는 문제였다.

 

문제를 푸는데 한 두번 밖에 시행착오를 겪지 않았지만, 다른 사람들의 풀이를 보니 내 풀이가 최적의 풀이는 아니었다.

 

<정답 코드>

def solution(s):
    answer = 1
    n = len(s)
    
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
            	mid = (i+j) // 2
                aft = s[j:mid:-1]
                if (i+j) % 2 == 0:
                    pre = s[i:mid]
                else: 
                    pre = s[i:mid+1]
                    
                if pre == aft:
                    answer = max(answer, j-i+1)
                        

    return answer

접근은 아래와 같다.

  1. S를 구성하는 모든 문자를 점검하면서 현재 값과 같은 값을 가지는 위치를 모두 찾은 다음 비교한다.
  2. 문자열을 비교할 때는 split된 문자열의 길이가 짝수일 때와 홀수일 때가 다르다.
    1. 홀수일 때는 중앙값을 제외한 나머지가 대칭을 이루면 팰린드롬이다.
    2. 짝수일 때는 중앙값이 없으므로 전체가 대칭을 이루면 팰린드롬이다.
  3.  가장 큰 값을 answer로 업데이트한다. 가장 짧은 팰린드롬의 길이는 한 단어 (ex. 'a')이므로 최소값이 1이 출력될 수 있도록 수정해야한다.

시행착오 부분은 처음에 팰린드롬은 길이가 홀수여야한다는 착각과, 최소 길이가 1이라는 점을 망각했기에 틀린 답을 제출했었다. 이 부분만 제거하니 문제는 풀렸다.

 

다만 제출된  답안의 실행시간이 1647ms로 크게 나왔다는 점이 살짝 걸렸다.

 

다른 사람들의 풀이를 살펴보니 DP로 접근한 사람도 있고, early stop 조건을 삽입한 사람도 있었다. 다양한 풀이가 있는 만큼 내 코드도 개선될 부분이 있을거라 생각한다.

문제 출처: 프로그래머스

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제 설명

🔎 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

출처: 프로그래머스


처음에는 최소공배수 문제인 줄 알았다. 하지만 심사관의 수가 변화할 수 있는데다가 심사 시간이 너무 크고, 무엇보다 기다렸다가 다른 사람한테 받는 경우가 더 빠른 경우도 있어서 아니라는 것을 알 수 있었다.

 

결국 이 문제는 이분탐색 문제였는데, 내가 이분탐색을 많이 연습하지 않아 접근하기 힘들어 결국 질문하기의 도움을 받아 풀 수 있었다.

 

<정답 코드>

def solution(n, times):
    answer = 0
    
    min_t = times[0]
    max_t = times[0] * n
    
    while True:
        mid = (min_t + max_t) // 2
        cnt = 0
        
        for i in times:
            cnt += mid//i
        
        if cnt < n:
            min_t = mid
        
        elif cnt >= n:
            max_t = mid
        
        if min_t == max_t - 1:
            answer = max_t
            break
        
    return answer

접근은 아래와 같다.

주어진 times 배열은 오름차순으로 정렬된 배열이라는 가정을 포함한다. (⬅ 문제 내에서 제시된 사항은 아니지만, 주어진 테스트 케이스는 위 가정을 모두 만족하였다.)

  1. 입국심사가 가장 빠르게 끝날 때는 가장 빠른 심사관 한명에게 한명이 심사 받는 시간이므로 times[0], 가장 오래 걸린다하더라도 가장 빠른 심사관이 n명을 모두 점검하는 시간이므로 times[0] * n 을 각각 변수로 저장한다.
  2. 이 두 변수를 가지고 이분탐색을 시작한다.
    1. mid 시간을 소요했을 때 심사 받은 사람의 수는 mid 시간에서 각 심사관의 소요 시간을 나눈 몫만큼이다.
    2. 통과한 사람의 수가 n보다 작다면 mid가 증가하는 방향으로 가야하므로 min_t를 mid로 업데이트 한다. 반대로 n보다 크다면 mid가 감소해야 하므로 max_t를 mid로 업데이트 한다.
    3. 결과적으로 정확히 n명을 통과하는 시간 중 최단 시간을 출력해야하므로 n == cnt라도 계속해서 시간을 줄여가면서 탐색한다.
    4. 최종 탐색 결과는 min_t와 max_t가 1만큼 차이날 때가 되므로 이 때의 시간을 출력한다.

 

이분탐색 문제는 원래 난이도가 높기도 하고 다른 문제들에 비해 문제 수도 많지 않아서 연습이 덜 되어 있었다. 이번 문제로 배열 안에서 필요한 시간을 도출하는게 아닌, 외부 조건을 도입하면서 이분 탐색을 하는 방법을 배울 수 있어서 좋았다.

문제 출처: 프로그래머스

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

출처: 프로그래머스


처음 문제를 읽었을 때는 어떻게 접근 해야할지 고민을 오래한 문제다.

 

내 생각의 흐름은 이랬다.

순위를 정하는 문제 ➡ sort문제 ➡ 하지만 sort의 key를 설정하기 어려움 ➡ Tree 형식으로 질 때 마다 자식 노드로 추가해주면 되지 않을까? ➡ 이렇게 됐을 때 구현은 어떻게 해야하나..

 

이런 식으로 생각을 이어가면서 깨작깨작 작성하다보니 정답에 도달할 수 있었다.

 

<정답 코드>

def solution(n, results):
    answer = 0
    rank = {i + 1: [set(), set()] for i in range(n)}
    order = [0] * (n + 1)

    for win, lose in results:
        rank[win][0].add(lose)
        rank[lose][1].add(win)

    for _ in range(2):
        for i in rank.keys():
            for wins in rank[i][0]:
                rank[i][0] = rank[i][0].union(rank[wins][0])

            for loses in rank[i][1]:
                rank[i][1] = rank[i][1].union(rank[loses][1])

    for i in rank.keys():
        if len(rank[i][0]) + len(rank[i][1]) == n - 1:
            answer += 1

    return answer

접근은 아래와 같다.

어떤 선수의 총 경기 횟수가 n-1이면 해당 선수의 순위를 알 수 있다. (비기는 경우는 없기 때문에)

  1. 선수 번호를 기준으로 해당 선수가 이긴 선수들과 패배한 선수들을 기록하는 dictionary를 만든다.
    1. 딕셔너리의 value는 두 set의 집합으로 만들어진다.
    2. 0번 index는 해당 선수가 이겼던 선수들을 기록했고, 1번 index에는 해당 선수가 졌던 선수들을 기록했다.
  2. 경기 결과를 하나씩 살피면서 rank를 채워준다.
  3. 채워진 rank를 순회하면서 한번 이겼던 선수에게 패배한 선수들이 있다면 채워주는 작업을 반복한다.
    1. 예를 들어 results가 [3, 1], [1, 2]이었다고 하면 최초의 rank는 {1: [(2), (3)], 2:[(1), ()], 3:[(), (1)]}이 된다. 이 때 아래 for문을 통해 한번 순회해주면 rank는 {1:[(2), (3)], 2:[(1), (3)], 3:[(),(1, 2)]가 되게 된다.
  4. 마지막으로 모든 선수들 중 총 경기횟수가 n-1번 진행된 선수들만 count해준다.

 

운이 좋게 위 코드에서는 rank를 채워주는 작업이 총 3번 만에 모든 test case가 통과되었지만, 곰곰히 다시 생각해보니 rank에 업데이트가 새로 일어나지 않을 때 까지 반복해서 업데이트해주어야 진짜 정답이지 않을까 했다. (아닐수도 있음)

 

이렇게 보니 트리라기 보다 그래프 문제에 가까워 보였다. 실제 문제를 보니 그래프 문제로 분류되어 있었고 다른 사람들은 bfs나 플로이드-와샬 알고리즘으로 문제를 해결했다고 했다. 독특한 풀이를 했다고 좋아하긴 했지만, 남들이 생각하는 걸 생각하지 못했다는 점에서 약간의 아쉬움도 있었다.


이번 문제를 통해서 드디어 프로그래머스 level3에 도달할 수 있었다.

여러 번 시도하면서 운 좋게 몇일 전에 풀어봤던 문제가 나오기도 하고, level 3치고 쉬운 문제가 나온 적도 있었지만 항상 다른 문제에서 막혀서 뚫지 못했었는데 이번에는 둘다 모르는 문제였지만 천천히 생각하면서 푸니 통과할 수 있었다.

 

프로그래머스의 level이 현재 내 코딩 수준을 정의해주는 것은 아니지만 (현재까지 프로그래머스 문제만 300문제 가까이 풀었지만, 아직도 풀지 못한 level2, level3문제가 많다.) 꾸준히 성장하고 있고, 꼼수 부리지 않고 통과하겠다는 의지가 먹혀든 것 같아서 기분이 좋았다.

 

'알고리즘 > 그래프 탐색' 카테고리의 다른 글

[프로그래머스] 합승 택시 요금 (파이썬)  (0) 2023.02.14
[백준] 13023 ABCDE  (0) 2023.01.26

문제 출처: 백준 온라인 저지

 

6603번: 로또

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로

www.acmicpc.net

 

문제 설명

🔎 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

출처: 백준 온라인 저지


<정답 코드>

from heapq import heapify, heappop
from itertools import combinations

while True:
    inp = list(map(int, input().split()))
    if inp == [0]:
        break

    n = inp[0]
    inp = inp[1:]
    com = list(combinations(inp, 6))
    heapify(com)

    while com:
        print(*heappop(com))

    print()

combinations를 통해 구현하는 간단한 문제였다.

 

접근은 아래와 같다.

  1. 입력 받은 배열을 k와 S로 구분한 후, combinations를 이용해 6개를 뽑는 집합을 만든다.
  2. 집합을 heapq를 통해 정렬한 후 heappop하면서 오름차순으로 뽑는다.

이 전에 비슷한 문제들을 풀었던 것과 달리 min heap을 활용해서 정렬해보았다.