이 대회에서 데이터는 .tiff 파일로 되어있다. 이 파일을 불러오기 위해 rasterio를 설치해준다.

pip install rasterio

각 .tiff 파일은 인코딩 결과가 기록되어있는 csv 파일의 id를 파일명으로 가지고 있다. 이 id를 이용해 id와 일치하는 .tiff파일을 가져오고, 이미지를 같은 크기로 잘라내 각각 id를 prefix로 두고 저장한다. index가 파일 이름, id라고 할 때

import os
import rasterio
from rasterio.windows import Window

data = rasterio.open(os.path.join('path/to/train/images/', f"{index}.tiff"), num_threads = 'all_cpus')

목표 크기는 256 x 256으로 다른 필요한 변수들을 설정한다. 원본 이미지가 256에 맞게 잘리지 않기 때문에 부족한 부분은 패딩으로 처리해준다. (패딩 크기 = 목표 크기 - 자르고 남은 부분)

target_size = 256
image_shape = original_image.shape # [height, width]

pad_height = (target_size - image_shape[0] % target_size)
pad_width = (target_size - image_shape[1] % target_size)

원본 이미지에 패딩까지 더하면 256으로 다 나눠떨어지니 모든 이미지를 256x256에 맞게 잘라준다.

# 전체 타일 인덱스
height_indices = (image_shape[0] + pad_height) // target_size
width_indices = (image_shape[1] + pad_width) // target_size

이제 이미지들을 잘라주기만 하면 된다. 하나의 .tiff 파일에서 잘라낸 이미지 중 idx 번째 이미지를 불러온다면 잘라낸 이미지의 원점이 되는 지점은 idx를 전체 가로 인덱스로 나눠준 값을 기준으로 구할 수 있다. 그리고 원본 이미지에 패딩도 추가되었기 때문에 양쪽으로 패딩이 있다고 하면 절반씩 빼주어야한다.

hight_idx = idx // width_indices
width_idx = idx % width_indices

