지금까지 공부했던 내용들을 정리한 문서입니다. 참고 서적을 정리한 내용도 있지만 제가 알고 있는 지식을 기반으로 정리한 내용도 있기 때문에 틀린 부분이 있을 수 있습니다. 혹시 발견하신다면 피드백 부탁드립니다 😁

또한 이 문서는 군집화와 군집화 알고리즘의 개념적인 부분을 다룹니다. 좀 더 심화된 이론이 필요하신 분은 다른 글을 참고해 주세요 😋

군집화(clustering)란, 데이터의 특성을 분석하여 유사한 속성을 갖는 데이터끼리 하나의 군집(cluster)으로 묶는 작업을 의미한다. 여기서 유사한 속성을 갖는 데이터란 특정 데이터 공간에서 비슷한 구역에 위치한 데이터 점들을 말한다. 기계학습 알고리즘 중 비지도 학습에 속하는 방법이며, 데이터 분석에서 군집화 기법을 이용하면 데이터가 굉장히 많아도 데이터의 특성을 파악하기 비교적 쉬워진다. 군집화 기법은 소프트 클러스터링과 하드 클러스터링으로 세분화될 수 있다.

군집화 예시

💡 소프트 클러스터링과 하드 클러스터링

• 소프트 클러스터링(soft clustering): 각 데이터가 여러 개의 군집에 속할 수 있는 방법
• 하드 클러스터링(hard clustering): 각 데이터가 오직 한 개의 군집에만 속할 수 있는 방법

✅ 거리 함수(Distance Function)

데이터 점들을 특징짓기 위해 군집화에서는 기본적으로 거리 함수(distance function)를 사용한다. 거리 함수는 말 그대로 두 원소 쌍(여기서는 데이터 샘플 간) 사이의 거리를 계산하는 함수로써, 군집화에서는 보통 그 값이 작으면 비슷한 속성(혹은 비슷한 공간에 위치)을 가지고 있다고 판단한다. 대표적인 거리 함수는 다음과 같으며, 일반적으로 유클리디언 거리가 많이 사용된다.

Fig A 출처, Fig B 출처

✅ 군집화 결과 평가 하기

군집화 알고리즘을 통해 만들어진 군집이 잘 만들어졌는지 평가하기 위한 척도가 존재한다. 여러 지표가 존재하지만 유명한 지표들은 다음과 같다.

💡 (참고) 군집화 평가 지표 수식

** 1. Dunn Index **

• $\delta(C_i, Cj)$: 군집 $i$와 $j$ 간의 거리
• $\triangle_k$: $k$번째 군집 내 거리

$$ DI_m = \frac{\underset{1\le i < j \le m}{\min}\delta(C_i, Cj)}{\underset{1\le k \le m}{\max}\triangle_k} $$

** 2. Silhouette 계수 **

• 자세한 계산 방법은 링크 참고 $$ SC = \underset{\kappa}{\max}\ \tilde{s}(\kappa) $$

군집화 알고리즘

1️⃣ K-평균 군집화 (K-means Clustering)

K-평균 군집화는 대표적인 군집화 알고리즘으로, 주어진 데이터 셋을 K개의 군집으로 나누는 작업을 수행한다. K-평균 군집화를 수행하기 위해서는 K값을 사람이 직접 설정해 주어야 한다. K-평균 군집화가 수행되는 과정은 다음과 같다.

💡 K-평균 군집화 프로세스

1. k개의 데이터 표본을 선택하여 군집 중심점(centroid)으로 정한다. (초기값 설정 과정) 2. 군집 중심점으로 선택된 데이터 표본을 제외한 다른 데이터들은, 군집 중심점과의 거리(distance)를 계산하여 가장 가까운 군집에 할당한다. 3. 모든 데이터의 군집이 결정되었다면, 할당된 데이터들을 기준으로 군집의 중심점을 다시 계산한다. (군집 중심은 클러스터 내 데이터들의 평균값으로 계산된다.) 4. 최적의 군집이 만들어질 때까지 2번과 3번이 반복적으로 수행된다. (군집 중심 변동이 거의 없을 때까지 수행)

그림출처

scikit-learn 라이브러리를 사용하여 Python3으로 구현하면 다음과 같다.

K-평균 군집화를 수행하기 전 초기 군집 중심점을 정할 때 사용하는 방법들이 존재한다. 여러 방법이 있지만 아래 예제에서는 k-means++ 방법을 사용하니 참고하자.

• k-means++: 초기에 무작위로 선택된 중심점을 기준으로 각 데이터 간의 거리를 계산하여 거리 비례 확률에 따라 다음 중심점을 정하는 방법, 처음에 선택된 중심점으로부터 최대한 먼 곳에 위치한 점을 선택하여 군집을 잘 나눌 수 있도록 함, k개가 될 때까지 반복

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from pandas import DataFrame
import numpy as np
import seaborn as sns
import matplotlib.pyplot as plt

# Generate data samples
np.random.seed(1)
data, _ = make_blobs(n_samples=1000, centers=5, cluster_std=0.8)

# Fit kmeans model
KMeans = KMeans(n_clusters=5, init="k-means++")
KMeans.fit(data)

# Label of each point
labels = KMeans.labels_ 
print('labels: ', labels) 

# Coordinates of cluster centers
centroids = KMeans.cluster_centers_ 
print('centroids: ', centroids)

# Make dataframe
df = DataFrame({'X':data[:,0], 'Y': data[:,1]})

# Visualize clustering result
plt.figure(figsize=(15, 10))
sns.scatterplot(x="X", y="Y", data=df, hue=labels, palette='coolwarm')
plt.scatter(centroids[:, 0], centroids[:, 1], c='red', alpha=0.5, s=150)

K-평균 군집화 결과

2️⃣ 계층적 군집화 (Hierarchical Clustering)

계층적 군집화란 트리 모형을 이용해 개별 개체들을 순차적, 계층적으로 유사한 개체 내지 그룹과 통합하여 군집화를 수행하는 알고리즘이다. K-평균 군집화(K-means Clustering)와 다르게 사전에 군집 수를 정해주지 않아도 학습이 가능하다. 계층적 군집화는 보통 덴드로그램(dendrogram)이라고 하는 그래프를 이용해 시각화 할 수 있으며, 일정 높이에서 덴드로그램을 자르는 방식으로 군집의 개수를 정한다. 계층적 군집화는 합병에 의한 방법(agglomerative)과 분할에 의한 방법(divise)으로 나눌 수 있다.

그림참고

✅ 합병에 의한 방법(Agglomerative methods)

💡 계층적 군집화 프로세스 - 합병

1. 1개의 개체를 가지는 n개의 군집을 생성한다. 2. 군집 간의 거리를 계산하여 가장 유사한 군집 쌍을 찾아 하나의 군집으로 묶는다. 3. 2를 반복하여 모든 데이터가 하나의 군집이 될 때까지 군집 합병을 수행한다.

합병에 의한 계층적 군집화 방법에서, 군집 간 거리를 계산하기 위해 사용되는 여러 가지 방법이 존재하며, 데이터에 따라 군집화가 잘 되는 방법을 선택하면 된다. 종류는 다음과 같다.

Scipy 라이브러리를 사용하여 Python3으로 구현하면 다음과 같다.

