Nividia에서 개발한 3D 모델링 AI

참고

공식 사이트 : https://research.nvidia.com/labs/dir/neuralangelo/ Baseline : https://colab.research.google.com/drive/1JD9CpAPteg_JsxneB1B-0XX-pZpybuEj

환경 세팅

1. WSL Ubuntu 22.04 : 파이썬 버전과 CUDA 버전, cmake 버전을 모두 만족하는 ubuntu 버전

python3 --version
> 3.10

sudo apt update

sudo apt upgrade

sudo apt install build-essential ffmpeg git python3-pip cmake python3-venv

python3 -m venv venv
source venv/bin/activate

git clone https://github.com/nvlabs/neuralangelo
cd ./neuralangelo
git submodule update --init --recursive

cd ..

sudo apt-get install \
    ninja-build \
    build-essential \
    libboost-program-options-dev \
    libboost-filesystem-dev \
    libboost-graph-dev \
    libboost-system-dev \
    libeigen3-dev \
    libflann-dev \
    libfreeimage-dev \
    libmetis-dev \
    libgoogle-glog-dev \
    libgtest-dev \
    libsqlite3-dev \
    libglew-dev \
    qtbase5-dev \
    libqt5opengl5-dev \
    libcgal-dev \
    libceres-dev

sudo apt-get install xvfb

pip install gdown
pip show gdown
echo 'export PATH=$PATH:/home/crysh/.local/bin' >> ~/.bashrc
source ~/.bashrc


gdown 1Ob2pSUFp46lZNAEK7y7ZSnpwvdIMsILb
sudo tar -C /usr -zxf colmap-3.8.tar.gz
pip install \
    addict \
    k3d \
    opencv-python-headless \
    pillow \
    plotly \
    pyyaml \
    trimesh


cd ./neuralangelo

gdown 1Ee6ucKlmmS2ZsB1uD09XHhf3p_pYv7nt

cd ./third_party/colmap

mkdir build
cd build

sudo apt-get update
sudo apt-get install -y libceres-dev libboost-all-dev libfreeimage-dev libflann-dev libsqlite3-dev libgl1-mesa-dev libglu1-mesa-dev libglew-dev libmetis-dev qtbase5-dev qt5-qmake

cmake .. -DCUDA_ENABLED=ON -DCMAKE_CUDA_ARCHITECTURES="70;72;75;80;86" -GNinja

ninja 

sudo sudo ninja install

wget https://developer.download.nvidia.com/compute/cuda/repos/wsl-ubuntu/x86_64/cuda-wsl-ubuntu.pin

sudo mv cuda-wsl-ubuntu.pin /etc/apt/preferences.d/cuda-repository-pin-600

wget https://developer.download.nvidia.com/compute/cuda/11.8.0/local_installers/cuda-repo-wsl-ubuntu-11-8-local_11.8.0-1_amd64.deb

sudo dpkg -i cuda-repo-wsl-ubuntu-11-8-local_11.8.0-1_amd64.deb

sudo cp /var/cuda-repo-wsl-ubuntu-11-8-local/cuda-*-keyring.gpg /usr/share/keyrings/

sudo apt-get update

sudo apt-get -y install cuda

echo 'export PATH=/usr/local/cuda-11.8/bin:$PATH' >> ~/.bashrc
echo 'export LD_LIBRARY_PATH=/usr/local/cuda-11.8/lib64:$LD_LIBRARY_PATH' >> ~/.bashrc

sudo ln -sfn /usr/local/cuda-11.8 /usr/local/cuda

source ~/.bashrc

which nvcc
nvcc --version

cd ~
git clone https://github.com/NVIDIA/libglvnd
cd ./libglvnd

sudo apt-get install libxext-dev libx11-dev x11proto-gl-dev
sudo apt-get install autoconf automake libtool
sudo apt-get install libffi-dev
sudo ./autogen.sh
sudo ./configure
sudo make -j4
sudo make install
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/lib/wsl/lib
export LDFLAGS="-L/usr/lib/wsl/lib"

---
pip uninstall -y tinycudann

sudo apt-get update
sudo apt-get install -y build-essential cmake ninja-build

cd ~
git clone https://github.com/NVlabs/tiny-cuda-nn.git

cd ~/tiny-cuda-nn/
git submodule update --init --recursive
cd bindings/torch

export TCNN_CUDA_ARCHITECTURES=75


pip install .

이후 필요한 코드만 사용하면 됩니다.

code

예제에서 설치부분을 제외한 실행 부분만을 사용했습니다. 순차적으로 ipynb 파일에서 쉘 단위로 실행하면 됩니다. (1)

# Take a look at the video.
from IPython.display import HTML
from base64 import b64encode
mp4 = open("lego.mp4", "rb").read()
data_url = "data:video/mp4;base64," + b64encode(mp4).decode()
HTML(f"""<video src="{data_url}" width=400 controls></video>""")

(2)

SEQUENCE = "lego"
PATH_TO_VIDEO = "lego.mp4"
DOWNSAMPLE_RATE = 2
SCENE_TYPE = "object"  # {outdoor,indoor,object}
# Run the script.
colmap_path = f"datasets/{SEQUENCE}_ds{DOWNSAMPLE_RATE}"
!rm -rf {colmap_path}
!bash projects/neuralangelo/scripts/preprocess.sh {SEQUENCE} {PATH_TO_VIDEO} {DOWNSAMPLE_RATE} {SCENE_TYPE}
# Check whether we have 100 images registered.
import os
num_images = len(os.listdir(f"{colmap_path}/images"))
print("----------------------------------------")
print(f"Number of registered images: {num_images}")

(3)

%cd ./neuralangelo
# Import Python libraries.
import numpy as np
import torch
import k3d
import json
import plotly.graph_objs as go
from collections import OrderedDict
# Import imaginaire modules.
from projects.nerf.utils import camera, visualize
from third_party.colmap.scripts.python.read_write_model import read_model
# Read the COLMAP data.
cameras, images, points_3D = read_model(path=f"{colmap_path}/sparse", ext=".bin")
# Convert camera poses.
images = OrderedDict(sorted(images.items()))
qvecs = torch.from_numpy(np.stack([image.qvec for image in images.values()]))
tvecs = torch.from_numpy(np.stack([image.tvec for image in images.values()]))
Rs = camera.quaternion.q_to_R(qvecs)
poses = torch.cat([Rs, tvecs[..., None]], dim=-1)  # [N,3,4]
print(f"# images: {len(poses)}")
# Get the sparse 3D points and the colors.
xyzs = torch.from_numpy(np.stack([point.xyz for point in points_3D.values()]))
rgbs = np.stack([point.rgb for point in points_3D.values()])
rgbs_int32 = (rgbs[:, 0] * 2**16 + rgbs[:, 1] * 2**8 + rgbs[:, 2]).astype(np.uint32)
print(f"# points: {len(xyzs)}")

(4)

json_fname = f"{colmap_path}/transforms.json"
with open(json_fname) as file:
    meta = json.load(file)
center = meta["sphere_center"]
radius = meta["sphere_radius"]
# ------------------------------------------------------------------------------------
# These variables can be adjusted to make the bounding sphere fit the region of interest.
# The adjusted values can then be set in the config as data.readjust.center and data.readjust.scale
readjust_x = 0.  # @param {type:"number"}
readjust_y = 0.  # @param {type:"number"}
readjust_z = 0.  # @param {type:"number"}
readjust_scale = 1.  # @param {type:"number"}
readjust_center = np.array([readjust_x, readjust_y, readjust_z])
# ------------------------------------------------------------------------------------
center += readjust_center
radius *= readjust_scale
# Make some points to hallucinate a bounding sphere.
sphere_points = np.random.randn(100000, 3)
sphere_points = sphere_points / np.linalg.norm(sphere_points, axis=-1, keepdims=True)
sphere_points = sphere_points * radius + center

(5)

vis_depth = 0.2
# Visualize with Plotly.
x, y, z = *xyzs.T,
colors = rgbs / 255.0
sphere_x, sphere_y, sphere_z = *sphere_points.T,
sphere_colors = ["#4488ff"] * len(sphere_points)
traces_poses = visualize.plotly_visualize_pose(poses, vis_depth=vis_depth, xyz_length=0.02, center_size=0.01, xyz_width=0.005, mesh_opacity=0.05)
trace_points = go.Scatter3d(x=x, y=y, z=z, mode="markers", marker=dict(size=1, color=colors, opacity=1), hoverinfo="skip")
trace_sphere = go.Scatter3d(x=sphere_x, y=sphere_y, z=sphere_z, mode="markers", marker=dict(size=0.5, color=sphere_colors, opacity=0.7), hoverinfo="skip")
traces_all = traces_poses + [trace_points, trace_sphere]
layout = go.Layout(scene=dict(xaxis=dict(showspikes=False, backgroundcolor="rgba(0,0,0,0)", gridcolor="rgba(0,0,0,0.1)"),
                              yaxis=dict(showspikes=False, backgroundcolor="rgba(0,0,0,0)", gridcolor="rgba(0,0,0,0.1)"),
                              zaxis=dict(showspikes=False, backgroundcolor="rgba(0,0,0,0)", gridcolor="rgba(0,0,0,0.1)"),
                              xaxis_title="X", yaxis_title="Y", zaxis_title="Z", dragmode="orbit",
                              aspectratio=dict(x=1, y=1, z=1), aspectmode="data"), height=800)
fig = go.Figure(data=traces_all, layout=layout)
fig.show()

(6)

GROUP = "test_exp"
NAME = "lego"
!torchrun --nproc_per_node=1 train.py \
    --logdir=logs/{GROUP}/{NAME} \
    --show_pbar \
    --config=projects/neuralangelo/configs/custom/lego.yaml \
    --data.readjust.scale=0.5 \
    --max_iter=40000 \
    --validation_iter=99999999 \
    --model.object.sdf.encoding.coarse2fine.step=200 \
    --model.object.sdf.encoding.hashgrid.dict_size=19 \
    --optim.sched.warm_up_end=200 \
    --optim.sched.two_steps=[12000,16000]

(7)

mesh_fname = f"logs/{GROUP}/{NAME}/mesh.ply"
!torchrun --nproc_per_node=1 projects/neuralangelo/scripts/extract_mesh.py \
    --config=logs/{GROUP}/{NAME}/config.yaml \
    --checkpoint=logs/{GROUP}/{NAME}/epoch_00068_iteration_000020000_checkpoint.pt \
    --output_file={mesh_fname} \
    --resolution=300 --block_res=128 \
    --textured

(8)

import numpy as np
import trimesh
# Load the mesh.
mesh = trimesh.load(mesh_fname)
print(f"# vertices: {len(mesh.vertices)}")
print(f"# faces: {len(mesh.faces)}")
# Create a Trimesh scene and visualize the mesh.
scene = trimesh.Scene()
scene.add_geometry(mesh)
scene.show()

결과물

(원본)

위의 영상을 랜더링한 결과는 아래와 같습니다.

(결과물)

• [[Wi-Fi (Wireless Fidelity)]]: 가장 널리 사용되는 무선 근거리 통신망(WLAN) 기술입니다. IEEE 802.11 표준을 기반으로 하며, Wi-Fi 4 (802.11n), Wi-Fi 5 (802.11ac), Wi-Fi 6/6E (802.11ax), Wi-Fi 7 (802.11be) 등 다양한 버전이 있습니다.

• [[블루투스 (Bluetooth)]]: 스마트폰, 이어폰, 키보드 등 휴대용 장치 간의 저전력, 단거리 데이터 교환에 사용됩니다. 클래식 블루투스와 저전력 블루투스(BLE)로 나뉩니다.

• [[Zigbee]]: 저전력, 저속도, 저비용을 특징으로 하는 프로토콜입니다. 스마트 홈의 조명, 센서, 스위치 등 사물 인터넷(IoT) 기기 제어에 널리 쓰입니다.

• [[Z-Wave]]: Zigbee와 유사하게 스마트 홈 및 IoT 기기에 사용되는 저전력 무선 기술입니다.

• [[NFC (Near Field Communication)]]: 매우 짧은 거리(약 10cm 이내)에서 작동하며, 교통카드, 모바일 결제, 기기 간 간편한 페어링에 사용됩니다.

• [[UWB (Ultra-Wideband)]]: 매우 넓은 주파수 대역을 사용하여 정밀한 거리 측정과 위치 추적이 가능한 기술입니다. 스마트폰을 이용한 디지털 키나 물품 추적에 활용됩니다.

장거리 무선 통신 (Long-Range Wireless)

