Autograd

• Autograd ; Automatic gradient calculating API
• forward와 backward가 가능하게 해줌
• 즉, 해당 변수가 계산되는 데에 사용했던 모든 변수들의 미분값을 구하면서 forward 또는 backward를 진행하게 해준다.
• 해당 변수가 계산되어 온 history를 Computational Graph로 가지고 있어서 이러한 동작이 가능한 것이다.

위 이미지와 같은 Computational Graph를 사용하여 Autograd가 진행된다.

autograd를 사용한 예제를 살펴보자.

x = torch.ones(2,2, requires_grad=True) # requires_grad=True로 해야 x의 연산들을 추적하기 시작한다.

'''
print(x) 는 다음과 같음
tensor([[1., 1.],
        [1., 1.]], requires_grad=True)
'''

y = x+1

'''
print(y) 는 다음과 같음
tensor([[2., 2.],
        [2., 2.]], grad_fn=<AddBackward0>)
'''

z = 2*y**2
res = z.mean()

'''
print(res) 는 다음과 같음
tensor(8., grad_fn=<MeanBackward0>)
'''

res.backward() # 역전파 계산

'''
print(x.grad) 는 다음과 같음 (계산한 x의 미분값 출력)
tensor([[2., 2.],
        [2., 2.]])
'''

위 코드의 계산 과정을 수식으로 보면 다음과 같다.

1. res = z.mean() 이었으므로 $res = \dfrac{(z_1 + .. + z_4)}{4}$ 이다.

2. 이때 $z_i = 2 * y_i^2$ 이다.

3. $y_i = x_i+1$ 이었으므로, $z_i = 2(x_i+1)^2$ 이다.

4. $\dfrac{d(res)}{dx_i}$ 는 1번 전개에 의해 $\dfrac{d(z)}{4\cdot dx_i}$ 이다.

5. 이때 $\dfrac{d(z)}{dx_i} = 4(x_i+1)$ 이다.

6. 따라서 $\dfrac{d(res)}{dx_i}$는 $x_i+1$ 이다.

7. 처음에 x = torch.ones(2,2, requires_grad=True) 이었으므로, x는 1로 채워진 2 x 2 행렬이다.

8. 따라서 x.grad는 여기에 1씩 더한 tensor([[2., 2.], [2., 2.]])가 된다.

보다시피 단순한 연산 몇 개에 대한 계산임에도 꽤나 복잡하다.. 이러한 연산을 직관적이고 간단히 해주는 pytorch에게 박수를 👏👏

☠️ autograd 사용 시 주의해야 할 점 ☠️

• 순전파/역전파를 적용할 변수를 선언할 때 requires_grad=True 로 해야 x의 연산들을 추적하기 시작한다.
• backward를 두 번 호출하게 되면 에러가 뜬다. backward를 한 번 호출하면, 이를 계산한 computational graph를 그대로 가지고 있으면 메모리적으로 비효율적이므로 이를 날려버리는 것이 default이다. 따라서, backward를 두 번 호출하게 되면 에러가 뜨며, 만약 또 호출하고 싶으면 처음 backward 시에 retain_graph=True 옵션을 지정해 주어야 한다. (이렇게 하게되면 두번째에서부터 이전 gradient 결과값에 누적되어 더해지는 식으로 계산이 된다.)
• retain_graph=True를 안하더라도 zero_grad()를 해주지 않으면, gradient 결과값들이 계속 누적이 된다.

🧐Computational Graph를 통한 autograd 동작 원리

위에서 변수가 계산되어 온 history를 Computational Graph형태로 가지고 있다고 했었다.

이때 각 변수의 미분연산을 grad_fn (gradient function) 이라는 클래스 객체로서 각각의 연산이 무엇인지 Computational Graph에 저장된다. (e.g. grad_fn=<AddBackward0>)

즉, ① .backward를 하면 역전파가 시작되고, ② 해당 변수의 미분연산 .grad_fn 클래스가 호출이 되면서 미분값들이 계산되며, ③ 이 값이 .grad에 누적되면서 모든 노드에 대한 역전파가 일어나게 되는 것이다.

실제 딥러닝 훈련에서 사용되는 autograd

import torch
import torch.nn as nn
import torch.optim as optim

BATCH_SIZE = 256
train_iter = torch.utils.data.DataLoader(mnist_train,batch_size=BATCH_SIZE,shuffle=True)

loss = nn.CrossEntropyLoss()
optimizer = optim.Adam(model.parameters(),lr=1e-3) # 이때 model은 사용자가 정의한 딥러닝 모델

for epoch in range(EPOCHS):
    total_loss = 0
    for batch_in,batch_out in train_iter:
        y_pred = model.forward(batch_in.view(-1,1,28,28).to(device))
        loss_out = loss(y_pred,batch_out.to(device))
        # Update
        optimizer.zero_grad()   # reset gradient 
        loss_out.backward()     # loss_out을 계산하는 것에 관여한 노드들에 대해 backpropagate
        optimizer.step()        # 파라미터 값들이 현재의 gradient값에 기반하여 업데이트 되도록 수행
        total_loss += loss_out

hook

• 패키지화된 코드에서 다른 프로그래머가 custom 코드를 중간에 실행시킬 수 있도록 만들어놓은 인터페이스
• self.hooks 에 등록된 함수가 있으면 실행하게 된다.
• 아래 코드와 같이 활용할 수 있다.

  def hook_custom(x):
    print(f'current value is {x}')
  클래스객체.hooks = []
  클래스객체.hooks.append(hook_custom)

Tensor에 hook을 적용할 때

• register_hook으로 등록

  tensor = torch.rand(1, requires_grad=True)
  

def tensor_hook(grad): pass

tensor.register_hook(tensor_hook)

tensor는 backward hook만 있다.

tensor._backward_hooks

</br>

## Module에 hook을 적용할 때
- `register_forward_hook`, `register_forward_pre_hook`, `register_full_backward_hook`으로 등록할 수 있다.

- register_forward_hook : forward pass를 하는 동안 (output이 계산할 때 마다) 만들어놓은 hook function을 호출. 
이렇게 등록한 함수에 인자로 모듈이 실행되기 전 입력값과 실행 후 출력값을 받음 (input, output)
- register_forward_pre_hook : forward pass를 하기 직전에 hook function을 호출. 
이렇게 등록한 함수에 인자로 모듈이 실행되기 전 입력값만을 받음 (input)
- register_full_backward_hook : backward pass를 하는 동안 (gradient가 계산될 때마다) hook function을 호출. 
이렇게 등록한 함수에 인자로 backpropagation에서의 gradient 값들을 받음 (grad_input, grad_output)