아래 예제는 Wholesale customers data 데이터를 사용하여 구현한 예제이므로, 사전에 다운로드가 필요합니다.

from scipy.cluster.hierarchy import linkage, dendrogram
from sklearn.preprocessing import normalize
import matplotlib.pyplot as plt
import pandas as pd

# dataset URL
# https://archive.ics.uci.edu/ml/machine-learning-databases/00292/Wholesale%20customers%20data.csv
data = pd.read_csv('Wholesale customers data.csv')

data_scaled = normalize(data)
data_scaled = pd.DataFrame(data_scaled, columns=data.columns)

linkage_list = ['single', 'complete', 'average', 'centroid', 'ward']

fig, axes = plt.subplots(nrows=3, ncols=2, figsize=(15, 10))
for i in range(len(linkage_list)):
    hierarchical = linkage(data_scaled, method=linkage_list[i])
    dn = dendrogram(hierarchical , ax=axes[i%3][i%2])
    axes[i%3][i%2].title.set_text(linkage_list[i])

plt.tight_layout()
plt.show()

합병에 의한 계층적 군집화 결과, 군집 거리 계산 방법 별 덴드로그램

✅ 분할에 의한 방법(Divisive methods)

합병에 의한 계층적 군집화 방법과는 반대로 하나의 군집에서 시작하며, 1개의 개체가 하나의 군집이 되는 순간까지 군집을 분할해 나가는 방식으로 군집화를 수행하는 방법이다.

💡 계층적 군집화 프로세스 - 분할

1. 모든 데이터가 속해 있는 하나의 군집에서 시작한다. 2. 군집을 가장 유사하지 않은 두 개의 군집으로 나눈다. 3. 2를 반복하여 각 데이터가 하나의 군집이 될 때까지 군집 분할을 수행한다.

(코드 구현 예정)

3️⃣ 밀도 기반 군집화 (DBSCAN)

밀도 기반 군집화(Density-based spatial clustering of application with noise)는 주어진 데이터의 밀도를 기반으로 군집화를 수행하는 알고리즘으로, 데이터 점 간 거리를 이용하여 클러스터링 하는 K-평균 군집화, 계층적 군집화와는 다르게, 데이터가 모여있는, 즉 밀도가 높은 부분을 찾아 군집화하는 방법이다.

밀도 기반 군집화의 과정에 앞서 학습 과정 이해를 위해 필요한 기본 하이퍼 파라미터와 주요 개념을 소개한다.

✅ 밀도 기반 군집화(DBSCAN) 기본 하이퍼 파라미터

이름	설명
엡실론 (epsilon)	어떤 한 점으로 부터의 거리
점 최소 개수 (min_samples)	어떤 점을 핵심 점(중심점)으로 간주하는 점들의 최소 개수

점 최소 개수(minpts)가 4개인 경우

✅ 밀도 기반 군집화(DBSCAN) 주요 개념

이름	설명
Core Point	epsilon 반경 내에 min_samples 이상의 데이터를 포함하는 군집의 중심점
Border Point	epsilon 반경 내에 min_samples 이상의 데이터를 포함하지 않지만, 해당 반경에 core point를 가지고 있는 점
Noise Point	epsilon 반경 내에 min_samples 이상의 데이터를 포함하지 않고, 해당 반경에 core point도 없는 점

그림참고

밀도 기반 군집화는 다음의 단계로 수행된다.

💡 밀도 기반 군집화 프로세스

1. 공간에서 임의의 점을 선택한다.
2. 앞 단계에서 선택한 임의의 점을 기준으로, epsilon 거리 범위 내에 있는 점의 개수를 센다.
   • 여기서 만약 점의 개수가 minpts-1 이상이면 해당 점을 core point로, 그렇지 않으면 noise point로 분류한다.
3. 앞 단계의 점이 core point가 되었다면, 해당 점을 기준으로 epsilon 범위 내에 있는 모든 데이터를 하나의 군집으로 지정한다.
   • 여기서 묶은 군집에 또 다른 core point가 속해 있다면, 그 점의 이웃 점들을 border point에 도달할 때까지 차례로 방문하여 군집에 포함시킨다.
4. 모든 데이터가 어떤 군집에 속하거나 혹은 noise point가 될 때까지 1-3을 반복한다.

scikit-learn 라이브러리를 사용하여 Python3으로 구현하면 다음과 같다.

from sklearn.datasets import make_blobs
from sklearn.cluster import DBSCAN
from pandas import DataFrame
import mglearn
import numpy as np

# Generate data samples
np.random.seed(1)
data, _ = make_blobs(n_samples=15, centers=3, cluster_std=0.8)

# Fit kmeans model
DBSCAN = DBSCAN(eps=3, min_samples=2)
DBSCAN.fit(data)

# Labels of each point
labels = DBSCAN.labels_ 
print('labels: ', labels) 

# Visualize clustering result
mglearn.plots.plot_dbscan()

DBSCAN 예제 결과

✅ DBSCAN 예제 결과 설명 core point는 크게, border point는 작게 표시되었으며, noise point는 흰색, 그 외에 군집에 속한 데이터 들은 색상이 칠해졌다. 해당 예시에서는 min_sample: 3, eps: 1.5가 데이터를 가장 잘 나눈 것으로 보인다.

4️⃣ 스펙트럼 군집화 (Spectral Clustering)

스펙트럼 군집화(Spectral Clustering)는 그래프 기반(graph-based) 군집화 기법으로, 데이터 간 절대적 거리를 기반으로 군집화를 수행하는 K-평균 군집화(K-means clustering), 계층적 군집화(Hierarchical clustering)와는 다르게, 데이터 간의 상대적 관계나 유사성을 고려하여 군집화를 수행한다.

💡 스펙트럼 군집화 프로세스

1. 주어진 데이터셋에서 데이터 점들 간의 관계를 정의한다.
   • 여기서 가중치는 데이터 간의 거리가 멀수록 커지고, 가까울수록 작아지도록 한다.
   • 보통 가우시안 커널을 사용하여 가중치를 정의한다.
2. 앞 단계에서 정의한(혹은 계산한) 값들을 바탕으로 인접 행렬(Adjacency matrix) 형태의 유사도 행렬(Affinity matrix)을 만든다.
   • 무방향 가중치 그래프(Undirected Weighted Graph) 형태로 볼 수 있다.
   • fully connected graph, k-nearest neighbor graph, ε-neighborhood graph 등 그래프를 만드는 여러 가지 방법들이 존재하며, 각 방법들이 가진 장단점이 다르므로 상황에 맞게 사용하도록 하자.
3. 만들어진 그래프에서 군집을 잘 나눌 수 있는 간선(edge)들을 선택하여 잘라낸다. (Fig C 참고)
   • 그래프를 자르는 방법으로 Minimum Cut이 보편적이며, 이 밖에도 Ratio cut, Normalized cut 등이 존재한다.
   • 그래프 컷은 각 방법에서 정의된 목적 함수(objective function)의 출력 값을 최소화하는 고유 벡터(eigenvector)를 찾아 이에 해당하는 가중치를 가진 간선들을 자르는 방식으로 수행된다.

Fig C. 그래프 컷 예시

scikit-learn 라이브러리를 사용하여 Python3으로 구현하면 다음과 같다.