h0 = hight_idx * target_size - (pad_height//2)
w0 = width_idx * target_size - (pad_width//2)

자른 이미지와 마스크를 저장하기 위해 초기화 시켜준다. 파일들을 읽어보면 어떤 이미지는 band(channel과 비슷하다고 보면 된다)가 1인 경우도 있고 3인 경우도 있다. 그래서 자른 부분을 사용할 때 band가 3인 경우는 그대로 사용하고 1인 경우는 전체 band에 같은 값이 들어가도록 했다. 이미지는 band의 최대값은 3이므로 목표 크기인 256에 맞게 256 x 256 x 3로, 마스크는 256 x 256으로 만든다.

import numpy as np

img = np.zeros((target_size, target_size, 3), dtype=np.uint8)
mask = np.zeros((target_size, target_size), dtype=np.uint8)

사용하는 좌표는 이미지 사이즈보다 같거나 작아야한다. 그리고 자른 이미지에 패딩이 포함되어있다면 패딩부터 포함되도록 해준다.

height0, height1 = max(0, h0), min(h0 + target_size, image_shape[0])
width0, width1 = max(0, w0), min(w0 + target_size, image_shape[1])

img[(height0 - h0) : (height1 - h0), (width0 - w0) : (width1 - w0)] = \
    np.moveaxis(data.read(list(range(1, data.count+1)),
                          window=Window.from_slices((height0, height1),
                                                      (width0, width1))),
                0, -1) # rasterio의 read 메서드로 불러오게 된다면 [band 수, height, width] 로 불러오게 된다. 이미지 형식에 맞게 [height, width, band(channel)]로 바꿔준다.

마스킹 데이터도 있다면 같은 좌표로 마스크 배열도 만들어준다.

mask[(height0 - h0) : (height1 - h0), (width0 - w0) : (width1 - w0)] = \
    mask[height0 : height1, width0 : width1]

제일 위에 원본 이미지를 보면 아무것도 없는 까만 테두리와 하얀 배경 부분이 있다. 이 부분은 학습에 필요하지 않으니 삭제해줘야한다. 삭제해주는 방법은 cv2로 색 공간을 HSV로 바꿔주어 채도값이 특정 값보다 높은 픽셀 수가 임계값보다 적으면 저장하지 않도록 하는 것이다.

cs2는 RGB와 반대인 BGR로 저장되므로

hsv = cv2.cvtColor(img, cv2.COLOR_BGR2HSV)
h, s, v = cv2.split(hsv)
is_save = -1 if (s > s_threshold).sum() <= pixel_threshold else idx

이제 전체 코드를 pytorch의 Dataset 클래스로 만들어서 전체 과정이 반복되도록 합쳐주면 된다.

import os
import numpy as np

import cv2
import rasterio
from rasterio.windows import Window
from torch.utils.data import Dataset

target_size = 256
s_threshold = 40
pixel_threshold = 1000 * target_size ** 2

class FTUDataset(Dataset):
    def __init__(self, index, size=target_size, encs=None):
        # rasterio로 데이터 가져오기
        self.data = rasterio.open(os.path.join('path/to/train/images/', f"{index}"), 
                                  num_threads = 'all_cpus')
        self.shape = self.data.shape
        self.size = size
        # 패딩 크기
        self.pad_height = (self.size - self.shape[0] % self.size)
        self.pad_width = (self.size - self.shape[1] % self.size)
        # 타일 수
        self.height_indices = (self.shape[0] + self.pad_height) // self.size
        self.width_indices = (self.shape[1] + self.pad_width) // self.size

        # 마스킹 데이터(RLE)가 있다면 추가, enc2mask 함수는 제일 위에 있는 RLE 포스팅 링크에
        self.mask = enc2mask(encs, (self.shape[1], self.shape[0])) if encs is not None else None


    def __len__(self):
        return self.height_indices * self.width_indices


    def __getitem__(self, idx):
        # 이미지 인덱스
        height_idx = idx // self.width_indices
        width_idx = idx % self.height_indices

        # 원점
        h0 = height_idx * self.size - (self.pad_height//2)
        w0 = width_idx * self.size - (self.pad_width//2)

        # 저장 배열 초기화
        img = np.zeros((self.size, self.size, 3), dtype=np.uint8)
        mask = np.zeros((self.size, self.size), dtype=np.uint8)

        # 이미지와 마스크 배열에 저장할 이미지 좌표 구하기 및 데이터 저장
        height0, height1 = max(0, h0), min(h0 + self.size, self.shape[0])
        width0, width1 = max(0, w0), min(w0 + self.size, self.shape[1])

        img[(height0 - h0) : (height1 - h0), (width0 - w0) : (width1 - w0)] = \
            np.moveaxis(data.read(list(range(1, self.data.count+1)),
                                    window=Window.from_slices((height0, height1),
                                                              (width0, width1))),
                        0, -1)

        if self.mask is not None:
            mask[(height0 - h0) : (height1 - h0), (width0 - w0) : (width1 - w0)] = \
                mask[height0 : height1, width0 : width1]

        # 테두리 및 배경만 있는 이미지 체크
        hsv = cv2.cvtColor(img, cv2.COLOR_BGR2HSV)
        h, s, v = cv2.split(hsv)

        # 이미지 반환
        return img, mask, (-1 if (s > s_threshold).sum() <= pixel_threshold else idx)

이 데이터셋을 이용해 자른 이미지들을 저장해준다. 동시에 나중에 이 데이터를 학습에 사용할 때 전처리로 이미지 정규화를 해줄수 있기 때문에 전체 이미지의 채널 별 평균과 표준편차도 구해둔다.

import zipfile
import pandas as pd
from tqdm.auto import tqdm

TRAIN_CROPPED = 'train.zip'
MASK_CROPPED = 'masks.zip'
df_masks = pd.read_csv('/path/to/train.csv', index_col='id)

x_sum, x_ssum = [], []
with zipfile.ZipFile(TRAIN_CROPPED, 'w') as img_cropped, \
     zipfile.ZipFile(MASK_CROPPED, 'w') as mask_cropped:
    for index, encs in tqdm(df_masks.iterrows(), total=len(df_masks)):
        dataset = FTUDataset(index, encs=encs)
        for i in range(len(dataset)):
            img, msk, idx = dataset[i]
            if idx < 0: # 검은 테두리거 흰 배경일 경우
                continue

            x_sum.append((img/255.).reshape(-1, 3).mean(0))
            x_ssum.append(((img/255.)**2).reshape(-1, 3).mean(0))

            img = cv2.imencode('.png', cv2cvtColor(img, cv2.COLOR_RGB2BGR))[1]
            img_cropped.writestr(f'{index}_{idx:04d}.png', img)

            mask = cv2.imencode('.png', m)[1]
            mask_cropped.writestr(f'{index}_{idx:04d}.png', mask)

img_mean = np.array(x_sum).mean(0)
img_std = np.sqrt(np.array(x_ssum).mean(0) - img_mean**2)

실행하면 이 코드가 저장된 위치에 train.zip과 masks.zip이 저장되어있다.

참고: @Iafoss

여기에 있는 강의를 바탕으로 구현했다.

N, M, K = map(int, input().split())
arr = [int(input()) for _ in range(N)]
changes = [list(map(int, input().split())) for _ in range(M+K)]

## 세그먼트 트리 리스트 초기화
# 주어진 리스트의 길이보다 긴 2의 거듭제곱 길이만큼 리스트 생성
length = 0
while 2**length < N:
    length += 1
length = 2**length

# 곱을 저장하므로 1로 초기화
seg_tr = [1 for _ in range(length*2)]

# 전체 길이의 절반 위치부터 입력 값들을 새 리스트에 저장
for idx in range(N):
    seg_tr[length + idx] = arr[idx]

# 범위를 줄여가면서 같은 부모 노드를 가지는 두 자식 노드로 부모 노드 업데이트
rng = length
while rng > 1:
    # 길이가 16이라면 8번째 인덱스와 9번째 인덱스의 곱이 4번째 인덱스로,
    # 길이를 절반으로 줄이고 다시 반복해서 1번 인덱스까지 반복한다
    for idx in range(rng//2, rng):
        seg_tr[idx] = (seg_tr[idx*2] * seg_tr[idx*2 + 1]) % 1_000_000_007
    rng //= 2


for a, b, c in changes:
    rng = length

     # 배열의 수를 바꾸는 경우
    if a == 1:
        # 세그먼트 트리에 맞는 범위로 인덱스 수정
        b = rng + b - 1
        # 해당하는 인덱스 값 수정
        seg_tr[b] = c

        while b > 1:
            # 처음 세그먼트 트리를 초기화 할 때처럼 부모 노드 업데이트
            # 바뀐 노드의 부모 노드들만 바꿔주면 된ㅏ
            if b%2 == 0:
                seg_tr[b//2] = (seg_tr[b] * seg_tr[b+1]) % 1_000_000_007
            else:
                seg_tr[b//2] = (seg_tr[b] * seg_tr[b-1]) % 1_000_000_007
            b //= 2

    # 출력하는 경우
    if a == 2:
        ans = 1

        # 범위 수정
        b = rng + b - 1
        c = rng + c - 1

        # 시작 노드가 끝나는 노드와 같거나 작을 동안
        while b <= c:
            # 시작 노드의 부모노드가 포함되지 않고 현재 노드만 포함된다면
            if b%2 == 1:
                # 바로 적용
                ans *= (seg_tr[b] % 1_000_000_007)
            # 부모 노드가 포함되는 된다면 바로 부모 노드로, 
            # 포함되지 않는다면 인덱스가 더 큰 오른쪽 노드의 부모 노드로 가하므로
            # 1을 더하고 부모 노드로 이동
            b = (b+1) // 2

            # 끝 노드에도 마찬가지로 적용하지만,
            # 끝 노드는 시작 노드와 반대 방향으로 이동하므로 부모노드가 포함되지 않는다면
            # 1을 빼주고 부모 노드로 이동
            if c%2 == 0:
                ans *= (seg_tr[c] % 1_000_000_007)
            c = (c-1) // 2

        print(ans % 1_000_000_007)

여기에 있는 강의 내용을 바탕으로 구현해봤다.

from collections import deque

N = int(input())
edges = [list(map(int, input().split())) for _ in range(N-1)]
M = int(input())
pairs = [list(map(int, input().split())) for _ in range(M)]

# 간선들을 인접 리스트로 표현
graph = [[] for _ in range(N+1)]
for i, j in edges:
    graph[i].append(j)
    graph[j].append(i)


# 너비 우선 탐색으로 노드들의 깊이와 부모 노드 탐색
def bfs():
    q = deque([1])
    parent = [-1 for _ in range(N+1)]
    parent[1] = 0
    depth = [-1 for _ in range(N+1)]
    depth[1] = 0

    while q:
        node = q.popleft()
        for next_node in graph[node]:
            if parent[next_node] == -1:
                parent[next_node] = node
                depth[next_node] = depth[node] + 1
                q.append(next_node)

    return parent, depth

# 너비 우선 탐색에서 얻은 정보로 2**k 단계씩 올라가며 부모 노드를 찾는 dp 함수
def dp(d):
    for k in range(1, K+1):
        for i in range(1, N+1):
            if d[k-1][i] == -1:
                d[k][i] = -1
            else:
                d[k][i] = d[k-1][d[k-1][i]]
    return d


parent, depth = bfs()
K = 0
while 2**K < max(depth):
    K += 1
    if 2**K > max(depth):
        K -= 1
        break

dp_parent = [[-1 for _ in range(N+1)] for _ in range(K+1)]
dp_parent[0] = parent

dp_depth = [[-1 for _ in range(N+1)] for _ in range(K+1)]
dp_depth[0] = depth

dp_parent = dp(dp_parent)
dp_depth = dp(dp_depth)


for i, j in pairs:
    # 깊이가 더 깊은 노드가 트리의 리프에 더 가깝다 -> low
    if dp_depth[0][i] > dp_depth[0][j]:
        high, low = j, i
    else:
        high, low = i, j

    # 낮은 위치(리프에 가까운) 노드를 루트에 가까운 노드와 깊이를 맞춰준다.
    k = K # 2**k가 트리의 전체 높이보다 커질 수 없으므로 높이보다 낮은 가장 큰 2의 거듭제곱 수터
    # 아래의 노드의 깊이가 더 깊다면
    while dp_depth[0][high] < dp_depth[0][low]:
        # 아래 노드의 깊이에서 2**k 만큼 올라갔을 때 위 노드보다 높아진다면
        if dp_depth[0][low] - 2**k < dp_depth[0][high]:
            # k-1을 해줘서 더 위 노드보다 낮은 깊이가 되도록 k 감소
            k -= 1
        else:
            # 위 노드보다 높이가 낮거나 같다면 아래 노드를 2**k 단계 위의 노드로 변경
            low = dp_parent[k][low]

    # 공통 노드 찾기
    k = K
    # k가 0이 될 때까지
    while k >= 0:
        # 둘의 노드가 같다면 -> 최소가 아닌 공통 조상일 경우도 있다
        if dp_parent[k][high] == dp_parent[k][low]:
            # 같은 노드를 가르키지 않을 때까지 k 감소
            k -= 1
        else:
            # 서로 다른 노드를 가르킨다면 각 노드를 부모 노드로 업데이트
            high = dp_parent[k][high]
            low = dp_parent[k][low]

    # k=0일 때는 부모 노드가 같은 노드를 가르킬 경우와 현재 노드가 같은 노드일 경우이다
    if high == low:
        print(high)
    else:
        print(dp_parent[0][high])

RLE는 위 그림처럼 같은 값이 연속으로 나타나는 데이터를 연속된 수와 해당 값으로 인코딩하는 방법이다. 두 번째 열에 1111001111로 되어있는 부분은 1이 4번, 0이 2번, 다시 1이 4번 나타난다. 그래서 아래 410214로 표현이 된다.

캐글에 있는 segmentation 문제에 있는 데이터는 위와 비슷하지만 약간 다르게 표현되어있다. 이 표에서는 2차원 배열로 나타낼 수 있는 이미지(레이블이 하나일 경우)를 1차원 배열로 바꾼 뒤 레이블에 해당하는 픽셀이 얼마나 연속되는지를 나타낸다. 첫 번째 줄을 보면 1차원 배열로 바꿨을 때 296084587 번째에 해당하는 인덱스부터 연속된 4개의 픽셀이 레이블에 해당한다는 뜻이다.(296084587~296084560)

모델 학습을 위해서는 RLE로 인코딩 된 값을 입력 이미지와 같은 크기의 2차원으로 펼쳐야한다. shape = (height, width) 라면

import numpy as np
img = np.zeros(shape[0]*shape[1], dtype=np.uint8)

인코딩 된 값들은 [시작 위치, 길이, 시작위치, 길이]가 띄어쓰기로 구분되어 있으므로 .split()으로 나눠준다. 나눠진 리스트는 짝수 번째 인덱스(0, 2, 4, ...)에 시작 지점, 홀수 번째 인덱스(1, 3, 5, ...)에 길이가 담겨있다. 파이썬 코드로 나타내면

s = enc.split()
    for i in range(len(s)//2):
        start = int(s[2*i]) - 1
        length = int(s[2*i+1])
        img[start : start+length] = 1

이런 식으로 길이만큼을 연속된 1로 표현할 수 있다. 시작 지점에 1을 빼주는것은 인코딩 된 값은 1부터 시작하는데 배열은 인덱스가 0부터 시작해서 맞춰주기 위함이다.

전체 코드를 나타내면 아래와 같다.

def enc2mask(enc, shape):
    # 1차원 배열 초기화
    img = np.zeros(shape[0]*shape[1], dtype=np.uint8)

    s = enc.split()
    for i in range(len(s)//2):
        # 짝수 번째에는 시작 위치
        start = int(s[2*i]) - 1
        # 홀수 번째에는 길이
        length = int(s[2*i+1])
        # 시작 위치부터 시작위치 + 길이까지 1로 표시
        img[start : start+length] = 1
    # 입력 이미지와 같은 크기로 재배열
    return img.reshape(shape)

주의해야 하는 점은 RLE가 행 방향으로 표현되어있다면 그대로 쓰면 되지만(제일 처음 그림처럼 가로로 연속된게 몇 개인지), 열 방향으로 표현되어 있다면 함수에 입력되는 shape인자의 순서를 바꿔주고 반환하는 2차원 배열도 transpose 시켜줘야 한다. 그리고 위는 해당 픽셀이 레이블인지 아닌지 구별하는 이중 분류지만, 레이블이 여러개라면 enumerate를 이용한 이중 반복문으로 작성하면 된다. 이때는 배열에 레이블을 적을 때 1이 아닌 구별되는 값을 입력해준다.

이렇게 해서 학습을 하고 예측을 하고 나면 결과값을 다시 RLE로 압축해서 제출해야한다. 앞에와 반대로 레이블이 표시된 2차원 배열을 펼쳐준다. mask 배열에 저장되어있다면

import numpy as np
pixels = mask.T.flatten().astype(np.uint8)

로 바꿔준다. 다음으로 1이 얼마나 연속되는지 찾아야한다. 0과 1로 된 배열이 있을 때, 배열 값들을 한 칸씩 shift 시킨 배열을 새로 만들어서 이전 배열과 비교한다면 언제 값이 바뀌는지 알 수 있다.

예를 들어 [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0]과 같은 배열이 있다면

가 되고, 일치하지 않는 인덱스만 가져오게 되면 2, 8, 9, 14, 15, 16이다. 그렇다면 이 인덱스와 다음 인덱스까지는 같은 값을 가진다는 뜻이고, 인덱스의 차이가 그 값이 연속된 횟수가 된다. 이 방법으로 연속하는 1이 시작하는 위치와 길이를 구할 수 있다. 항상 0에서 1로 바뀌는 경우를 구하기 위해 주어진 배열 앞에 [0]을 추가하고, shift를 시킬수 있도록 마지막에도 [0]을 추가해준다.

p = np.concatenate([[0], pixels, [0]])

원본 배열과 shift한 배열의 차이로 레이블이 시작되고 끝나는 지점을 찾는다.

runs = np.where(p[1:] != p[:-1])[0] + 1

np.where은 참일 경우와 거짓일 경우에 적용할 값을 쓰지 않는다면 참일 때 인덱스를 반환한다. 앞에 [0]을 추가했으므로 원본에 해당하는 p[1:]과 shift한 배열 p[:-1]이 일치 하지 않는 경우의 인덱스를 받아온다. RLE는 1부터 시작하므로 1을 더해준다. 배열의 시작이 0이므로 np.where로 구한 첫 인덱스는 원본 배열에서 처음으로 0에서 1로 바뀐 경우이다. 위 코드로 구한 runs는 짝수 번째(0, 2, ...)에는 0에서 1로 바뀐 경우, 홀수 번째(1, 3, ...)에는 1에서 0으로 바뀐 경우가 저장된다. 따라서 연속된 값의 길이는 1에서 0으로 바뀌었을때에 0에서 1로 됐을 때 인덱스를 빼주면 된다.

전체 코드로 나타내면 다음과 같다.

def mask2enc(mask):
    # 마스킹된 2차원 배열 1차원 배열로
    pixels = mask.T.flatten().astype(np.uint8)
    # 앞 뒤로 [0] 추가
    p = np.concatenate([[0], pixels, [0]])
    # 값이 변하는 인덱스 찾기
    runs = np.where(p[1:] != p[:-1])[0] + 1
    # 1에서 0으로 바뀐 인덱스에서 0에서 1로 바뀐 인덱스 차이가 연속된 숫자의 길이
    # 짝수 번째에 시작 지점, 홀수 번째에 길이가 저장된다
    runs[1::2] -= runs[::2]
    return ' '.join(str(x) for x in runs)

먼저 집이나 사무실을 우선 정렬한다. 끝 지점이 가장 낮은값부터 시작해 순차적으로 탐색할 수 있도록 끝 지점을 기준으로 정렬한다. 같은 지점에서 끝나는 경우 출발지점이 더 앞쪽인 기준으로 정렬한다.

# 13334 철로
import heapq

N = int(input())
h_o = [sorted(list(map(int, input().split()))) for _ in range(N)]
h_o.sort(key=lambda x: [x[1], x[0]])
D = int(input())


pq = []
max_size = 0

for i in range(N):
    start, end = h_o[i]
    # 현재 선분의 길이가 선로의 길이보다 짧다면
    if end - start <= D:
        # 현재 선로의 끝지점에서 가장 멀리 있는 출발점부터 제거하기 위해 출발 지점을 힙에 저장
        heapq.heappush(pq, start)
    else:
        continue

    # 모든 출발 지점이 선로 내부에 있을 때까지
    while pq: 
        # 가장 멀리 있는 출발 지점이
        temp = heapq.heappop(pq)
        # 선로 내에 있을 경우
        if end - temp <= D:
            # 다시 힙에 저장하고 while문 종료
            heapq.heappush(pq, temp)
            break
    # 선로 내에 있는 선분의 수는 힙의 수와 같다 (선로는 끝지점을 기준으로 출발점과 비교했기 때문)
    max_size = max(max_size, len(pq))

print(max_size)

[행]에서 출발해 [열]로 가는 방법을 그래프로 나타낸 후 푼다

예시로 경로가 0에서 1, 1에서 0밖에 없다고 하면 $$ A = \begin{pmatrix} 0\rightarrow0 & 0\rightarrow1\ 1\rightarrow0 & 1\rightarrow1\ \end{pmatrix} $$

두번 이동한다면 $$ A \cdot A = \begin{pmatrix} (0\rightarrow0) \cdot (0\rightarrow0) + (0\rightarrow1)\cdot(1\rightarrow0) & (0\rightarrow0) \cdot (0\rightarrow1) + (0\rightarrow1)\cdot(1\rightarrow1)\ (1\rightarrow0) \cdot (0\rightarrow0) + (1\rightarrow1)\cdot(1\rightarrow0) & (1\rightarrow0) \cdot (0\rightarrow1) + (1\rightarrow1)\cdot(1\rightarrow1)\ \end{pmatrix} $$

따라서 같은 시작 노드에서 도착 노드까지 가는 방법의 수는 이동하는 횟수만큼 행렬을 곱하고 그에 해당하는 행과 열의 값을 선택하면 된다.

def matrix_mul(A, B):
    ans = [[0 for _ in range(len(A))] for _ in range(len(B[0]))]
    for i in range(len(A)):
        for j in range(len(B[0])):
            temp = 0
            for k in range(len(B)):
                temp += A[i][k] * B[k][j]
            ans[i][j] = temp % 1_000_000_007
    return ans

def divide_conquer(A, n):
    if n == 1:
        return A

    else:
        x = divide_conquer(A, n//2)
        if n %2 == 0:
            return matrix_mul(x, x)
        else:
            return matrix_mul(A, matrix_mul(x, x))

edges = [
    [0, 1],
    [0, 2],
    [1, 2],
    [1, 3],
    [2, 3],
    [2, 4],
    [3, 4],
    [3, 5],
    [4, 5],
    [4, 7],
    [5, 6],
    [6, 7],
]
graph = [[0 for _ in range(8)] for _ in range(8)]
for i, j in edges:
    graph[i][j] = graph[j][i] = 1

N = int(input())
print(divide_conquer(graph, N)[0][0])

건물의 모든 외부에서 입구가 생길 수 있으므로 전체 외곽을 방문 가능한 곳으로 추가해준다. 열쇠를 발견했다면 잠겨있는 곳으로 다시 가야하므로 방문 기록을 초기화시켜준다.

from collections import deque, Counter

T = int(input())
for _ in range(T):

    h, w = map(int, input().split())
    # 건물 외부에 접근 가능하도록
    building =  [['.'] + list(input()) + ['.'] for _ in range(h)]
    building =  [['.']*(w+2)] + building + [['.']*(w+2)]
    key_cnt = Counter(input())
    keys = {}
    for char in range(ord('a'), ord('z')+1):
        if key_cnt[chr(char)] != 0: # 가지고 있는 키 저장
            keys[chr(char)] = True
        else:
            keys[chr(char)] = False


    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    def bfs():
        q = deque([[0, 0]])
        visited = [[False for _ in range(w+2)] for _ in range(h+2)]
        visited[0][0] = True
        count = 0

        while q:
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if (0 <= nx < w+2 and 0 <= ny < h+2
                    # 방문한적이 없고 벽이 아니라면
                    and building[ny][nx] != '*'
                    and not visited[ny][nx]):

                    # 방문한 위치가 열쇠가 있는 곳이라면
                    if 'a' <= building[ny][nx] <= 'z':
                        # 열쇠가 없었을 경우
                        if not keys[building[ny][nx]]:
                            # 열쇠 추가
                            keys[building[ny][nx]] = True
                            # 방문 기록 초기화
                            visited = [[False for _ in range(w+2)] for _ in range(h+2)]

                    # 방문한 위치가 잠겨있다면
                    elif 'A' <= building[ny][nx] <= 'Z':
                        # 해당 키가 없을 경우
                        if not keys[building[ny][nx].lower()]:
                            continue # 다음 위치로

                    # 방문 위치에 문서가 있다면
                    elif building[ny][nx] == '$':
                        # 카운트, 중복되지 않도록 빈 공간으로
                        count += 1
                        building[ny][nx] = '.'

                    # 방문한 위치 추가
                    visited[ny][nx] = True
                    q.append([nx, ny])

        return count

    print(bfs())

https://st-lab.tistory.com/285

새로 들어오는 값이 현재 리스트의 마지막 값보다 크면 리스트 마지막에 추가해주면 된다. 더 작은 값이 들어오게 되면 현재 가지고 있는 리스트에서 이 값이 어디에 들어가야 할 지 정해줘야한다. 이 과정을 이분 탐색으로 구현하고, 들어갈 위치를 찾았다면 그 위치의 값을 더 작은 현재 들어온 값으로 바꿔준다. 길이만 구하면 되므로 이런식으로 중간의 값을 바꿔서 풀면 된다.

def bi_search(arr, x): # or import bisect
    start, end = 0, len(arr)
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] < x:
            start = mid + 1
        else:
            end = mid - 1
    return start

N = int(input())
A = list(map(int, input().split()))

lis = [0]
for i in range(N):
    if lis[-1] < A[i]: # 들어온 값이 더 크다면 
        lis.append(A[i]) # 바로 추가
    elif lis[-1] > A[i]: # 작다면
        idx = bi_search(lis, A[i]) # bisect.bisect_left(lis, A[i])
        lis[idx] = A[i] # 처음으로 더 리스트에서 더 큰 값이 나타나는 인덱스 찾은 후 교체

print(len(lis)-1)

도킹할 수 있는 가장 높은 번호의 게이트부터 비행기를 도킹시킨다. 해당 인덱스에 도킹을 시켰다면 다음에는 그 인덱스보다 1 적은 값에 도킹시켜야하므로 이 인덱스를 저장해주어야한다.

G = int(input())
P = int(input())
gates = [int(input()) for _ in range(P)]

parent = list(range(G+1)) # 도킹 예정 리스트
def find(p): # 도킹 가능한 게이트
    if p == parent[p]:
        return p
    else:
        parent[p] = find(parent[p]) # 경로 압축
        return parent[p]

count = 0
for g in gates:
    idx = find(g) # 비행기가 도킹하려는 게이트 찾기
    if idx < 1: # 가능한 게이트 없다면 
        break # 종료
    parent[idx] = idx - 1 # 있다면 도킹 후 이 게이트로 들어온다면 이전 인덱스로 가도록
    count += 1 # 도킹한 비행기 수 추가

print(count)

https://degurii.tistory.com/158 정리가 굉장히 잘 되있다. 이 글을 보고도 헷갈렸던 부분만 정리하면 처음 i 번째(i=3이라면 1000부터 1111까지) 자리까지 모두 더해주는 값은, 가장 높은 자리의 수 = $2^i$와 그 이하 자리에 있는 수의 합이다. 이전 자리의 수를 보면 그 앞자리, 아래 사진에서는 i=2 일 때, 모든 수와 동일해 두 번 더해주는 값이 된다. 그래서 i 번째 자리까지는

2 * dp[i-1] + 1 << i

가 된다. 다음으로 자리수까지 모든 합이 아닌 그 사이에 있는 값을 가져와야 하는 경우에는 i-1 번째 자리까지 모든 자리수까지 합 + i-1 번째 자리의 1의 개수 를 반복해서 더해주면 된다.

예를 들어 $14 = 1101_{(2)}$를 계산한다면

처럼 반복문으로 풀어 줄 수 있다.

max_len = len(bin(10**16)[2:])
dp = [0 for _ in range(max_len)]
dp[0] = 1
for i in range(max_len):
    dp[i] = 2 * dp[i-1] + (1<<i) # 초기값, i 번째 자리수까지 1의 합

def suffix_sum(x):
    ans = x & 1 # 0 번째 자리 수
    for i in range(max_len, 0, -1): # 가장 높은 자리 수 부터 
        if x & 1 << i: # x가 i 번째 자리에 값을 가지고 있다면
            ans += dp[i-1] + x - (1<<i) + 1 # 1의 수 계산
            x -= 1<<i # 가장 높은 자리의 1의 수는 계산 되었으므로 제거
    return ans

A, B = map(int, input().split())
print(suffix_sum(B) - suffix_sum(A-1))

가능하면 쉬운 문제부터 풀되 먼저 풀어야하는 문제는 먼저 풀어야한다. 선행되어야 하는 작업이 있고, 쉬운 문제부터 풀어야 하므로 힙을 이용해 위상 정렬로 풀었다.

import heapq

N, M = map(int, input().split())
order = [list(map(int, input().split())) for _ in range(M)]

graph = [[] for _ in range(N+1)] # idx 위치에 문제를 풀어야 다음 문제를 풀 수 있음
in_order = [0 for _ in range(N+1)] # 진입 차수, idx 번째 문제를 풀기 위해 풀어야하는 문제 수
visited = [False for _ in range(N+1)] # 방문 여

for first, then in order:
    heapq.heappush(graph[first], then) # 쉬운 문제부터 다음에 풀 문제 추가
    in_order[then] += 1

ans = []
q = []
for i, val in enumerate(in_order[1:], 1):
    if val == 0: # 먼저 풀어야 할 문제가 존재하지 않는다면
        heapq.heappush(q, i) # 푼 문제에 추가
        visited[i] = True # 방문 처리, 같은 문제가 반복되서 들어와 진입 차수가 감소되는 것 방지

while q:
    v = heapq.heappop(q) # 쉬운 문제부터
    ans.append(v) # 푼 문제에 추가
    for _ in range(len(graph[v])): # 다음에 풀 수 있는 문제 개수 동안
        next_v = heapq.heappop(graph[v]) # 다음으로 쉬운 문제
        if not visited[next_v] or in_order[next_v] >= 1: # 처음 본 문제거나 먼저 풀어야 할 문제가 있다면
            visited[next_v] = True # 방문 표시
            in_order[next_v] -= 1 # 먼저 풀어야할 문제 하나 해결
            if in_order[next_v] == 0: # 모두 풀었다면
                heapq.heappush(q, next_v) # 푼 문제에 추가
print(*ans)

가방에는 하나의 보석밖에 들어갈 수 없어 그리디로도 풀 수 있다. 가방에는 가방이 버틸수 있는 무게의 보석 중 가치가 가장 높은 것부터 들어가야한다. 먼저 가방을 오름차순으로, 보석은 무게를 기준으로 오름차순으로 정렬한다. 가능한 무게가 작은 가방부터 정렬을 해야 나중에 무거운 보석이 있을 때 큰 가방에 들어가도록 할 수 있다. 가능한 보석 중 가치가 가장 높은 보석을 가져와야 하므로 힙을 사용한다. 보석이 가방에 들어갈 수 있다면 모두 힙에 추가해주었다가 가장 가치가 높은 보석을 빼면서 최종 리스트에 추가해주면 된다.

# 1202 / 보석 도둑
import heapq

N, K = map(int, input().split())
gems = [list(map(int, input().split())) for _ in range(N)]
bags = [int(input()) for _ in range(K)]

bags.sort() 
gems.sort(key=lambda x: x[0]) # 무게 순 정렬

i = 0
total_val = 0
heap = []

for bag in bags:
    while i < N and gems[i][0] <= bag: # 현재 가방의 수용 가능 무게보다 가볍다면
        heapq.heappush(heap, -gems[i][1]) # 힙에 모두 추가
        i += 1
    if heap: # 힙에 보석이 들어있다면
        total_val -= heapq.heappop(heap, -gems[i][1]) # 가장 가치가 높은 보석 하나 추가

print(total_val)

출처: OnlineMathLearning 점 A와 점 B를 잇는 벡터를 $\overrightarrow{AB}$라 한다면 이를 $\overrightarrow{OB} - \overrightarrow{OA}$ (O는 원점)으로 표현할 수 있다. 그렇다면 주어진 점들로 만든 벡터도 원점에서 출발하는 벡터로 바꿔줄 수 있고,

$$\displaystyle\sum_{i=0}^{N/2}\overrightarrow{OB_i} - \overrightarrow{OA_i}$$

를 계산하는 문제로 바꿀 수 있다. 모든 점 중 절반은 더하고 절반은 빼서 최종 벡터의 길이를 구하면 된다.

import math
from itertools import combinations

T = int(input())
results = []
for _ in range(T):

    N = int(input())
    coords = [list(map(int, input().split())) for _ in range(N)]

    # 모든 벡터들의 합
    coords_total_sum = list(map(sum, zip(*coords)))
    min_distance = 10**12

    for idx in combinations(range(N), r=N//2):
        # 더해줄 벡터들의 합
        sums = list(map(sum, zip(*[coords[i] for i in idx])))
        # 모든 벡터들의 합에서 더해줄 벡터들을 빼면 빼줄 벡터들의 합만 남는다.
        subs = [coords_total_sum[0] - sums[0], coords_total_sum[1] - sums[1]]

        # 최종 벡터 계산
        fin_coords = [sums[0]-subs[0], sums[1]-subs[1]]
        # 거리 계산
        min_distance = min(min_distance, 
                        math.sqrt(fin_coords[0]**2 + fin_coords[1]**2))

        if min_distance == 0:
            break
    results.append(min_distance)    

print(*results, sep='\n')

로지스틱 회귀를 구현하기 위한 코드도 선형 회귀 코드와 거의 유사하다. 예측하는 부분에서 sigmoid 함수를 적용해주는 정도의 차이이다.

class LogisticRegression:

    def __init__(self, lr=0.001, n_iters=1000):
        self.lr = lr
        self.n_iters = n_iters
        self.weights = None
        self.bias = None

    def fit(self, X, y):
        # init parameters
        n_samples, n_features = X.shape
        self.weights = np.zeros(n_features)
        self.bias = 0

        # gradient descent
        for i in range(self.n_iters):
            y_pred = self._sigmoid(self._linear(X))

            cost = - (1 / n_samples) * np.sum(y*np.log(y_pred) + (1-y)*np.log(1-y_pred))

            dw = (1 / n_samples) * np.dot(X.T, (y_pred - y))
            db = (1 / n_samples) * sum(y_pred - y)

            self.weights -= self.lr * dw
            self.bias -= self.lr * db
            if i%100 == 99:
                print(f"{i+1}th iteration | Cost: {cost:.6g}")

    def predict(self, X):
        y_prob = self._sigmoid(self._linear(X))
        y_pred = np.where(y_prob > 0.5, 1, 0)
        return y_pred

    def _sigmoid(self, x):
        return 1 / (1 + np.exp(-x))

    def _linear(self, X):
        return np.dot(X, self.weights) + self.bias

선형 회귀 모델에서는 평균 제곱 오차를 사용했었다면 로지스틱 회귀에서는 오차를 계산하기 위한 손실 함수로 크로스 엔트로피(Cross entropy)를 사용한다.

아래 그래프와 함께 보면 타겟이 1일 경우 예측값이 1에 가까울수록 손실이 줄어들고, 0에 가까울수록 손실이 급격하게 커진다. 타겟이 0일 경우에는 반대로 나타나 결국 두 클래스를 제대로 맞출 경우에 손실이 줄어들게 된다.

$$ BCELoss = -\frac{1}{N}\sum^{N}_{i=0} y_i \cdot \log(\hat{y_i}) + (1-y_i) \cdot \log(1-\hat{y_i}) $$

$y$는 클래스, $\hat{y}$는 해당 클래스일 확률이다.

더 자세한 설명

위에서 만든 로지스틱 회귀를 사용해 1차원 데이터로 예측을 해보면

선형 회귀가 데이터를 한 평면으로 예측하는 것처럼 로지스틱 회귀는 한 평면을 기준으로 레이블을 나누게 된다. 여기서는 0.5를 기준으로 데이터가 0 또는 1로 예측된 것을 볼 수 있다.

2차원 데이터를 보면 더 확실하게 보인다.

가운데 레이블을 나누는 선을 기준으로 위는 모두 0, 아래는 모두 1로 예측한 것을 볼 수 있다.

다중 레이블의 경우에는 각각의 레이블마다 하나의 레이블과 다른 모두 레이블 (OVR, one versus rest)로 나눠, 이진 분류 문제로 바꿔서 예측하게 된다.

sklearn을 사용할 경우에는 아래처럼 해주면 된다. sklearn의 로지스틱 회귀를 이용할 경우에는 모델 객체를 만들 때 multi_class에 ovr 또는 multinomial을 넘겨줄 수 있는데. ovr 경우에는 위처럼 이진 분류로, multinomial은 전체 레이블로 오차를 계산한다(Cross Entropy). 기본값으로 다중레이블 분류를 진행하기 때문에 상관없다면 넘겨주지 않아도 된다. 위에 있는 BCE 손실을 여러 클래스로 확장한다면,

$$ CE = -\sum{y_i \cdot \log{\hat{y_i}}} $$

$y_i$는 i 번째 클래스, $\hat{y_i}$는 $y_i$ 클래스일 확률이다.

sklearn을 사용할 경우

from sklearn.linear_model import LogisticRegression

lgr = LogisticRegression()
lgr.fit(X_train, y_train)
y_preds = lgr.predict(X_test)

# 확률 반환
y_pred_probs = lgr.predict_proba(X_test)

전체 코드: github

벽 끝으로 간다면 알아서 멈추겠지만 방향 지도에서 루프가 생겨버리면 멈추지 못하고 계속 돌게 된다. 만들어진 루프마다 safe zone을 만들어 준다. 사이클을 찾는 다른 문제인 백준 9466 텀 프로젝트와 같은 방법으로 푼다.

N, M = map(int, input().split())
maps = [list(input()) for _ in range(N)]

visited = [[0 for _ in range(M)] for _ in range(N)]
safe_zone = 0

def dfs(x, y):
    global safe_zone

    # 현재 위치 방문처리
    visited[y][x] = True
    # 사이클에 현재 위치 추가
    cycle.append([x, y])

    if maps[y][x] == 'U' and y > 0: # 위로
        y -= 1
    elif maps[y][x] == 'D' and y < N-1: # 아래
        y += 1
    elif maps[y][x] == 'L' and x > 0: # 왼쪽
        x -= 1
    elif maps[y][x] == 'R' and x < M-1: # 오른쪽
        x += 1

    if visited[y][x]: # 이동한 위치를 이미 방문한 경우
        if [x, y] in cycle: # 사이클에 이 위치가 포함되어 있다면
            safe_zone += 1 # 사이클이 생겼으므로 세이프 존을 설치해야한다.
    else: # 방문안했으면 다음 위치로
        dfs(x, y)

for x in range(M):
    for y in range(N):
        if not visited[y][x]:
            cycle = []
            dfs(x, y)

print(safe_zone)

N = int(input())
mat_sizes = [[0, 0]] + [list(map(int, input().split())) for _ in range(N)]

INF = 10**12
# dp[시작 행렬 인덱스][마지막 행렬 인덱스] = 최소 곱셈 횟수
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(1, N): # 구간 설정, 마지막 행렬 인덱스 - 시작 행렬 인덱스
    for j in range(1, N-i+1): # 시작 인덱스, 시작 + 구간 <= 전체 행렬 길이
        dp[j][i+j] = INF
        for k in range(j, i+j): # 구간을 나누는 기준, 플로이드 워셜처럼 생각하면 된다
            # dp[j 번째 행렬][i+j 번째 행렬]의 곱셈 횟수 최솟값 = 시작 ~ k 번째 + k+1 번째 ~ 마지막 행렬 까지 곱셈 횟수 중 최솟값
            dp[j][i+j] = min(dp[j][i+j],
                             dp[j][k] + dp[k+1][i+j] + mat_sizes[j][0]*mat_sizes[k][1]*mat_sizes[i+j][1])

print(dp[1][N])

앞에 두 명처럼 지목한 사람들끼리 사이클을 형성하게 되면 같은 팀이 된다. 깊이 우선 탐색으로 부모 노드(지목한 사람)를 리스트에 추가하면서, 지목 당한 사람이 지목한 사람들 리스트에 포함 되어있다면 팀으로 만들어 준다.

T = int(input())
for _ in range(T):
    N = int(input())
    selected = [0] + list(map(int, input().split()))

    visited = [False] * (N+1)
    team_mems = 0

    def dfs(i):
        global team_mems

        visited[i] = True # 나부터
        team.append(i) # 팀 후보에 추가
        select = selected[i] # 다음 사람 지목

        if visited[select]: # 지목한 사람을 이미 방문했을 경우
            if select in team: # 그 사람이 팀 후보에 있다면
                # 그 사람부터 이후에 팀에 들어온 사람들은 한 팀이 된다
                team_mems += len(team[team.index(select):])
        else: # 아니라면 지목 받은 사람이 다른 사람 지목
            dfs(select)

    for i in range(1, N+1):
        if not visited[i]:
            team = []
            dfs(i)

    print(N - team_mems)

팀을 구성하는 부분

team_mems += len(team[team.index(select):])

은 위 예제로 본다면

1 → 3: 팀 [1, 3] 3 → 3: 팀 [3], 사이클에 해당하는 부분만 팀으로 만들어줘야 한다. 같은 번호가 처음으로 등장하는 사람이 가장 처음 팀의 멤버다.

2 → 1: 팀 [], 1번은 이미 다른 사람 지목해서 팀에 추가되지 않는다. 방문은 했으므로 dfs 함수의 첫 번째 조건문 중 참, 함수 종료 4 → 7: 팀 [4, 7] 7 → 6: 팀 [4, 7, 6] 6 → 4: 팀 [4, 7, 6]

따라 [3], [4, 7, 6] 두 팀만 생기고 다른 1, 2, 5번은 팀이 정해지지 않는다.

배낭 문제 강의

앱마다 사용하는 메모리와 비활성화 했을 때 비용의 효율이 다 다르고, 메모리를 분할시킬순 없으니 01배낭 문제 방식으로 접근하면 된다.

N, M = map(int, input().split())
apps = list(map(int, input().split()))
deact = list(map(int, input().split()))

# dp[비용][메모리]
dp = [[0 for _ in range(10000+1)] for _ in range(N+1)]
for i in range(1, N+1): # i 개의 앱 비활성화
    for w in range(10000+1): # 사용 가능한 비활성화에 필요한 비용
        if deact[i-1] <= w: # i-1 개의(리스트 시작 인덱스 = 1) 앱을 비활성화 시킬 수 있다면 
            # i개 비활성화로 확보된 메모리 = i-1 개 비활성화 + i-1 번 째 앱 메모리 (i-1 번째 비활성화)
            #                             i-1 번째 비활성화 X 중 최댓값
            dp[i][w] = max(apps[i-1] + dp[i-1][w-deact[i-1]], dp[i-1][w])
        else: # 비활성화 불가
            dp[i][w] = dp[i-1][w]

for i, c in enumerate(dp[-1]): # 
    if c >= M: # 처음으로 필요한 메모리보다 확보된 양이 많아진다면 출력
        print(i)
        break

$\hat{y} = wx + b \qquad···①$

로 값을 예측하게 된다. $\hat{y}$는 예측 값, $x$는 데이터의 특성이다. $w$(가중치)와 $b$(편향)는 모델에 훈련 데이터를 학습시키면서 업데이트 되는 값이다. 이 모델의 최종 목표는 위 식을 통해 예측한 $\hat{y}$과 실제 값 $y$의 오차를 최소화 시키는 가중치와 편향 값을 찾는 것이다.

모델의 파라미터(가중치, 편향)은 오차로부터 업데이트 된다. 아래 그림처럼 오차는 가중치, 편향, 오차, 3차원의 형태로 나타난다고 볼 수 있다. 오차가 낮을 수록 모델의 성능이 좋기 때문에 가중치와 편향은 오차가 낮아지는 방향으로 업데이트 된다.

아래로 내려가도록 하는 방법은 파라미터들에 대한 오차의 변화율을 구해서 그 반대 방향으로 모델 파라미터들을 업데이트 시켜주면 된다. 한 번 업데이트 할 때 변화율의 얼마만큼을 사용할지 learning rate(lr)를 정해줘서 학습 속도를 조절해 줄 수 있다. 학습률을 너무 높게 잡을 경우에는 최적값에 도달하지 못하고, 너무 낮게 잡았을 경우에는 최적값에 도달하기 전에 학습이 종료될 수도 있어서 적절한 값을 선택해야한다.

← 학습률이 너무 큰 경우        학습률이 너무 작은 경우→

오차를 평균 제곱 오차(MSE)로 계산한다면 $MSE=J(w, b)=\displaystyle\frac{1}{N}\sum{(y_i - (wx_i+b))^2}\qquad\qquad,,···②$

$J'(w, b) = \begin{bmatrix}\frac{dJ}{dw}\ \frac{dJ}{db}\end{bmatrix}
=\begin{bmatrix}\frac{1}{N}\sum-2x_i(y_i-(wx_i+b))\ \frac{1}{N}\sum-2(y_i-(wx_i+b))\end{bmatrix}\qquad···③$

코드로 구현할 때는 numpy의 dot을 써주면 된다. 위 식으로 변화량을 구한 후 파라미터들을 업데이트 해준다.

$w\leftarrow w-\mu\frac{dJ}{dw}$ $b\leftarrow b-\mu\frac{dJ}{db}$

class LinearRegression:

    # 초기값 설정
    def __init__(self, lr=0.001, n_iters=1000):
        self.lr = lr # 학습률
        self.n_iters = n_iters # 반복 횟수
        self.weights = None # 가중치
        self.bias = None # 편향

    def fit(self, X, y):
        # 학습 파라미터 초기화
        n_samples, n_features = X.shape # [데이터 수, 특성 수]
        self.weights = np.zeros(n_features) # 가중치 초기화
        self.bias = 0 # 편향 초기화

        for _ in range(self.n_iters):
            y_predicted = np.dot(X, self.weights) + self.bias # 예측, 1번 식에 해당한다.
            # 각 파라미터에 대한 오차 변화율 계산. 3번 식에 해당한다.
            dw = (1/n_samples) * np.dot(X.T, (y_predicted - y)) 
            db = (1/n_samples) * np.sum(y_predicted - y)

            # 파라미터 업데이트
            self.weights -= self.lr * dw
            self.bias -= self.lr * db

    def predict(self, X):
          # fit 메서드와 같은 방법으로 예측한다.
        y_predicted = np.dot(X, self.weights) + self.bias
        return y_predicted

# 오차로는 평균 제곱 오차를 사용했다.
def mse(y_true, y_pred):
    return np.mean((y_true-y_pred)**2)

이 데이터를 사용했을 때

처럼 예측하게 된다.

데이터의 특성이 1개가 아니라 N개의 경우에는 데이터를 가장 잘 표현하는 N차원 평면으로 예측을 하게 된다.

전체 코드: github

모든 별들을 이어주는데 필요한 비용의 최솟값을 출력해야한다. 최소 비용을 출력하므로 최소 스패닝 트리를 구하면 된다. 최소가 되려면 모든 노드를 포함하지만 두 노드 사이에는 하나의, 가장 비용이 적은 간선만 있도록 하면 된다. (최소 스패닝 트리 문제는 에지 리스트와 유니온 파인드로 해결한다.) 노드 사이의 비용은 유클리디안 거리로 반복문으로 구해주면 된다.

from decimal import Decimal

def find(p): # 부모 노드 찾기
    if p == parent[p]:
        return p
    else: 
        return find(parent[p])

def union(p, q): # 부모 노드가 다르다면 두 노드 병합, 부모 노드는 가장 작은 값으로
    p = find(p)
    q = find(q)
    assert p != q

    if p < q:
        parent[q] = p
    else:
        parent[p] = q

N = int(input())
coords = [list(map(Decimal, input().split())) for _ in range(N)]

# 두 별 사이의 유클리디안 거리를 구하고 이 세 값으로 에지 리스트를 만들어준다
edges = []
for i in range(N):
    for j in range(i+1, N):
        dist = ((coords[i][0] - coords[j][0])**2 
                + (coords[i][1] - coords[j][1])**2) ** Decimal('0.5')
        edges.append([i, j, dist])

# 가장 비용이 낮은 간선부터 비교해야하므로 비용 순으로 정렬해준다.
edges.sort(key=lambda x: x[2], reverse=True)

parent = list(range(N)) # 부모 노드 초기화, 초기값은 각 노드의 번호
edge_count = 0
cost = 0

# 최소가 되려면 간선이 (노드 수 - 1) 개만 있어야한다.
while edge_count < N-1:
    curr = edges.pop() # 가장 낮은 비용의 별과 비용 pop
    if find(curr[0]) != find(curr[1]): # 두 별이 아직 연결되지 않았다면
        union(curr[0], curr[1]) # 연결
        cost += curr[2] # 전체 비용에 추가
        edge_count += 1 # 간선 1회 추가

print(float(cost))