광역 통신망(WAN) 환경에서 사용되며, 더 넓은 범위를 지원합니다.

• [[LoRaWAN (Long Range Wide Area Network)]]: 저전력으로 수 킬로미터까지 통신이 가능하여, 스마트 시티, 스마트 농업 등 넓은 지역의 IoT 센서 데이터 수집에 적합합니다.

• [[Sigfox]]: LoRaWAN과 유사한 저전력 광역 통신망(LPWAN) 기술로, 간단한 메시지를 보내는 데 특화되어 있습니다.

• [[LTE-M (LTE for Machine-Type Communication)]]: 기존 LTE 망을 활용하여 IoT 기기 통신을 지원하는 기술입니다. LoRa나 Sigfox보다 빠른 속도를 제공합니다.

• [[NB-IoT (Narrowband-IoT)]]: LTE-M과 함께 대표적인 셀룰러 IoT 기술로, 더 좁은 대역폭을 사용하여 커버리지를 넓히고 배터리 소모를 줄인 것이 특징입니다.

셀룰러 통신 (Cellular Communication)

이동통신 기지국을 통해 음성 및 데이터를 주고받는 기술입니다.

• [[3G (WCDMA, EV-DO)]]: 초기 데이터 통신을 가능하게 한 3세대 이동통신 기술입니다.

• [[4G (LTE, LTE-Advanced)]]: 고속 데이터 통신을 대중화시킨 4세대 이동통신 기술입니다.

• [[5G (NR - New Radio)]]: 초고속, 초저지연, 초연결을 특징으로 하는 5세대 이동통신 기술로, 자율주행, 원격의료, 실감형 미디어 등에 활용됩니다.

미디어 스트리밍 프로토콜

언급하신 프로토콜들은 실시간 음성/영상 데이터를 전송하는 데 특화되어 있으며, 유선 및 무선 환경 모두에서 사용됩니다.

• [[WebRTC (Web Real-Time Communication)]]: 웹 브라우저 간에 별도의 플러그인 없이 실시간으로 음성, 영상, 데이터를 주고받을 수 있게 하는 개방형 기술입니다. 화상 회의, 온라인 교육 등에 널리 쓰입니다.

• [[RTMP (Real-Time Messaging Protocol)]]: 실시간 비디오 및 오디오 스트리밍을 위한 프로토콜입니다. 주로 인터넷 방송 플랫폼으로 영상을 송출할 때 사용됩니다.

• [[RTSP (Real-Time Streaming Protocol)]]: 미디어 서버를 원격으로 제어하기 위한 프로토콜로, IP 카메라나 영상 감시 시스템에서 많이 사용됩니다.

• [[HLS (HTTP Live Streaming)]]: Apple에서 개발한 프로토콜로, HTTP를 기반으로 하여 안정적인 스트리밍이 가능합니다. 대부분의 동영상 플랫폼에서 사용됩니다.

• [[MPEG-DASH (Dynamic Adaptive Streaming over HTTP)]]: HLS와 유사한 HTTP 기반의 적응형 스트리밍 기술로, 국제 표준이라는 장점이 있습니다.

• [[Secure Reliable Transport (SRT)]]: SRT 프로토콜은 스트리밍 기술 제공업체인 Haivision이 개발한 오픈 소스 표준입니다.

RFC(Request for Comments) 직역하면 비평을 기다리는 문서. IETF는 RFC로 발표된 일부 제안을 인터넷 표준으로 채택함. 모든 내용이 표준인 것은 아님.

https://en.wikipedia.org/wiki/Request_for_Comments

IETF(Internet Engineering Task Force) 인터넷 표준 기구. 프로토콜을 구성하는 기술 표준을 담당함.

https://en.wikipedia.org/wiki/Internet_Engineering_Task_Force

인터넷 표준(Internet Standard, STD) 인터넷에 적용되는 기술이나 방법론을 표준으로 제정한 규격.

참고 : https://en.wikipedia.org/wiki/Internet_Standard 공식문서 : https://www.rfc-editor.org/standards

NAT (Network Address Translation) 여러 대의 컴퓨터가 IP 주소를 공유하도록 하는 기술 : https://developer.mozilla.org/ko/docs/Glossary/NAT 공인 IP 부족을 해결하는 기술 : https://en.wikipedia.org/wiki/Network_address_translation

but. 얘 때문에 P2P 연결이 까다로워짐.

ICE (Interactive Connectivity Establishment)

https://datatracker.ietf.org/doc/html/rfc8445

P2P 네트워킹에서 두 컴퓨터가 가능한 한 직접적으로 서로 통신할 수 있는 방법을 찾기 위해 컴퓨터 네트워킹에 사용되는 기술

공식문서 기반 Gemini 설명

ICE란 무엇인가? (초간단 비유)

일단 개념부터 잡고 가자. ICE는 Interactive Connectivity Establishment의 약자야. 우리말로 하면 '상호 연결성 확립' 정도 되겠네.

쉽게 비유를 들어볼게.

네가 아파트 단지(사설망, Private Network)에 사는 친구(Peer)에게 전화를 걸고 싶다고 해보자.

1. 직접 전화 (Host Candidate): 친구의 집 전화번호(내부 IP)를 알면 바로 걸 수 있겠지. 하지만 너도 다른 아파트 단지에 산다면, 같은 동네가 아닌 이상 그 번호는 소용이 없어.

2. 경비실 통해 연결 (Server-Reflexive Candidate): 친구 집 전화번호를 모르니, 친구네 아파트 경비실(STUN 서버)에 전화를 걸어서 "XX동 OOO호 사는 친구 좀 연결해주세요"라고 하는 거야. 그럼 경비실이 친구 집으로 연결해주면서, 외부에서 전화할 수 있는 대표 번호(공인 IP 주소)를 알려주지.

3. 교환원 통해 연결 (Relayed Candidate): 경비실을 통해서도 연결이 안 되는 아주 보안이 철저한 아파트(대칭형 NAT 등)도 있어. 이럴 땐 외부 통신을 중계해주는 교환원(TURN 서버)을 쓰는 거야. 너는 교환원에게 전화하고, 교환원이 다시 친구에게 전화를 걸어서 서로 통화하게 해주는 거지. 이건 확실하지만, 교환원을 거치니 조금 느리고 비용(서버 트래픽)이 발생해.

ICE는 바로 이 모든 방법을 다 시도해서, 너와 친구가 통신할 수 있는 가장 빠르고 효율적인 경로를 찾아내는 프로토콜이야. 핵심은 '될 때까지 다 해본다'는 아주 적극적인 방식이라는 거지.

ICE의 작동 원리 (4단계)

ICE는 크게 4단계로 동작해. RFC 8445 문서의 핵심 내용이기도 하지.

1단계: 후보 수집 (Candidate Gathering)

각 클라이언트(Peer)는 자신이 통신에 사용할 수 있는 모든 주소, 즉 후보(Candidate)들을 수집해. 위 비유에서 말한 방법들이 다 동원돼.

• Host Candidate: 자신의 네트워크 카드에 할당된 IP 주소 (내부 IP). 같은 네트워크에 있다면 가장 빠른 경로야.

• Server-Reflexive Candidate: STUN 서버에 요청을 보내서 알아낸 자신의 공인 IP 주소. 대부분의 가정집이나 사무실 환경(NAT 환경)에서 필요해.

• Relayed Candidate: TURN 서버를 통해 할당받은 중계 주소. 가장 강력한 최후의 보루야. 어떤 네트워크 환경에서도 통신을 가능하게 해주지.

이렇게 수집한 후보 리스트를 만들어. 각 후보는 우선순위(priority)를 가지는데, 보통 Host > Server-Reflexive > Relayed 순으로 높아. 직접 연결하는 게 가장 좋으니까.

2단계: 후보 교환 (Candidate Exchange)

이제 각자 수집한 후보 리스트를 상대방에게 알려줘야 해. 이건 ICE 프로토콜 자체의 역할은 아니고, SIP나 WebSocket 같은 신호(Signaling) 프로토콜을 통해 이뤄져. 보통 SDP(Session Description Protocol)라는 형식에 담아서 교환하지.

나(Peer A): "안녕? 나랑 통화하려면 여기로 연락해봐. 내 후보들은 A, B, C야."

너(Peer B): "오케이! 내 후보들은 X, Y, Z야. 너도 참고해."

이제 양쪽 모두 자신과 상대방의 모든 후보 주소 목록을 갖게 됐어.

3단계: 연결성 검사 (Connectivity Checks)

이 단계가 ICE의 핵심이야. 서로의 후보들을 조합해서 후보 쌍(Candidate Pair)을 만들어. 예를 들면 (A, X), (A, Y), (B, X), (B, Y) ... 이런 식으로 모든 조합을 만드는 거지.

그리고 우선순위가 높은 후보 쌍부터 차례대로 STUN 프로토콜을 이용해서 연결을 시도해봐.

나(A) -> 너(X) 에게: "STUN 요청 보낸다! 들리니?"

너(X) -> 나(A) 에게: "어, 잘 받았어! STUN 응답 보낸다!"

이 요청과 응답이 성공적으로 오가면, 해당 후보 쌍은 유효(Valid)하다고 판단하고 '유효 리스트(Valid List)'에 추가해. 이 과정에서 새로운 후보가 발견되기도 하는데, 이걸 Peer-Reflexive Candidate라고 해. 내가 보낸 요청을 받은 상대방이 "어? 네가 나한테 보낸 주소는 내가 아는 네 공인 주소랑 다른데? 실제로는 이 주소로 왔어" 라고 알려주는 거지. 이것도 아주 중요한 통신 경로가 될 수 있어.

4단계: 후보 쌍 지명 및 ICE 종료 (Nominating Pairs & Concluding)

연결성 검사를 통해 유효한 경로들을 여러 개 찾았을 수 있잖아? 그럼 이제 둘 중 하나의 제어 에이전트(Controlling Agent)가 최종적으로 사용할 경로를 하나 지명(Nominate) 해야 해.

나(Controlling): "여러 경로를 테스트해보니 (B, Y) 경로가 제일 좋은 것 같아. 앞으로 이걸로 통신하자!"

제어 에이전트는 STUN 요청에 USE-CANDIDATE 라는 특별한 플래그를 붙여서 보내. 이 요청을 받은 상대방(Controlled Agent)도 동의하면, 이 후보 쌍이 선택된 쌍(Selected Pair)이 되고, 앞으로 모든 데이터는 이 경로를 통해 오가게 돼.

ICE 프로세스가 성공적으로 끝나면, 다른 후보들은 정리하고 선택된 경로로만 통신을 유지하는 거야.

왜 이런 기능이 필요할까? (의문점 파헤치기)

RFC 문서를 읽다 보면 '이건 왜 이렇게 복잡하게 만들었지?' 싶은 부분이 있을 거야. 몇 가지 중요한 것들을 짚어줄게.

❓ 왜 후보마다 복잡한 우선순위(Priority)를 계산할까?

• 이유: 효율성 때문이야. 수십 개의 후보 쌍을 무작위로 테스트하면 가장 좋은 경로를 찾기까지 너무 오래 걸려. 그래서 RFC 5.1.2.1에 나오는 공식 priority = (2^24)*(type preference) + (2^8)*(local preference) + (2^0)*(256 - component ID) 을 사용해.

• 상황: 이 공식을 통해 양쪽 피어가 거의 동일한 순서로 테스트를 진행하게 돼. Host(직접) > Peer-Reflexive > Server-Reflexive(NAT 통과) > Relayed(중계) 순으로 우선순위를 부여해서, 가장 빠르고 비용이 적게 드는 경로를 먼저 시도하게 만드는 거지. 이렇게 함으로써 통화 연결 시간을 단축시킬 수 있어.

❓ 왜 주기적으로 Keepalive 메시지를 보낼까?

• 이유: NAT 장비가 길을 잊어버리기 때문이야. NAT는 일정 시간 동안 트래픽이 없으면 만들어뒀던 '내부 IP <-> 공인 IP' 매핑 정보를 삭제해버려. 이걸 NAT 바인딩 타임아웃이라고 해.

• 상황: 통화 중에 잠시 말을 안 하면(Silence Suppression) 데이터 전송이 멈추겠지? 그때 NAT가 연결을 끊어버리면 상대방 목소리가 다시 들리지 않게 돼. 이걸 막기 위해 RFC 11장에 따라 보통 15초마다 작은 STUN 패킷(Binding Indication)을 보내서 "나 아직 이 경로 쓰고 있어!"라고 NAT에게 알려주는 거야.