```python
class Model(nn.Module):
    def __init__(self):
        super().__init__()

def module_hook(grad):
    pass

model = Model()
model.register_forward_pre_hook(module_hook)
model.register_forward_hook(module_hook)
model.register_full_backward_hook(module_hook)

모델의 특정 layer에 대해서만 해당 hook 함수를 적용하고 싶을 때

# model.get_model_shortcuts ; 모델 각각의 모듈
for name, module in model.get_model_shortcuts():
    if(name == 'target_layer_name'): # 만약 해당 모듈이름이 우리가 원하는 모듈 네임이면
        module.register_forward_hook(module_hook) # 해당 모듈에 hook 등록

hook 지우기

hook을 등록할 때, 이를 특정 변수에 지정하여 등록한 후, 해당 변수.remove()를 하게 되면 등록된 hook을 지우고 사용할 수 있다.

* 관련 유튜브 자료 : https://www.youtube.com/watch?v=syLFCVYua6Q

torch.nn.Module

• 딥러닝을 구성하는 layer의 base class
• 하나의 function, 여러 function으로 이루어진 layer, layer로 이루어진 model이 포함될 수 있다. (Module이 다른 Module을 포함할 수 있다.)

torch.nn.Sequential

• 모듈(Module)들을 하나로 묶어 순차적으로 실행시키고 싶을 때 사용

torch.nn.ModuleList

• 리스트와 같이 인덱싱으로 원하는 모듈을 가져다 쓰고 싶을 때 사용
• ModuleList를 써야 submodule로 등록하여, 파라미터 값들의 학습이 일어나게 된다.

torch.nn.ModuleDict

• 딕셔너리와 같이 key값을 통해 원하는 모듈을 가져다 쓰고 싶을 때 사용

torch.nn.Parameter

• 일반 텐서와 달리 parameter는 계속 최적값으로 업데이트되어야 한다.
• torch.nn.Parameter 함수를 이용해야 값을 저장하고 계산가능하게 유지해준다.

+ register_buffer를 이용하면, Parameter와 같이 gradient를 계산하여 값을 업데이트해주지는 않지만, 모델 저장시에 buffer값이 저장되게 된다.

named_children vs named_modules

• 모델 내부의 module들 목록을 확인하게 해주는 함수
• for name, module in model.named_modules 과 같이 사용하면 된다.
• named_children은 바로 아래단계의 모듈 목록들을 알려준다.
• named_modules은 해당 모듈에 속한 모든 모듈을 알려준다. (모듈안에 모듈이 들어갈 수 있으므로, 그렇게 속한 모듈들을 다 알려주는 것)
• 모듈의 이름이 필요하지 않은 경우에는 named를 뺀, modules, children을 사용하면 된다.

get_submodule

• 특정 module을 가져와서 쓰고 싶을 때 사용
• model.get_submodule('서브모듈 이름')과 같이 사용

named_parameters

• 모델 내부의 Parameter들 목록을 확인하게 해주는 함수
• for name, parameter in model.named_parameters()과 같이 사용하면 된다.
• 모듈의 이름이 필요하지 않은 경우에는 named를 뺀, parameters을 사용하면 된다.

get_parameter

• 특정 모듈에 속한 특정 파라미터를 가져다 쓰고 싶을 때 사용
• model.get_parameter('모듈이름.파라미터이름')과 같이 사용

Tensor

numpy에 ndarray가 있다면, PyTorch에는 Tensor가 있다.

이 외에도 대부분의 numpy에서 사용법과 비슷하게 pytorch에서 적용된다.

torch.tensor vs torch.Tensor

torch.Tensor

• 클래스 (Class)
• int 입력시 float로 변환
• torch 데이터 입력시 입력 받은 데이터의 메모리 공간을 그대로 사용 (얕은 복사; shallow copy와 비슷)
• list, numpy 데이터 입력 시 입력 받은 데이터를 복사하여 생성 (깊은복사; deep copy와 비슷)

torch.tensor

• 함수 (Function)
• 항상 data를 복사
• int 입력시 int 그대로 입력
• 입력 받은 데이터를 새로운 메모리 공간으로 복사하여 생성

차원

CV분야에서의 3D Tensor의 경우에는 (배치 사이즈, 이미지의 높이, 이미지의 너비)를 의미한다.

이미지가 흑백인 경우에는 이러한 3D Tensor로 가능하지만, 컬러인 경우에는 Channel 차원이 추가되어 (배치 사이즈, 채널의 수, 이미지의 높이, 이미지의 너비)인 4D Tensor로 사용된다. * 이때 컬러의 채널 수는 R, G, B로 3이다. 즉, (배치 사이즈, 3, 이미지의 높이, 이미지의 너비)로 사용된다.

unsqeeze()와 sqeeze()

sqeeze

• 차원이 1인 차원을 제거
• 따로 차원을 설정하지 않으면 1인 차원을 모두 제거
• dim 지정 선택

  unsqeeze

• 1인 차원을 생성
• 어느 차원에 1인 차원을 생성할 지 지정
• dim 지정 필수

view VS reshape

• tensor의 shape을 바꾸는데 사용
• view는 copy를 하여 데이터값들을 가져온 것이 아닌, 데이터의 shape만 다르게 보이도록 해주는 것. (view 이후에 기존 데이터 값을 변경하면, view가 적용된 데이터 값도 변경됨)

cat VS stack

• cat은 주어진 차원을 기준으로 주어진 텐서들을 붙임 (차원이 깊어지고, 차원의 수는 유지)
• stack은 새로운 차원으로 주어진 텐서들을 붙임 (차원이 확장되고, 기존 차원들의 깊이는 유지)
• e.g. (3, 4)의 shape을 갖는 2개의 텐서 A와 B를 붙이는 경우, torch.cat([A, B], dim=0)의 결과는 (6, 4)의 shape을 갖고, torch.stack([A, B], dim=0)의 결과는 (2, 3, 4)의 shape을 갖는다.

dot VS mm VS matmul

• dot은 벡터의 내적연산
• mm은 행렬 곱 연산 (matmul도 동일)
• mm과 다르게 matmul은 자동 broadcasting 지원하여 계산 * 어떤 조건을 만족했을 때 연산이 가능해지도록 배열을 자동 변환

참고 사이트 https://stackoverflow.com/questions/54307225/whats-the-difference-between-torch-stack-and-torch-cat

sequential data (순차 데이터)

순서가 있는 데이터 ** **⇒ 주의! 이러한 순차 데이터는 학습시에 데이터들의 순서를 섞어서 훈련하지 않도록 한다.

순서가 있는 데이터의 경우 학습 시에 이전 데이터들에 대한 정보를 “기억”하고 있어야 한다.

데이터의 흐름이 앞으로만 전달되는 피드포워드 신경망(feedforward neural network; FFNN)에서는 이전 데이터들에 대한 정보를 기억하는 메모리가 없다.

완전 연결 신경망인 MLP와 합성곱 신경망 CNN이 피드포워드 신경망에 속한다.

RNN은 이러한 순차 데이터를 다룰 수 있도록 구성된 모델이다.

RNN (Recurrent Neural Network)

순환 신경망 ⇒ 이전 데이터의 정보가 신경망 층에서 순환되며 기억하도록 구성된 모델

완전 연결 신경망에서 순환하는 고리를 추가

순환 데이터 A → B → C 가 있을 때, A를 학습한 출력값 $O_A$ 가 B 데이터 학습시 같이 들어가게 된다.

C 데이터 학습 시에는 B를 학습한 출력값 $O_B$ 가 들어간다. 이때 $O_B$에는 A에 대한 정보 $O_A$도 포함되어 있었으므로, 결과적으로 C 학습시에 이전 데이터 B와 A의 정보가 전부 들어가게 된다.

✔️ 용어 체크

타임 스텝 (time step) ; 데이터를 처리하는 한 단계

※ 첫번째 타임 스텝에서는 이전 은닉 상태가 없으므로, 이를 0으로 두고 계산한다.

일반적으로 순환층 (은닉층; 히든 레이어)의 활성화 함수로는 하이퍼볼릭 탄젠트 함수 tanh 가 사용된다.

※ tanh 함수: -1~1사이의 범위를 가진다.

🧐 구조 살펴보기

$h_t$가 히든 레이어에서 계산되는 값으로, 이 값이 타임스탭을 돌면서 이전 데이터의 정보를 기억할 수 있게 한다.

따라서 기존에는 학습되는 가중치가 입력 데이터 x에만 붙었던 반면, RNN에서는 $h_t$에도 가중치가 붙어 학습이 되도록 구성되어 있다.

따라서 이 $h_t$항을 제외하고는 기존의 MLP와 비슷하게 구성되어 있다.

또한, 위에서 언급했듯이 RNN에서는 보통 활성화 함수로 tanh를 사용하기 때문에 위 이미지에서도 tanh로 감싸 계산되는 것을 확인할 수 있다.

RNN 이미지를 검색하면 히든 레이어에서 값이 순환이 되는 형태로 모델이 표현되어 있는 경우가 있는데, 이는 RNN이 입력 x$t$가 들어오면 이전 타임스탭에서 계산된 $h{t-1}$와 함께 $h_t$가 계산되는 반복적인 형태이므로 그렇게 표현한 것이다.

이러한 RNN은 다양한 형태의 데이터 입력으로 다양한 유의미한 결과들을 도출할 수 있다.

예를 들어, 한 문장이 들어와 단어 단위로 입력 x에 들어가게 되면, 이를 다른 언어의 문장으로 번역을 하는 형태로 활용이 될 수 있다. 또는, 해당 문장이 부정적인 감정을 나타내는지 판단하는 형태로 활용이 될 수도 있다.

참고 : 혼자 공부하는 머신러닝+딥러닝 (저자 박해선)

• MLE ; Maximum Likelihood Estimation ; 최대 가능도 추정법 * 가능도 (우도; likelihood) : $L(D; X)$ ? * 실험자가 설정한 사전 확률 분포 P(D)가 있을 때, 실제로 일어난 특정 사건의 x가 사전확률분포 P(D)에서 일어났을 확률 (즉, 확률 분포 P(D)를 바꿔가면서 최적의 확률분포를 찾아가는 데에 사용할 수 있다.)
• 가장 높은 가능성을 가진 모수를 추정 * 모수 : 모집단의 특성을 나타내는 측정값 (e.g. 모평균, 모분산, 최빈값)

이 MLE를 간단화한 수식은 다음과 같다.

$$\widehat{θ}{MLE} =$$ argmax$${,θ}L(θ; X) =$$ argmax$$_{,θ}f(X|θ)$$

이때 x는 관측된 데이터들을 의미하며, θ는 모델의 파라미터를 의미한다.

즉, MLE는 likelihood $L(θ; X) = f(X|θ)$를 최대화하는 파라미터 θ를 찾아가는 것이다.

위 식에서 각 데이터 x가 iid(독립 항등 분포)라고 가정하에 다음과 같이 정리할 수 있다.

$$L(θ; X) = f(X|θ) = \prod_{i=1}^{n} f(x_i|θ)$$

모든 데이터 x에 대하여 모델의 파라미터가 θ인 경우에 결과값들을 product 연산 한 것이다.

이때 likelihood에 일반적으로 log-likelihood가 많이 사용된다. log는 데이터의 숫자단위를 줄여주며, 단조증가함수이고, 곱셈들을 덧셈으로 바꿔주므로 컴퓨터 연산의 효율성과 편의를 위해 log-likelihood가 자주 이용되는 것이다.

따라서 위 수식에 log를 적용하면 다음과 같이 정리할 수 있다.

$$\log L(θ; X) = \log f(X|θ) = \sum_{i=1}^{n} \log f(x_i|θ)$$

이때, 최대값을 구해야 가장 가능성이 높은 확률분포에 대한 추론을 하게 된다. 이 최대값을 구하는 가장 일반적인 방법은 미분계수가 0이 되는 지점을 찾는 것이다. 즉, 구하려는 파라미터 θ에 대하여 편미분을 하여 값이 0이 되도록 하는 θ값을 찾아야 한다.

$$\frac{\partial}{\partial\theta}\log L(θ; X) = \frac{\partial}{\partial\theta}\log f(X|θ) = \sum_{i=1}^{n} \frac{\partial}{\partial\theta}\log f(x_i|θ)$$

기존 MLP의 한계

• 파라미터가 많다. (fully-connected) ⇒ 오버피팅이 되기 쉽다. 메모리 소비가 크다.

CNN 특징

• convolution: 가중치 공유 ⇒ 파라미터 개수 감소. 계산량 감소
• pooling: 이미지를 작게 표현 ⇒ 파라미터 개수 감소. 계산량 감소

필터의 등장

MLP에서는 각 입력마다 다른 가중치들이 계산되며 적용되었는데, CNN에서는 이 가중치 뉴런이 한 뭉탱이로 묶여 입력들 사이로 이동하며 계산이 된다. 이때 이런 하나의 뭉탱이(?)인 가중치를 필터 혹은 커널 이라고 한다.

일반적인 CNN 모델을 치면 나오는 이미지이다. 아직은 이를 보면 어떤 식으로 동작하는 건지 잘 와닿지 않겠지만, 이 포스팅이 끝나면 이러한 CNN 모델들을 이해할 수 있게 될 것이다.

#1 합성곱(Convolution)

필터(Filter)를 통해 이미지의 특징(feature)을 추출

Filter(Kernel) 란

Filter라는걸 통해서 어떻게 이미지의 feature(특징)를 뽑을 수 있는지 예시를 통해 살펴보자.

이미지처리에서 자주 등장하는 sobel filter는 이미지의 가로세로 feature를 뽑아낼 수 있는 필터이다.

필터를 보면 이런 값을 가지고 있다.

위의 원본 이미지에 sobel 필터를 차례대로 적용시키면 다음과 같은 결과를 확인할 수 있다.  

왼쪽이 sobel-x가 적용이 된 이미지이고, 오른쪽이 sobel-y가 적용된 이미지이다.

각 이미지의 특징을 보니 왼쪽은 세로선이 detect되고 오른쪽은 가로선이 detect된 것을 확인할 수 있다.

이 둘을 합치면 아래와 같이 원본사진의 feature를 확인할 수 있다.

이처럼 CNN에서도 여러개 필터를 이용해 이미지의 세부 특징을 추출해서 학습을 할 수 있다.

CNN은 신경망에서 학습을 통해 자동으로 적합한 필터를 생성해 준다는 것이 특이사항이다.

Zero-padding

이미지 가장자리에 0을 덧댐으로써, 특정 이미지에서 Convolution을 가장자리에서도 하게 하려는 것

입력데이터보다 출력데이터가 작아지는것을 방지하는 방법이 Padding이다.

Stride

n칸씩 건너뛰면서 convolution을 하는 것

활성화 함수

해당 필터에 대한 특징이 “있다”와 “없다”로 바꾸어주는 과정

일반적으로 렐루(ReLU) 함수를 사용한다.

렐루는 양수일 경우에는 입력을 그대로 내보내며, 음수인 경우에는 0으로 변경한다.

2차원 Conv 예시

Conv2D 예시 코드

# keras.Sequential(): 순차적인 레이어(keras.layers.~~)를 더하는(add) 형태로 구성되는 모델
model = keras.Sequential()
model.add(keras.layers.Conv2D(32, kernel_size=3, activation='relu', 
                              padding='same', input_shape=(28,28,1)))

⇒ 위의 함수 사용 결과

#2 Pooling (subsampling)

특징(feature)을 강화시키고, 이미지의 크기를 줄임

사진 전체 부분을 유지한 상태로 픽셀만 줄이는 것 (해상도를 줄인다고 생각)

서브 샘플링은 두 종류의 풀링 연산으로 합성곱 신경망에 적용된다.

최대 풀링(max-pooling)과 평균 풀링(mean-pooling 또는 average-pooling)이다.

풀링 층은 보통 $P_{n \times m}$로 표시한다. 아래 첨자 nxm는 최댓값과 평균 연산이 수행되는 이웃한 픽셀 크기이다.

이런 이웃 픽셀 개수를 풀링 크기라고 한다.

최대 풀링은 이웃한 픽셀에서의 최댓값을 취하고, 평균 풀링은 픽셀의 평균을 계산한다. 최대 풀링은 입력 데이터에 있는 잡음에 좀 더 안정적인 특성을 생성한다. 또한 이러한 풀링은 특성 크기를 줄이므로 계산 효율성을 높인다. 특성(feature) 개수가 줄어들면 과대적합도 감소한다.

Pooling을 하는 예시 코드

model.add(keras.layers.MaxPooling2D(2))

⇒ 위의 함수 사용 결과

#3 Fully-Connected

2차원의 배열 형태 이미지를 1차원의 형태로 펼쳐주는 작업

1. 2차원 배열 형태의 이미지를 1차원 배열로 flatten
2. 분류 함수(다중 분류; softmax/ 이진분류; sigmoid)로 최종 레이블 예측

Fully-Connected을 하는 예시 코드

model.add(keras.layers.Flatten())
model.add(keras.layers.Dense(100, activation='relu'))
model.add(keras.layers.Dropout(0.4))
model.add(keras.layers.Dense(10, activation='softmax'))

⇒ 위의 함수 사용 결과

최종 CNN 코드 예시

model = keras.Sequential()
model.add(keras.layers.Conv2D(32, kernel_size=3, activation='relu', 
                              padding='same', input_shape=(28,28,1)))
model.add(keras.layers.MaxPooling2D(2))
model.add(keras.layers.Conv2D(64, kernel_size=(3,3), activation='relu', 
                              padding='same'))
model.add(keras.layers.MaxPooling2D(2))
model.add(keras.layers.Flatten())
model.add(keras.layers.Dense(100, activation='relu'))
model.add(keras.layers.Dropout(0.4))
model.add(keras.layers.Dense(10, activation='softmax'))
model.summary()

참고 자료: https://www.edwith.org/deeplearningchoi/lecture/15293

• 경사 ⇒ 기울기
• 하강법 ⇒ 내려가는 방법
• 경사하강법 ⇒ 기울기를 따라 내려가는 방법

배치 경사하강법(Batch Gradient Descent)?

모든 학습 데이터를 사용하여 비용함수의 기울기를 계산한다. 일반적인 경사하강법은 이 배치 경사하강법을 의미한다. 전체 데이터를 사용하기 때문에 안정적이지만, 효율적이지 않다.

확률적 경사하강법(Stochastic Gradient Descent; SGD)?

하나의 샘플을 랜덤하게 골라 해당 데이터의 기울기를 따라 조금 내려간다. 이렇게 하나의 샘플씩 랜덤하게 선택하여 경사하강법을 취하는 것이 확률적 경사하강법이다. 만족할만한 최소값 위치에 도달할 때까지 계속 이를 반복적으로 시행한다.

그러나 이 방법은 랜덤한 하나의 샘플의 기울기를 기반으로 업데이트 되므로 잘못된 곳으로 업데이트가 될 수 있다.

미니배치 경사하강법(Minibatch Gradient Descent; Mini batch SGD)?

하나의 데이터가 아닌 여러개의 샘플을 랜덤으로 선택하여 그 데이터들의 비용함수의 기울기를 계산한다. SGD 보다 안정적이면서, BGD보다 효율적이므로 일반적으로 사용되는 기법이다.

Q. 미분계수가 0인 지점을 찾는 방식이 아닌 gradient descent를 이용해 함수의 최소값을 찾는 이유?

실제 미분계수를 계산하는 과정을 컴퓨터로 구현하는 것에 비해 gradient descent는 컴퓨터로 비교적 쉽게 구현할 수 있다. 데이터 양이 매우 큰 경우 한번에 모든 데이터에 대한 기울기를 구하는 것보다, 경사하강법과 같은 iterative한 방법을 통해 해를 구하는 것이 계산량 측면에서 더 효율적이다.

행렬(matrix)

행렬 A의 크기 : m x n (행 개수 x 열 개수) 이러한 행렬 A를 m by n 행렬 또는 m by n matrix 라고 한다.

특히, m = n 일 때의 행렬 A를 n차의 정사각행렬이라고 한다.

$a_{ij}$ 에서 i는 행 번호, j는 열 번호를 의미한다. 이때 $a_{ij}$를 행렬 A의 (i, j) 성분 이라고 한다.

이때 i = j인 성분들을 주대각선 성분이라고 한다. (e.g., $a_{11}$, $a_{22}$, $a_{33}$, ... , $a_{nn}$)

행렬의 연산

[용어 정리] 상등 : 크기가 같은 두 행렬 A, B가 모든 i, j에 대해 $a_{ij}$ = $b_{ij}$일 때 (즉, 모든 성분이 동일한 값을 가질 때), 두 행렬은 서로 같다고 하고, A = B라고 한다.

행렬의 합

A + B = $[a_{ij}+b_{ij}]_{mn}$ 각 위치들에 대해서 해당 값들을 상수 덧셈과 동일하게 하면 된다.

※ 행렬의 크기가 같아야 합 연산이 가능하다.

스칼라 배

kᆞA = $[k\cdot a_{ij}]_{mn}$ 각 위치들에 대해서 해당 값들을 상수 곱셈과 동일하게 하면 된다.

행렬의 곱

AB = $[c_{ij}]{mn}$ 이때 A = $[a{ij}]{m\times p}$ , B = $[b{ij}]{p\times n}$이며, AB = $[c{ij}]{mn}$에서 $c{ij}$는 $a_{i1}b_{1j}+a_{i2}b_{2j}+...+a_{ip}b_{pj}$이다.

※ 행렬 A와 B의 크기에 주의하자. 행렬 A의 크기는 m x p, 행렬 B의 크기는 p x n이다. 즉, 앞에서 곱해지는 행렬의 열의 개수와 뒤에서 곱해지는 행렬의 행의 개수가 서로 같아야 함을 유의하자.

행렬의 곱을 좀 더 직관적으로 이해를 하기위해 다음의 그림을 보자.

여기서 1ᆞa = $\sum_{i=1}^{3} a_{1i}\times b_{i1}$ = $a_{11}\times b_{11}+a_{12}\times b_{21}+a_{13}\times b_{31}$ 로 계산이 되는 것이다.

$c_{ij}$가 $a_{i1}b_{1j}+a_{i2}b_{2j}+...+a_{ip}b_{pj}$인 것을 위의 행렬 상의 위치와 대조하며 따라가 보면, 보다 쉽게 이해할 수 있다.

<행렬 연산의 기본 성질> 이때 A, B, C는 행렬이며, a, b는 스칼라이다.

1) A+B = B+A 2) A+(B+C) = (A+B)+C 3) A(BC) = (AB)C 4) A(B+C) = AB+AC 5) (B+C)A = BA+CA 6) a(B+C) = aB+aC 7) (a+b)C = aC+bC 8) (ab)C = a(bC) 9) a(BC) = (aB)C = B(aC)

행렬의 거듭제곱

[용어 정리] 단위행렬 ($I_n$) : 주대각선 성분이 모두 1이고, 나머지 성분이 모두 0인 n차 정사각행렬

이때 $A^k$ = $A_1A_2 ... A_k$일 때, $A^0$ = $I_n$로 표현된다. 마치 실수에서 $a^0$ = 1인 것과 비슷하게 생각할 수 있다.

👉 단위행렬의 성질 (A가 m x n 행렬일 때) $I_mA$ = $AI_n$ = $A$

<행렬 거듭제곱의 지수법칙>

1) $A^rA^s$ = $A^{r+s}$ 2) $(A^r)^s$ = $A^{rs}$

해당 포스팅은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅 하였습니다. ✍️✍️

그래프 알고리즘

그래프 알고리즘은 매우 다양한데, 코딩 테스트에서 출제 비중이 낮은 편이지만 제대로 알아야 하는 알고리즘이다.

그래프는 노드(Node)와 노드 사이를 연결하는 간선(Edge)으로 이루어져있는 자료구조이다. 따라서 서로 다른 객체가 연결되어 있다는 내용이 있으면, 그래프 알고리즘을 떠올려야 한다.

또한 트리 자료구조는 다양한 알고리즘에서 사용되므로 기억해두어야 한다.

다익스트라 최단 경로 알고리즘에서 사용되는 우선순위 큐를 구현할 때, 최소힙을 이용할 수 있는데, 이때 최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속한다.

• 그래프 VS 트리 자료구조

그래프를 표현하는 방식으로는 인접 행렬과 인접 리스트가 있다.

• 인접 행렬: 2차원 배열을 사용하여 그래프의 연결 관계를 표현
• 인접 리스트: 리스트를 사용하여 그래프의 연결 관계를 표현

노드의 개수가 V, 간선의 개수가 E인 그래프가 있다고 하자.

이때 인접 행렬을 이용하는 방식은 간선 정보를 저장하기 위해 O(V²)만큼의 메모리 공간을 사용한다. 반면, 인접 리스트를 이용할 때는 간선의 개수만큼인 O(E)만큼만 메모리 공간을 사용한다.

또한 인접 행렬은 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(1)의 시간으로 즉시 알 수 있다는 장점이 있지만, 인접 리스트를 이용할 때에는 O(V) 만큼의 시간이 소요된다.

다익스트라 최단 경로 알고리즘은 인접 리스트를 이용하고, 플로이드 워셜 알고리즘은 인접 행렬을 이용하는 방식이다.

이때 주의해야 할 점은 어떤 문제를 만나든 메모리와 시간을 염두하고 알고리즘을 선택하여 구현해야 한다는 점이다.

예를 들어 최단 경로를 찾아야 하는 문제에서 노드의 개수가 적은 경우에는 플로이드 워셜 알고리즘을 이용하고, 노드와 간선의 개수가 모두 많으면 다익스트라 알고리즘을 이용하면 유리하다.

이제 다른 그래프 알고리즘들에 대해 알아보자.

서로소 집합

수학에서의 서로소 집합은 공통원소가 없는 두 집합을 의미한다.

서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 이 서로소 집합 자료구조는 union과 find 2개의 연산으로 조작할 수 있다.

union(합집합) 연산은 하나의 집합으로 합치는 연산이다. find(찾기) 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.

서로소 집합 자료구조는 합집합과 찾기 연산으로 구성된다. 따라서 union-find(합집합 찾기) 자료구조라고 불리기도 한다.

두 집합이 서로소 관계인지 확인하기 위해서는 각 집합이 어떤 원소를 공통으로 가지고 있는지를 확인하면 되기 때문이다.

서로소 집합 자료구조

서로소 집합 자료구조는 트리 자료구조를 이용하여 구현한다.

서로소 집합 계산 알고리즘은 다음과 같다.

1. union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.

   1-1. A와 B의 루트 노드 A', B' 를 각각 찾는다.

   1-2. A'를 B'의 부모 노드로 설정한다. (즉, B'가 A'를 가리키도록 한다.)

2. 모든 union 연산을 처리할 때까지 1번 과정을 반복한다.

실제 구현시에 더 작은 원소가 부모 노드가 되도록 구현하는 경우가 많으므로, 여기서도 그러한 방식으로 구현하였다.

이 알고리즘을 그림을 통해 더 직관적으로 이해해보자.

전체 집합이 {1, 2, 3, 4, 5, 6}으로 총 6개의 원소로 구성되어 있을 때, 다음과 같은 4개의 union 연산이 있다고 하자.

각 union 연산은 두 원소가 같은 집합이라는 의미를 가지고 있다.

• step 0

  초기 단계에서는 가장 먼저 노드의 개수 크기의 부모 테이블을 초기화한다.

  이때 모든 원소가 자기 자신을 부모로 가지도록 설정한다.

• step 1

  첫번째 union 연산을 확인하여, 1과 4를 합친다. 이때, 더 작은 원소가 부모가 되도록 설정한다.

• step 2

  두번째 union 연산을 확인하여, 2와 3을 합친다.

• step 3

  세번째 union 연산을 확인하여, 2와 4을 합친다. 이때, 노드 2와 노드 4의 루트 노드인 1에서 더 작은 원소인 1이 노드 2의 부모가 되도록 설정한다.

• step 4

  마지막 union 연산을 확인하여, 5와 6을 합친다.

부모 테이블을 계속해서 확인하며, 이를 갱신해야 한다.

서로소 집합 알고리즘으로 루트를 찾기 위해서는 재귀적으로 부모를 거슬러 올라가야 한다.

결과적으로 최종 루트가 같은 것끼리 묶으면 다음과 같이 나누어진다.

이렇게 나뉘게 된 묶음끼리 서로소 집합이 되는 것이다.

기본적인 서로소 집합 알고리즘의 소스코드는 다음과 같다.

# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return x

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v+1) # 부모 테이블 초기화

# 부모 테이블에서 부모를 자기 자신으로 초기화
for i in range(1, v+1):
    parent[i] = i

# union 연산을 각각 수행
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end='')
for i in range(1, v+1):
    print(find_parent(parent, i), end=' ')

print()

# 부모 테이블 내용 출력
print('부모 테이블: ', end='')
for i in range(1, v+1):
    print(parent[i], end=' ')

# 입력 예시
6 4
1 4
2 3
2 4
5 6

# 출력 예시
각 원소가 속한 집합: 1 1 1 1 5 5
부모 테이블: 1 1 2 1 5 5

이렇게 구현을 하는 경우, find 함수가 최악의 경우 모든 노드를 확인하여 시간 복잡도가 O(V)가 된다.

따라서 경로 압축 기법을 적용하면 시간 복잡도를 개선시킬 수 있다. 이를 구현하기 위해서는 기존의 find 함수를 다음과 같이 변경하면 된다.

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

이렇게 수정하면, 각 노드에 대하여 find 함수를 호출한 후, 해당 노드의 루트 노드가 바로 부모 노드가 된다.

따라서 경로 압축 방법을 이용할 경우의 서로소 집합 알고리즘의 시간복잡도를 알아보자.

노드가 V개이고, 최대 V-1개의 union 연산과 M개의 find 연산이 가능할 때, 경로 압축 방법을 적용한 시간 복잡도는 O(V+M(1+log_2-M/VV))라고 알려져 있다.

보다 더 시간 복잡도를 줄일 수 있는 방법들도 있지만, 코딩 테스트를 위해서는 이 정도로 충분하다고 한다. 그러므로 경로 압축을 이용한 서로소 집합 알고리즘의 코드는 꼭 기억하도록 하자.

이 서로소 집합 알고리즘을 사용하여 방향이 없는 그래프에서 사이클 존재 여부를 판별할 수 있다.

서로 다른 두 노드의 루트 노드를 확인하여 이들이 같으면 사이클이 발생했다고 보면 된다.

이에 대한 소스코드는 다음과 같다.

# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v+1) # 부모 테이블 초기화

# 부모 테이블에서 부모를 자기 자신으로 초기화
for i in range(1, v+1):
    parent[i] = i

cycle = False

# union 연산을 각각 수행
for i in range(e):
    a, b = map(int, input().split())
    # 사이클이 발생한 경우 종료
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    # 사이클이 발생하지 않았으면 합집합 수행
else:
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end='')
for i in range(1, v+1):
    print(find_parent(parent, i), end=' ')

if cycle:
    print("사이클이 발생했습니다.")
else:
    print("사이클이 발생하지 않았습니다.")

# 입력 예시
3 3
1 2
1 3
2 3

# 출력 예시
사이클이 발생했습니다.

신장 트리

하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이라, 이러한 조건이 붙은 그래프를 신장 트리라고 하는 것이다.

오른쪽 그림이 왼쪽 그래프에서 가능한 신장 트리 중 하나이다.

왼쪽 그림은 "모든 노드가 서로 연결"이 되지 않았으므로 신장 트리가 아니다.

오른쪽 그림은 "사이클이 존재"하므로 신장 트리가 아니다.

크루스칼 알고리즘

최소한의 비용으로 신장 트리를 찾아야 할 때 사용하는 알고리즘을 "최소 신장 트리 알고리즘" 이라고 한다. 이 최소 신장 트리 알고리즘 중 대표적인 것으로는 크루스칼 알고리즘이 있다.

그리디 알고리즘으로 분류되는 크루스칼 알고리즘은 모든 간선에 대하여 정렬을 한 후, 가장 거리가 짧은 간선부터 집합에 포함시키는 방식으로 진행된다. 이때 사이클을 발생시킬 수 있는 간선의 경우, 집합에 포함시키지 않는다.

최소 신장 트리는 일종의 트리 자료구조이므로, 신장 트리에 포함되는 간선의 개수가 '노드의 개수-1'과 같다는 특징이 있다.

*트리 자료구조는 노드가 N개일 때, 항상 간선의 개수가 N-1개 이다.

구체적인 크루스칼 알고리즘은 다음과 같다.

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.

2. 간선을 하나씩 확인하며, 현재의 간선이 사이클을 발생시키는지 확인한다.

   2-1. 사이클이 발생하지 않으면, 최소 신장 트리에 포함시킨다.

   2-2. 사이클이 발생하면, 최소 신장 트리에 포함시키지 않는다.

3. 모든 간선에 대하여 2번의 과정을 반복한다.

다음 그래프의 최소 신장 트리를 구해보자.

• step 0

  모든 간선 정보를 빼내어 정렬을 수행한다.

• step 1

  가장 짧은 간선을 선택한다.

• step 2 ~ 3

  가장 짧은 간선을 선택한다.

• step 4

  가장 짧은 간선을 선택한다. 이때, (6, 7)은 이미 step 2와 step 3에서 포함된 노드들이므로, 이를 신장 트리에 포함하면 사이클이 존재하게 된다. 따라서 신장 트리에 포함하지 않게 처리한다.

• step 5 ~ 6

  가장 짧은 간선을 선택한다.

• step 7

  가장 짧은 간선을 선택한다. 이때, (2, 3)은 이미 둘 다 포함된 노드들이므로, 이를 신장 트리에 포함하면 사이클이 존재하게 된다. 따라서 신장 트리에 포함하지 않게 처리한다.

• step 8

  가장 짧은 간선을 선택한다.

• step 9

  가장 짧은 간선을 선택한다. 이때, (1, 5)은 이미 둘 다 포함된 노드들이므로, 이를 신장 트리에 포함하면 사이클이 존재하게 된다. 따라서 신장 트리에 포함하지 않게 처리한다.

결과적으로 다음과 같은 최소 신장 트리를 찾을 수 있다.

이때, 간선들의 비용을 모두 더하면, 159로 최소 신장 트리를 만드는데 필요한 총비용이 된다.

크루스칼 알고리즘의 소스코드는 다음과 같다.

# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
    # 루트 노드가 아니면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v+1) # 부모 테이블 초기화

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

# 부모 테이블에서 부모를 자기 자신으로 초기화
for i in range(1, v+1):
    parent[i] = i

# 모든 간선에 대한 정보를 입력받기
for _ in range(e):
    a, b, cost = map(int, input().split())
    # 비용순으로 정렬하기 위하여 튜플의 첫 원소를 비용으로 설정
    edges.append((cost, a, b))

# 간선을 비용순으로 정렬
edges.sort()

# 간선을 하나씩 확인
for edge in edges:
    cost, a, b = edge
    # 사이클이 발생하지 않는 경우, 집합에 포함
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost

print(result)

# 입력 예시
7 9
1 2 29
1 5 75
2 3 35
2 6 34
3 4 7
4 6 23
4 7 13
5 6 53
6 7 25

# 출력 예시
159

크루스칼 알고리즘은 간선의 개수가 E 일 때, O(ElogE)의 시간 복잡도를 가진다. 크루스칼 알고리즘의 가장 오래 걸리는 부분은 간선 비용의 정렬 부분이며, 이 정렬의 시간 복잡도가 O(ElogE)이기 때문이다.

크루스칼 알고리즘에서 사용되는 서로소 집합 알고리즘의 시간 복잡도는 정렬 알고리즘보다 작으므로 무시할 수 있다.

위상 정렬

위상 정렬은 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘이다.

이론적으로는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서를 나열하는 것이다.

그래프 상에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다.

위상 정렬을 알아보기 전에, 진입차수에 대해 알아야 한다.

진입차수란 특정한 노드로 들어오는 간선의 개수를 의미한다.

예를 들어, 컴퓨터공학과의 커리큘럼에는 선수과목이 정해져 있다고 하자. 총 3개의 과목으로 '알고리즘', '자료구조', '고급 알고리즘'이 있을 때, 각 과목을 노드로 표현하고, 선수관계를 간선으로 표현하면 다음과 같다.

'알고리즘'의 선수과목으로는 '자료구조'가 있으며, '고급 알고리즘'의 선수과목으로는 '자료구조'와 '알고리즘'이 있는 것을 확인할 수 있다.

구체적인 위상 정렬 알고리즘은 다음과 같다.

1. 진입차수가 0인 노드를 큐에 넣는다.

2. 큐가 빌 때까지 다음의 과정을 반복한다.

   2-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.

   2-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

즉, 큐가 빌 때까지 큐에서 원소를 계속 꺼내서 처리하는 과정을 반복한다.

이때 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재한다고 판단할 수 있다. 큐에서 원소가 V번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것이다.

사이클이 존재하는 경우에는 사이클에 포함되어 있는 원소들이 큐에 들어가지 못하기 때문이다.

그러나, 기본적으로 위상 정렬 문제에서는 사이클이 발생하지 않는 경우를 고려하는 경우가 많으므로, 여기서 또한 사이클이 발생하지 않는다고 가정하여 살펴볼 것이다.

다음 그래프의 위상 정렬을 구해보자.

• step 0

  진입차수가 0인 노드를 큐에 넣는다. 현재 노드 1의 진입차수만 0 이므로, 큐에 노드 1만 삽입한다.

• step 1

  큐에 들어있는 노드 1을 꺼내어, 노드 1과 연결되어 있는 간선들을 제거한다.

  새롭게 진입차수가 0이 된 노드 2와 노드 5를 큐에 삽입한다. (처리된 노드와 간선은 점선으로 표시하였다.)

• step 2

  큐에 들어있는 노드 2을 꺼내어, 노드 2과 연결되어 있는 간선들을 제거한다.

  새롭게 진입차수가 0이 된 노드 3을 큐에 삽입한다.

• step 3

  큐에 들어있는 노드 5을 꺼내어, 노드 5과 연결되어 있는 간선들을 제거한다.

  새롭게 진입차수가 0이 된 노드 6을 큐에 삽입한다.

• step 4

  큐에 들어있는 노드 3을 꺼내어, 노드 3과 연결되어 있는 간선들을 제거한다.

  새롭게 진입차수가 0이 되는 노드가 없으므로, 그냥 넘어간다.

• step 5

  큐에 들어있는 노드 6을 꺼내어, 노드 6과 연결되어 있는 간선들을 제거한다.

  새롭게 진입차수가 0이 된 노드 4를 큐에 삽입한다.

• step 6

  큐에 들어있는 노드 4를 꺼내어, 노드 4와 연결되어 있는 간선들을 제거한다.

  새롭게 진입차수가 0이 된 노드 7를 큐에 삽입한다.

• step 7

  큐에 들어있는 노드 7을 꺼내어, 노드 7과 연결되어 있는 간선들을 제거한다.

  새롭게 진입차수가 0이 되는 노드가 없으므로, 그냥 넘어간다.

위 과정을 수행하는 동안, 큐에서 빠져나간 노드를 순서대로 출력한 것이 위상 정렬을 수행한 결과가 된다.

위상 정렬은 한 단계에서 새롭게 들어가는 원소가 2개 이상인 경우, 여러 가지의 답이 존재하게 된다.

위 예시의 경우에는 1 - 2 - 5 - 3 - 6 - 4 - 7 이외에 1 - 5 - 2 - 3 - 6 - 4 - 7 또한 답이 될 수 있다.

위상 정렬 알고리즘의 소스코드는 다음과 같다.

from collections import deque

# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v+1)
# 각 노드에 연결된 간선 정보를 담기위한 연결 리스트 초기화
graph =[[] for i in range(v+1)]

# 방향 그래프의 모든 간선 정보를 입력받기
for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b) # 정점 A에서 B로 이동 가능
    # 진입차수를 1 증가
    indegree[b] += 1

# 위상 정렬 함수
def topology_sort():
    result = []
    q = deque() # 큐 기능을 사용하기위한 deque 라이브러리 사용

    # 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)

    # 큐가 빌 때까지 반복
    while q:
        # 큐에서 원소 꺼내기
        now = q.popleft()
        result.append(now)
        # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for i in graph[now]:
            indegree[i] -= 1
            # 새롭게 진입차수가 0이 되는 노드 큐에 삽입
            if indegree[i] == 0:
                q.append(i)
    # 위상 정렬 수행 결과 출력
    for i in result:
        print(i, end=' ')

topology_sort()

# 입력 예시
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4

# 출력 예시
1 2 5 3 6 4 7

위상 정렬의 시간 복잡도는 O(V+E)이다.

위상 정렬은 차례대로 모든 노드를 확인하면서, 해당 노드에서 출발하는 간선들을 차례대로 제거해야 한다. 따라서, 모든 노드와 간선을 전부 확인하므로 O(V+E)의 시간이 소요되는 것이다.

해당 포스팅은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅 하였습니다. ✍️✍️

최단 경로

말 그대로 가장 짧은 경로를 찾는 알고리즘이다.

최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 3가지가 대표적이다. 이 중 다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘에 대해 다뤄보도록 하자.

다익스트라 최단 경로 알고리즘

다익스트라 최단 경로 알고리즘은 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 이 다익스트라 최단 경로 알고리즘은 매번 '가장 비용이 적은 노드'를 선택하여 임의의 과정을 반복하기 때문에 기본적으로 그리디 알고리즘으로 분류된다.

알고리즘의 원리는 다음과 같다.

1. 출발 노드를 설정

2. 최단 거리 테이블을 초기화

   초기 상태에서는 다른 모든 노드로 가는 최단 거리를 '무한'으로 초기화 한다.

   • 999,999,999 (약 10억)으로 설정해주면 된다. => int(1e9)

3. 방문하지 않은 노드 중, 최단 거리가 가장 짧은 노드를 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여, 최단 거리 테이블을 갱신

5. 3과 4번을 반복

항상 1차원의 리스트에 '각 노드에 대한 현재까지의 최단 거리' 정보를 저장하며 리스트를 계속 갱신한다. 나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면, 이를 갱신하는 것이다.

이미지 출처: https://haningya.tistory.com/116

다익스트라 알고리즘은 구현하기 쉽지만, 느리게 동작하는 코드와 구현하기 조금 까다롭지만, 빠르게 동작하는 코드 2가지로 구현할 수 있다.

그러나 코딩 테스트를 준비한다면, 조금 까다롭지만 빠르게 동작하는 코드를 정확하고 제대로 구현할 수 있을 때까지 연습해야 한다.

방법 1: 간단한 다익스트라 알고리즘

간단한 다익스트라 알고리즘은 O(V²)의 시간 복잡도를 가지며, 처음 고안된 다익스트라 알고리즘이다. 이때 V는 노드의 개수를 의미한다.

import sys
# input()을 더 빠르게 동작하는 sys.stdin.readline()으로 치환
input = sys.stdin.readline 
INF = int(1e9)

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int,input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n+1)]
# 방문한 적이 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (n+1)
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int,input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c
    graph[a].append((b, c))

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
    min_value = INF
    index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    # 시작 노드에 대해 초기화
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]
    # 시작 노드를 제외한 전체 n-1개의 노드에 대해 반복
    for i in range(n-1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
        now = get_smallest_node()
        visited[now] = True
        # 현재 노드와 연결된 다른 노드를 확인
        for j in graph[now]:
            cost = distance[now] + j[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 ㅕㅇ우
            if cost < distance[j[0]]:
                distance[j[0]] = cost
# 다익스트라 알고리즘 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        pritn("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

# 입력 예시
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

# 출력 예시
0
2
3
1
2
4

위 알고리즘은 총 O(V)번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색을 하고, 현재 노드와 연결된 노드를 매번 일일이 확인해야 되므로, 시간복잡도가 O(V²)인 것이다.

따라서, 노드의 개수가 10,000개를 넘어가면 보다 효율적으로 개선된 다익스트라 알고리즘을 이용해야 한다.

방법 2: 개선된 다익스트라 알고리즘

이 구현방법을 사용하면 다익스트라 최단 경로 문제가 최악의 경우에도 시간 복잡도 O(ElogV)를 보장할 수 있다. 이때 V는 노드의 개수이고, E는 간선의 개수를 의미한다.

개선된 다익스트라 알고리즘에서는 힙 자료구조를 사용한다. 이렇게 함으로 선형 시간이 아닌 로그 시간이 걸려, 이전에 비해 매우 빠른 속도를 지니게 된다.

힙 (Heap)

우선순위 큐(Priority Queue)를 구현하기 위하여 사용하는 자료구조 중 하나이다.

큐는 가장 먼저 삽입된 데이터를 가장 먼저 삭제하는 선입선출(First In First Out) 구조를 가졌었다.

이처럼 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다.

따라서 가치가 높은 데이터부터 확인해야 하는 경우, 우선순위 큐 자료구조를 이용하면 효과적이다. 이러한 우선순위 큐는 라이브러리로 지원을 하므로, 직접 구현하는 코드를 공부하지 않아도 된다.

파이썬에서는 heapq를 사용하여 우선순위 큐 기능을 이용하도록 하자.

또한, 우선순위 값을 표현할 때에는 일반적으로 정수형 자료형을 사용한다는 점을 알아두자.

우선순위 큐를 구현할 때에는 최소 힙 또는 최대 힙을 이용한다. 최소 힙을 이용하는 경우 "값이 낮은 데이터가 먼저 삭제"되며, 최대 힙을 이용하는 경우 "값이 큰 데이터가 먼저 삭제"된다. 파이썬 라이브러리에서는 기본적으로 최소 힙 구조를 이용하므로, 비용이 적은 노드를 먼저 방문하는 다익스트라 최단 경로 알고리즘에서는 파이썬의 우선순위 큐 라이브러리를 그대로 사용하면 적합하다.

최단 거리를 저장하기 위해 1차원 리스트를 사용하고, 현재 가장 가까운 노드를 저장하기 위한 목적으로 우선순위 큐를 추가로 이용할 것이다.

++ 최소 힙을 최대 힙처럼 사용하기 위해서는 데이터를 넣을 때 우선순위 값에 음수를 붙인 후, 우선순위 큐에서 꺼낸 후 다시 음수를 붙여 원래의 값으로 돌리는 식으로 사용할 수 있다.

import heapq
import sys
input = sys.stdin.readline 
INF = int(1e9)

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int,input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n+1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int,input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    # 시작 노드로 가기위한 최단 경로는 0으로 설정하여 큐에 삽입
    heapq.heappush(q,(0,start))
    distance[start] = 0
    while q: # 큐가 비어있지 않으면
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적 있는 노드라면 무시
        if distance[now] < dist:
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))

# 다익스트라 알고리즘 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        pritn("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

# 입력 예시
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

# 출력 예시
0
2
3
1
2
4

플로이드 워셜 알고리즘

다익스트라 알고리즘은 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우에 사용했던 알고리즘이었던 반면, 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다.

이 둘의 차이를 먼저 알아본 후, 플로이드 워셜에 대해 더 자세히 살펴보자.

다익스트라 알고리즘 VS 플로이드 워셜 알고리즘

• 다익스트라 알고리즘

단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택하여, 해당 노드를 거쳐 가는 경로를 확인하며 최단 거리 테이블을 갱신하는 방식으로 동작한다.

최단 거리 테이블로 1차원 리스트를 이용한다.

그리디 알고리즘을 바탕으로 한다.

• 플로이드 워셜 알고리즘

단계마다 현재 노드를 거쳐가는 경로를 기준으로 알고리즘을 수행한다.

노드의 개수가 N개일 때, 알고리즘 상 N번의 단계를 수행하며, 이때 각 단계는 O(N²)의 연산을 한다. 따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N³)이다.

최단 거리 테이블로 2차원 리스트를 이용한다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다.

다이나믹 프로그래밍을 바탕으로 한다.

플로이드 워셜 알고리즘

현재의 노드를 제외하고 서로 다른 노드 쌍 (A, B)를 선택한다. 이후 A → 현재의 노드 → B 로 가는 비용을 확인한 뒤에 최단 거리를 갱신한다. 즉, 노드의 개수가 N이라고 할 때, _N-1P₂개의 쌍을 매 단계마다 반복해서 확인하는 것이다.

이를 점화식으로 표현하면 다음과 같다. $$ D_{ab} = min(D_{ab},,D_{ak}+D_{kb}) $$ 이전까지의 A에서 B로 가는 최소비용과 현재 노드 K를 거쳐가는 비용을 비교하여 작은 값을 갱신한다는 의미이다.

이를 바탕으로 한 소스코드는 다음과 같다.

INF = int(1e9)

# 노드의 개수 및 간선의 개수 입력받기
n = int(input())
m = int(input())
# 2차원 리스트를 생성, 무한으로 초기화
graph = [[INF]*(n+1) for _ in range(n+1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0
for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    # A에서 B로 가는 비용은 C라 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 플로이드 워셜 점화식 사용하여 알고리즘 수행
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행 결과 출력
for a in range(1, n+1):
    for b in range(1, n+1):
        # 연결되지 않은 간선은 무한(INFINITY) 출력
        if graph[a][b] == INF:
            print("INFINITY", end=" ")
        # 도달할 수 있는 경우 거리를 출력
    else:
        print(graph[a][b], end=" ")
    print()

# 입력 예시
4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2

# 출력 예시
0 4 8 6
3 0 7 9
5 9 0 4
7 11 2 0

해당 포스팅은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅 하였습니다. ✍️✍️

다이나믹 프로그래밍

연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 짜도록 해야한다.

어떤 문제에 대해 약간의 메모리를 더 사용함으로써, 연산 속도를 매우 증가시킬 수 있는 다이나믹 프로그래밍 기법(동적 계획법)이 있다. 이를 개념적으로 설명하자면, 큰 문제를 중복이 일어나지 않는 작은 문제들로 나누어 푸는 방식이다. 이때, 작은 문제들이 반복하는 경우에 해당 문제에 대한 정답이 동일하다. 따라서 한번 계산한 작은 문제들을 각각 저장을 해놓고 나중에 반복이 될 때 다시 사용할 수 있도록 한다. 이를 메모이제이션(Momoization)이라고 한다.

이 다이나믹 프로그래밍은 탑다운(Top-down)과 보텀업(Bottom-up)으로 2가지의 방식이 있다.

• 탑다운(Top-down)

  일반적으로 재귀함수로 구현

  큰 문제를 풀다가 작은 문제가 풀리지 않았을 때, 해당 문제를 해결하는 방식

• 보텀업(Bottom-up)

  작은 문제부터 해결해나가는 방식

이 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 문제로는 피보나치 수열이 있다.

피보나치 수열은 이전 두 항의 합을 현재의 항으로 갖는 수열이다. 이를 점화식을 이용하여 간결하게 표현하면 다음과 같다. $$ a_{n+2} = f(a_{n+1},a_n)=a_{n+1}+a_n $$

$$ a_n = a_{n-1}+a_{n-2},\quad a_1=1,a_2=1 $$

• n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수

• 단, 1번째 피보나치 수, 2번째 피보나치 수 = 1

프로그래밍에서 이러한 수열을 배열 또는 리스트로 표현할 수 있다. 수열은 여러 개의 수가 규칙에 따라 배열된 형태이기 때문이다. 파이썬의 경우에는 보통 리스트 자료형으로 이를 처리한다.

이 피보나치 함수를 재귀함수로 작성한 코드는 다음과 같다.

# 피보나치 함수를 재귀함수로 구현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)
print(fibo(4))

그러나 위 소스코드는 f(n)에서 n이 커지면 코드 수행시간이 기하급수적으로 늘어난다는 문제점이 있다. 일반적으로 O(2^N)의 지수 시간이 소요된다고 볼 수 있다. 예를 들어 N=30이면, 약 10억 가량의 연산을 수행해야 한다.

f(6)일 때의 호출과정을 시각적으로 표현하면 다음과 같다.

이를 보면, 이미 계산이 되었던 함수들도 여러번 반복 호출이 되는 것을 확인할 수 있다.

이런 불필요한 연산은 f(n)에서 n이 커질수록 매우 많아지게 된다.

이러한 반복되는 연산을 저장하기위해 메모이제이션을 사용하는데, 이는 한번 구한 정보를 리스트에 저장하는 방식으로 구현한다. 이에 대한 파이썬 코드는 다음과 같다.

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있는 문제인 경우
    if d[x] != 0:
        return d[x]
    # 계산한 적 없는 문제인 경우
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

print(fibo(99))    

재귀 함수 대신에 반복문을 사용할 수 있다. 일반적으로 재귀함수보다 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋다. 이 다이나믹 프로그래밍의 시간복잡도는 O(N)이다. 각각의 문제에 대해 한번씩만 계산이 되기 때문이다.

반복문을 사용하여 피보나치 수열을 해결하는 파이썬 코드는 다음과 같다.

# 앞서 계산된 결과를 저장하기 윈한 DP 테이블 초기화
d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수를 반복문으로 구현 (보텀업 다이나믹 프로그래밍)
for i in rane(3, n+1):
    d[i] = d[i-1] + d[i-2]

print(d[n])

보텀업 방식에서 사용되는 결과 저장용 리스트를 'DP 테이블'이라고 부른다.

메모이제이션을 사용 시, 일부의 문제에 대해서만 저장된 결과가 필요한 경우에는 사전 자료형을 사용하면 더 효과적이다.

해당 포스팅은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅 하였습니다. ✍️✍️

이진 탐색

순차 탐색

순차 탐색은 리스트 안에 있는 특정한 데이터를 찾기위해 앞에서부터 순서대로 데이터를 하나씩 확인하는 방법이다. 이 방식은 정렬이 되지 않은 리스트에서 원하는 특정 데이터를 시간만 있다면 찾아낼 수 있다는 장점이 있다.

순차 탐색의 파이썬 코드는 다음과 같다.

# 순차 탐색 소스코드 구현
def sequential_search(n, target, array):
    # 각 원소를 하나씩 확인
    for i in range(n):
        # 현재 원소가 찾고자하는 원소와 동일 하면
        if array[i] == target:
            return i + 1 # 현재 위치 반환

print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()
n = int(input_data[0]) # 원소 개수
target = input_data[1] # 찾고자 하는 문자열

print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()

# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, array))

이러한 순차 탐색은 데이터 개수가 N개 일 때 최대 N번의 비교 연산이 필요하므로 최악의 경우의 시간 복잡도가 O(N)이다.

이진 탐색

이진 탐색은 순차 탐색과 달리 이미 정렬이 되어 있어야만 사용할 수 있는 알고리즘이다. 이진 탐색은 위치를 나타내는 변수를 3개 사용하는데, 이는 탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점이다. 즉, 찾고자 하는 데이터와 중간점에 위치한 데이터를 비교하며 어느 쪽에 원하는 데이터가 있을지 찾아가는 방식이다.

따라서 이진 탐색 알고리즘은 한 단계마다 평균적으로 원소가 절반씩 줄어든다. 따라서 이를 빅오 표기법으로 나타내면 O(logN)이라고 할 수 있다.
이러한 이진 탐색을 구현하는 방법 중 재귀함수를 이용한 코드는 다음과 같다.

# 이진 탐색 코드 (재귀 함수 사용)
def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2 # 중간점
    # 찾은 경우 중간 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽으로
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽으로
    else:
        return binary_search(array, target, mid + 1, end)

# 원소의 개수 n과 target 입력받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
res = binary_search(array, target, 0, n - 1)
if res == None:
    print("원소가 존재하지 않습니다.")
else:
    print(res + 1)

단순하게 반복문을 사용하여 이진 탐색을 구현한 코드는 다음과 같다.

# 이진 탐색 소스코드 (반복문 사용)
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) //2
        # 찾은 경우 중간 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽으로
        elif array[mid] > target:
            end = mid -1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽으로
        else:
            start = mid + 1
    return None


# 원소의 개수 n과 target 입력받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
res = binary_search(array, target, 0, n - 1)
if res == None:
    print("원소가 존재하지 않습니다.")
else:
    print(res + 1)        

위의 코드들을 보면 이진 탐색 소스코드 작성이 어렵지 않다고 수 있지만, 참고자료가 없는 상황에서 이를 정확히 구현하기는 생각보다 까다로울 수 있다. 이진탐색은 코딩 테스트에서 자주 나오는 문제이므로 위 코드를 여러번 작성하며 외워두자. 특히, 데이터의 범위가 큰 상황에서 탐색을 하는 상황이 온다면, 이진 탐색으로 접근해보자.

트리 자료구조

이진 탐색 알고리즘은 이미 정렬이 되어있는 데이터들에 대해 사용가능하였다. 프로그램에서는 데이터를 정렬해두는 경우가 많아 이진탐색을 효과적으로 사용할 수 있는데, 실제 데이터베이스에서는 이를 트리 자료구조를 이용하여 정렬한다. 따라서 데이터베이스에서는 이진 탐색과는 다른 유사한 방식으로 항상 빠른 탐색이 가능하게 설계되어 있다.

이때 사용하는 트리 자료구조는 다음과 같다.

트리 구조는 일부를 떼어내어도 여전히 트리구조의 형태를 유지하고 있다. 이러한 트리를 서브 트리라고 부른다. 이 트리 자료구조는 파일 시스템과 같이 계층적이고 정렬을 해야하는 데이터에 사용하기 적합하다.

그러면 이러한 트리 구조를 이용하여 어떤식으로 이진탐색이 진행되는지 알아보자.

이진 탐색 트리

이진 탐색 트리의 특징

• 부모 노드의 왼쪽 부분 자식노드들은 더 작은 값을 가지고 있다.
• 부모 노드의 오른쪽 부분 자식노드들은 더 큰 값을 가지고 있다.

즉, 이진 탐색 트리는 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 순으로 데이터가 정렬되어 있는 형태이다.

이러한 이진 탐색 트리는 알고리즘보다는 자료구조 쪽이며, 코딩 테스트에서 이를 구현하도록 요구하는 경우는 거의 없으므로 구현 코드는 생략하자. 따라서 이진 탐색 트리가 구현되어 있는 상황에서 데이터를 탐색하는 방식만 간단히 살펴보자.

이미지 출처: https://medium.com/swlh

위 참고자료는 찾는 원소가 27일 때 동작하는 과정이다.

이진 탐색 트리를 이용한 탐색과정을 정리하면 다음과 같다.

부모 노드와 찾고자 하는 원소값 간의 크기 비교를 한 후, 왼쪽 자식노드로 이동할지, 오른쪽 자식노드로 이동할지 결정한다. 이 과정을 찾고자 하는 값과 동일한 노드에 도달할 때까지 반복한다.

이 동작원리는 매우 직관적이며 간단하다.

++ 참고

이진 탐색 문제의 경우에는 보통 데이터 범위가 매우 많은 경우에 사용된다. 이런 경우에 데이터를 input() 함수로 받게되면, 동작 속도가 느려 시간 초과로 오답이 될 수 있다. 이처럼 입력 데이터가 많은 경우에는 sys 라이브러리의 readline() 함수를 이용하여 보다 효율적인 입력 방식을 사용하도록 하자.

import sys
# 하나의 문자열 데이터 입력받기
input_data = sys.stdin.readline().rstrip()

#입력받은 문자열 그대로 출력
print(input_data)

readline() 까지만 작성을 하면, 데이터 입력 후 엔터 줄바꿈 기호가 입력이 되어, 이 부분을 제거하기 위해 rstrip() 함수를 함께 사용해 주어야 한다. 위 코드는 외워두도록 하자.

사전 수학 개념들

• 기저?

  백터공간 V에 대하여 임의의 벡터집합 S가

  ① 서로 1차 독립이면서

  ② 벡터공간 V를 생성하면

  S는 V의 기저이다.

  
  

  즉, 기저라 함은 특정 벡터 공간을 선형 생성하는 선형 독립인 벡터들로, S가 N 차원의 기저이면 N개의 벡터로 이루어져 있다.

  이때 기저의 크기는 일반적으로 길이가 1인 단위벡터로 표시한다. (크기보다는 방향이 중요하기 때문이다.)

• 고유값, 고유벡터

  행렬 A에 대해 다음 식을 만족한다고 가정하자. $$ Ax = λx $$ 이때, λ는 고유값으로 스칼라라고도 한다.

  또한 이때 x를 고유벡터라고 한다.

  
  

  위 식을 기하하적인 입장에서 보면 고유값 λ는 변화되는 크기를 의미하며, x는 변화되는 방향을 의미한다.

  즉, 행렬 A에 대해 변환된 벡터 x가 λ배 만큼 확장 또는 축소가 된 것이다.

  
  

  선형대수학의 입장에서 고유값과 고유벡터 개념들을 다시 살펴보면 다음과 같다.

  고유값? det(λI_n-A)=0 또는 det(A-λI_n)=0 이 되게하는 λ이다.

  (이때 λI_n는 λ₁, λ₂, … , λ_n을 주대각선으로 하는 대각행렬이다.)

  *det는 행렬식을 의미한다.

  고유벡터? (λI_n-A)x=0 또는 (A-λI_n)x=0 이 되는 x 전체의 집합이다. (단, x=0을 제외한다.)

물론 수학적으로 이를 풀이할 수 있어야 하지만, 기하학적인 입장에서 왜, 어떻게 이러한 과정들이 진행되는지 이해하는 것이 더 중요하다.

다시 기하학적인 관점에서 고유벡터와 고유값에 대해 생각해보자.

행렬 A의 고유벡터가 v₁, v₂이고 고유값을 λ₁, λ₂라고 할 때, 벡터 x에 행렬 A 변환을 가한다는 말은 v₁, v₂로 이루어진 고유벡터 공간에서 v₁방향으로 λ₁배, v₂방향으로 λ₂배 했다는 의미이다.

고유벡터는 변화되는 방향, 고유값은 변화되는 비율이라는 점을 기억하자.

고유값 분해(EVD)

N x N 크기의 정방행렬 A를 PDP^T로 표현할 수 있다.

이때 P는 고유벡터 v_i로 이루어진 행렬로 변화되는 방향을 의미한다.

이때 D는 고유값 λ_i로 이루어진 대각행렬로 변화되는 비율을 의미한다.

따라서 고유값 분해를 기하학적인 의미로 살펴보면 P 방향으로 돌리고, D만큼 확대 또는 축소를 한 후, 다시 원래 방향으로 복구하는 것을 의미한다.

SVD(Singular Value Decomposition)

정방행렬이 아닌, M x N 크기의 직사각행렬 A를 3단계로 나누어 분해할 수 있다. (m차원을 n차원으로 바꾸는 것이라고 볼 수 있다.)

A = U∑V^T

이때 U는 A x A^T로 m x m 직교 행렬이다.

이때 V는 A^T x A 로 n x n 직교 행렬이다.

이때 ∑는 주대각 성분이 고유값 λ에 루트를 씌운 값인 m x n 직사각 대각행렬이다.

이미지 출처: https://www.pikpng.com/transpng/hxRRmbR/

특이값 분해인 SVD는 고유값 분해 EVD와 기하학적인 해석으로는 의미가 비슷하다.

그러나 SVD는 A가 직사각 행렬일 때를 의미한다는 차이가 있다.

이로 인해, 고유값 분해에서는 고유벡터로 이루어진 행렬들이었던 P와 P^T가, 특이값 분해에서는 U와 V^T 를 정사각행렬로 변환해준 뒤 계산해진다는 것을 확인할 수 있다.

이렇게 제곱으로 계산이 된 고유벡터 값들에 대응되는 고유값을 구한 것이므로, 직사각 대각행렬 ∑에 주대각 성분으로 들어오는 고유값들에는 루트를 씌워주는 것이다.

SVD 종류

• full SVD

  

• thin SVD: Σ에서 마지막 주대각성분이 있던 값까지 해서 정방행렬로 바꾸어준 뒤, U에서도 이에 대응되는 열들을 지워준 것이다. 원본 복구가 가능하다.

• compact SVD: 주대각 성분인 λ가 0인 것까지 다 지운다. 원본 복구가 가능하다.

  

• truncated SVD: 주대각 성분인 λ가 0이 아닌 것까지 다 지운다. 원본 복구가 불가능하다.

참고로 저주파는 왼쪽 상단에 해당되는 행렬로 중요한 정보들 밀집되어 있는 것이고, 고주파는 오른쪽 하단에 해당되는 행렬 디테일한 세부 정보들에 해당된다.

따라서 왼쪽 상단을 기준으로 데이터를 압축함으로써 정보들을 가능한 보존하는 것이다.

PCA(Princpal Component Analysis)

데이터 분포에 대한 주성분(Principal Component)을 찾는 것이다.

PCA의 목적은 최적의 feature 조합을 찾는 것으로, feature selection과 feature dimension reduction을 하기 위해 쓰인다.

• PCA 알고리즘 순서

1. 데이터의 평균으로 원점을 옮긴다.
2. 데이터의 공분산행렬, 고유값, 고유벡터를 구한다.
3. 고유벡터를 기저라고 가정하고 데이터를 보면, 가장 큰 분산을 관점으로 보게 된다.

일반적으로 가장 분산(고유벡터; Eigenvalue)이 큰 축 하나만 사용 or 축 2개 사용

• 공분산? 두 feature가 얼마나 동시에 같은 방향으로 변하는가.

• 고유벡터를 얻는다? == 연관있는 피쳐쌍의 기저를 얻는다.

• 공분산(cov) 행렬은 원본 데이터 feature의 개수가 n이면 n X n 크기의 cov행렬이 생기게 된다.

PCA는 피쳐선택, 피쳐수감소에 주로 쓰이지만, 이미지 압축에도 사용된다.

• PCA 장점

​ 데이터 feature차원이 크면 데이터 직관하기 힘든데, PCA를 사용하면 도움이 된다.

• PCA 단점

1. 공분산이 중요하기 때문에, 분산이 작은게 좋은 데이터에 사용하기에 부적합하다.

2. 데이터의 분산이 직교하지 않으면 적합하지 않다.

LDA(Linear Discriminant Analysis)

클래스 간 중심거리(분산)는 크고, 클래스 내 분산은 작게 학습시킨다

분자는 클래스 중심간의 거리이며, 분모는 동일 클래스 내의 분산이다.

LDA에 의해 생성되는 vector로 projection(사영)하면, 클래스 판별이 잘 된다.

• LDA 용도

1. class 3개 이상도 가능
2. feature selection도 가능
3. 분류도 가능 (그렇지만 classifier은 아니다.)

• LDA 한계점

​ 비선형분포인 데이터에서는 적합하지 않다.

• PCA과 LDA차이점

​ PCA는 종합적인 전체 데이터를 잘 설명하는 축을 찾는게 목표 (클래스 레이블을 고려하지 않는다.)

​ LDA는 클래스 레이블을 고려하여 분류를 잘해주는 축을 찾는 것이 목표이다.

참고한 사이트

https://m.blog.naver.com/kiakass/222200041769

https://darkpgmr.tistory.com/106

해당 포스팅은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅 하였습니다. ✍️✍️

정렬

정렬은 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다.

정렬 알고리즘은 다음에 포스팅할 이진 탐색의 전처리 과정이라고 할 수 있다. 많은 정렬 알고리즘들 중 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해 알아보자. 이 정렬 알고리즘들을 공부하면서 알고리즘의 효율성의 중요성을 자연스럽게 깨닫게 될 수 있다.

선택 정렬

선택정렬은 맨 앞의 데이터부터 가장 작은 데이터를 맨 앞으로 보내면서 데이터를 정렬하는 방식이다. 이렇게 가장 작은 데이터가 맨 앞에 오게 되면, 그 다음 두 번째 자리부터 이를 다시 반복하게 된다.

이를 파이썬 코드로 표현하면 다음과 같다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] # 스와프

print(array)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

이때 주석에 쓰인 스와프는 특정한 리스트가 있을 때, 두 변수의 위치를 변경하는 작업을 의미한다. 이는 파이썬이 아닌 다른 대부분의 프로그래밍 언어에서는 직관적으로 시행되지 않는 경우가 많으니 참고하자.

선택 정렬의 시간 복잡도

선택 정렬의 연산 횟수는 N + (N-1) + (N-2) + ... + 2로 볼 수 있다.

따라서 이의 근사치는 N x (N+1) / 2 라고 할 수 있다. 이의 빅오 표기법으로는 O(N²)이다.

그러므로 선택 정렬을 이용하는 경우 데이터의 개수가 10,000개 이상이면 속도가 급격히 느려지는 것을 확인할 수 있다. 실제로 대부분의 정렬 알고리즘과 비교했을 때, 매우 비효율적이지만 이 선택 정렬의 방식은 특정 리스트에서 가장 작은 데이터의 값을 찾는 때 자주 쓰이므로 익숙해져야 한다.

삽입 정렬

삽입 정렬은 데이터를 하나씩 확인하면서, 각 데이터를 적절한 위치에 삽입하는 알고리즘이다. 따라서 이는 데이터가 거의 정렬이 되어 있을 경우 더욱 효율적이다.

첫번째의 데이터는 정렬이 되어있다고 보고 두번째의 데이터부터 정렬이 되어있는 데이터들 사이에 적절히 삽입하면서 (선택정렬과는 달리) 한 턴에 정렬이 완료되는 알고리즘이다.

이를 파이썬 코드로 표현하면 다음과 같다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1,len(array)):
    for j in range(i,0,-1): # 인덱스 i부터 1까지 감소하면서 반복
        if array[j] < array[j-1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j-1] = array[j-1], array[j]
        else: # 자기보다 작은 데이터가 있을 때, 해당 위치에 멈춤
            break

print(array)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

삽입 정렬의 시간 복잡도

선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었으므로, 삽입 정렬의 시간 복잡도는 O(N²)이다. 여기서 기억해두어야 할 점은 삽입 정렬은 거의 정렬이 되어 있는 데이터의 경우, 매우 빠르게 동작한다는 점이다. 이 경우에는 O(N)의 시간복잡도를 가질 수도 있게 된다. 심지어는 거의 정렬이 되어있는 경우에는 다음에 배울 퀵 정렬보다 삽입 정렬이 더 효율적인 알고리즘이다.

퀵 정렬

퀵 정렬은 지금까지의 정렬 알고리즘 중 가장 보편적으로 사용되는 알고리즘이다. 대부분의 상황에서 효율적인 알고리즘이기 때문이다. 퀵 정렬은 기준값을 정한 후, 이를 기준으로 큰 수들은 오른쪽으로 작은 수들은 왼쪽으로 정렬하면서 동작한다. 이때 기준이되는 값을 '피벗'이라고 한다. 이때 피벗을 설정하는 방식은 다양한데, 여기서는 첫번째 데이터를 피벗으로 정하는 것으로 설정하자.

이미지 출처: https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

일반적으로 사용되고 있는 퀵 정렬의 소스코드는 다음과 같다.

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end: # 원소 개수가 1인 경우 종료
        return
    pivot = start # 피벗은 첫 번째 데이터
    left = start + 1
    right = end
    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right: # 엇갈렸으면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않았으면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

quick_sort(array, 0, len(array)-1)
print(array)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

시간 면에서 조금 비효율적이지만, 이보다 더 직관적인 코드는 다음과 같다.

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    # 리스트가 하나의 원소만 담고 있으면 종료
    if len(array) <= 1:
        return array
    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array))

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

퀵 정렬의 시간 복잡도

앞에서 배웠던 선택 정렬과 삽입 정렬의 시간 복잡도는 O(N²)이었다. 이에 반해 퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다. 그러나 이때 주의할 점은 최악의 경우에 대한 시간 복잡도는 O(N²)라는 점이다. 무작위로 입력된 데이터의 경우 퀵 정렬은 효율적이지만, 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작된다. 즉, 삽입 정렬은 데이터가 거의 정렬되어 있는 경우 효율적이라고 하였는데, 이와 반대의 경우라고 생각하면 된다.

계수 정렬

계수 정렬 알고리즘은 특정한 조건이 부합하는 경우에만 사용할 수 있지만, 매우 빠른 정렬 알고리즘이다.

계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있는 경우'에만 사용할 수 있다. 즉, 데이터의 범위가 무한한 실수형 데이터인 경우 계수 정렬을 사용하기 어렵다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.

계수 정렬이 이러한 조건을 가지는 이유는, 계수 정렬 이용 시 '모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언'해야 하기 때문이다. 즉, 가장 큰 데이터와 가장 작은 데이터의 차이가 N 이라면 총 N+1개의 데이터가 들어갈 수 있는 리스트를 초기화해야 한다.

계수 정렬은 이전의 설명했던 정렬 알고리즘들처럼 직접 데이터의 값들을 비교한 후, 위치를 변경하며 정렬하는 방식이 아니다. 계수 정렬은 별도의 리스트를 선언하고 그 안에 데이터들의 정보를 저장하는 식으로 정렬된다.

1. 데이터 배열을 처음부터 끝까지 돌면서 각 요소가 몇번 나왔는지 count배열에 저장한다.

2. count 배열의 누적합을 구한다. (카운트 된 숫자들 간의 빈 공간이 있을 때, 이에 대한 비효율성을 줄이기 위하여 필요하다.)

3. 원래 데이터 배열과 카운트 누적 리스트를 비교하며, 정렬된 리스트를 생성한다.

이를 파이썬 코드로 표현하면 다음과 같다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

count = [0] * (max(array) + 1) # 모든 범위를 포함하는 리스트 선언

for i in range(len(array)):
    count[array[i]] += 1 # 각 데이터에 해당하는 인덱스 값 증가

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

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

계수 정렬의 시간 복잡도

데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라 하면 계수 정렬의 시간 복잡도는 O(N+K)이다. 따라서 데이터의 범위만 한정되어 있다면 매우 빠르게 동작한다. 현존하는 정렬 알고리즘 중 기수 정렬과 더불어 가장 빠르다고 볼 수 있다. 그러나, 계수정렬은 특정 범위내에서 반복되는 숫자가 많은 데이터의 경우에 효율적인 알고리즘이므로, 만약 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다.

++ 참고

파이썬 기본 정렬 라이브러리인 sorted()는 퀵정렬과 비슷한 병합 정렬을 기반으로 만들어졌다. 이는 최악의 경우에도 시간복잡도 O(NlogN)을 보장한다. 리스트 객체의 내장함수인 sort() 또한 이와 마찬가지이다.

따라서 코딩 테스트의 문제에서 별도의 요구가 없이 단순히 정렬을 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 하는 경우에는 계수 정렬을 사용하도록 하자.

정규분포

이미지 출처: https://www.mathsisfun.com/data/standard-normal-distribution.html $$ N(x;μ,σ^2)=\frac{1}{\sqrt{2πσ^2}}{exp(−\frac{(x−μ)^2}{2σ^2})} $$ 정규분포는 평균 μ을 기점으로 분산이 σ인 대칭을 띄는 종 모양의 그래프이다.

특히 평균 0, 분산이 1 인 정규분포를 표준정규분포라고 한다.

표준화

표준정규분포가 아닌 일반 정규분포를 평균이 0, 분산이 1이 되도록 맞추어 표준정규분포 형태로 바꾸는 것이다.

μ 가 데이터들의 평균이고, σ가 데이터들의 표준편차일 때, 표준화는 다음과 같이 진행된다. $$ Z=\frac{X- \mu }{\sigma} $$

중심 극한 정리

모딥단이 정규분포를 따르지 않는 표본이더라도, 표본들의 수가 30개 이상이면 근사적으로 정규분포를 따른다는 이론이다. (모분산을 모르는 경우에도, 표본의 수 n이 30 이상인 경우 정규분포를 사용한다.)

표본의 크기가 클수록 모집단의 평균에 근사하는 정규분포 형태를 띄게 된다.

이미지 출처: https://m.blog.naver.com/mykepzzang/220851280035

t 분포

t=0을 중심으로 하는 좌우대칭형 그래프이다.

모집단이 정규분포이지만, 표본의 크기가 30보다 작은 경우에 t 분포를 사용한다. (모분산을 모르는 경우에도 t 분포를 사용하기도 한다.)

따라서 표본의 크기 n이 무한대로 발산하게 되면, 표준 정규분포와 일치하게 된다.

표본 비율의 정규 분포

성공 또는 실패의 두 가지로만 구분되는 이항분포를 따르는 모집단의 표본의 수 n이 충분히 큰 경우, 중심극한정리에 의하여 확률 $\hat{p}=x/n$ 은 근사적으로 정규분포를 따른다. (일반적으로 np>5, nq>5 일 때 n이 충분히 크다고 본다. ) $$ z = \frac{\hat{p}-p}{\sqrt{\frac{pq}{n}}} \sim N(0,1) $$ 이때 p는 어떤 사건이 일어날 확률이며 q는 일어나지 않을 확률로, 이 둘을 더하면 1이 된다. (p+q=1)

크기가 n인 표본을 추출하여 성공횟수가 x라 할 때, 이를 표본비율이라고 하며 $\hat{p}=\frac{x}{n}$와 같이 나타낸다.

표본비율의 평균, 분산의 값은 기존의 모집단인 이항분포의 평균($E(X)=np$), 분산($Var(X)=npq$)를 이용하여 다음과 같이 계산할 수 있다. $$ E(\hat{p})=E(\frac{X}{n})=\frac{1}{n}E(X)=p $$

$$ Var(\hat{p})=Var(\frac{X}{n})=\frac{1}{n^2}npq=\frac{pq}{n} $$

신뢰구간

표본을 통해 추정한 모수를 통해 실제 모수가 있을 구간을 추정한 것이다.

따라서 해당 구간내에 실제 모수가 있을 확률인 신뢰수준을 몇으로 잡느냐에 신뢰구간이 달라진다.

일반적으로 95%와 99%의 신뢰수준을 가질 경우에 대해 신뢰구간을 추정하는 경우가 많다.

신뢰구간은 (하한값, 상한값) 의 형태로 나타낸다. 이는 실제 모수가 하한값 이상과 상한값 이하의 사이에 들어올 것이라고 예상한 것이다.

따라서 모비율 p에 대한 (1-α)*100% 신뢰구간은 다음과 같이 계산된다. $$ (\hat{p}-z_{\frac{\alpha}{2}}\sqrt{\frac{\hat{p}\hat{q}}{n}}, ;\hat{p}+z_{\frac{\alpha}{2}}\sqrt{\frac{\hat{p}\hat{q}}{n}}) $$ 이때 α는 유의수준으로 1종 오류를 범할 최대확률이다.

• 1종 오류: 귀무가설이 맞는데 대립가설을 맞다고 한 경우(연구자가 주장하고자 하는게 대립가설)

또한, 위 식에서 $z_{\frac{\alpha}{2}}\sqrt{\frac{\hat{p}\hat{q}}{n}}$ 은 표본 비율이 모비율과 다를 수 있는 차이인 오차를 나타내는 값이라고 하여, 표본오차라고 불린다. (허용오차, 최대허용오차, 오차범위, 오차한계라고도 불린다.)

해당 포스팅은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅하였습니다. ✍️✍️

DFS/BFS

사전 지식

탐색은 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다.

이때 대표적인 탐색 알고리즘은 DFS와 BFS이다.

이 DFS와 BFS를 알아보기 위하여 기본 자료구조인 스택과 큐에 대한 개념과 재귀함수, 그래프에 대해서 먼저 알아보자.

스택

스택(Stack)은 상자를 쌓는 것과 비슷하다고 할 수 있다.

일반적으로 상자는 바닥부터 위로 쌓으며, 이를 다시 꺼내기 위해서는 위에서부터 순서대로 꺼낸다.

이러한 구조를 선입후출구조 (First In Last Out) 또는 후입선출구조(Last In First Out)라고 한다.

이를 파이썬 코드로 표현하면 다음과 같다.

stack=[]

# 삽입(3) - 삽입(1) - 삭제() - 삽입(5)
stack.append(3)
stack.append(1)
stack.pop()
stack.append(5)

print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력

[3, 5]
[5, 3]

파이썬에서 스택을 이용할 시에는 기본 리스트에 append()와 pop() 메서드를 사용하면 된다.

append()는 리스트의 가장 뒤쪽에 데이터를 삽입하고, pop()은 리스트의 가장 뒤쪽에서 데이터를 꺼내는 함수이다.

큐

큐(Queue)는 대기 줄과 비슷하다고 할 수 있다. 맛집에서 음식을 기다리는 대기줄을 생각해보자. 새치기와 같은 반칙은 없는 기본적인 대기줄의 룰을 생각했을 때, 먼저온 사람이 제일 먼저 먹을 수 있게 된다. 이러한 구조를 선입선출(First In First Out) 구조라고 한다.

이를 파이썬 코드로 표현하면 다음과 같다.

from collections import deque # 큐 구현을 위해 deque 라이브러리 사용

queue=deque()

# 삽입(3) - 삽입(1) - 삭제() - 삽입(5)
queue.append(3)
queue.append(1)
queue.popleft()
queue.append(5)

print(queue) # 먼저 들어온 원소부터 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력

deque([1, 5])
deque([5, 1])

파이썬에서 큐를 구현할 시에는 collections 모듈에서 제공하는 deque를 활용한다.

deque는 리스트 자료형에 비해 데이터를 넣고 빼는 것이 효율적이며, queue 라이브러리 보다 간단하다. 또한 대부분의 코딩 테스트에서 collentions 모듈과 같은 기본 라이브러리는 사용하도록 허용하므로 참고하자.

재귀 함수

재귀함수란 자기 자신을 다시 호출하는 함수이다.

예시 코드를 살펴보자.

def func():
    print('hello')
    func()
func()

이 코드를 실행하면 'hello'라는 문자열을 무한히 출력하게 된다. func() 함수는 'hello'를 출력한 후, 다시 자기 자신을 불러오기 때문에 이러한 현상이 발생하게 된다. (참고로 이를 실행했다가 출력을 멈추고 싶으면 ctrl+C를 누르면 무한루프에서 빠져나오게 된다.)

이러한 재귀함수는 특정 조건을 만족할 시 반복적인 코드가 종료되거나, 함수가 진행됨에 따라 수렴하는 식으로 종료가 되는 형태로 코드를 작성할 때 자주 사용된다.

이러한 재귀함수를 사용시, 반복문을 사용하는 것보다 더 간결하게 표현할 수 있는 경우들이 있으니, 이점을 참고해서 코드를 작성하면 좋을 것 같다.

그래프

그래프는 노드(Node)와 간선(Edge)으로 이루어져있다. 이때 노드를 정점(Vertex)이라고도 말한다.

두 노드가 간선으로 연결되어 있는 것을 '두 노드가 인접하다'라고 한다.

이러한 그래프를 표현하는 방식으로는 인접 행렬과 인접 리스트가 있다.

• 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현
• 인접 리스트: 리스트로 그래프의 연결 관계를 표현

위 그래프에 대한 인접 행렬은 다음과 같다.

위 인접행렬을 파이썬으로 작성해보자.

(이때 연결이 되어있지 않은 코드는 무한의 비용으로 작성한다.)

# 인접 행렬 예제
INF = 999999999 # 무한의 비용 선언

graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

[[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]

위 그래프에 대한 인접 리스트는 다음과 같이 생성할 수 있다.

인접 리스트는 위 그림과 같이, 모든 노드에 대해 연결된 다른 노드의 정보만을 연결하여 저장한다.

이를 파이썬 코드로 작성하면 다음과 같다.

# 인접 리스트 예제
graph = [[] for _ in range(3)] # 총 노드가 3개인 그래프에 대한 인접 리스트

# 노드 0에 연결된 다른 노드들의 정보 (노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))

# 노드 1에 연결된 다른 노드들의 정보 (노드, 거리)
graph[1].append((0, 7))

# 노드 2에 연결된 다른 노드들의 정보 (노드, 거리)
graph[2].append((0, 5))

print(graph)

[[(1 ,7), (2, 5)], [(0, 7)], [(0, 5)]]

인접 행렬은 인접 리스트보다 직관적이지만, 대용량 데이터에 사용하기에는 메모리상 비효율적이라는 단점이 있다. 반면, 인접 리스트는 연결된 정보만을 저장하기 때문에 효율적으로 메모리를 사용할 수 있다.

DFS

DFS(Depth-First Search)는 깊이 우선 탐색이라고도 불린다.

(이때 그래프를 탐색한다는 것은 하나의 노드를 시작으로 모든 노드들을 한번씩 방문하는 것을 말한다.)

이 DFS 현재 노드의 자식의 자식들을 처리해 준다고 할 수 있다. 즉, 현재 노드의 자식, 그 자식 노드의 자식, 그 자식 노드의 자식 .. 으로 제일 말단 노드까지 찍고 그 다음 다시 올라와 다른 자식에 대한 자식의 자식의 ... 이런 식으로 처리하기 때문에 깊이 우선 탐색이라고 하는 것이다.

DFS는 깊이 부분에서 얕은 것부터 깊은 것 순으로 우선 처리한 후, 그 다음 너비 부분에서 얕고 깊은 것들을 고려한다. (이때, 제일 깊은 노드를 방문한 후, 다시 그 다음으로 얕은 다른 노드를 갈 때에는 방문을 생략하고 이동한다.)

DFS는 스택 자료구조를 사용하며, 구체적인 동작과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입 후, 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 있을 시, 그 노드를 스택에 삽입 후, 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면, 다시 스택에서 최상단 노드(가장 얕은 노드)를 꺼낸다.
3. 2번을 더 이상 수행할 노드가 없을 때까지 반복한다.

이때 방문 처리는 스택에 한 번 삽입 되었던 노드가 다시 삽입되지 않도록 처리하는 것이다. 따라서 각 노드는 한번씩만 방문 처리를 하게 된다.

이미지 출처: https://ko.wikipedia.org

이를 파이썬으로 다음과 같이 구현할 수 있다.

def dfs(graph, v, visited):
    visited[v] = True # 현재 노드를 방문 처리
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited) # 현재 노드와 연결된 다른 노드를 재귀적으로 방문

# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원)
visited = [False]*9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

1 2 7 6 8 3 4 5

BFS

BFS(Breadth First Search) 알고리즘은 너비 우선 탐색이라고도 한다.

현재 노드와 연결된 자식들을 먼저 처리한다고 할 수 있다. 즉, 현재 노드의 모든 자식 노드를 처리한 다음, 그 중 한 노드의 모든 자식 노드를 처리하고 ... 이런식으로 같은 깊이에 해당되는 노드들을 처리하면서 깊어지기 때문에 너비 우선 탐색이라고 하는 것이다.

BFS는 너비 부분에서 얕은 것부터 깊은 것 순으로 우선 처리한 후, 그 다음 깊이 부분에서 얕고 깊은 것들을 고려한다.

BFS는 큐 자료구조를 사용하며, 구체적인 동작과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입 후, 방문 처리를 한다.
2. 큐에서 노드를 꺼내, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번을 더 이상 수행할 노드가 없을 때까지 반복한다.

이때 방문 처리는 스택에 한 번 삽입 되었던 노드가 다시 삽입되지 않도록 처리하는 것이다. 따라서 각 노드는 한번씩만 방문 처리를 하게 된다.

이미지 출처: https://ko.wikipedia.org

이를 파이썬으로 다음과 같이 구현할 수 있다.

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True # 현재 노드를 방문 처리
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        # 해당 원소와 인접한, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원)
visited = [False]*9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

1 2 3 8 7 4 5 6

그러면 코딩 테스트 문제에서 어떤 경우에 이 탐색 알고리즘을 사용할 수 있을까?

1차원 배열이나 2차원 배열을 그래프 형태로 생각하여 DFS와 BFS를 사용하는 풀이방법을 생각해 볼 수 있다.

실전 문제 1

난이도 중 | 풀이 시간 30분 | 시간 제한 1초 | 메모리제한 128MB

N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. 다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다.

입력 조건

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
• 두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

출력 조건

• 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

입력 예시

15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111

출력 예시

8

이 문제는 DFS로 해결할 수 있다.

실전 문제 2

난이도 중 | 풀이 시간 30분 | 시간 제한 1초 | 메모리제한 128MB

N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

입력 조건

• 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력 조건

• 첫째 줄에 최소 이동 칸의 개수를 출력한다.

입력 예시

5 6
101010
111111
000001
111111
111111

출력 예시

10

이 문제는 BFS로 해결할 수 있다.

본 책 저자의 깃허브에 이미 책에 실린 문제들에 대한 풀이 코드들이 정리된 repository가 있으니 위 문제에 대한 답을 참고하고 싶으신 분은 github.com/ndb796/python-for-coding-test를 통해 참고해주시기 바랍니다!

해당 포스팅은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅 하였습니다. ✍️✍️

구현

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

즉, 어떤 문제든 소스코드를 작성하는 과정이 있으므로, 구현 문제는 모든 코딩 테스트 문제 유형을 포함한다고 할 수 있다.

구현 유형의 문제는 풀이를 떠올리기 쉽지만, 이를 소스코드로 옮기는 것은 어려운 문제를 의미한다.

특히 이 책에서는 완전 탐색과 시뮬레이션을 구현 유형으로 다루고 있다.

완전 탐색은 모든 경우의 수를 다 계산하는 해결 방법이며, 시뮬레이션은 제시된 알고리즘을 한 단계씩 직접 수행하는 문제를 의미한다.

이 유형은 따로 정해진 알고리즘 틀이 있는 것이 아니므로, 문제들을 통해 어떤 식으로 풀어야 하는지 감을 잡아보도록 하자.

예제 4-1

난이도 하 | 시간 제한 1초 | 메모리제한 128MB

여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여있다.

계획서에는 하나의 줄에 띄어쓰기를 기준으로 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 각 문자의 의미는 다음과 같다

• L: 왼쪽으로 한 칸 이동
• R: 오른쪽으로 한 칸 이동
• U: 위로 한 칸 이동
• D: 아래로 한 칸 이동

이때 여행가 A가 N × N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1, 1)의 위치에서 L 혹은 U를 만나면 무시된다. 다음은 N = 5인 지도와 계획서이다.

이 경우 6개의 명령에 따라서 여행가가 움직이게 되는 위치는 순서대로 (1, 2), (1, 3), (1, 4), (1, 4), (2, 4), (3, 4)이므로, 최종적으로 여행가 A가 도착하게 되는 곳의 좌표는 (3, 4)이다. 다시 말해 3행 4열의 위치에 해당하므로 (3, 4)라고 적는다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 <= N <= 100)
• 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 <= 이동 횟수 <= 100)

출력 조건

• 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표(X, Y)를 공백으로 구분하여 출력한다.

입력 예시

5

R R R U D D

출력 예시

3 4

이 문제는 시뮬레이션 유형으로 분류할 수 있다. 코딩 테스트의 1~2번 문제는 대부분 그리디나 구현 유형으로 이 두 유형은 난이도가 낮은 만큼 합격을 좌우하는 중요한 문제이므로 놓치지 않도록 하자.

예제 4-2

난이도 하 | 시간 제한 2초 | 메모리제한 128MB

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.

• 00시 00분 03초
• 00시 13분 30초

반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.

• 00시 02분 55초
• 01시 27분 45초

입력 조건

• 첫째 줄에 정수 N이 입력된다. (0 <= N <= 23)

출력 조건

• 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

입력 예시

5

출력 예시

11475

이 문제는 완전 탐색 유형으로 분류할 수 있다.

본 책 저자의 깃허브에 이미 책에 실린 문제들에 대한 풀이 코드들이 정리된 repository가 있으니 위 문제에 대한 답을 참고하고 싶으신 분은 github.com/ndb796/python-for-coding-test를 통해 참고해주시기 바랍니다!

선형회귀(Linear regression)

• 학습과정

1. 임의의 파라미터 값을 설정해서 선형모델을 가정한다.

2. train data로 학습한다.

3. loss, cost를 사용해서 MSE를 구한다.

4. 경사하강법을 사용해서 MSE가 가장 작은 파라미터를 찾는다. (Least Squares methods; 최소 제곱법)

이미지 출처: https://vitalflux.com

loss는 실제값과 예측값 차이(오차)를 제곱한 것(SE; Squared Error)이다. $$ loss = (Y-Y')^2 $$ 이때 Y는 실제값을 의미하고, Y'는 예측값을 의미한다.

cost는 오차제곱들의 평균(MSE; Mean SE)이다.

$$ MSE=\frac{1}{N}\sum_{i=1}^N (Y_i-Y_i')^2 $$

이때 다중 선형회귀 모형의 식은 다음과 같다. (다중 선형회귀란 독립변수 x가 여러개가 있는 선형회귀이다.) $$ \sum_{i=1}^n 𝑦𝑖 = \sum{i=1}^n (\beta_0 + \sum_{j=1}^p\beta_jx_{ij} + \epsilon_𝑖) , \qquad 𝑖 = 1, 2, ..., 𝑛, \epsilon_𝑖~𝑁(0, \sigma^2) $$ 따라서 회귀계수의 추정은 경사하강법을 이용하여 오차항인 𝜖_𝑖의 제곱을 최소로 하는 값을 찾는 것이다. $$ \sum_{i=1}^n \epsilon_𝑖^2 = \sum_{i=1}^n (𝑦𝑖-\beta_0 - \sum{j=1}^p\beta_jx_{ij})^2 $$

경사하강법(Gradient Descent)은 MSE 함수식을 최소화하기 위한 값을 찾는 방법으로, 미분으로 기울기를 구해서 조금씩 하강시키며 최적의 값을 찾는다. $$ 새로운값=기존값-러닝레이트\times 미분결과 $$

참고로 convex는 (아래로) 볼록한 함수를 의미하며, concave 오목한 함수를 의미한다.

Ridge regression

선형회귀에서 파라미터가 너무 커지지 않도록(즉, 과적합되지 않도록) L2 norm을 사용해서 제한한다.

이때, norm은 벡터의 크기(magnitude)를 측정하는 방법이다.

• L2 norm

  유클리드 노름이라고도 한다.

  이 L2 norm은 다음과 같이 계산된다.

  $$ L_2=||x||_2=\sqrt{\sum_i^nx_i^2} = \sqrt{\sum_i^nx_i\cdot x_i} = \sqrt{\sum_i^nx_i^T x_i} $$

위의 L2 norm을 선형회귀 추정을 위한 비용함수인 오차항의 제곱식에 추가하면 최종 릿지 회귀식이 된다. $$ \sum_{i=1}^n(y_i-\beta_0-\sum_{j=1}^p\beta_jx_{ij})^2+\lambda\sum_{j=1}^p\beta_j^2 $$

그러면 이러한 Ridge regression이 어떻게 과적합을 막을까?

위 식을 살펴보면 릿지회귀의 식은 기존의 비용함수 $\sum_{i=1}^n(y_i-\beta_0-\sum_{j=1}^p\beta_jx_{ij})^2$에 람다를 곱한 L2 norm 을 더한 것이다.

이때 람다는 0에서 1 사이의 값을 갖는데, 이 람다의 값이 커질수록 비용함수의 변화가 줄어들게 되는 Regularization이 일어나게 된다. 즉, $\lambda\sum_{j=1}^p\beta_j^2$ 값을 regular term으로 보게 되며, 이때 람다가 클수록 제한이 강해지는 것이다.

Lasso regression

과적합을 막기위해서 L1 norm을 사용하는 방법이다.

• L1 norm

  맨허튼 노름이라고도 한다.

  이 L1 norm은 다음과 같이 계산된다. $$ ||x||1=\sum{i=1}^n|x_i| $$

이 방법은 절대값을 이용하였으므로 미분이 불가능하기에 경사하강법이 아닌 다른 방법으로 최적화를 해야한다.

따라서 라쏘 회귀의 식은 다음과 같다. $$ \sum_{i=1}^n(y_i-\beta_0-\sum_{j=1}^p\beta_jx_{ij})^2+\lambda\sum_{j=1}^p|\beta_j| $$

Lasso regression의 경우 중요하지 않은 feature에 대해 weight 값을 0으로 둔다. 즉, feature selection효과도 있다.

또한, 절대값을 사용하기 때문에 Ridge regression보다 더 타이트하게 Regularization이 일어난다.

Logistic Regression

Logistic regression은 "regression"이라고 명시되어 있지만, "classification"문제를 풀기위한 모델이다. 헷갈릴 수 있으므로 잘 기억해야 한다.

Logistic regression은 선형 회귀를 이용하여 선형 분류를 하는 모델이다.

이미지 출처: https://nittaku.tistory.com/478

위와 같이 데이터의 형태인 경우, 선형회귀로는 이를 예측하기 힘들다. 따라서 이를 곡선으로 만들어 주어 회귀식으로 이진분류를 가능하게 만든다. 이때 이렇게 로지스틱 함수와 같이 s자형으로 표현되는 곡선 함수들을 통틀어 시그모이드 함수라고 한다. (그러나 일반적으로 시그모이드 함수라 하면 로지스틱 함수를 의미한다.)

이러한 로지스틱 회귀를 하기위한 과정은 다음과 같다.

1. 오즈비(odds ratio)를 구한다. $$ Odds(P)=\frac{P}{1-P} = \frac{A일,확률}{A가,아닐,확률} $$

2. 오즈비에 로그함수를 취한다. 이를 로짓 함수(Logit function)라고 한다. $$ logit(P)=log(\frac{P}{1-P}) = e^z = wx+b $$

3. logit 함수를 P에 대해 역변환을 한다. 이를 로지스틱 시그모이드 함수(Logistic Sigmioid function)라고 한다. $$ P(x)=\frac{1}{1+e^{-z}}=\frac{1}{1+e^{-(wx+b)}} $$ 이때 이 wx+b 는 선형합을 의미한다. 따라서 이 z에 최적화된 선형합이 들어가게 되면 해당 데이터 x에 대해 A일 확률값이 나오게 되는 것이다.

이때 최적화된 선형합을 구하는 수식은 다음과 같은 방법으로 계산된다.

$$ argmax\prod P(label|x)=\prod\frac{1}{1+e^{-label\times(wx+b)}} $$ 이때 label값은 A인 경우 1, A가 아닌 경우 -1로 설정한다. 따라서 부호가 항상 같게 유지가 되어 어떤 데이터가 들어오든지 전부 최대화를 가능하게 만든다.

그러나 이 식을 최대화를 하는 식이며, 곱셈들로 이루어졌으므로 경사하강법을 이용할 수 없다.

따라서 위 식에 ① 로그를 씌워 곱셈들을 덧셈 연산으로 변환되게 하며, ② 부호를 바꾸어 최소화를 시키는 식으로 바꾸어 준다. $$ \sum -log\frac{1}{(1+e^{-label\times(wx+b)})}=\sum log(1+e^{-label\times(wx+b)}) $$ 위 식에 경사하강법을 이용하여 최적의 파라미터 값을 찾으면 된다.

따라서 logistic function 값이 0.5보다 큰지, 작은지에 따라 데이터 레이블을 결정을 한다.

++ 참고로 이진분류가 아닌 label 개수가 3개 이상일 때 사용하는 다항 로지스틱회귀라는 모델이 있다.

부가적인 내용들

Q. 왜 경사하강법과 같이 iterative(반복적인) 방법으로 학습할까?

A. 많은 양의 데이터를 학습할 때에는, 한번에 바로 최적화시키기가 어렵다. 따라서 최적화를 하기 위해 반복적인 학습과정을 거치는 것이다.

Classification vs Regression

• 분류는 예측하려는 목적값이 label, 회귀는 예측하려는 목적값이 real-number이다.

• 분류, 회귀 둘 다 지도학습이다.

Linear Classification vs Linear Regression

• 선형 분류는 0~1사이의 확률값 생성한다. 따라서 이때의 임계치값을 정하여, 이를 기준으로 분류한다.

• 선형 회귀는 0~1이외의 값들이 나온다. 즉, 확률값이 아니므로 분류 문제들에 적합하지 않다.

여러가지 확률 분포

여러가지 확률분포들에 대해 살펴보고, 각각 평균과 분산이 어떻게 계산되는지 알아보자.

이산 균등 분포

취하는 확률들이 모두 같은 확률분포이다.

이산균등분포의 f(x)는 다음과 같이 계산된다.

$$ f(x)=\frac{x}{n} $$

이때 평균과 분산은 다음과 같이 계산된다.

$$ E(x)=\sum_{x=1}^n x \cdot f(x) = \sum_{x=1}^n \frac{x}{n}=\frac{1}{n}\frac{n,(n+1)}{2}=\frac{n+1}{2} $$

$$ Var(x)=\sum_{x=1}^n x^2 f(x)-{E(x)}^2=\sum_{x=1}^n \frac{x^2}{n}-(\frac{n+1}{2})^2=\frac{1}{n}\frac{n(n+1)(2n+1)}{6}-(\frac{n+1}{2})^2=\frac{n^2-1}{12} $$

이때 n은 데이터들의 총 개수이다.

베르누이 분포

실험 시행 결과가 성공 or 실패 중 하나로 결정되는 사건에 대한 확률 분포이다.

이때, 성공할 확률을 p, 실패할 확률을 q라고 하자. (이때 p + q = 1)

각각의 시행들은 독립적이라고 가정한다.

베르누이 분포의 f(x)는 다음과 같이 계산된다.

$$ f(x)=p^x(1-p)^{1-x}\quad(x=0;or;1) $$

성공 또는 실패 중 하나이기 때문에, x가 0 또는 1로 결정된다.

이때 평균과 분산은 다음과 같이 계산된다.

$$ E(x)=1\times p+0 \times q =p $$

$$ Var(x)=E(x^2)-{E(x)}^2=1\times p+0 \times q -p^2 = p-p^2=p(1-p) $$

이항분포

베르누이 분포를 여러번 시행한 것이 이항분포이다.

이때 이항분포를 다음과 같이 표현할 수 있다.

$$ B(n,p) $$

이때 n은 시행횟수이며 p는 성공확률을 의미한다.

이항분포의 f(x)는 다음과 같이 계산된다.

$$ f(x)=_nC_x,p^x(1-p)^{n-x}\quad(x=0,,1,...,,n) $$

참고로 이때 _nC_k는 다음과 같이 계산된다.

$$ _nC_k=\frac{n!}{k!(n-k)!} $$

이 n!은 1~n까지의 수로 만들 수 있는 경우의 수로 0!일 경우에는 0~1로 만들 수 있는 경우의 수이기에 0! = 1 이 됨을 주의하자.

이때 평균과 분산은 다음과 같이 계산된다.

$$ E(x)=np $$

$$ Var(x)=np(1-p) $$

이 이항분포의 평균과 분산은 베르누이 분포가 n번 시행된 것이므로 베르누이 분포의 평균과 분산에 n을 곱한 값들이다.

초기하 분포

N개의 유한한 모집단에서 n번의 비복원 추출을 하는 확률분포이다.

이때 M개는 성공하고 (N-M)개는 실패한다고 가정하자.

이때 초기하 분포를 다음과 같이 표현할 수 있다.

$$ H(N,M,n) $$

초기하 분포의 f(x)는 다음과 같이 계산된다.

$$ f(x)=\frac{MC_x \cdot _{N-M}C{n-x}}{_NC_n}\quad (0\leq x\leq M,, 0\leq n-x \leq N-M) $$

이때 평균과 분산은 다음과 같이 계산된다.

$$ E(x)=n\frac{M}{N} $$

$$ Var(x)=n\frac{M}{N}(1-\frac{M}{N})(\frac{N-n}{N-1}) $$

이때 M/N은 성공하는 경우를 전체 경우로 나눈 것으로 p와 유사한 값을 갖게 된다.

또한 분산의 마지막에 곱해진 term은 다음과 같이 계산될 수 있음을 생각할 수 있다.

$$ \lim_{N \to \infty}\frac{N-n}{N-1}=1 $$

따라서 초기하 분포의 평균과 분산은 모집단의 수 즉, N이 증가할수록 이항분포의 평균과 분산인 np, npq와 유사한 값을 갖게 된다고 볼 수 있다.

$$ \lim_{N \to \infty} H(N,M,n) \simeq B(n,\frac{M}{N}) $$

기하 분포

여러번 시도 끝에 성공이 나오는 확률을 구하는 분포이다.

이때 성공할 확률을 p, 실패할 확률을 q 라고 할 때, 기하분포를 다음과 같이 표현할 수 있다.

$$ Geo(p),or,NB(1,p) $$

기하분포 p(x)는 다음과 같이 계산된다.

$$ P(x)=q^{x-1}\cdot p $$

이때 평균과 분산은 다음과 같이 계산된다.

$$ E(x)=\frac{1}{p} $$

$$ Var(x)=\frac{q}{p^2} $$

음이항 분포

총 x번 중 k번 성공하고, 마지막 x번째에도 성공할 확률분포이다. 기하분포가 여러 번 있다고 생각하면 이해하기 쉬울 것 같다.

이때 성공할 확률을 p, 실패할 확률을 q 라고 할 때, 음이항 분포를 다음과 같이 표현할 수 있다.

$$ NB(k,p) $$

음이항 분포 p(x)는 다음과 같이 계산된다.

$$ f(x)={x-1}C{k-1}p^k \cdot q^{x-k}\quad (x\geq k) $$

참고로 이때 _x-1C_k-1는 다음과 같이 계산된다.

$$ {x-1}C{k-1} = \frac{(x-1)!}{(k-1)!(x-k)!} $$

맨 마지막은 항상 성공이기 때문에 마지막 성공을 빼고 시도한 (x-1)번 중 성공한 (k-1)끼리는 순서가 없고, 실패한 (x-k)끼리도 순서가 없기 때문에 경우의 수가 위와 같이 계산된다.

이때 평균과 분산은 다음과 같이 계산된다. $$ E(x)=\frac{k}{p} $$

$$ Var(x)=\frac{kq}{p^2} $$