from sklearn.datasets import make_circles
from sklearn.cluster import SpectralClustering, AgglomerativeClustering
import matplotlib.pyplot as plt

X, y = make_circles(n_samples=(250,500)
                                , random_state=3
                                , noise=0.04
                                , factor = 0.3)

fig, ax = plt.subplots(1,3, figsize=(15,4))

ax[0].scatter(X[:, 0], X[:, 1], alpha=0.7)
ax[0].set_title("Raw Data")

# Spectral clustering
pred = SpectralClustering(n_clusters=2
                            , eigen_solver="arpack"
                            , affinity="nearest_neighbors",).fit_predict(X)

ax[1].scatter(X[:, 0], X[:, 1], c=pred, cmap=plt.cm.rainbow, alpha=0.7)
ax[1].set_title("Spectral Clustering")

# Agglomerative clustering
pred = AgglomerativeClustering(n_clusters=2
                                  , linkage="ward").fit_predict(X)
ax[2].scatter(X[:, 0], X[:, 1], c=pred, cmap=plt.cm.rainbow, alpha=0.7)
ax[2].set_title("Agglomerative Clustering")

Spectral Clustering과 합병에 의한 계층적 군집화(Agglomerative Clustering) 비교 예제 결과

References

고민삼,『Machine Learning』, 강의 교안.

ratsgo, "K-Nearest Neighbor Algorithm", Github.io, 2017.4.17
, https://ratsgo.github.io/machine%20learning/2017/04/17/KNN/

Tobigs, "클러스터링 실습 (1) (EDA,Sklearn)", Gitbook
, https://tobigs.gitbook.io/tobigs/data-analysis/undefined-3/python-2-1

조대협, "클러스터링 #3 - DBSCAN (밀도 기반 클러스터링)", Tistory, 2017.10.13 
, https://bcho.tistory.com/m/1205

Vibhor Agarwal, "Let’s cluster data points using DBSCAN", Medium, 2019.6.28 
, https://medium.com/@agarwalvibhor84/lets-cluster-data-points-using-dbscan-278c5459bee5

Satyam Kumar, "Hierarchical Clustering: Agglomerative and Divisive — Explained", Medium, 2020.8.3 
, https://towardsdatascience.com/hierarchical-clustering-agglomerative-and-divisive-explained-342e6b20d710

Zaid.Ryu, "[ML with Python] 3.비지도 학습 알고리즘 (3-3) DBSCAN", Github.io, 2020.12.26 
, https://jhryu1208.github.io/data/2020/12/26/ML_DBSCAN/

Problem Link https://school.programmers.co.kr/learn/courses/30/lessons/42579

✅ Problem Summary

노래 장르(genres)와 재생 횟수(plays)가 주어질 때, 장르별 가장 많이 재생된 노래 2개씩 모아 해당 노래의 인덱스(index)를 다음 조건에 맞추어 순서대로 출력하는 문제

1. 속한 노래가 많이 재생된 장르를 먼저 수록한다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록한다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호(인덱스, index)가 낮은 노래를 먼저 수록한다.

📑 My Answer

• 모든 테스트 케이스 통과

  def solution(genres, plays):
    streamingInfo = {}
    for i, (g, p) in enumerate(zip(genres, plays)):
        value = streamingInfo.get(g, [0, []])
        value[0] += p
        value[1].append((p, i))
        streamingInfo[g] = value
  
    answer = []
    for songs in sorted(streamingInfo.values(), reverse=True):
        songs[1].sort(key=lambda x:x[0], reverse=True)
        answer += [s[1] for s in songs[1][:2]]
    return answer

  📌 *코드 구현 설명 *

• 딕셔너리(dictionary) 자료형을 사용하여 주어진 곡들을 장르별로 (재생횟수 p, 인덱스 i) 형태로 저장한다.

  • 장르 별 노래들의 재생 횟수의 총합도 같이 저장하여 이후 속한 노래가 많이 재생된 장르를 찾는데 사용

• 곡 정보가 저장된 딕셔너리가 만들어졌다면, 문제 에서 주어진 조건에 따라 값들을 정렬한다.

  • 속한 노래가 많이 재생된 장르를 먼저 수록하기 위해 우선 장르별 곡들의 총 재생 횟수를 기준으로 내림차순 정렬
  • 다음으로는 장르 내에서 많이 재생된 노래를 먼저 수록해야 하므로 노래 별 재생 횟수를 기준으로 내림차순 정렬 (이 과정에서 3번 조건은 자동으로 정렬됨)

• 정렬된 리스트 songs에서 해당 곡의 인덱스를 순서대로 answer에 저장하여 답을 구한다.

Problem Link https://school.programmers.co.kr/learn/courses/30/lessons/43163

✅ Problem Summary

두 개의 단어 begin, target과 단어의 집합 words가 주어질 때, begin을 target으로 변환하는 최소 단계 수를 구하는 문제

• 한 번에 한 개의 알파벳만 바꿀 수 있음
• words에 있는 단어로만 변환할 수 있음
• 모든 단어의 길이는 같으며, 중복되는 단어는 없음
• 변환할 수 없는 경우에는 0를 return

🧮 Applied Theory & Algorithm

1. 너비 우선 탐색 (Breadth-First Search) 그림 출처: Wikipedia

📑 My Answer

• 모든 테스트 케이스 통과

  from collections import deque
  def solution(begin, target, words):
    if target not in words:
        return 0
  
    queue = deque([(0, begin)])
    while queue:
        depth, tempWord = queue.popleft()
        if tempWord == target:
            return depth
  
        for w in words:
            diffChar = 0
            for i in range(len(w)):
                if tempWord[i] != w[i]:
                    diffChar += 1
            if diffChar == 1:
                queue.append((depth + 1, w))
    return 0

  📌 *코드 구현 설명 *

• 현재 단어 tempWord가 target 단어와 같은지 확인한다.

• 만약 tempWord가 target 단어와 같지 않다면 word에서 바꿀 수 있는 문자를 탐색한다.

  • 한 번에 한 문자만 바꿀 수 있기 때문에, tempWord에서 하나의 문자만 다른 문자를 찾는다.

• tempWord가 target와 같아질 때 까지 반복하며, 만약 바꿀 수 없다면 0을 return 한다.

Problem Link https://www.hackerrank.com/challenges/primsmstsub/problem?isFullScreen=true

✅ Problem Summary