❓ Lite 구현과 Full 구현은 왜 나뉘어 있나?

• 이유: 모든 장치가 복잡한 ICE 로직을 다 구현할 필요는 없기 때문이야.

• 상황: 예를 들어, 항상 공인 IP를 사용하는 서버(미디어 서버 등)가 있다고 해보자. 이 서버는 NAT 뒤에 있는 클라이언트처럼 복잡하게 자기 주소를 찾을 필요가 없어. 이런 서버는 Lite 버전만 구현해서, 들어오는 연결성 검사에 응답만 잘 해주면 돼. 반면, 일반 사용자 PC나 스마트폰은 언제 어디서든 접속해야 하니 모든 기능을 갖춘 Full 버전을 구현해야 하는 거지. 이렇게 역할을 나눠서 구현의 부담을 줄여주는 거야.

❓ ice2 옵션은 무엇이고 왜 필요한가?

• 이유: 프로토콜 버전 관리 및 하위 호환성 때문이야.

• 상황: 현재 표준인 RFC 8445는 이전 버전인 RFC 5245에서 일부 기능을 개선하고 변경했어. 가장 큰 차이는 '공격적 지명(Aggressive Nomination)'이라는 절차가 사라진 거야. ice2 옵션은 후보 교환 시 "나는 새로운 RFC 8445 규격을 따르는 에이전트야"라고 상대방에게 알려주는 신호야. 이 신호를 받은 구버전 에이전트는 호환되지 않는 기능을 사용하지 않게 되어 통신 오류를 막을 수 있어.

❓ STUN 사용자 이름(Username)은 왜 그렇게 중요할까? (보안 그 이상)

• 이유: 이건 단순히 인증을 넘어, 잘못된 상대와 연결되는 것을 막기 위한 핵심 장치야.

• 상황: (RFC 부록 B.4 참조) A, B 두 회사가 있다고 치자. 두 회사 모두 내부망에서 192.168.1.10 이라는 IP를 쓰는 직원이 있을 수 있어. A사의 '철수'가 B사의 '영희'에게 연결을 시도하는데, 신호가 잘못 전달되어 같은 A사에 있는 '민수'의 후보 정보가 전달됐다고 생각해봐. 철수는 영희의 주소라고 생각하고 192.168.1.10으로 연결성 검사를 보냈는데, 그게 민수에게 도착할 수 있어. 이때, 후보 교환 시 주고받은 무작위 username 값이 다르면 민수의 ICE 클라이언트는 "어? 이거 내 거 아닌데?" 하고 요청을 거부해. 만약 이 장치가 없다면, 철수는 영희가 아닌 민수와 연결될 뻔한 거지!

ICE는 네트워크 환경의 불확실성을 극복하기 위해 만들어진 아주 똑똑하고 실용적인 프로토콜이야. 처음에는 용어도 많고 절차도 복잡해 보이지만, 각 단계와 기능이 왜 필요한지 이해하고 나면 전체 그림이 보일 거야. 궁금한 거 있으면 언제든지 다시 물어보라고.

WebRTC

추가 참고 공식문서 https://www.rfc-editor.org/rfc/rfc7742.html

공식 홈페이지 : https://www.ydlidar.com/ 공식 github : https://github.com/YDLIDAR/YDLidar-SDK

사용한 LiDAR 버전은 X4-Pro

윈도우에서는 build가 너무 힘들어서 WSL을 사용

USB 포트 연결

1. WSL 20.04 설치 및 등록
2. VSCode에서 연결
3. Powershell 관리자 모드로 열기
4. win-usbipd 설치^[https://github.com/dorssel/usbipd-win]

   winget install usbipd

5. 설치가 완료되면 Powershell 관리자 모드로 새로 창 열고 기존 창은 닫기
6. usb 포트 확인하기

   usbipd list

7. 연결할 포트 번호 확인해서 공유로 변경

   usbipd bind --busid 3-2

8. 공유가 가능한 포트 wsl에 연결

   usbipd attach --wsl --busid 3-2

9. 다시 WSL로 돌아가서 확인해보기

   lsusb

Cmake 세팅

sudo apt update && sudo apt upgrade -y
sudo apt install git cmake g++ build--essential swig

Python 세팅

sudo apt install python3-pip

YDLidar 설치

cd ~
git clone https://github.com/YDLIDAR/YDLidar-SDK.git

cd ~/YDLidar-SDK
mkdir build

cd build
cmake ..
make
sudo make install

cd ~/YDLidar-SDK
sudo python3 setup.py install

추가 정보

YDLiDAR의 SDK API for Developers를 확인하면 파라미터 테이블이 있다. 하지만 여기에는 X4-Pro의 파라미터가 없어 사용할 수 없었다.

이를 해결하기 위해 깃허브를 탐색했고, 그 결과 YDLiDAR ROS2에서 힌트를 얻을 수 있었다.

X4와의 차이점은 isSingleChannel과 support_motor_dtr 였고 이를

dir(ydlidar)

를 통해 유사한 함수를 찾았고, 해당 파라미터 옵션을 세팅하니 동작하여 X4-Pro를 사용할 수 있었다.

OAuth2.0이란?

참고 : https://datatracker.ietf.org/doc/html/rfc6749#section-1.1

사진으로 보는 프로토콜 요약

개요

OAuth는 인가 계층(authorization layer)을 도입하고 클라이언트의 역할과 리소스 소유자의 역할을 분리함으로써 이러한 문제들을 해결합니다.

1. OAuth에서 클라이언트는 리소스 소유자에 의해 제어되고 리소스 서버에 의해 호스팅되는 리소스에 대한 접근을 요청하며, 리소스 소유자의 자격 증명과는 다른 별개의 자격 증명 집합을 발급받습니다.
2. 리소스 소유자의 자격 증명을 사용하여 보호된 리소스에 접근하는 대신, 클라이언트는 액세스 토큰—특정 범위, 수명 및 기타 접근 속성을 나타내는 문자열—을 획득합니다.
3. 액세스 토큰은 리소스 소유자의 승인을 받아 인가 서버에 의해 제3자 클라이언트에게 발급됩니다.
4. 클라이언트는 이 액세스 토큰을 사용하여 리소스 서버가 호스팅하는 보호된 리소스에 접근합니다.

예를 들어, 최종 사용자(리소스 소유자)는 인쇄 서비스(클라이언트)에 자신의 사용자 이름과 비밀번호를 공유하지 않고도 사진 공유 서비스(리소스 서버)에 저장된 자신의 보호된 사진에 대한 접근 권한을 부여할 수 있습니다. 대신, 그녀는 사진 공유 서비스가 신뢰하는 서버(인가 서버)에 직접 인증하고, 이 서버는 인쇄 서비스에 위임 관련 특정 자격 증명(액세스 토큰)을 발급합니다.

이 명세는 HTTP([RFC2616])와 함께 사용하도록 설계되었습니다. HTTP 이외의 프로토콜을 통한 OAuth의 사용은 이 문서의 범위를 벗어납니다.

정보 문서로 발표된 OAuth 1.0 프로토콜([RFC5849])은 소규모의 임시 커뮤니티 노력의 결과물이었습니다. 이 표준 트랙 명세는 OAuth 1.0의 배포 경험뿐만 아니라, 더 넓은 IETF 커뮤니티로부터 수집된 추가적인 사용 사례 및 확장성 요구사항을 기반으로 합니다. OAuth 2.0 프로토콜은 OAuth 1.0과 하위 호환되지 않습니다. 두 버전은 네트워크 상에서 공존할 수 있으며, 구현체는 둘 다 지원하도록 선택할 수 있습니다. 그러나 이 명세의 의도는 새로운 구현이 이 문서에 명시된 대로 OAuth 2.0을 지원하고, OAuth 1.0은 기존 배포를 지원하기 위해서만 사용되도록 하는 것입니다. OAuth 2.0 프로토콜은 OAuth 1.0 프로토콜과 구현 세부 사항을 거의 공유하지 않습니다. OAuth 1.0에 익숙한 구현자는 이 문서의 구조와 세부 사항에 대한 어떠한 가정도 없이 접근해야 합니다.

나의 비유

사용자가 가게에서 어떤 물건을 구매하고자 한다. 사용자의 돈은 모두 은행에 있다.

이 상황에서 금액을 지불하기 위해 사용자가 자신의 “계좌번호”와 “비밀번호”를 달려주는 것은 최악이다.

가게 사장이 물건 값 이상의 비용을 출금할 수 있기 때문이다. 이를 방지하기 위해 사용자는 수표를 써주기로 한다.

1. 수표에 “누가” 돈을 “얼마나” 출금할 수 있게 허가하는지 본인이 돈을 저축해둔 "은행”에서 수표를 작성해준다.
2. 이를 가게 사장에게 제공하면 가게 사장은 해당 은행에 수표를 들고 가서 제출하고, 은행에서는 금고 접근 허가증을 발급해준다.
3. 허가증을 가지고 가게 사장이 금고에 가면 금고 보안 요원이 허가증에 적힌 금액만큼 돈을 꺼내서 가게 사장에게 준다. 이를 받은 가게 사장은 사용자에게 물건을 제공한다.

Gemini로 이해하는 예제 및 설명

👨‍💻 초보 개발자도 이해하는 OAuth 2.0: 구글 소셜 로그인 파헤치기

안녕하세요! 이제 막 개발의 세계에 발을 들인 여러분을 위해, '인증'과 '인가'라는 복잡해 보이는 산을 함께 넘어보려 합니다. 그중에서도 현대 웹 서비스의 필수 기능인 OAuth 2.0에 대해 알아보겠습니다. RFC 6749 문서는 그 표준 명세지만, 처음 보면 외계어 같을 수 있죠. 제가 실제 '구글 소셜 로그인'이 어떻게 동작하는지 보여드리면서 쉽고 재미있게 풀어드리겠습니다.

🤔 OAuth 2.0, 대체 왜 필요한가요?

옛날 옛적, '찍스타그램'이라는 사진 편집 앱이 있다고 상상해봅시다. 이 앱은 여러분의 구글 포토에 있는 사진을 가져와서 편집하고 싶어 합니다. 어떻게 해야 할까요?

• 나쁜 방법 👎: '찍스타그램' 앱에 여러분의 구글 아이디와 비밀번호를 직접 알려준다.
• 문제점:
  1. 비밀번호 유출 위험: '찍스타그램'이 해킹당하면 내 구글 계정 정보가 통째로 넘어갑니다.
  2. 과도한 권한: '찍스타그램'은 사진만 필요한데, 내 이메일, 주소록, 구글 드라이브 파일까지 모두 접근할 수 있게 됩니다.
  3. 접근 차단 불가: '찍스타그램'의 접근만 막고 싶어도, 구글 비밀번호를 바꾸는 수밖에 없습니다. 그럼 다른 모든 서비스에서도 비밀번호를 바꿔야 하죠.

이런 끔찍한 문제를 해결하기 위해 등장한 것이 바로 OAuth (Open Authorization) 입니다. OAuth는 "비밀번호를 직접 주지 않고, 특정 권한만 제한적으로 부여하는 똑똑한 위임 방식"이라고 할 수 있습니다. 마치 호텔 룸키처럼, 레스토랑이나 수영장은 이용할 수 있지만 다른 손님의 방은 열 수 없는 '제한된 키'를 발급해주는 것과 같습니다.

등장인물 (Roles): OAuth 2.0의 4가지 역할

OAuth 2.0에는 4명의 주요 등장인물이 있습니다. 구글 로그인 예시와 함께 살펴보죠.

1. Resource Owner (자원 소유자):
   • 설명: 보호된 자원(개인정보, 사진, 이메일 등)의 주인입니다.
   • 구글 로그인 예시: 바로 '나' 자신, 즉 서비스를 이용하려는 사용자입니다.
2. Client (클라이언트):
   • 설명: 자원 소유자를 대신해 특정 자원에 접근하려고 요청하는 애플리케이션입니다.
   • 구글 로그인 예시: 우리가 로그인하려는 웹사이트나 앱 (예: awesome-service.com)
3. Authorization Server (권한 서버):
   • 설명: 자원 소유자를 인증하고, 클라이언트에게 액세스 토큰(Access Token)을 발급해주는 서버입니다. "너는 이 권한을 가져도 좋아"라고 허락해주는 주체죠.
   • 구글 로그인 예시: Google의 인증/권한 서버 (accounts.google.com)
4. Resource Server (자원 서버):
   • 설명: 보호된 자원을 실제로 가지고 있는 서버입니다. 액세스 토큰을 확인하고 요청에 응답합니다.
   • 구글 로그인 예시: Google의 API 서버 (예: 사용자의 프로필 정보를 제공하는 googleapis.com)

💡 Tip: 많은 경우, 권한 서버와 자원 서버는 같은 회사(Google)에 의해 운영되지만, 역할은 명확히 구분됩니다.

🔑 핵심 아이템: 토큰(Token)이란?

OAuth 2.0의 핵심은 '토큰'이라는 특별한 열쇠를 주고받는 것입니다.

• Access Token (액세스 토큰):
  • 자원 서버에 접근할 수 있는 임시 출입증입니다.
  • 수명이 짧고(예: 1시간), "프로필 정보 읽기"와 같이 제한된 권한만 담고 있습니다.
  • 클라이언트(앱)는 이 토큰을 가지고 자원 서버(Google API)에 가서 "이 출입증 보여줄 테니, OOO님의 프로필 정보 좀 주세요!"라고 요청합니다.
• Refresh Token (리프레시 토큰):
  • 액세스 토큰의 유효기간이 만료되었을 때, 새로운 액세스 토큰을 발급받기 위한 티켓입니다.
  • 수명이 길며(예: 6개월), 사용자가 다시 로그인하는 번거로움 없이 서비스를 계속 이용하게 해줍니다.
  • 액세스 토큰이 만료되면, 클라이언트는 이 리프레시 토큰을 권한 서버(Google)에 보내 "티켓 여기 있으니, 새 출입증(액세스 토큰)으로 바꿔주세요"라고 요청합니다.

🚀 구글 소셜 로그인 과정 (Authorization Code Grant 방식)

이제 모든 조각을 맞춰봅시다. OAuth 2.0의 가장 표준적이고 안전한 방식인 'Authorization Code Grant' 흐름을 통해 구글 소셜 로그인이 어떻게 이루어지는지 단계별로 살펴보겠습니다. (RFC 6749, Section 4.1)

1단계: 사용자의 로그인 요청

나 (Resource Owner)는 awesome-service.com(Client)에서 "Google로 로그인하기" 버튼을 클릭합니다.

이 간단한 클릭이 모든 여정의 시작입니다!

2단계: 권한 요청을 위한 Google로의 이동

awesome-service.com(Client)은 나를 Google 권한 서버로 보냅니다. 이때 그냥 보내는 게 아니라, 특별한 정보들을 담아서 보냅니다.

실제로는 브라우저가 아래와 같은 URL로 리디렉션됩니다.

https://accounts.google.com/o/oauth2/v2/auth? response_type=code& client_id=YOUR_CLIENT_ID.apps.googleusercontent.com& scope=openid%20profile%20email& redirect_uri=https://awesome-service.com/auth/google/callback& state=a_random_string_to_prevent_csrf

각 파라미터의 의미는 다음과 같습니다.

• response_type=code: "나중에 인증 코드(Authorization Code)를 발급해주세요" 라는 의미입니다. 이게 바로 'Authorization Code Grant' 방식의 핵심입니다.
• client_id: awesome-service.com이 구글에 미리 등록하고 발급받은 고유 식별자입니다. "제가 바로 그 앱이에요!"라고 신분을 밝히는 것이죠. (RFC, Section 2.2)
• scope: 앱이 요청하는 권한의 범위입니다. 여기서는 'openid, profile, email' 정보에 접근하겠다고 요청하고 있습니다. (RFC, Section 3.3)
• redirect_uri: 구글이 인증 절차를 마친 후, 사용자를 다시 돌려보낼 주소입니다. (awesome-service.com의 특정 경로) 보안을 위해 이 주소는 구글에 미리 등록되어 있어야 합니다. (RFC, Section 3.1.2)
• state: CSRF(Cross-Site Request Forgery) 공격을 방지하기 위한 임의의 문자열입니다. 나중에 구글이 이 값을 그대로 돌려주면, awesome-service.com은 자기가 처음에 보낸 값이 맞는지 확인합니다. (RFC, Section 10.12)

3단계: 사용자의 동의

Google 권한 서버는 나에게 로그인 창을 보여줍니다. 로그인을 하면, "awesome-service.com이(가) 내 이름, 이메일 주소, 프로필 사진 등에 액세스하려고 합니다. 동의하시겠습니까?" 라는 동의 화면을 보여줍니다.

여기서 내가 "동의" 버튼을 누르면, 자원에 대한 접근을 허락하는 것입니다.

4단계: Google의 '인증 코드' 발급

내가 동의하면, Google 권한 서버는 2단계에서 지정된 redirect_uri로 나를 다시 돌려보냅니다. 이때 주소 뒤에 아주 짧은 시간만 유효한 임시 인증 코드(code)를 붙여줍니다.

브라우저는 다음 주소로 리디렉션됩니다.

https://awesome-service.com/auth/google/callback?code=A_TEMPORARY_AUTHORIZATION_CODE&state=a_random_string_to_prevent_csrf

중요: 아직 액세스 토큰이 아닙니다! 이건 그저 액세스 토큰으로 교환할 수 있는 '교환권'일 뿐입니다. 이 교환권은 브라우저(사용자)를 통해 전달되므로 비교적 덜 안전한 채널을 거칩니다.

5단계: '인증 코드'로 '액세스 토큰' 요청

awesome-service.com의 백엔드 서버는 브라우저를 통해 전달받은 인증 코드와 자신의 Client Secret(구글에 등록할 때 받은 비밀키)을 가지고, Google 권한 서버의 토큰 엔드포인트(Token Endpoint)에 직접 요청을 보냅니다.

이 과정은 사용자의 브라우저를 거치지 않고, 서버 대 서버로 안전하게 통신합니다. (RFC, Section 4.1.3)

Bash

awesome-service.com 서버가 Google 토큰 서버에 보내는 요청 예시 (curl)

curl --location --request POST 'https://oauth2.googleapis.com/token' \
--header 'Content-Type: application/x-www-form-urlencoded' \
--data-urlencode 'code=A_TEMPORARY_AUTHORIZATION_CODE' \
--data-urlencode 'client_id=YOUR_CLIENT_ID.apps.googleusercontent.com' \
--data-urlencode 'client_secret=YOUR_CLIENT_SECRET' \
--data-urlencode 'redirect_uri=https://awesome-service.com/auth/google/callback' \
--data-urlencode 'grant_type=authorization_code'

• grant_type=authorization_code: "제가 받아온 인증 코드를 드릴 테니, 액세스 토큰으로 바꿔주세요" 라는 의미입니다.

6단계: Google의 '액세스 토큰' 및 '리프레시 토큰' 발급

Google 권한 서버는 인증 코드, client_id, client_secret 등이 모두 유효한지 확인하고, 마침내 액세스 토큰과 리프레시 토큰을 awesome-service.com 서버에게 발급해줍니다.

성공 시 awesome-service.com 서버가 받는 응답(JSON)입니다. (RFC, Section 5.1)

{
  "access_token": "A_REAL_ACCESS_TOKEN_STRING",
  "expires_in": 3599,
  "refresh_token": "A_LONG_LIVED_REFRESH_TOKEN",
  "scope": "openid https://www.googleapis.com/auth/userinfo.profile https://www.googleapis.com/auth/userinfo.email",
  "token_type": "Bearer"
}

이제 awesome-service.com은 드디어 진짜 열쇠(액세스 토큰)를 손에 넣었습니다! 이 토큰들은 서버의 데이터베이스에 안전하게 저장됩니다.

7단계: '액세스 토큰'으로 사용자 정보 요청

awesome-service.com 서버는 발급받은 액세스 토큰을 이용해 Google 자원 서버(API 서버)에 내 프로필 정보를 요청합니다.

awesome-service.com 서버가 Google API 서버에 보내는 요청 예시

curl --location --request GET 'https://www.googleapis.com/oauth2/v2/userinfo' \
--header 'Authorization: Bearer A_REAL_ACCESS_TOKEN_STRING'`

• Authorization: Bearer ...: HTTP 요청 헤더에 "이 Bearer(소지자) 토큰을 가지고 있으니 권한을 확인해주세요" 라는 의미로 액세스 토큰을 담아 보냅니다. (RFC, Section 7)

8단계: 자원 제공 및 로그인 완료

Google 자원 서버는 액세스 토큰이 유효한지 확인하고, awesome-service.com 서버에게 내 프로필 정보(이름, 이메일 등)를 보내줍니다.

이제 awesome-service.com은 내 정보를 받았으므로, 이 정보를 바탕으로 회원가입을 시키거나 로그인을 완료하고 서비스를 제공할 수 있게 됩니다.

✨ 요약 및 결론

복잡해 보이지만 핵심은 간단합니다.

1. "비밀번호를 직접 주지 않는다."
2. 사용자는 Google에 직접 로그인해서 권한을 '동의'만 한다.
3. 앱은 '인증 코드(교환권)'를 임시로 받아온다.
4. 앱의 '서버'가 안전하게 '액세스 토큰(진짜 열쇠)'으로 교환한다.
5. 앱은 이 액세스 토큰으로 허락된 정보(예: 프로필)에만 접근한다.

이것이 바로 OAuth 2.0이 우리의 소중한 정보를 안전하게 지키면서도 편리한 소셜 로그인을 가능하게 하는 원리입니다. 이 흐름을 잘 이해하신다면, 앞으로 API 문서를 보거나 인증 관련 기능을 구현할 때 훨씬 더 자신감을 가질 수 있을 겁니다. 화이팅입니다! 🚀

• 완전 이진 트리에 있는 노드 중에서 키 값이 "가장 큰 노드"(max heap)나 키 값이 "가장 작은 노드"(min heap)를 찾기 위해서 만든 자료구조

개요

최대 힙(max heap)

• 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
• 부모 노드의 키 값 > 자식 노드의 키 값
• 루트 노드: 키 값이 가장 큰 노드

최소 힙(min heap)

• 최대 힙의 반대 개념

예시

<힙 구조 O>

<힙 구조 X>

힙(heap) 연산

1. 삽입

2. 삭제

구현

class MaxHeap:
    def __init__(self):
        self.heap = []

    def heappush(self, item):
        self.heap.append(item)
        self._siftup(len(self.heap) - 1)

    def _siftup(self, idx):
        parent = (idx - 1) // 2
        while idx > 0 and self.heap[idx] > self.heap[parent]:
            self.heap[idx], self.heap[parent] = self.heap[parent], self.heap[idx]
            idx = parent
            parent = (idx - 1) // 2

    def heappop(self):
        if len(self.heap) == 0
            raise IndexError("힙이 비었습니다.")
        if len(self.heap) == 1:
            return self.heap.pop()
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._siftdown(0)
        return root

    def heapify(self, array):
        self.heap = array[:]
        n = len(array)
        for i in range(n // 2 - 1, -1, -1):
            self._siftdown(i)

    def _siftdown(self, idx):
        n = len(self.heap)
        largest = idx
        left = 2 * idx + 1
        right = 2 * idx + 2

        if left < n and self.heap[left] > self.heap[largest]:
            largest = left
        if right < n and self.heap[right] > self.heap[largest]:
            largest = right
        if largest != idx:
            self.heap[idx], self.heap[largest] = self.heap[largest], self.heap[idx]
            self._siftdown(largest)

heapq 모듈

• 최소 힙을 구현한 라이브러리
• 힙 함수 활용
  • heapq.heappush(heap, item) : item을 heap에 추가
  • heapq.heappop(heap) : heap에서 가장 왼쪽 원소를 pop
  • Heapq.heapify(x) : 리스트 x를 heap으로 변환 ( O(N) )

그러면 최대 힙은 어떻게? -> 값들을 모두 음수로 바꾸면 최소 힙으로 최대 힙처럼 사용 가능. 결과의 부호만 잘 처리하면 됨

우선순위 큐 (Priority Queue)

• 우선순위를 가진 항목들을 저장하는 큐
• FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 된다.
• 우선순위 큐를 구현하는 가장 효율적인 방법은 힙을 사용하는 것이다.
• 노드 하나 추가/삭제의 시간 복잡도가 O(logN) 이며, 최대값/최소값을 O(1)에 구할 수 있다.

예시

import heapq

priority_queue = []

heapq.heappush(priority_queue, (3, "3순위 작업"))
heapq.heappush(priority_queue, (1, "1순위 작업"))
heapq.heappush(priority_queue, (2, "2순위 작업"))

print(priority_queue)
# [(1, "1순위 작업"), (3, "3순위 작업"), (2, "2순위 작업")]

while priority_queue:
    task = heapq.heappop(priority_queue):
    print(task)

# (1, "1순위 작업")
# (2, "2순위 작업")
# (3, "3순위 작업")

백트래킹

개요

백트래킹 기법

• 어떤 노드의 유망성(promising)을 점검하여 유망하지 않다면 그 부모의 노드로 돌아가고(backtracking) 다음 자식 노드를 살핀다.
• 유망하다. = 해답이 될 가능성이 있다.
• 가지치기(pruning) = 유망하지 않다면 해당 노드를 가지 않는다. 나무(Tree)의 쓸모없는 가지를 치는 것.

백트래킹 절차

1. 상태 공간 트리의 깊이 우선 탐색(DFS)를 실시한다.
2. 각 노드가 유망한지 점검한다.
3. 만일 해당 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 다른 노드 검색을 계속 진행한다.

백트래킹과 DFS 차이점

• DFS는 완전 탐색이다. 백트래킹은 가지치기를 통해 필요한 요소만 탐색한다. -> DFS를 pruning으로 최적화 하면 그게 백트래킹이다.

일반적인 코드 형태

def backtracking(node v):
    if promising(v):
        if there is a solution at v:
            find the solution
    else:
        for child of v:
            backtracking(child)

NVIDIA GPU가 있어야 사용 가능 윈도우에서 내 GPU 확인하기

nvidia-smi

2. 아키텍쳐 확인 https://en.wikipedia.org/wiki/CUDA#GPUs_supported

3. 아키텍쳐에 맞는 CUDA 버전 확인

본인은 11.1~12.5까지 가능

4. CUDA 버전 및 파이썬 버전에 맞는 Pytorch 버전 확인 https://github.com/pytorch/pytorch/blob/main/RELEASE.md#release-compatibility-matrix

결론 : CUDA 12.1 | CUDNN 9.1.0.70 | Pytorch 2.4 | Python 3.12

5. CUDA 설치 https://developer.nvidia.com/cuda-toolkit-archive

6. CUDA 설치 확인 명령어

   nvcc --version

   

7. 설치할 때 입력한 경로와 실제 설치된 경로가 다르다는 것을 헤매다 블로그를 통해 알게됨. exe로 설치해서 그런듯

   C:\Program Files\NVIDIA GPU Computing Toolkit\CUDA\v12.1

8. CUDNN도 설치 https://developer.nvidia.com/rdp/cudnn-archive

9. 설치된 zip파일의 압축을 해제하고, 안에 있는 bin, include, lib, LICENSE를 전부 복사해서 CUDA에 덮어쓰기

10. 버전에 맞는 Pytorch 설치 https://pytorch.org/get-started/locally/ 밑에 나오는 명령어 가상환경에서 실행

11. Pytorch 버전 확인

    import torch
    print(torch.__version__)

    

12. GPU 연결 확인

    USE_CUDA = torch.cuda.is_available()
    device = torch.device('cuda:0' if USE_CUDA else 'cpu')
    

print('CUDA 사용 가능 여부 :', USE_CUDA) print('현재 사용 device :', device) print('CUDA Index :', torch.cuda.current_device()) print('GPU 이름 :', torch.cuda.get_device_name()) print('GPU 개수 :', torch.cuda.device_count())

![](https://velog.velcdn.com/images/yoo-seunghyeon/post/3f79868b-3f6b-4ea0-9285-2c01430aa7c0/image.png)

아이콘 만드는 사이트 https://shields.io/badges

아이콘 정보를 알 수 있는 사이트 https://simpleicons.org/

shields.io 사용법

추가로 도움 되는 아이콘 사이트

Draw.io 또는 PPT에 사용하기 좋은 아이콘 사이트 https://techicons.dev/

aws --version

AWS Configure 확인

aws sts get-caller-identity

AWS Configure 등록

aws configure

이후 access key 와 secret key 입력하고 나머지 2개의 입력창은 그냥 enter 누르면 됨.

AWS Configure 삭제 명령어가 따로 있는건 아닌듯. 그냥 home 디렉토리에 있는 .aws라는 디렉토리를 지우면 됨.

# 데이터베이스 생성 방식 선택 : 표준 생성
# 엔진 옵션 : MySQL -> 확장지원, 다중 AZ, 최적화된 쓰기를 ... 모두 비활성화
# 템플릿 : 프리티어
# 가용성 및 내구성 : 템플릿을 프리티어로 하면 모두 비활성화 됨.
# 설정
- DB 인스턴스 식별자 : 소문자로 원하는 이름 지정
- 자격 증명 설정
-> 마스터 사용자 이름 : admin | root 쓰는게 편해보임.
-> 자격 증명 관리 : 자체 관리
-> 암호 자동 생성 : 비활성화
-> 마스터 암호 : [알아서 입력]
-> 마스터 암호 확인 : [알아서 입력]
# 인스턴스 구성
- 모두 비활성화, 프리티어 템플릿 사용하면 자동으로 다 비활성화 되어 있음.
- 인스턴스만 "db.t3.micro" 쓰는게 속편함.
# 스토리지
- 스토리지 유형 : 안전하게 gp2 사용하는게 속편함.
- 할당된 스토리지 : 20~6144GiB 인데 20이 제일 편함.
- 고급 설정 : 프리티어 템플릿이면 자동으로 비활성화
- 스토리지 자동 조정
-> 스토리지 자동 조정 활성화 : 비활성화로 바꿀 필요 있음
# 연결
- 컴퓨팅 리소스 : 원하는거 선택. 본인은 EC2 컴퓨팅 리소스에 연결 안함 선택
- 네트워크 유형 : IPv4
- Virtual Private Cloud(VPC) : 자신의 VPC 선택
- DB 서브넷 그룹 : 생성하기로 생성
- 퍼블릭 액세스 : 테스트 용도로 쓸거라 허용했음.
- VPC 보안 그룹(방화벽) : DB용 보안 그룹 생성해둔거 사용
- 가용 영역 : 앞서 만들어둔 2개의 subnet 중 하나 선택
- RDS 프록시 : 비활성화
- 인증 기관 : 기본값
- 추가구성
-> 포트 : 3306이 기본값. 그대로 사용
# 태그
- 새 태그 추가 : Name 태그를 통해 이름 설정
# 데이터베이스 싱증
- 데이터베이스 인증 옵션 : 암호 인증 선택
# 모니터링
- 아직은 비활성화
# 추가 구성
- 데이터 베이스 옵션
-> 초기 데이터베이스 이름 : 입력해서 생성함
-> DB 파라미터 그룹 : 그대로
-> 옵션 그룹 : 그대로
- 백업 : 비활성화
- 암호화 : 비활성화
- 로그 내보내기 : 전부 비활성화
- IAM 역할 : 비활성화 (CloudWatch 쓸거면 세팅해야한다고 함.)
- 유지 관리
-> 마이너 버전 자동 업그레이드 사용 : 비활성화
- 유지 관리 기간 : 기본 설정 없음
- 삭제 방지 : 비활성화

Estimated Monthly costs

위와 같이 세팅하면 이렇게 나온다.

주의할점은 VPC에서 서로 다른 AZ에 Subnet을 각각 하나씩 2개 이상은 만들어 둬야지 RDS가 만들어진다.

What?

• 머신러닝의 지도학습 알고리즘 중 하나.
• 새로운 데이터 포인트에서 가장 가까운 k개의 이웃을 찾고, 가장 빈도가 높은 클래스를 예측값으로 사용하는 알고리즘.

When?

• 데이터를 분류하거나 회귀할 때.

장단점

장점

1. 이해하기 쉽다.
2. 적은 조정으로 좋은 성능을 발휘한다.

단점

1. 훈련 세트가 매우 크면 예측이 느려짐.
2. 많은 특성을 가진 데이터셋에는 잘 동작하지 않음.
3. 특성 값 대부분이 0인 데이터셋과는 특히 잘 동작하지 않음.

How?

# 필요한 라이브러리 import
from sklearn.datasets import load_iris                     # 데이터
from sklearn.model_selection import train_test_split     # 데이터 분할
from sklearn.neighbors import KNeighborsClassifier         # K-최근접 알고리즘 모듈

# 데이터 가져오기
iris_datasets = load_iris()

# 학습용, 테스트용 으로 데이터 분할 (75%, 25%)
X_train, X_test, y_train, y_test = train_test_split(iris_dataset['data'], iris_dataset['target'], random_state=0)

# K-최근접 이웃 알고리즘 적용. 학습용 데이터 사용
knn = KNeighborsClassifier(n_neighbors=1)                # k=1 적용
knn.fit(X_train, y_train)

# 정확도 측정. 테스트용 데이터 사용
print("테스트 세트의 정확도 : {.2f}".format(knn.score(X_test,y_test)))

What?

• 입력과 출력 샘플 데이터가 있고, 주어진 입력으로부터 출력을 예측하는 머신러닝 방법.

종류

[1] 분류

What? 미리 정의된, 가능성 있는 여러 클래스 레이블 중 하나를 예측하는 것.

종류

1. 이진 분류 : 딱 두 개의 클래스로 분류 (예/아니오)
2. 다중 분류 : 셋 이상의 클래스로 분류

[2] 회귀

What? 연속적인 숫자를 예측하는 것.

핵심 키워드

[1] 일반화

모델이 처음 보는 데이터에 대해 정확하게 예측할 수 있는 것 ( = 훈련 데이터, 테스트 데이터 모두 잘 예측하는 것)

[2] 과대적합

모델이 훈련 데이터에 너무 가깝게 맞춰져서 일반화가 안되는 것 ( = 훈련 데이터는 잘 예측하나 테스트 데이터는 잘 예측하지 못하는 것)

[3] 과소적합

모델이 너무 간단해서 데이터의 면면과 다양성을 잡아내지 못하는 것 ( = 훈련 데이터, 테스트 데이터 모두 잘 예측하지 못하는 상태)

AWS 강의실 - 인증서 없이 HTTP 웹사이트를 HTTPS로 바꾸는 2가지 방법 https://youtu.be/WS2n8mkrFaY?si=-abefK4zcoraHcge

루트 노드의 자식 노드들을 먼저 모두 차례로 방문한 후, 방문했던 자식 노드들을 기준으로 하여 다시 해당 노드의 자식 노드들을 차례로 방문하는 방식

인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 큐가 적합함

간단한 트리에서의 BFS

from collections import deque

def bfs_tree(tree, root_node):
    queue = deque([root_node])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        if node not in tree: continue

        for child in tree[node]:
            queue.append(child)

    return result

tree = {
    'A': ['B', 'C', 'D'],
    'B': ['E', 'F'],
    'D': ['G', 'H', 'I']
}

root_node = 'A'

result = bfs_tree(tree, root_node)

print(' '.join(result))

BFS - 그래프

Tree BFS와 전체적으로 동일하나 방문 여부를 확인해야 한다.

그래프 BFS 코드

from collections import deque

def bfs(start):
    nodes = list(graph.keys())
    visited = [False] * len(nodes)
    queue = deque([start])
    result = []

    start_index = nodes.index(start)
    visited[start_index] = True

    while queue:
        vertex = queue.popleft()
        result.append(vertex)

        for neighbor in graph[vertex]:
            neighbor_index = nodes.index(neighbor)
            if not visited[neighbor_index]:
                queue.append(neighbor)
                visited[neighbor_index] = True

    return result

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A'],
    'D': ['B', 'F'],
    'E': ['B', 'F'],
    'F': ['D', 'E', 'G'],
    'G': ['F'],
}
nodes = list(graph.keys())
visited = [False] * len(nodes)
result = []
for node in nodes:
    if not visited[nodes.index(node)]:
        result.extend(bfs(node))
print("그래프 탐색 경로:", result)

비선형구조(= 트리, 그래프)의 각 노드(정점)를 중복되지 않게 "전부" 방문하는 것을 의미함.

선형구조와 다르게 선후 연결 관계를 알 수 없다. => 특별한 방법이 필요하다

두 가지 방법

1. 깊이 우선 탐색 (Depth First Search, DFS)
2. 너비 우선 탐색 (Breadth First Search, BFS)

DFS (Depth First Search)

• 루트 노드에서 출발하여 한 방향으로 갈 수 있는 곳까지 "깊이 탐색"을 하고, 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와서 다른 방향의 노드로 탐색을 계속 반복하여 결국 모든 노드를 방문하는 순회 방법

• 가장 마지막에 만났던 갈림길의 노드로 되돌아 가서 다시 깊이 우석 탐색을 반복 => 재귀 or 스택 으로 구현 가능

간단한 트리 DFS 코드

tree = {'A': ['B', 'C', 'D'],
        'B': ['E', 'F'],
        'D': ['G', 'H', 'I']}

def dfs(tree, node):
    print(node) # 방문한 노드 출력

    if node not in tree: # 자식 노드가 없으면 종료
        return

    for child in tree[node]: # 자식 노드들을 순서대로 다시 탐색
        dfs(tree, child)

dfs(tree, 'A')

DFS - 그래프

시작 정점에서 출발하여 한 방향으로 갈 수 있는 곳까지 "깊이 탐색"을 진행하고, 더 이상 갈 곳이 없다면 가장 마지막 갈림길 간선이 있는 정점에서 다시 "깊이 탐색"을 진행하는 흐름은 같음.

하지만 자식 노드라는 관계가 없기 때문에 "방문여부"를 체크한다.

간단한 그래프 DFS 코드

N = 5  # 정점의 수
# 인접 행렬로 그래프 표현
adj_matrix = [
    [0, 1, 1, 0, 0]
    [1, 0, 0, 1, 1],
    [1, 0, 0, 0, 1],
    [0, 1, 0, 0, 1],
    [0, 1, 1, 1, 0]
]
visited = [False] * N

def dfs(current, adj_matix, visited):
    visited[current] = True

    for i in range(len(adj_matrix)):
        # 현재 정점과 연결되어 있고, 아직 방문하지 않은 정점이라면
        if adj_matrix[current][i] and not visited[i]:
            dfs(i, adj_matrix, visited)

# 연결되어 있지 않은 정점을 위해 모든 정점에 대해 dfs 실행
for i in range(N):
    if visited[i]:
        continue

    dfs(0, adj_matrix, visited)

로그 데이터를 수정하고, DB의 구성과 Front에 자신의 평가 지표가 보이는 등 두 번째 배포를 진행했습니다.

이러한 형태로 진행이 되었습니다.

추가로 분석페이지를 설계하여 제작중에 있습니다.

하지만 이번 배포의 가장 중요한 사항은 바로 서버에 모니터링 시스템을 도입한 것이라고 생각합니다.

서버 모니터링

서버를 운영하면서 사용자가 몰릴때 서버가 어느정도 부하가 가해지는지 궁금했고 이를 위해 NetData를 도입했습니다.

NetData는 특별한 설치 없이 모니터링 시스템을 웹 브라우저를 통해 볼 수 있는 오픈소스 프로그램입니다.

bash <(curl -SsL https://my-netdata.io/kickstart.sh)

sudo ufw allow 19999/tcp

그리고 외부에서도 모니터링이 가능하게 nginx도 수정했습니다.

location /netdata/ {
    proxy_pass http://localhost:19999/;
    proxy_set_header Host $host;
    proxy_set_header X-Real-IP $remote_addr;
    proxy_http_version 1.1;
    proxy_pass_request_headers on;
    proxy_set_header Connection "keep-alive";
}

이를 세팅하고 모니터링을 진행한 결과 큰 문제를 발견했습니다. 아무 접속자가 없을 때 CPU 사용률이 66% 이상인 것을 확인했습니다. 이를 이상하게 생각하여 조사한 결과 uvicorn을 실행할 때 사용한 --reload 옵션이 문제임을 알았습니다.

그래서 이를 해결하면서 추가로 서버를 종료했다가 실행해도 바로 동작하도록 세팅을 진행했습니다. 이를 적용하여 fastapi를 백그라운드에서 실행하고 cpu 사용률을 측정한 결과는 다음과 같았습니다.

앞서 아무런 사용자가 없어도 6680%까지 오가던 cpu 사용량이 10% 미만으로 확 줄어버렸습니다.(2025.04.11)~~ 다시 확인한 결과 그대로 60% 대를 유지하고 있었습니다. 그 원인을 파악중에 있습니다. (2025.04.12)

사용한 스크립트는 다음과 같습니다.

sudo nano /etc/systemd/system/fastapi.service

해당 경로에 파일을 생성하고, 다음과 같이 스크립트를 작성했습니다.

[Unit]
Description=FastAPI Server (Uvicorn)
After=network.target

[Service]
User=ssabab
WorkingDirectory=/home/ssabab/바탕화면/projects/ssabab/back-end
ExecStart=/home/ssabab/바탕화면/projects/ssabab/back-end/venv/bin/uvicorn app.main:app --host 127.0.0.1 --port 8000 --proxy-headers --forwarded-allow-ips="*"

Restart=always
RestartSec=3

[Install]
WantedBy=multi-user.target

이후 스크립트를 등록하기 위해 아래의 명령어를 실행하면 모든 적용이 끝납니다.

sudo systemctl daemon-reload
sudo systemctl enable fastapi
sudo systemctl start fastapi

덕분에 저희는 지속적인 모니터링이 가능했고, 이를 통해 수집되는 log 또한 추후 활용할 예정입니다.

URL : https://ssabab.com GitHub : https://github.com/haeri-ne

소개

싸피 대전 캠퍼스의 식단에 대한 선호도를 조사하는 앱

구성

App : Vue(Front) + FastAPI(Back) + Sqlite(DB) Infra : Vercel(Front) + AWS EC2(Back, DB) + S3(DB Backup)

팀원

김*리(Front), 황*혁(Back), 유승현(Infra)

SDS (요약)

문제 발생

1. Front .env파일의 중요성 배포할 때 모든 url을 전부 서버 도메인으로 바꾸면서 굉장히 후회했습니다. 이를 계기로 .env를 도입했고, Vite의 경우 환경변수 앞에 꼭 VITE_ 가 붙어야 한다는 사실을 알았습니다.
2. Nginx와 SSL 기존의 계획은 EC2가 아니라, 제 개인 PC를 24시간 돌릴 예정이었습니다. 하지만 Nginx 세팅이 너무 힘들어서 2일간 시도하고, 일단 EC2로 배포를 하자고 결정했습니다.
3. 코딩 전 설계 부족 SDS를 작성하면서 설계를 충분히 했다 생각했으나, 프로그램을 만들고 보니 생각보다 구조가 효율적이지 못했습니다. 예를 들어 AdminView.vue 의 경우 local에서는 잘 돌아갔으나 배포를 해서는 해당 url을 따로 사용하는 것이 되지 않았습니다. 이를 늦게 알고 admin 페이지를 따로 만들었습니다.
4. 로그의 어려움 처음으로 로그를 도입했는데, 한 사람이 평가 하나만 해도 로그가 약 20개씩 쌓였습니다. 또한 이걸 브라우저에 저장하고 있다가 제출하기 버튼을 누르거나 페이지를 옮길 때 제출되게 했더니 제출하기 버튼을 눌렀을 때 제출이 너무 느린 문제가 있었습니다. 이런 설계 미스가 너무 아쉬워웠습니다.

피드백

감사하게도 많은 분들이 피드백을 주셨습니다.

성과

2025.04.03 11시 쯤 배포를 했고 14시까지 수집된 데이터가 굉장히 만족스러웠습니다.

back_logs 7443개 front_logs 6414개 score 216개

앞으로 진행할 과정

1. 피드백 반영
2. 로그 전송 수정
3. 서버 추가 구매 또는 개인 pc로 서버 전환
4. DADE를 도입하여 메뉴 추천 기능
5. 한 줄 맛평가 기능 추가
6. 평가 요약 기능 추가

• 비선형 구조
• 원소들 간에 1:N 관계를 가지는 자료구조
• 원소들 간에 "계층관계"를 가지는 계층형 자료구조
• 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조

트리의 정의

• 한 개 이상의 노드로 이루어진 유한 집합
• 노드 중 최상위 노드를 루트(root)라 한다.
• 나머지 노드들은 n(>= 0)개의 분리 집합 T1, T2, ..., Tn으로 분리될 수 있다.
• 분리 집합 각각은 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree)라 한다.

트리 용어

1. 노드 (node)

   • 티리의 원소를 의미함
   • A, B, C, ...

2. 간선 (edge)

   • 노드와 노드를 연결하는 선
   • 부모 노드와 자식 노드를 연결

3. 루트 노드 (root node)

   • 트리의 시작 노드인 최상위 노드
   • 트리 T의 루트 노드 = A

4. 형제 노드 (sibling node)

   • 같은 부모 노드의 자식 노드들
   • B, C, D는 형제 노드

5. 조상 노드 (ancestor node)

   • 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
     • K의 조상 노드: F, B, A

6. 서브 트리 (subtree)

   • 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리

7. 자손 노드 (descendant node)

   • 서브 트리에 있는 하위 레벨의 노드들
   • B의 자손 노드: E, F, K

8. 차수 (degree)

   • 노드의 차수
     • 노드에 연결된 자식 노드 수
     • B의 차수 = 2, C의 차수 = 1
   • 트리의 차수
     • 트리에 있는 노드의 차수 중에서 가장 큰 값
     • 트리 T의 차수 = 3
   • 단말 노드 (leaf node)
     • 차수가 0인 노드. 즉, 자식 노드가 없는 노드

9. 레벨

   • 루트에서 노드까지의 거리
   • 로트 노드의 레벨은 0, 자식 노드의 레벨은 부모 레벨 + 1

10. 높이

    • 루트 노드엠서 가장 먼 리프 노트까지의 간선 수
    • 트리의 높이는 최대 레벨 (트리 T의 높이 = 3)

이진 트리(Binary Tree)

• 차수가 2인 트리
• 각 노드가 자식 노드를 최대 2개 까지 가질 수 있는 트리 (왼쪽, 오른쪽 자식 노드)

ex)

이진 트리 특성

• 레벨 i에서의 노드의 최대 개수는 2^i개
• 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^{h+1}-1)개가 된다.

포화 이진 트리(Perfect Binary Tree)

• 모든 레벨에 노드가 포화 상태로 차 있는 이진 트리
• 높이가 h일 때, 최대 노드 개수인 (2^{h+1}-1)의 노드를 가진 이진 트리
  • 높이가 3일 때 2^{3+1}-1 = 15개의 노드
• 루트를 1번으로 하여 2^{h+1}-1까지 정해진 위치에 대한 노드 번호를 가짐 이렇게 꽉 찬 이진 트리를 의미함

완전 이진 트리(Complete Binary Tree)

• 높이가 h이고 노드 수가 n일 때 (단, h+1 <= n < 2^{h+1}-1), 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리 이렇게 왼쪽부터 오른쪽으로 하나씩 채워져 나가는 트리

편향 이진 트리(Skewed Binary Tree)

• 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드 만을 가진 이진 트리
  • 왼쪽 편향 이진 트리
  • 오른쪽 편향 이진 트리

리스트를 이용한 이진 트리

파이썬에서는 리스트를 이용하여 이진 트리를 표현할 수 있다.

우선 이진 트리를 숫자로 표현하면 다음과 같다.

여기서 규칙을 찾을 수 있다. 바로 왼쪽 자식 노드는 (부모 노드 x 2), 오른쪽 자식 노드는 (부모 노드 x 2 + 1) 이다. 이를 활용하여 노드를 표현하면 다음과 같다.

이렇게 인덱스를 활용하여 노드를 표현하고 이를 활용해 해당 노드의 부모 노드와 자식 노드들을 찾을 수 있다!

ex) 이를 활용한 이진 트리 구현

class BinaryTree:
    def __init__(self):
        self.tree = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L']

    def insert(self, value):
        self.tree.append(value)

    def get_node(self, index):
        if index < len(self.tree):
            return self.tree[index]
        return None

    def set_node(self, index, value):
        while len(self,tree) < index:
            self.tree.append(None)
        self.tree[index] = value

    def get_left_child(self, index):
        left_index = 2 * index
        if left_index < len(self.tree):
            return self.tree[left_index]
        return None

    def get_right_child(self, index):
        right_index = 2 * index + 1
        if right_index < len(self.tree):
            return self.tree[right_index]
        return None

    def get_parent(self, index):
        if index = 0:
            return None
        parent_index = index // 2
        return self.tree[parent_index]

리스트를 이용한 이진 트리 표현의 단점

• 편향 이진 트리의 경우에 사용하지 않는 리스트 원소에 대한 메모리 낭비 발생
• 트리 중간에 새로운 노드를 삽입하거나 기존의 노드를 삭제할 경우 리스트의 크기 변경이 어려워 비효율적

연결 리스트를 이용한 이진 트리 표현

• 리스트를 이용한 이진 트리의 표현의 단점을 보완하기 위해 연결 리스트를 이용하여 트리를 표현할 수 있다.
• 이진 트리의 모든 노드는 최대 2개의 자식 노드를 가지므로 일정한 구조의 이중 연결 리스트 노드를 사용하여 구현

이진 트리 순회(traversal)

• 트리의 노드들을 체계적으로 방문하는 것.
• 3가지 기본적인 순회 방법
  1. 전위 순회(Preorder Traversal) : VLR 순서로 순회
  2. 중위 순회(Inorder Traversal) : LVR 순서로 순회
  3. 후위 순회(Postorder Traversal) : LRV 순서로 순회

해당 구현들은 재귀의 순서만 바꾸면 쉽게 구현할 수 있다.

ex) 전위 순회 구현

class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def preorder_traversal(root):
    if root:
        print(root.val)
        preorder_traversal(root.left)
        preorder_traversal(root.right)

ex) 중위 순회 구현

class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val)
        inorder_traversal(root.right)

ex) 후위 순회 구현

class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def postorder_traversal(root):
    if root:
        postorder_traversal(root.left)
        postorder_traversal(root.right)
        print(root.val)

수식 트리(Expression Tree)

• 수식을 표현하는 이진 트리
• 수식 이진 트리(Expression binary Tree)라고 부르기도 함
• 연산자는 루트 노드이거나 가지 노드
• 피연산자는 모두 잎 노드

동일한 트리에 대해 세가지 순회 방법에 따른 계산 방법

• 전위 순회 : + * * / A B C D E
• 중위 순회 : A / B * C * D + E
• 후위 순회 : A B / C * D * E +

그래프

그래프 유형과 표현

• 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계를 표현한다.

• 정점(Vertex): 그래프의 구성요소로 하나의 연결점

• 간선(Edge): 두 정점을 연결하는 선

• 차수(Degree): 정점에 연결된 간선의 수

• 그래프 = 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조

  • V: 정점의 개수, E: 그래프에 포함된 간선의 개수
  • V 개의 정점을 가지는 그래프는 최대 V * (V - 1) / 2 간선이 개수

• 선형 자료구조나 트리 자료구조로 표현하기 어려운 M:N 관계를 가지는 원소들을 표현하기에 용이하다.

그래프 유형

무방향 그래프(Undirected Graph)

방향 그래프(Directed Graph)

가중치 그래프(Weighted Graph)

사이클 없는 방향 그래프(DAG, Directed Acyclic Graph)

트리(Tree)

완전 그래프 정점들에 대해 가능한 모든 간선들을 가진 그래프

부분 그래프 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프

인접 정점

인접(Adjacency)

• 두 개의 정점에 간선이 존재 (연결됨)하면 서로 인접해 있다고 한다.
• 완전 그래프에 속한 임의의 두 정점들은 서로 인접해 있다.
• 두 정점 1과 2는 서로 인접해 있다.

그래프 경로

경로 : 어떤 정점 A에서 시작하여 다른 정점 B로 끝나는 순회로 두 정점 사이를 잇는 간선들을 순서대로 나열할 것.

• 같은 정점을 거치지 않은 간선들의 sequence

• 어떤 정점에서 다른 정점으로 가는 경로는 여러가지일 수 있다.

• 0 - 6의 경로 예시

  • 정점들: 0 - 2 - 4 - 6
  • 간선들: (0, 2), (2, 4), (4, 6)

사이클 : 경로의 시작 정점과 끝 정점이 같음 = 시작한 정점에서 끝나는 경로

• 1 - 3 - 5 - 1

그래프를 표현하는 세가지 방법

1. 인접 행렬(Adjacent Matrix): V * V 크기의 2차원 배열을 이요해서 간선 정보를 저장
2. 인접 리스트(Adjacent List): 각 정점마다 다른 정점으로 나가는 간선의 정보를 저장
3. 간선 리스트(Edge List): 간선의 정보를 객체로 표현하여 리스트에 저장

1. 인접 행렬

이렇게 무향 그래프, 유향 그래프인지에 따라 행렬의 형태가 달라진다. 무향 = 대칭 행렬 유향 = 비대칭 행렬

장점

• 두 정점 사이의 간선이 있는지 확인하는 연산이 O(1)로 빠름
• 구현이 단순
• 정적 그래프에 적합.(정적 그래프: 정점과 간선의 수가 변하지 않음)

단점

• 많은 메모리를 차지함 = O(V^2)
• 간선의 수를 확인하거나 인접한 정점을 나열하는 연산이 느림

사용하기 좋은 상황

• Dense Graph(밀집 그래프)에 적합
• 두 정점 사이에 간선이 있는지 빠르게 확인해야 하는 경우

2. 인접 리스트

이렇게 해당 정점과 연결된 정점을 표시. 무향이면 그 표시가 2배가 됨.

장점

• 필요한 공간만 사용하므로 공간 복잡도 O(V + E)
• 인접한 정점을 나열하는 연산이 빠름

단점

• 두 정점 사이에 간선이 있는지 확인하는 연산이 느림 = O(V)
• Linked List로 구현이 복잡

사용하기 좋은 상황

• Sparse Graph(희소 그래프)에 적합
• 그래프가 동적으로 변하는 경우 (정점과 간선이 자주 추가/삭제 되는 경우)
• 인접한 정점을 자주 순회해야 하는 경우

3. 간선 리스트

두 정점에 대한 간선 그 자체를 객체로 표현하여 리스트로 저장

장점

• 필요한 간선만 저장하므로 공간 복잡도 O(E)
• 간선을 직접 다루는 연산에 효율적

단점

• 두 정점 사이에 간선이 있는 지 확인하는 연산이 느림 = O(E)
• 특정 정점에 인접한 정점을 찾는 연산이 느림 = O(E)

사용하기 좋은 상황

• 간선 중심 연산을 자주 수행해야 하는 경우. ex) MST

BST

BST (Binary Search Tree)

정의

• 데이터의 저장, 검색, 삽입, 삭제를 효율적으로 처리하기 위한 자료구조

특징

• 각 노드가 최대 2개의 자식을 가짐
• 데이터를 정렬된 형태로 저장하여 탐색/삽입/삭제를 효율적으로 수행

구조

• 이진 트리의 특성을 가지지만 추가로 다음과 같은 속성을 가짐(순서 속성)

  • 왼쪽 자식 노드의 키 값이 부모 노드의 키 값보다 작다.
  • 오른쪽 자식 노드의 키 값이 부모 노드의 키 값보다 크다.

장점

• 배열이나 Linked List와 달라, 삽입/삭제 후에도 데이터가 정렬된 상태를 유지
• 데이터가 균형있게 분포되어 있을 때 평균적으로 탐색/삽입/삭제 연산의 시간 복잡도가 O(logN)
• 동적으로 크기를 조절할 수 있어, 크기가 고정된 배열에 비해 유연성이 높음

단점

• 트리가 한쪽으로 치우치면 (즉, 균형이 맞지 않으면) 최악의 경우, 시간 복잡도가 O(n)이 될 수 있음
• 각 노드의 두 개의 자식 포인터를 저장해야 하므로, 큰 데이터 집합의 경우 메모리 오버헤드가 발생할 수 있음

BST 속성

높이

• 특정 노드에서 가장 깊은 리프 노드까지의 경로에 있는 간선의 개수
• 트리의 높이는 루트 노드의 높이와 동일
• 리프 노드의 높이는 0
• 균형잡힌 트리의 높이는 O(ogN), 불균형한 트리의 높이는 O(N)이다.

깊이

• 루트 노드에서 해당 노드까지의 경로에 있는 간선의 수
• 루트 노드의 높이는 0

BST 주요 연산

탐색

루트 노드부터 탐색을 시작하며, 현재 노드값과 찾고자 하는 키를 비교, 그 차에 따라 왼쪽 또는 오른쪽으로 이동. 이를 반복하다 현재 노드값과 찾고자 하는 값이 같으면 탐색 종료

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def search(self, key):
        return self._search(self.root, key)

    def _search(self, node, key):
        if node is None or node.key == key:
            return node
        if key < node.key:
            return self._search(node.left,key)
        return self._search(node.right, key)

삽입

새로운 노드를 삽입해도 BST의 특징인 "자식노드는 최대 2개"를 유지하면서 삽입할 위치를 찾기위해 루트부터 적절한 위치까지 내려감. 트리의 순서 속성을 유지하기 위해서 새로운 노드는 리프 노드로 삽입

class BST:
    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert(self.root, key)

    def _insert(self, node, key):
        if key < node.key:
            if node.left is None:
                node.left = Node(key)
            else:
                self._insert(node.left, key)

        else:
            if node.right is None:
                node.right = Node(key)
            else:
                self._insert(node.right, key)

삭제

삭제하려는 노드의 위치와 자식 노드의 유무에 따라 세 가지 경우로 나눠서 처리

1. 삭제할 노드가 리프 노드인 경우 -> 단순히 제거하면 됨

2. 삭제할 노드가 한 개의 자식 노드를 가질 경우 -> 삭제할 노드의 자식노드를 부모 노드에 연결

3. 삭제할 노드가 두 개의 자식 노드를 가질 경우 -> 중위 후속자 또는 중위 전임자 찾기

• 중위 후속자 : 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 값 (일반적으로 사용)
• 중위 전임자 : 삭제할 노드의 왼쪽 서브 틀에서 가장 큰 값
• BST 구조를 유지하기 위해서 삭제할 노드와 가장 가까운 값을 찾는 것.

class BST:
    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, node, key):
        if node is None:
            return node

        if key < node.key:
            node.left = self._delete(node.left, key)
        elif key > node.key:
            node.right = self._delete(node.right, key)
        else:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left

            temp = self._minValueNode(node.right)
            node.key = temp.key
            node.right = self._delete(node.right, temp.key)

        return node

    def _minValueNode(self, node):
        current = node
        while current.left is not None:
            current = current.left
        return current

BST의 균형과 불균형

• BST의 구조는 삽입되는 데이터의 순서에 따라 결정되기 때문에 특정 패턴으로 삽입되는 경우 불균형이 발생

• 불균형한 BST의 문제점

  • 검색/삽입/삭제 연산의 시간복잡도가 O(N)이 됨. (균형 잡힌 BST의 경우 O(logN))
  • 트리의 높이가 증가하게 되면 많은 메로리 공간이 필요
  • 트리의 높이가 증가하게 되면서 깊있는 재귀호출로 인해서 스택 오버플로우가 발생할 수 있음

• 불균형 문제를 해결할 수 있는 방법은?

  • 자가 균형 트리(Self-Balancing Tree): AVL Tree, Red-Black Tree

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조

• 스택에 저장된 자료는 "선형 구조"를 갖는다.

  • 선형 구조 : 데이터 요소들 사이에 순서가 존재
  • 비선형 구조 : 데이터 요소가 순차적으로 나열되지 않음

• 스택에서 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다.

• LIFO (Last In First Out)

스택의 주요 연산

• Push : 삽입
• Pop : 삭제
• IsEmpty : 공백 확인
• Peek : 최상단 자료 확인

class Stack:
    def __init__(self, capacity = 10):
        self.capacity = capacity
        self.items = [None] * capacity
        self.top = -1

    def is_empty(self):
        return self.top == -1

    def is_full(self):
        return self.top == self.capacity - 1

    def get_size(self):
        return self.top + 1

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items[self.top]

    def push(self, item):
        if self.is_full():
            raise IndexError("Stack is full")
        self.top += 1
        self.items[self.top] = item

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        itme = self.items[self.top]
        self.items[self.top] = None
        self.top -= 1
        return item

파이썬에서는 list의 append()와 pop(), len()을 활용하여 쉽게 스택을 이용할 수 있다.

stack = []

# push
stack.append('a')
stack.append('b')
stack.append('c') # stack = ['a', 'b', 'c']

# pop
stack.pop() # c 출력, stack = ['a', 'b']

# peek
stack[len(stack)] # b 출력, stack = ['a', 'b']

큐

• 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
• FIFO (First In First Out)

큐의 주요 연산

• EnQueue : 삽입
• Dequeue : 삭제
• IsEmpty : 공백인지 확인
• Peek : 가장 앞쪽의 원소 확인

class Queue:
    def __init__(self, capacity = 10):
        self.capacity = capacity
        self.items = [None] * capacity
        self.front = -1
        self.reer = -1

    def is_empty(self):
        return self.front == self.rear

       def is_full(self):
        return self.rear == self.capacity - 1

    def peek(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.items[self.front + 1]

    def get_size(self):
        return self.rear - self.front

    def enqueue(self, item):
        if self.is_full():
            raise IndexError("Queue is full")
        self.rear += 1
        self.items[self.rear] = item

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        self.front += 1
        item = self.items[self.front]
        self.items[self.front] = None
        return item

여기서 문제점이 있음 잘못된 포화 상태 인식 삽입과 삭제를 반복하다 보면 리스트의 앞부분이 None임에도 불구하고 포화상태로 인식할 수 있다.

이를 위해 항상 앞쪽을 채우도록 하려면 한번의 삭제마다 n번의 이동이 필요하다. -> 매우 비효율적

이를 해결하기 위해 원형 큐를 사용할 수 있다.

class CircleQueue:
    def __init__(self, capacity = 10):
        self.capacity = capacity + 1
        self.items = [None] * self.capacity
        self.front = 0
        self.rear = 0

    def is_empty(self):
        return self.front == self.rear

    def is_full(self):
        return (self.rear + 1) % self.capacity == self.front

    def peek(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.itmes[(self.front + 1) % self.capacity]

    def get_size(self):
        return (self.rear - self.front + self.capacity) % self.capacity

    def enqueue(self, item):
        if self.is_full():
            raise IndexError("Queue is full")
        self.rear = (self.rear + 1) % capacity
        self.items[self.rear] = item

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        self.front = (self.front + 1) % self.capacity
        item = self.items[self.front]
        self.items[self.front] = None
        return item

파이썬에서 deque라는 라이브러리로 쉽게 사용가능하다.

연결 리스트

기존의 리스트에서 중간에 특정 값을 삭제하면 뒤의 모든 값을 앞으로 이동시켜야 하는 문제가 있다. 이렇게 하면 한 번의 삭제에 n번의 연산이 필요한 겂이다. 이를 해결하기 위해 연결 리스트를 사용할 수 있다.

• 자료의 논리적 순서와 메모리 상의 물리적 순서가 일치하지 않음
• 링크로 원소에 접근
• 자료구조의 크기를 동적으로 조정 가능 = 메모리의 효율적인 사용이 가능

연결 리스트의 기본 구조

• 노드

  • 연결 리스트에서 하나의 원소를 표현하는 구성 요소

  • 구성요소

    • 데이터 필드 : 원소의 값 저장
    • 링크 필드 : 다음 노드의 참조 값을 저장

• 헤드

  • 연결 리스트의 첫 노드에 대한 참조 값

단순 연결 리스트(Singly Linked List)

• 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조
• 헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킨다.
• 링크 필드가 Null인 노드가 가장 마지막 노드이다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def insert(self, data, position):
        new_node = Node(data)
        if position == 0:
            new_node.next = self.head
            self.head = new_node
        else:
            current = self.head
            for _ in range(position - 1):
                if current is None:
                    print("범위를 벗어난 삽입입니다.")
                    return
                current = current.next
            new_node.next = current.next
            current.next = new_node

    def append(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def delete(self, position):
        if self.is_empty():
            print("싱글 링크드 리스트가 비었습니다.")
            return

        if position == 0:
            deleted_data = self.head.data
            self.head = self.head.next
        else:
            current = self.head
            for _ in range(position - 1):
                if current is None or current.next is None:
                    print("범위를 벗어났습니다.")
                    return
                current = current.next
            deleted_node = current.next
            deleted_data = deleted_node.data
            current.next = current.next.next
        return deleted_data

    def search(self, data):
        current = self.head
        position = 0
        while current:
            if current.data == data:
                return position
            current = current.next
            position += 1
        return -1

    def __str__(self):
        result = []
        current = self.head
        while current:
            result.append(current.data)
            current = current.next
        return str(result)

장점

• 필요한 만큼만 메모리를 사용
  단점
• 특정 요소에 접근하려면 순차적으로 탐색 (O(n))
• 역방향 탐색 불가

이중 연결 리스트(Doubly Linked List)

역방향 탐색이 가능하도록 링크 필드를 두 개, 데이터 필드 한 개로 구성

삽입 연산

삭제 연산

무엇이 좋은 알고리즘 인가?

1. 정확성
2. 효율성
3. 확장성
4. 단순성

가장 중요한건 "정확성"

알고리즘을 평가하는 지표 = 복잡도

1. 시간 복잡도 (= 수행 시간)
2. 공간 복잡도 (= 메모리 사용량)

시간 복잡도

시간 복잡도는 세 가지 경우가 있다.

1. 최선의 경우 (Best Case)
2. 평균적인 경우 (Average Case)S
3. 최악의 경우 (Worst Case)

우리가 중요하게 생각하는건 "최악의 경우"

복잡도는 점근적 표기를 사용한다. 입력 크기 n에 대한 함수로 표기한다. 빅-오(O) 표기법은 함수 중 가장 큰 영향력을 주는 n에 대한 항만을 표시 만약 O(3n + 2) 라면 O(n)으로 표기

처음 알고리즘을 배울때는 정확도를 최우선으로 고려하고 그 후 빅-오를 통해 효율을 생각하자. 확장성과 단순성이 이후에 고려해도 늦지 않다.

완전 검색

• 정확도를 최우선으로 고려하는 알고리즘

• 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법

• Brute-foce 혹은 generate-and-test 기법이라고도 불린다.

  • "Just-do-it"
  • force의 의미는 사람(지능)보다는 컴퓨터의 force를 의미한다.

• 대부분의 문제에 적용 가능

• 모든 알고리즘의 시작!!! 매우 중요

완전 검색은 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 낮다.

검정 등에서 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직하다.

재귀 함수

• 자기 자신을 호출하는 함수
• 함수 호출은 메모리 구조에서 스택을 사용한다.
• 무분별한 재귀 함수는 성능저하를 발생시킨다.

대표적인 예시 (팩토리얼)

n! = 1 x 2 x 3 x ... x (n-1) x n 이다. 이를 재귀 함수로 표현하면 다음과 같다.

def fact(n):
    if n <= 1:
        return 1
    else:
        return n * fact(n-1)

이를 그림을 통해 살펴보면 다음과 같다.

fact(4)에서 fact(3), fact(3)에서 fact(2) 이렇게 자기 자신보다 값이 1 작은 함수를 계속해서 호출하다가 fact(1)이 되면 'return 1'이 되면서 다시 fact(2), fact(3)을 계산하고 최종적으로 시작했던 fact(4)를 return하면서 결과가 반환된다.

추가 예시 (피보나치 수열)

이전의 두 수 합을 다음 항으로 하는 수열을 피보나치 수열이라고 한다. 이를 재귀함수로 구현하면 다음과 같다.

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

가장 시작이 되는 fibonacci(0)과 fibonacci(1)만 return 값을 정의해주면 이후의 값은 재귀적으로 만들어지게 됩니다.

이처럼 재귀함수는 반환이 시작되는 부분을 기본 부분 이라고 하고, 재귀를 쌓는 부분을 유도 부분 이라고 한다.

이를 잘 구분하고 정의하는 것이 재귀함수를 잘 사용하는 첫 걸음이다.

피보나치 수열의 기본 부분과 유도 부분은 다음과 같다.

def fibonacci(n):
    if n == 0: # 기본 부분
        return 0
    elif n == 1: # 기본 부분
        return 1
    else: # 유도 부분
        return fibonacci(n - 1) + fibonacci(n - 2)

순열

서로 다른 n개에서 r개를 뽑아 순서대로 나열하는 것. -> 순서가 중요. (표현법 : nPr)

다수의 알고리즘 문제들은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련이 있다.

이를 반복문을 통해 생성한다면 다음과 같다. ex) {1, 2, 3}의 모든 순열

for i in range(1, 4):
    for j in range(1, 4):
        if j != i:
            for k in range(1, 4):
                if k != i and k != j:
                    print(i, j, k)

이는 n이 커지면 반복문을 그만큼 중첩해야하고, 이를 하나의 함수로 표현하기도 어렵다. 그래서 보통 재귀 호출을 통해 순열을 생성한다.

ex) 재귀 호출을 활용한 {1, 2, 3}의 모든 순열

def perm(selected, remain):
    if not remain:
        print(selected)
    else:
        for i in range(len(remain)):
            select_i = remain[i]
            remain_list = remain[:i] + remain[i + 1:]
            perm(selected + [select_i], remain_list)

perm([], [1, 2, 3])

재귀 함수가 동작하는 것을 순서대로 따라가면 다음과 같다.

perm([], [1, 2, 3]) -> perm([1], [2, 3]) -> perm([1, 2], [3]) -> perm([1, 2, 3], [])에서 print(1, 2, 3) 실행 -----> perm([1, 3], [2]) -> perm([1, 3, 2], [])에서 print(1, 3, 2) 실행 -> perm([2], [1, 3]) -> perm([2, 1], [3]) -> perm([2, 1, 3], [])에서 print(2, 1, 3) -----> perm([2, 3], [1]) -> perm([2, 3, 1], [])에서 print(2, 3, 1) -> perm([3], [1, 2]) -> perm([3, 1], [2]) -> perm([3, 1, 2], [])에서 print(3, 1, 2) -----> perm([3, 2], [1]) -> perm([3, 2, 1], [])에서 print(3, 2, 1)

이런식으로 진행이 된다.

조합

서로 다른 n개의 원소 중 r개를 순서없이 골라낸 것. (표현법 : nCr)

ex) {1, 2, 3, 4}중 3개를 뽑는 조합을 반복문으로 표현하면?

for i in range(1, 5):
    for j in range(i + 1, 5):
        for k in range(j+1, 5):
            print(i, j, k)

순열과 동일하게 r이 증가하면 그만큼 for문이 반복된다. 그래서 보통 재귀 함수를 통해 조합을 생성한다.

ex) 동일한 조합을 재귀 함수로 표현하면?

def comb(arr, r):
    result = []
    if r == 1:
        return [[i] for i in arr]

    for i in range(len(arr)):
        elem = arr[i]
        for rest in comb(arr[i + 1:], r - 1):
            result.append([elem] + rest)
    return result

print(comb([1, 2, 3, 4], 3))

조합의 재귀 함수가 동작하는 것을 순서대로 따라가면 다음과 같다.

comb([1, 2, 3, 4], 3) -> result = [], elem = 1, rest = comb([2, 3, 4], 2) comb([2, 3, 4], 2) -> result = [], elem = 2, rest = comb([3, 4], 1) comb([3, 4], 1) -> return [[3], [4]] comb([2, 3, 4], 2) -> result = [[2, 3], [2, 4]], elem = 3, rest = comb([4], 1) comb([4], 1) -> return [[4]] comb([2, 3, 4], 2) -> result = [[2, 3], [2, 4], [3, 4]] comb([1, 2, 3, 4], 3) -> result = [[2, 3], [2, 4], [3, 4]], elem = 2, rest = comb([3, 4], 2) -> result = [[1, 2, 3], [1, 2, 4], [1, 3, 4]] comb([3, 4], 2) -> result = [], elem = 3, rest = comb([4], 1) comb([4], 1) -> return [[4]] comb([3, 4], 2) -> result = [[3, 4]] comb([1, 2, 3, 4], 3) -> result = [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]

중복 순열 & 중복 조합

def comb(arr, r):
    result = []
    if n == 1:
        return [[i] for i in arr]

    for i in range(len(arr)):
        elem = arr[i]

        for rest in comb(arr[i + 1:], r - 1): # 조합
        # for rest in comb(arr[:i] + arr[i + 1:] r - 1): # 순열
        # for rest in comb(arr, r - 1): # 중복 순열
        # for rest in comb(arr[i:], r - 1): # 중복 조합
            result.append([elem] + rest)

    return result

부분 집합(Power Set)

ex) {1, 2, 3}집합의 모든 부분 집합 반목문으로 구현

selected = [0] * 3
for i in range(2):
    selected[0] = i
    for j in range(2):
        selected[1] = j
        for m in range(2):
            selected[2] = ,
            subset = []
            for n in range(3):
                if selected[n] = 1:
                    subset.append(n + 1)
            print(subset)

재귀 함수로 구현

def generate_subset(depth, included):
    if depth == len(input_list):
        cnt_subset = [input_list[i] for i in range(len(input_list)) if included[i]]
        subsets.append(cnt_subset)
        return

    included[depth] = False
    generate_subset(depth + 1, included)

    included[depth] = True
    generate_subset(depth + 1, included)

input_list = [1, 2, 3]
subsets = []
init_included = [False] * len(input_list)
generate_subset(0, init_included)
print(subsets)

Binary Counting 이진법을 활용한 방법

arr = [1, 2, 3]
n = len(arr)
subset_cnt = 2 ** n

subsets = []
for i in range(subset_cnt):
    subset = []
    for j in range(n):
        if i & (1 << j):
            subset.append(arr[j])
    subsets.append(subset)

print(subsets)