프림 알고리즘(Prim's algorithm)을 이용한 최소 신장 트리(Minimum spanning tree) 탐색 문제

🧮 Applied Theory & Algorithm

1. 프림 알고리즘(Prim's algorithm) 그림 출처: Wikipedia

📑 My Answer

• 모든 테스트 케이스 통과

  from collections import defaultdict
  import heapq
  

def prims(n, edges, start): visited = [0] * (n + 1) graph = defaultdict(list) for u, v, w in edges: graph[u].append([w, u, v]) graph[v].append([w, v, u])

heapq.heapify(graph[start])
visited[start] = 1
total_weight = 0

while graph[start]:
    w, u, v = heapq.heappop(graph[start])
    if visited[v] == 0:
        visited[v] = 1
        total_weight += w
        for edge in graph[v]:
            if visited[edge[2]] == 0:
                heapq.heappush(graph[start], edge)

return total_weight

```

📌 *코드 구현 설명 *

• 간선 정보가 저장된 edges를 이용하여 graph를 만든다.
• heapq 라이브러리를 사용하여 graph를 최소 힙(Min heap) 형태로 만든다.
  • 가중치가 가장 작은 간선(edge)을 우선적으로 선택해야 하므로 최소 힙을 사용한다.
• 모든 노드를 방문할 때 까지 graph를 탐색한다.
  • visited에 방문 여부를 기록하여 재방문하지 않도록 한다.
  • 노드를 방문할 때 마다 total_weight에 가중치를 더하고, 반복문이 종료되면 return하여 정답을 구한다.

Problem Link https://programmers.co.kr/learn/courses/30/lessons/43162

✅ Problem Summary

주어진 노드(node) 연결 데이터에서 그래프의 개수를 세는 문제

🧮 Applied Theory & Algorithm

1. 깊이 우선 탐색(Depth-First Search) 그림출처:Wikipedia

📑 My Answer

• 모든 테스트 케이스 통과

  def dfs(computers, i, visited):
    visited[i] = True
    for j in range(len(computers)):
        if computers[i][j] == 1 and visited[j] == 0:
            dfs(computers, j, visited)
  

def solution(n, computers): answer = 0 visited = [0] * n for i in range(n): if visited[i] != True: dfs(computers, i, visited) answer += 1 return answer

```

Problem Link https://www.hackerrank.com/challenges/even-tree/problem?isFullScreen=true

✅ Problem Summary

주어진 트리(tree)의 간선(edge)을 끊었을 때 만들어지는 서브 트리(subtree)의 노드 갯수가 반드시 짝수여야 할 때, 끊을 수 있는 간선의 최대 갯수를 구하는 문제

• 주어지는 트리의 노드 개수는 양수

💡 Idea

최대한 많은 간선, 즉 최대한 많은 서브 트리를 만들기 위해서는 서브 트리를 구성하는 노드가 최대한 적어야 한다. 이를 구현하기 위해서 리프 노드(leaf node)부터 탐색하여 잘라나가는 방식을 채택했다.

우선, 각 노드별 자식 노드의 갯수를 센다.

모든 노드의 자식 노드의 갯수를 세었으면, 리프 노드부터 탐색하여 자신을 포함한 자식 노드의 갯수가 양수인 노드를 찾는다. 찾은 노드의 부모와 연결되어 있는 간선을 끊어보면, 양수 개의 노드로 구성된 서브 트리를 만들 수 있게 된다. (여기서 리프 노드부터 탐색하는 이유는 주어진 트리를 최대한 조각내기 위함이다.)

위의 과정을 더 이상 끊을 수 있는 간선이 없을 때까지 반복한다. 이 방법이 가능한 이유는, 문제에서 주어지는 그래프의 노드 수가 무조건 양수라는 조건이 있기 때문이다. 짝수 - 짝수 = 짝수이므로 조각난 서브 트리들의 노드 개수가 무조건 양수가 될 수 밖에 없다.

📑 My Answer

• 모든 테스트 케이스 통과

  def evenForest(t_nodes, t_edges, t_from, t_to):
    tree = [[] for _ in range(t_nodes + 1)]
    for f, t in zip(t_from, t_to):
        tree[t].append(f)
  
    cumulativeSums = [1] * (t_nodes + 1)
    for pa in range(t_nodes, 1, -1):
        if tree[pa] != []:
            for ch in tree[pa]:
                cumulativeSums[pa] += cumulativeSums[ch]
  
    edges = 0
    for sums in cumulativeSums:
        if sums % 2 == 0:
            edges += 1
    return edges

  📌 *코드 구현 설명 *

• 각 노드별 자식 노드 정보가 저장된 tree를 만든다.

  • 문제에서는 t_from의 부모 노드로 t_to가 주어지므로, tree[t_to].append(t_from)을 수행하여 트리를 만든다.

• 만들어진 tree의 노드를 노드 번호 역순으로 탐색하여 해당 노드의 자식 노드 갯수를 저장한 cumulativeSums 리스트를 만든다.

  • 노드 번호를 인덱스로 하여 자식 노드 갯수를 저장하자.

• 위의 단계가 끝나면 cumulativeSums 안의 양수 갯수를 세어 정답을 구한다.

Problem Link https://www.hackerrank.com/challenges/kruskalmstrsub/problem?isFullScreen=true

✅ Problem Summary

크루스칼 알고리즘(Kruskal's algorithm)를 이용한 최소 신장 트리(Minimum spanning tree) 탐색 문제

🧮 Applied Theory & Algorithm

1. 크루스칼 알고리즘(Kruskal's algorithm) 그림 출처: Wikipedia

📑 My Answer

• 모든 테스트 케이스 통과
• 참고 코드

  def graph_info(g_nodes, g_from, g_to, g_weight):
    parents = [i for i in range(g_nodes+1)]
    edges_info = [(g_weight[i], g_from[i], g_to[i]) for i in range(len(g_from))]
    edges_info.sort()
    return parents, edges_info
  

def find_parent(parents, n): if parents[n] != n: parents[n] = find_parent(parents, parents[n]) return parents[n]

def union_parent(parents, up, vp): if up < vp: parents[vp] = up else: parents[up] = vp return parents

def kruskal(g_nodes, g_from, g_to, g_weight): parents, edges_info = graph_info(g_nodes, g_from, g_to, g_weight) total_weights = 0 for w, u, v in edges_info: u_parent, v_parent = find_parent(parents, u), find_parent(parents, v) if u_parent != v_parent: parents = union_parent(parents, u_parent, v_parent) total_weights += w return total_weights

```

📌 *코드 구현 설명 *

• graph_info 함수에서 간선(edge) 정보를 저장한 edge_info와 서브 트리(subtree)의 루트 노드 정보를 저장할 parents 리스트를 생성한다.
  • 가중치가 작은 간선을 선택해나가는 방법인 크루스칼 알고리즘을 구현하기 위해 edge_info 생성후, 간선 가중치(weight)를 기준으로 오름차순으로 정렬
  • parents는 우선 노드 본인으로 초기화 (이후 서브 트리를 만들며 갱신)
• 가중치를 기준으로 오름차순 정렬된 edge_info의 간선들을 탐색하며 서브 트리를 만들어감
  • 트리의 사이클 여부를 확인하기 위해, 간선을 선택할 때마다 parents에서 해당 노드(node)의 루트(root) 노드를 확인
  • 루트 노드가 같지 않다면, parents에 저장된 각각의 루트 노드 번호 중 작은 값으로 갱신
• 모든 간선 탐색 후 종료

Problem Link https://www.acmicpc.net/problem/1012

✅ Problem Summary

주어진 행렬에서 수평(horizontally), 수직(vertically)으로 이어진 구역의 갯수를 세는 문제

🧮 Applied Theory & Algorithm

1. 깊이 우선 탐색(Depth-First Search) 그림출처:Wikipedia

📑 My Answer

• 메모리 : 33220KB
• 시간 : 396ms

  import sys
  sys.setrecursionlimit(10**6)
  

def dfs(matrix, matsize, pos): dx, dy = [1, -1, 0, 0], [0, 0, 1, -1] matrix[pos[0]][pos[1]] = 0 for i in range(4): ni, nj = pos[0]+dy[i], pos[1]+dx[i] if 0<=ni<matsize[0] and 0<=nj<matsize[1] and matrix[ni][nj] == 1: matrix = dfs(matrix, matsize=matsize, pos=(ni, nj)) return matrix

def main(): T = int(input()) result = [] for _ in range(T): M, N, K = map(int, input().split()) matrix, cnt = [[0]M for _ in range(N)], 0 for _ in range(K): X, Y = map(int, input().split()) matrix[Y][X] = 1 for i in range(N): for j in range(M): if matrix[i][j] == 1: matrix = dfs(matrix, matsize=(N, M), pos=(i, j)) cnt += 1 result.append(cnt) print(result, sep='\n')

main()

```

Problem Link https://www.acmicpc.net/problem/2667

✅ Problem Summary

주어진 행렬에서 수평(horizontally), 수직(vertically)으로 이어진 구역(1로 표시, 문제에서는 단지로 표현)들의 크기(문제에서는 집의 갯수로 표현)를 구하는 문제

• 출력 형태 : 첫 번째 줄에는 총 단지 수, 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력

이미지 출처: 백준 2667번

🧮 Applied Theory & Algorithm

1. 깊이 우선 탐색(Depth-First Search) 그림출처:Wikipedia

📑 My Answer

• 메모리 : 31084KB
• 시간 : 68ms

  def dfs(matrix, n, pos, cnt):
    dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
    matrix[pos[0]][pos[1]] = '0'
    for i in range(4):
        ni, nj = pos[0]+dx[i], pos[1]+dy[i]
        if 0<=ni<n and 0<=nj<n and matrix[ni][nj] == '1':
            cnt = dfs(matrix, n, pos=(ni, nj), cnt=cnt+1)
    return cnt
  

def main(): n = int(input()) matrix = [] for _ in range(n): matrix.append(list(input())) result = [] for i in range(n): for j in range(n): if matrix[i][j] == '1': cnt = dfs(matrix, n, pos=(i,j), cnt=1) result.append(cnt) result.sort() print(len(result)) print(*result, sep='\n')

main()

```

Problem Link https://www.hackerrank.com/challenges/bfsshortreach/problem?isFullScreen=true

✅ Problem Summary

너비 우선 탐색(Breadth First Search)을 이용하여 특정 노드와 다른 노드와의 최단 거리를 구하는 문제

🧮 Applied Theory & Algorithm

1. 너비 우선 탐색 (Breadth-First Search) 그림 출처: Wikipedia

📑 My Answer

• 모든 테스트 케이스 통과

  from collections import deque
  

def bfs(n, m, edges, s): graph = [set() for _ in range(n)] for u, v in edges: graph[u - 1].add(v - 1) graph[v - 1].add(u - 1)

end_nodes = [i for i in range(n)]
end_nodes.remove(s - 1)
queue, result = deque([(s - 1, 0)]), [-1] * n
while queue:
    temp, depth = queue.popleft()
    if temp in end_nodes:
        result[temp] = depth * 6
        end_nodes.remove(temp)
    for n in list(graph[temp]):
        queue.append((n, depth + 1))
        graph[temp].remove(n)
        graph[n].remove(temp)
result.pop(s - 1)
return result

```

📌 *코드 구현 설명 *

• 정점 연결 정보가 저장되어 있는 edges를 가지고 graph를 만든다.
• 거리를 계산할 노드 번호를 저장할 end_nodes를 만든다.
  • 시작 노드는 제외시켜야 하므로 리스트 내장함수인 remove를 사용하여 시작 노드 번호를 리스트에서 제거한다.
• 탐색 결과를 저장할 queue와, 노드 간 최단 거리를 저장할 result를 선언한다.
• 반복문을 사용하여 그래프 내의 노드들을 BFS 방법으로 탐색한다.
  • 만나는 노드(temp)가 end_nodes에 있으면 result[temp]에 최단 거리인 depth를 저장하고(문제에서는 간선(edge) 하나의 길이가 6이라고 했으므로 6을 곱하여 저장), 해당 노드의 최단 거리를 구했으므로 end_nodes에서 지운다.
  • 노드 temp의 자식 노드들을 depth 정보와 함께queue에 저장하고, 해당 노드에 다시 방문하지 못하도록 graph에서 간선 정보를 지운다.
  • queue에 방문 정보가 더 이상 없을 때(조건에 맞는 모든 노드를 탐색한 상태)까지 반복한다.
• 탐색이 끝나면, result에서 시작 노드 s에 저장되어 있는 값을 지우고(시작 노드는 제외하고 출력해야함) return 한다.

1️⃣ O(n)으로 구현하기

소수(prime number)란, 1과 자기 자신 외의 수로 나누어지지 않는 수를 말한다. 즉, 약수(divisor)가 1과 자기 자신밖에 없는 수가 소수인 것이다. 이러한 소수의 특성을 이용해서 입력한 숫자가 소수인지 판별하는 Python3 코드를 작성해보면 다음과 같다.

def checkPrimeNumber(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

위의 코드는 입력 숫자 n 을 2 부터 n-1 까지 차례대로 나누어서 만약 나누어진다면 False(소수가 아님), 나누어지면 True(소수임)를 반환하여 소수인지 아닌지 판별한다. 시간 복잡도 O(n) 으로, 가장 기초적인 방법임에도 나쁘지 않은 효율을 갖고 있다고 말할 수 있겠다. 하지만, n이 커지면 연산량이 그만큼 많아지게 된다.

2️⃣ O($\sqrt{n}$)으로 구현하기

연산량을 좀 더 줄여보자. 약수의 특성을 활용하면 어떨까? 어떤 수의 약수, 예를 들어 16의 약수들을 나열한다고 생각해보자. 나열하면 다음과 같다.

16의 약수 1, 2, 4, 8, 16

나열한 수들을 자세히 보면 중앙값을 기준으로 대칭을 이루고 있는 것을 알 수 있다. 또한 중앙값 이후의 약수들은 중앙값 이전의 약수들로 나눌 수 있다. 그렇다면 중앙값 즉, 소수인지 판별하고 싶은 어떤 수의 제곱근 보다 작은 수들로 나누어진다면, 제곱근 보다 큰 수들로 나누어 보지 않아도 소수가 아님을 알 수 있다. 이 방식으로 코드를 설계하게 되면 시간 복잡도 O($\sqrt{n}$) 으로, 이전 보다 효율성을 좀 더 챙길 수 있게 된다. Python3로 작성해보면 다음과 같다.

def checkPrimeNumber(n):
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

✅ 특정 구간에서 소수 찾기

지금까지는 어떤 수가 입력되었을 때, 해당 수가 소수인지 아닌지 판별하는 문제를 다루어보았다. 위의 코드를 이용해서 특정 구간에서의 모든 소수를 찾는 코드를 작성해보면 다음과 같다.

def checkPrimeNumber(n):
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def findPrimeNumbers(start, end):
    result = []
    for i in range(start, end+1):
        if checkPrimeNumber(i):
            result.append(i)
    return result

findPrimeNumbers(10, 100)

에라토스테네스의 체

위의 코드는 시간복잡도 O($n^2$) 에 가까운 연산을 수행한다. 조금 더 빠른 코드를 작성해보고 싶다면 에라토스테네스의 체를 적용하면 된다. 에라토스테네스의 체 알고리즘은 다음과 같이 작동한다.

그림 출처: 위키백과

💡 에라토스테네스의 체 규칙 1️⃣ 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2️⃣ 2부터 시작하여 소수의 배수들을 차례로 지워 나간다. 이 때 자기 자신은 지우지 않으며, 이미 지워진 수는 넘어간다. 3️⃣ 더이상 지울 숫자가 없을 때까지 2번을 반복한다. 4️⃣ 3번 이후 남아있는 숫자가 소수가 된다.

에라토스테네스의 체를 사용하면 소수 찾는 문제를 시간 복잡도 O($NloglogN$) 으로 구현할 수 있다. 굉장히 빠른 속도로 연산할 수 있지만, 입력 수만큼의 데이터 공간을 만들어야 하기 때문에 너무 큰 수에 대해서는 메모리를 많이 쓴다는 단점이 있다. 하지만 컴퓨터 메모리가 부족할 정도로 큰 범위의 소수 찾기 문제는 흔치 않으므로 편하게 쓰도록 하자. 해당 알고리즘을 적용한 코드는 다음과 같다.

def SieveOfEratosthenes(n):
    isPrime = [True] * (n+1)
    for i in range(2, int(n**0.5)+1):
        j = 2
        while i*j <= n:
            isPrime[i*j] = False
            j += 1
    return isPrime

def findPrimeNumbers(start, end):
    isPrime = SieveOfEratosthenes(end)
    result = []
    for i in range(start, end):
        if isPrime[i]:
            result.append(i)
    return result

findPrimeNumbers(10, 100)

Problem Link https://www.hackerrank.com/challenges/minimum-loss/problem?isFullScreen=true

✅ Problem Summary

구매한 집을 되팔았을 때 날 수 있는 손해 금액 중 최솟값을 구하는 문제

• $post$: 집 값이 저장되어 있는 리스트(혹은 배열)
• $post$의 인덱스(index)는 연도를 뜻하며, 해당 인덱스에 저장되어 있는 값은 그 해의 집 값임
• 집은 1년 이후 부터 팔 수 있으며, 무조건 손해가 나야함

📑 My Answer

• 모든 테스트 케이스 통과

  import os
  import sys
  

def minimumLoss(price): idxWprice = [(i, v) for i, v in enumerate(price)] idxWprice.sort(key = lambda x:x[1]) minVal = sys.maxsize for i in range(1, len(price)): if idxWprice[i][0] < idxWprice[i-1][0]: diff = idxWprice[i][1] - idxWprice[i-1][1] minVal = min(diff, minVal) return minVal

```

📌 *코드 구현 설명 *

• (연도, 집값) 정보를 저장한 idxWprice 리스트 생성
• 집값을 기준으로 idxWprice 정렬
• 정렬한 idxWprice를 앞에서부터 순차적으로 탐색하며 최소 손해 금액을 계산
  • 인덱스 i번째의 연도가 i-1의 연도보다 작은 경우에만 계산
  • 집값을 기준으로 정렬하였기 때문에, 해당 연도 끼리(i번째의 연도와 i-1의 연도)의 최소 손해 금액을 idxWprice[i][1] - idxWprice[i-1][1] 로 계산할 수 있음
• 반복문이 한번 수행될 때마다 이전 최솟값과 비교하여 정답을 구함

💼 Takeaway

• 원인이 무엇인지 모르겠으나(메모리..?), 코딩 테스트 플랫폼에 따라서 처리할 수 있는 값의 최대치가 존재하는 것 같다. 따라서 최솟값을 비교하기 위해 초깃값을 시스템의 최댓값인 sys.maxsize로 설정하였다. (마냥 큰 값으로 설정하면 코드를 잘 짜도 오류가 나는 경우가 있었다.)

Problem Link https://www.hackerrank.com/challenges/cut-the-tree/problem?isFullScreen=true

✅ Problem Summary

각 노드에 키 값이 들어있는 이진 트리(Binary Tree)에서 엣지(edge) 하나를 끊어 두개의 트리를 만들고, 각 트리의 노드 값 총합의 차이 중 최솟값을 구하는 문제

🧮 Applied Theory & Algorithm

1. 너비 우선 탐색 (Breadth-First Search) 그림 출처: Wikipedia

💡 Idea

문제 풀이를 위해 노드 값을 리프 노드 부터 역순으로 누적합을 구하여 계산하는 방법을 채택하였다.

우선 예시로 주어진 트리에서 리프 노드(leaf node)부터 루트 노드(root node)까지 누적합을 구하면 다음과 같다. 여기서 하나의 엣지(edge)를 끊었을 때 만들어지는 두 트리의 각 노드 총합을 구하려면 다음과 같이 계산하면 된다. 나누어진 두 트리에서 원래 루트 노드인, Vertex 1이 포함되지 않은 트리(tree1)의 총합은 루트 노드에 할당되어 있었던 누적합으로 계산할 수 있다. 그리고 나머지 트리(tree2)의 총합은 Vertex 1의 누적합, 즉 모든 노드의 총합에서 tree1의 루트 노드에 해당하는 누적합을 빼주면 구할 수 있다.

위의 방식을 따라 계산하면, 나누어진 두 트리의 총합의 차이는 다음 공식으로 구할 수 있게 된다.

두 트리 총합 차이 = (노드 들의 총합) - 2*(Vertex1이 포함되지 않은 트리의 총합)

이 아이디어를 적용하기 위해서는 노드 들의 깊이(depth) 정보가 있어야 한다(리프 노드 부터 루트 노드 방향으로 누적합을 계산하기 때문에). 이를 설정하기 위해 너비 우선 탐색(Breadth-First Search) 알고리즘을 사용하여 각 노드들의 깊이를 추적하였다.

📑 My Answer

• 모든 테스트 케이스 통과
• 참고 코드: qayum_khan_usa 님의 글

  def bfs(tree):
    parent_nodes, visited_nodes = {1}, []
    while parent_nodes:
        pn = parent_nodes.pop()
        # Save visited nodes in descending order along depth level
        visited_nodes.insert(0, pn)
        parent_nodes.update(set(tree[pn]))
        # Prevent node revisiting
        for cn in tree[pn]:
            tree[cn].remove(pn)
    return visited_nodes
  
  

def cutTheTree(data, edges): tree = {} for n1, n2 in edges: tree[n1] = tree.get(n1, []) + [n2] tree[n2] = tree.get(n2, []) + [n1] # bfs for calculating node's depth visited_nodes = bfs(tree) for node in visited_nodes: data[node - 1] += sum(data[cn - 1] for cn in tree[node]) return min(abs(data[0] - 2 * data[n]) for n in range(1, len(data)))

```

📌 *코드 구현 설명 *

• 주어진 노드에 저장된 값(data)과 엣지(edge) 정보를 이용하여 트리 내 노드 간 연결 관계를 딕셔너리 형태로 만듦
  • 딕셔너리 키(key): 노드 번호 / 값(value): 키 노드와 이어져 있는 노드 번호 집합(set)
• 너비 우선 탐색(bfs) 알고리즘을 사용하여 각 노드 들의 깊이 정보를 추적한다. (방문순서 -> 노드 깊이로 생각)
  • 노드를 번호의 오름차순으로 탐색하기 때문에 방문한 노드 번호를 저장할 때 역순으로 저장하여, 이후 누적합 계산 시 앞에서부터 차례로 계산할 수 있도록 만든다.
• 💡 Idea 에서 언급한 공식으로 누적합 차이를 구하고, 그들 중 최솟값을 return 한다.

💼 Takeaway

• 트리를 이용한 이런 형태의 문제에서 누적합을 활용하는 방법을 알게 되었다.

• BFS를 단순 노드 값 탐색이 아닌 트리의 깊이를 탐색하는데 사용할 수 있다는 것을 깨닫게 되었다.

Problem Link https://www.hackerrank.com/challenges/pairs/problem?isFullScreen=true

✅ Problem Summary

양수 $k$와 양수로 이루어진 배열($arr$)이 주어졌을 때, 배열 내 두 수의 차가 $k$인 짝의 갯수를 구하는 문제

📑 My Answer

• 모든 테스트 케이스 통과

  def pairs(k, arr):
    arr.sort()
    cnt = 0
    for i in range(len(arr)-1):
        for j in range(i+1, len(arr)):
            diff = arr[j]-arr[i]
            if k == diff:
                cnt+=1
            elif k < diff:
                break
    return cnt

  📌 *코드 구현 설명 *

• 입력된 배열($arr$)을 오름차순으로 정렬
• 정렬된 배열을 반복문으로 탐색하며 두 수의 차가 $k$인 경우 계산
  • 반복문 종료 조건은 배열($arr$) 내의 같은 숫자가 존재하지 않는다는 점을 이용
  • 만약 두 수의 차가 $k$보다 큰 경우, 더 이상 $k$와 같아질 수 없기 때문에 반복문 종료

Problem Link https://www.hackerrank.com/challenges/red-knights-shortest-path/problem?isFullScreen=true

✅ Problem Summary

아래 그림과 같이 여섯 가지의 이동을 할 수 있는 특수 체스 말을 주어진 위치 $(i_{start},j_{start})$ 에서 목적지 $(i_{end},j_{end})$ 까지의 최소 이동 횟수와, 해당 이동 횟수에 해당하는 체스 말의 움직임을 출력하는 문제

• 경로가 겹치는 경우, UL > UR > R > LR > LL > L 를 우선 순위로 하여 경로 출력
• 만약 불가능하다면 Impossible 출력

그림 출처: HackerRank Red Knight's Shortest Path

🧮 Applied Theory & Algorithm

1. 너비 우선 탐색 (Breadth-First Search) 그림 출처: Wikipedia

📑 My Answer

• 모든 테스트 케이스 통과

  def bfs(n, pos, dtn):
    matrix = [[0]*n for _ in range(n)]
    dx = [-2, -2, 0, 2, 2, 0]
    dy = [-1, 1, 2, 1, -1, -2]
    moveName = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
    queue = [(pos[0], pos[1], [])]
    while queue:
        tx, ty, path = queue.pop(0)
        if (tx, ty) == dtn:
            return (matrix[tx][ty], path)
        for i in range(6):
            nx, ny = tx + dx[i], ty + dy[i]
            if 0<=nx<n and 0<=ny<n and matrix[nx][ny] == 0:
                matrix[nx][ny] = matrix[tx][ty] + 1
                queue.append((nx, ny, path+[moveName[i]]))
    return -1
  

def printShortestPath(n, i_start, j_start, i_end, j_end): result = bfs(n, pos=(i_start, j_start), dtn=(i_end, j_end)) if result == -1: print("Impossible") else: print(result[0]) print(*result[1], end=' ')

```

📌 *코드 구현 설명 *

• 최소 이동 횟수를 구하기 위해 가능한 모든 경우의 수를 탐색해야 한다는 점과, 우선 순위 경로가 있다는 점_(queue를 활용하기 때문에)_에서 BFS 알고리즘 사용
• 0으로 표시된 방문하지 않은 위치(노드)로만 이동이 가능하며, 목적지에 도착할 때 까지 UL > UR > R > LR > LL > L 순서 대로 경로를 탐색
  • 현재 방문한 위치 matrix[nx][ny]에는 이전 위치까지의 이동 횟수 matrix[tx][ty]에 1을 더하여 저장
• bfs 함수를 통해 목적지에 무사히 도착하면 해당 결과를, 아니라면 -1을 return하여 답 출력

Problem Link https://www.hackerrank.com/challenges/count-luck/problem?isFullScreen=true

✅ Problem Summary

., X, M, * 로 이루어진 행렬에서 시작점인 M에서 목적지인 * 까지 이동하면서 만날 수 있는 교차점의 갯수를 세는 문제

• 상하좌우로 움직일 수 있으며, 값이 . 인 위치로만 움직일 수 있음
• M에서 * 까지는 오직 한 개의 길만 존재
• 입력된 k값과 실제로 계산한 교차로 갯수가 일치하면 Impressed, 일치하지 않으면 Oops!를 출력

🧮 Applied Theory & Algorithm

1. 깊이 우선 탐색(Depth-First Search) 그림출처:Wikipedia

📑 My Answer

• 모든 테스트 케이스 통과

  def findMPosition(matrix):
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == 'M':
                return [i, j]
  

def checkIntersection(pos): dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] res = []

for i in range(4):
    nx, ny = pos[0] + dx[i], pos[1] + dy[i]
    if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] != 'X':
        res.append([nx, ny])
return res

def dfs(matrix, wave_cnt, pos): if matrix[pos[0]][pos[1]] == '*': return wave_cnt

matrix[pos[0]][pos[1]] = 'X'
moves = checkIntersection(pos)
if len(moves) > 1:
    wave_cnt += 1
for nx, ny in moves:
    result = dfs(matrix, wave_cnt, pos=[nx, ny])
    if result != -1:
        return result
return -1

def countLuck(matrix, k): temp_pos = findMPosition(matrix) wave_cnt = dfs(matrix, 0, pos=temp_pos) return 'Oops!' if wave_cnt != k else 'Impressed'

```

📌 *코드 구현 설명 *

• M부터 *까지 한 개의 길만 존재한다는 점에서,DFS 알고리즘 활용
• 우선 findMPosition 함수로 M의 위치를 탐색
• M의 위치를 찾으면, dfs 함수를 이용해 *까지의 길을 탐색
  • 방문 위치(노드)는 X로 표시하여 다시 방문하지 못하게 함
  • 매 탐색 마다 해당 위치가 교차점에 해당하는지 확인 (checkIntersection 함수)
  • 해당 위치에서 갈 수 있는 길이 2개 이상이면 교차점으로 판별하여 교차점 갯수 + 1 을 수행
• *에 도착하면 입력 k와 실제 교차점 갯수를 비교하여 결과 출력

Problem Link https://www.hackerrank.com/challenges/knightl-on-chessboard/problem?isFullScreen=true

✅ Problem Summary

직각 형태로 움직일 수 있는 체스 말(knight)을 이용하여, $n\times n$ 크기의 행렬에서 $(0, 0)$ 부터 $(n-1, n-1)$ 까지 말의 최소 이동 횟수를 구하는 문제

• 아래에 해당하는 모든 경우의 수를 구하여 행렬 형태로 출력해야 함 ($KnightL(i,j)$에 해당하는 값을 행렬 $(i,j)$에 넣어서 출력)

$$ KnightL(i,j) \qquad 0\le i < n , \quad 0\le j < n $$

🧮 Applied Theory & Algorithm

1. 너비 우선 탐색 (Breadth-First Search) 그림 출처: Wikipedia

📑 My Answer

• 모든 테스트 케이스 통과

  def bfs(n, i, j):
    checkVisit = [[0] * n for _ in range(n)]
    queue = [[0, 0]]
    dx, dy = [i, i, -i, -i, j, -j, j, -j], [j, -j, j, -j, i, i, -i, -i]
    while queue:
        px, py = queue.pop(0)
        for p in range(8):
            nx, ny = px + dx[p], py + dy[p]
            if 0 <= nx < n and 0 <= ny < n and checkVisit[nx][ny] == 0:
                queue.append([nx, ny])
                checkVisit[nx][ny] = checkVisit[px][py] + 1
    return -1 if checkVisit[n - 1][n - 1] == 0 else checkVisit[n - 1][n - 1]
  
  

def knightlOnAChessboard(n): result = [[0] * (n - 1) for _ in range(n - 1)] for i in range(1, n): for j in range(i, n): val = bfs(n, i, j) result[i - 1][j - 1], result[j - 1][i - 1] = val, val return result

```

📌 *코드 구현 설명 *

• 반복문을 사용하여 발생할 수 있는 모든 경우를 탐색함 (BFS 알고리즘 이용)
  • $KnightL(i,j) = KnightL(j,i)$ 이므로, 절반만 탐색
• BFS 함수에서 $Knight$의 방문 노드 확인 및 이동 횟수 계산을 위해 checkVisit 이라는 행렬을 생성
  • $Knight$는 다음 위치인 checkVisit[i][j] 의 값이 0일 때만 이동하며, 이동한 이후에는 checkVisit[i][j]에 이전 단계까지의 $Knight$ 이동 횟수에 1을 더하여 저장
• 모든 경우를 탐색한 후, 최종적으로 checkVisit[n-1][n-1]의 값이 0이 아니라면 checkVisit[n-1][n-1] 에 저장된 값을 return, 0이라면 -1을 return

💼 Takeaway

• BFS 문제 유형에 대해 감을 잡게 되었다.

Problem Link https://www.hackerrank.com/challenges/connected-cell-in-a-grid/problem?isFullScreen=true

✅ Problem Summary

주어진 행렬에서 수평(horizontally), 수직(vertically), 대각(diagonally)으로 이어진 구역(1로 표시) 중 가장 넓은 구역의 크기를 구하는 문제

🧮 Applied Theory & Algorithm

1. 깊이 우선 탐색(Depth-First Search) 그림출처:Wikipedia

📑 My Answer

• 모든 테스트 케이스 통과

  def dfs(matrix, tempCnt, matsize, pos):
    matrix[pos[0]][pos[1]] = 0
    dx = [0, 0, 1, 1, 1, -1, -1, -1]
    dy = [1, -1, 0, 1, -1, 0, 1, -1]
    for i in range(8):
        ni, nj = pos[0] + dx[i], pos[1] + dy[i]
        if 0 <= ni < matsize[0] and 0 <= nj < matsize[1] and matrix[ni][nj] == 1:
            tempCnt = dfs(matrix, tempCnt + 1, matsize=matsize, pos=(ni, nj))
    return tempCnt
  

def connectedCell(n, m, matrix): maxCnt = 0 for i in range(n): for j in range(m): if matrix[i][j] == 1: tempCnt = dfs(matrix, 1, matsize=(n, m), pos=(i, j)) maxCnt = max(tempCnt, maxCnt) return maxCnt

```

📌 *코드 구현 설명 *

• 여러 경우의 수가 아닌 특정 위치에서 하나의 구역을 찾는 문제이기 때문에 DFS를 적용
• 행렬을 탐색하면서 1을 만날 때 마다 DFS 알고리즘을 사용하여 구역의 크기를 계산함 (DFS 함수를 만들어 재귀의 형태로 구현)
• DFS 함수에서, 방문한 위치에는 0을 넣어 다시 방문하지 못하게 만듦
• DFS 함수를 통해 return된 값을 매 행렬 탐색마다 비교하여 최댓값을 계산

💼 Takeaway

• DFS 문제 유형에 대해 감을 잡을 수 있었다.

Problem Link https://www.hackerrank.com/challenges/countingsort4/problem?isFullScreen=true

✅ Problem Summary

문자와 함께 주어진 인덱스(index)를 가지고 분류하여 순서대로 나열하는 문제 (전체 문자의 반절은 -로 변환하여 출력)

📑 My Answer

• 모든 테스트 케이스 통과

  def countSort(arr):
    maxVal = max([int(i) for i, _ in arr])
  
    result = [[] for _ in range(maxVal+1)]
    for idx, (i, s) in enumerate(arr):
        if idx < len(arr) // 2:
            result[int(i)].append('-')
        else:
            result[int(i)].append(s)
    print(' '.join([y for x in result for y in x]))

  📌 *코드 구현 설명 *

• 주어진 인덱스(index)값 중 최댓값을 찾은 후, 최댓값 만큼의 빈 리스트가 들어있는 이중 리스트 생성

• 입력 문자가 들어 있는 배열을 차례대로 탐색하여 처음 반절은 -로 치환, 나머지는 문자열 그대로 사용

• 처음에 생성해둔 이중 리스트에서, 문자열 인덱스(index)에 해당하는 리스트에 앞 단계에서 만든 문자열을 넣어줌

• 탐색이 끝나면 이중 리스트를 분해하여 문자들을 출력

💼 Takeaway

• 인덱스 혹은 클래스가 포함된 데이터를 계수 정렬(counting sort)의 개념을 적용해서 정렬할 수 있음을 배울 수 있었음

Problem Link https://www.hackerrank.com/challenges/quicksort3/problem?/isFullScreen=True

✅ Problem Summary

Lumoto Partitioning 알고리즘을 이용한 퀵소트(quicksort) 구현 문제

🧮 Applied Theory & Algorithm

1. Lumoto Partition Scheme

• pivot 값을 정한 후, 배열 앞에서 부터 순차적으로 탐색
• pivot보다 큰 수가 나타나면 직전의 pivot보다 작은 수와 위치를 바꾸는 방식으로 정렬 그림출처:hackerrank quicksort in-place

📑 My Answer

• 모든 테스트 케이스 통과

  # Lomuto Partitioning
  def quickSort(arr, l , r):
    if l >= r or l < 0:
        return
  
    arr, p = partition(arr, l, r)
    quickSort(arr, l, p-1)
    quickSort(arr, p+1, r)
  

def partition(arr, l, r): i, pivot = l-1, arr[r] for j in range(l, r): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] i += 1 arr[i], arr[r] = arr[r], arr[i] print(*arr) return arr, i

```

💼 Takeaway

• 퀵소트 구현 방법이 다양하다는 것을 알게됨
• 또 다른 퀵소트 알고리즘으로 Hoare partition scheme이 있음