도메인 로직과 데이터 접근 로직을 분리하기 위해 자주 사용되는 소프트웨어 디자인 패턴. 주로 DDD(Domain-Driven Design)에서 강조되지만, MVC나 계층형 아키텍처에서도 널리 사용된다.

저장소 패턴은 GoF 디자인 패턴 23개에 포함되어 있지 않다. 하지만 실무 백엔드에서 정말 자주 쓰이는 실용적인 설계 패턴이라고 생각한다.

저장소 패턴(Repository Pattern)이란?

저장소(Repository)는 도메인 객체의 컬렉션처럼 작동하는 추상 계층으로, 데이터베이스, 외부 API, 캐시 등 다양한 저장소에서 데이터를 가져오는 복잡한 로직을 캡슐화하여 일관된 인터페이스로 제공하는 역할을 한다.

즉, Service -> Repository -> Data Source(DB, API) 구조로, 비즈니스 로직은 Repository에만 의존하며, 구체적인 구현은 숨겨진다.

저장소 패턴을 사용하는 이유

일반적인 Service-Controller 구조에서는 비즈니스 로직과 DB 접근 로직이 강하게 결합되어 있다. 이는 장기적으로 보았을 때 코드의 복잡도를 높이고 가독성을 떨어뜨리며, 유지보수에 어려움을 겪을 수 있다. 저장소 패턴은 비즈니스 로직에서 데이터 접근 로직을 분리하여, DB나 외부 API 구조가 바뀌어도 Repository만 수정하면 되기 때문에 유지보수에 용이하며, 실제 DB 없이 Repository를 mocking하여 테스트가 가능하다. 또한 비즈니스 로직에서 복잡한 쿼리나 조건이 Repository로 숨겨지기 때문에 깔끔한 인터페이스를 제공할 수 있다.

저장소 패턴 예시 (FastAPI + SQLAlchemy)

AS-IS: 로그인 기능

라우터에서 요청 파라미터를 받아서, 비즈니스 로직으로 넘기게 된다.

# ❌ 비즈니스 로직과 데이터 접근 로직이 강하게 결합된 형태
class AuthService:
    def login(self, request, db: Session) -> tuple[str, str]:
        # DB 접근 로직 (User 조회)
        user = db.query(User).filter(User.email == request.email).first()

        # 비즈니스 로직 (비밀번호 검증, 토큰 생성)
        ...

AuthService에서 처리 후 결과값을 router에게 다시 넘겨주게 된다.

TO-BE: 로그인 기능

위 과정에서 비즈니스 로직에 DB 접근 로직이 포함되어 있다. 이를 Repository로 분리해주는 것이다.

class UserRepository:
    def __init__(self, db: Session):
        self.db = db

    def get_by_email(self, email: str) -> Optional[User]:
        # ✅ DB 쿼리 세부 구현은 여기서만 관리
        return self.db.query(User).filter(User.email == email).first()

class AuthService:
    def __init__(self, user_repo: UserRepository):
        self.user_repo = user_repo

    def login(self, request) -> tuple[str, str]:
        user = self.user_repo.get_by_email(request.email)
        if not user or not auth.verify_password(request.password, user.password):
            raise HTTPException(...)

        # ✅ 비즈니스 로직만 남음
        ...

이후 router에서 Repository 클래스와 AuthService 클래스를 생성해 넣어준다. 위와 같은 방식으로 구현하게 되면 각 계층이 단일 책임 원칙(SRP)을 따르기 때문에 테스트, 유지보수, 확장이 쉬워진다.

저장소 패턴의 장단점

장점

• 비즈니스 로직과 인프라(데이터 저장소)를 분리하여 유지보수성 향상
• 다양한 저장소(DB, Redis, API 등)로 교체 가능
• Mock Repository를 사용하여 테스트하기 쉬움
• 코드 일관성과 확장성 증가

단점

• 초기 설계 시 복잡도 증가 (작은 프로젝트에 적용할 경우 오버엔지니어링)
• Repository가 너무 비대해지면 SRP(Single Responsibility Principle) 위반
• Interface/Implementation의 중복 코드 가능성

규모가 작은 프로젝트의 경우 오버엔지니어링일 수 있으나, 규모가 커질 수 있는 프로젝트라면 나중을 대비해 저장소 패턴을 활용하여 API 로직을 설계하는 것도 좋은 방안이 될 수 있을 것 같다.

Reference 저장소 패턴(Repository Pattern) 도입기, by daco2020 [디자인패턴] Repository Pattern 레포지토리 패턴, by ttoogi

Redis는 극한의 속도를 자랑하는 인메모리 데이터 저장소로, 캐시부터 실시간 데이터 처리까지 모든 퍼포먼스를 가속시켜준다.

우리는 다양한 프로젝트를 진행하다 보면 종종 다음과 같은 고민을 하게 된다.

• DB 조회가 느리다... 캐싱을 해야 하나?
• 트래픽이 몰릴 때 응답이 버벅거린다
• 실시간 랭킹이나 세션 저장을 어떻게 하지?

이런 문제를 해결해주는 빠르고 가벼운 저장소가 바로 Redis이다.

Redis란?

Redis는 Remote Dictionary Service의 약자로, 오픈 소스 기반의 Key-Value 형태 In-Memory 데이터 저장소이다.
Key-Value 기반이기 때문에 쿼리를 직접 보낼 필요 없이 $O(1)$의 시간 복잡도로 값을 바로 조회할 수 있다.

또한 디스크가 아닌 메모리에서 데이터를 처리하므로 속도가 매우 빠르고,
NoSQL 구조이며 List, Hash, Set, Sorted Set 등 다양한 자료구조도 지원한다.

Redis가 빠른 이유

Redis는 내부적으로 해시 테이블(dict) 구조를 기반으로 동작한다.

SET user:1001 "Alice"
GET user:1001 # -> "Alice"

왜 빠를까?

Redis는 key를 해시 처리한 후, 메모리 주소에서 즉시 조회한다. 디스크 접근이 필요 없기 때문에, 일반 RDBMS보다 수백 배 이상 빠르다.

Redis는 "Key → Value"를 메모리에서 바로 찾아내므로,
쿼리가 아닌 "주소 접근"처럼 작동한다.

인메모리(In-Memory) 방식

인메모리 방식이란, 데이터를 하드디스크가 아닌 RAM에 올려서 직접 처리하는 방식이다.
메모리 내부에서 모든 연산이 이루어지기 때문에 저장과 조회 속도가 매우 빠르다.

하지만 한계도 있다:

• RAM 용량을 초과하면 더 이상 저장할 수 없고,
• 별도로 영속성 설정을 하지 않으면 Redis 재시작 시 데이터가 유실될 수 있다.

Redis는 언제 쓸까?

MySQL과 Redis를 같이 쓰는 이유

Redis는 MySQL을 대체하지 않고, 보완하는 용도로 많이 사용된다.

• MySQL: 영속적인 데이터 저장
• Redis: 빠른 조회/임시 데이터 저장

예시: 게시글 조회수 처리

1. 사용자들이 게시글을 조회할 때 Redis에서 조회 수를 증가시킨다.
   → INCR post:123:views
2. 일정 주기마다 MySQL에 반영 (배치 업데이트)

이렇게 하면 DB 부하를 줄이면서도 실시간 응답이 가능해진다.

Redis 사용 시 주의점

• 메모리 용량 한계: In-Memory 기반이므로 용량 초과 시 문제가 발생할 수 있다.
• 데이터 유실 가능성: 기본 설정에선 재시작 시 데이터가 날아갈 수 있다.
  → RDB, AOF 설정 필요
• 키 설계 중요: 무분별한 키 생성은 메모리 낭비와 관리 어려움을 초래할 수 있다.

다음 포스팅에서는 실전에서 Redis를 어떻게 사용하는지를 다뤄볼 예정이다.

파이썬 패키지를 설치하고 관리하기 위한 만능 패키지 관리 도구. Rust로 구현되어 있으며, 기존 pip보다 훨씬 빠른 설치 속도와 더 안전한 의존성 관리를 목표로 개발됨.

uv는 pip, pip-tools, pipenv를 모두 대체할 수 있도록 설계된 패키지 매니저이다.

최근에는 MCP(Model Context Protocol) 개발 등에 많이 활용되면서 큰 관심을 받고 있다.

❓ 왜 uv를 사용할까?

기존엔 파이썬 프로젝트를 관리할 때는 보통 다음 과정을 거쳤다.

python -m venv venv
source venv/Scripts/activate
pip install pandas

• python -m venv로 가상환경을 만들고,
• source로 가상환경을 활성화한 뒤,
• pip로 필요한 패키지를 설치하는 방식이다.

하지만 이 방법은 관리가 번거롭고, 패키지를 설치할 때마다 시간이 오래 걸리는 문제가 있었다.

또한, pip만으로는 의존성 충돌 관리나 lockfile 생성을 자동화하기 어렵고, poetry 같은 도구는 설정이 복잡하고 무겁게 느껴질 수 있다.

하지만, uv를 사용하면 상황이 완전히 달라진다.

uv를 사용하면, pip나 poetry 대비 10배에서 최대 100배까지 빠르게 패키지를 설치할 수 있다. Rust 기반 최적화 덕분이다.

또한, 프로젝트 관리 역시 훨씬 간단해진다.

uv init
uv add pandas

• uv init으로 프로젝트를 초기화하고,
• uv add 명령어로 필요한 패키지를 간편하게 추가할 수 있다.

추가로, uv는 가상환경을 직접 관리하기 때문에 python -m venv나 pyenv, virtualenv같은 명령어를 따로 신경 쓸 필요가 없다.

모든 패키지 의존성은 uv.lock 파일로 명확하게 기록되기 때문에, 다른 환경에서도 동일한 설치 결과를 재현할 수 있다.

✨ uv의 특징

🛠️ uv 설치 방법

Linux 및 macOS에서 uv는 다음과 같이 간단하게 설치할 수 있다. 설치 방법 참고

# curl 사용하기
curl -LsSf https://astral.sh/uv/install.sh | sh
# wget 사용하기
wget -qO- https://astral.sh/uv/install.sh | sh
# 특정 버전 설치하기
curl -LsSf https://astral.sh/uv/0.6.14/install.sh | sh

혹은 기존 패키지 관리 도구로 설치 가능하다.

pip install uv

설치가 완료되었으면, 다음 명령어로 설치 여부를 확인할 수 있다.

uv --version

🧪 uv 사용해보기

🏗️ 프로젝트 생성

uv init test
cd test

uv init 명령어를 사용하면, 현재 디렉토리를 uv 프로젝트로 초기화하거나, 새로운 프로젝트 폴더를 생성할 수 있다.

위 예시에서는 test라는 이름의 uv 프로젝트를 생성하였다.

생성된 test 폴더의 구조는 다음과 같다.

test/
├── .git
├── .gitignore
├── .python-version
├── README.md
├── main.py
└── pyproject.toml

• .python-version을 통해 파이썬 버전이 고정된다.
• pyproject.toml은 의존성 및 프로젝트 메타데이터를 정의하는 핵심 파일이다.
• .venv 폴더는 의존성을 관리하기 위한 폴더이다.

.venv 폴더는 실제로 패키지를 설치하거나 uv sync를 실행할 때 생성된다.

➕ 패키지 추가

패키지를 추가하는 것도 매우 간단하다.

uv add pandas

• uv add 명령어를 사용하면 패키지를 설치하고,
• pyproject.toml과 uv.lock에 의존성이 자동으로 기록된다.

추가적으로 로컬 캐시를 활용하여, 설치 속도가 pip에 비해 월등히 빠르다.

📋 설치된 패키지 확인

현재 설치된 패키지 목록을 확인하려면

uv pip list

또는,

uv pip freeze

를 사용할 수 있다. pip 명령어처럼 사용할 수 있다는 점이 매우 직관적이다.

🔄 의존성 동기화

만약 다른 개발자가 이 프로젝트를 클론했다면, 다음 명령어 하나로 모든 환경을 재현할 수 있다.

uv sync

• uv.lock 파일을 기준으로 정확히 동일한 패키지 버전이 설치된다.
• 프로젝트 환경 복원이 완벽하게 보장된다.

▶️ 실행 테스트

초기화 시 생성된 main.py 파일을 실행해보자.

uv run main.py

기본적으로 Hello, world!가 출력된다.

필요에 따라 main.py에 코드를 추가해서 본격적인 개발을 진행하면 된다.

uv는 빠르고 직관적이며, 가상환경과 의존성 관리를 통합한 덕분에 파이썬 프로젝트를 훨씬 효율적으로 관리할 수 있다.

아마 이제 아나콘다처럼 무겁고 복잡한 환경은 점점 필요 없어지지 않을까 싶다.

📚 References

uv 공식 문서 - Getting Started

정렬되어 있는 데이터 집합에서, 원하는 값을 빠르게 찾는 알고리즘.

전체를 순차적으로 탐색하는 대신, 항상 탐색 범위를 절반씩 줄여나가면서 원하는 값을 찾아나간다.

시간 복잡도는 $O(\log n)$으로 매우 빠른 탐색을 할 수 있다.

전제 조건

• 데이터가 정렬되어 있어야 한다.
• 데이터가 오름차순/내림차순 등으로 이미 정리되어 있지 않다면, 먼저 정렬해야 한다.

동작 과정

1. 탐색 범위의 중간값 mid를 찾는다.
2. 중간값이 찾는 값이면 종료한다.
3. 중간값보다 찾는 값이 작으면 왼쪽 구간만 탐색한다.
4. 중간값보다 찾는 값이 크면 오른쪽 구간만 탐색한다.
5. 탐색 구간이 없을 때까지 반복한다.

항상 절반씩 범위를 좁히기 때문에, $O(\log n)$이라는 빠른 속도를 가진다.

구현

이분 탐색으로 풀 수 있는 문제인 #1920. 수 찾기를 예시로 들어보자.

주어진 수열에서 특정 수가 존재하는지 아닌지만 판별하는 문제이다.

처음 떠올릴 수 있는 가장 직관적인 방법은, 단순히 모든 원소를 순회하면서 하나씩 비교하는 방식이다.

def find(target: int, seq: list) -> bool:
    for n in seq:
        if n == target: return True
    return False

하지만 이 방법은 최악의 경우 모든 원소를 다 비교해야 하므로 $O(n)$이 걸린다.

특히 데이터가 수십만 개 이상일 경우, 시간 초과가 발생할 수 있다.

따라서 더 효율적인 방법인 이분 탐색을 사용해 문제를 해결할 수 있다.

def find(target: int, seq: list) -> bool:
    low = 0
    high = len(seq) - 1
    while low <= high:
        mid = (low + high) // 2
        if seq[mid] == target: return True
        elif seq[mid] < target: low = mid + 1
        else: high = mid - 1
    return False

여기서 seq는 반드시 정렬되어 있어야 한다. 정렬되어 있지 않으면, 이분 탐색은 올바르게 동작하지 않는다.

이처럼 탐색 문제에서 단순 반복문 대신 정렬 + 이분 탐색 패턴을 적용하면 시간복잡도를 대폭 줄여 효율적인 해결이 가능하다.

#1865. 웜홀

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 $N$개의 지점이 있고 N개의 지점 사이에는 $M$개의 도로와 $W$개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

접근 방식

웜홀이 음수 가중치를 갖기 때문에, 그래프 내 음수 사이클 존재 여부를 확인하는 문제로 해석할 수 있다. 따라서, 벨만-포드 알고리즘을 적용하는 방향으로 접근하였다.

def solution(n: int, edges: list) -> bool:
    dist = [float("inf")] * (n + 1)
    dist[1] = 0
    for i in range(1, n + 1):
        for s, e, cost in edges:
            if dist[s] != float("inf") and dist[e] > dist[s] + cost:
                dist[e] = dist[s] + cost
                if i == n: return True
    return False

위는 일반적인 벨만-포드 알고리즘 구현 방식이다. n번 반복한 뒤, 마지막 반복에서 거리 갱신이 일어나면 음수 사이클이 존재하는 것이므로 True를 리턴하고, 그렇지 않다면 False를 리턴해 출발하였을 때보다 시간이 되돌아가 있는 경우가 있는지를 확인할 수 있다.

주의해야 할 점

여기서 중요하게 짚고 넘어가야 하는 부분이 있다.

1. 백준이가 출발을 어디서 하는가?

백준이는 아무데서나 출발할 수 있다. 따라서 음수 가중치가 존재하기만 한다면, 출발했을 때보다 시간이 되돌아가 있는 경우가 있다는 의미이다.

2. 출발 지점을 어디로 설정해야 하는가?

모든 지점이 연결되어 있다면, 시작 지점이 1이어도 상관없지만(어차피 모든 지점을 모두 지나가게 됨), 1 지점과 연결되어 있지 않은 지점이 존재한다면, 해당 지점들 사이에서 음수 사이클이 발생하는지 확인할 수 없기 때문이다.

이 문제를 해결하기 위해 0이라는 가상 지점을 만든 후 모든 지점과 연결만 시켜준다면, 기존 알고리즘으로도 무리 없이 음수 사이클을 발견할 수 있다.

혹은 if문의 dist[s] != float("inf") 부분을 제거하여 방문하지 않은 노드더라도 일단 탐색을 하는 방식이 있다.

코드 1(가상 지점 만들기)

def solution(n: int, edges: list) -> bool:
    new_edges = edges + [(0, i, 0) for i in range(1, n + 1)]
    dist = [float("inf")] * (n + 1)
    dist[0] = 0
    for i in range(n + 1):
        for s, e, cost in new_edges:
            if dist[s] != float("inf") and dist[e] > dist[s] + cost:
                dist[e] = dist[s] + cost
                if i == n: return True
    return False

0과 모든 지점간 비용이 0으로 연결되어있는 간선을 만든 후, 시작 지점을 0으로 둔다.

이후 n번 반복한 다음, 마지막 반복에서 갱신이 일어나면 음수 사이클이 있는것이므로 True를 리턴한다.

코드 2(방문 여부 체크 X)

def solution(n: int, edges: list) -> bool:
    dist = [100_000_000] * (n + 1)
    dist[1] = 0
    for i in range(n + 1):
        for s, e, cost in edges:
            if dist[e] > dist[s] + cost:
                dist[e] = dist[s] + cost
                if i == n: return True
    return False

위 코드에서는 시작 지점을 1로 설정해주었지만, 시작 지점을 설정해주지 않아도 되고, 모든 지점에서 동시에 출발해도 상관 없다(dist 리스트의 모든 값을 0으로 초기화해도 상관 없음).

위 방식에서 중요한 점은 절대 dist 리스트를 float("inf")로 초기화하면 안된다는 점인데, 무한에 음수를 더해도 여전히 무한이기 때문에 거리 갱신이 이루어지지 않기 때문이다.

그럼에도 불구하고 내가 틀린 이유

두 가지 방식을 모두 적용해보았지만 2%에서 계속 틀려서 다른 사람들의 코드를 참고했다. 하지만 내 코드와의 차이점을 찾을 수 없었다..

그 해답을 질문 게시판에서 찾을 수 있었다.

그동안 도로의 간선도 웜홀과 동일하게 방향 그래프로 넣어주었다.. 즉, solution() 함수에 문제가 있는게 아니라 그래프 자체에 문제가 있었던 것이다.

# 원래 이렇게 넣어주고 있었음
edges.append(tuple(map(int, input().split())))

# 도로는 무방향 -> 양쪽 모두 추가해야 함
s, e, c = map(int, input().split())
edges.append((s, e, c))
edges.append((e, s, c))

바꿔주니까 잘 작동하는 것을 확인할 수 있었다..

이 문제는 최단 거리를 묻는 문제가 아니라서, 벨만 포드 외에도 다양한 풀이법이 존재하는 것 같다. 나중에 다른 방법도 시도해보는게 좋을 것 같다.

음수 가중치가 있는 그래프에서도 단일 출발점에서 모든 정점까지의 최단 경로를 구할 수 있는 알고리즘.

다익스트라 알고리즘은 음수 가중치를 허용하지 않지만, 벨만 포드는 이를 허용하며, 음수 사이클 존재 여부도 판별할 수 있다.

전제 조건

동작 원리

벨만 포드는 다음과 같은 방식으로 진행된다.

1. 모든 간선 (u -> v)에 대해 다음을 V-1번 반복한다.

if dist[v] > dist[u] + cost:
    dist[v] = dist[u] + cost

2. 위 작업을 정점 개수(V)보다 하나 적은 횟수만큼 반복하면 모든 최단거리가 안정적으로 수렴하게 된다.

3. 이후 한 번 더 반복했을 때 값이 갱신되면, 음수 사이클이 존재하는 것이다.

시간 복잡도는 $O(V \times E)$이다.

간선을 $V-1$번 반복하면서 모두 확인하므로, 간선 수가 많거나 정점이 많을 경우 느릴 수 있다.

즉, 음수 가중치가 존재하지 않는다면 다익스트라 알고리즘을 사용하는게 좋고(더 빠름), 음수 가중치가 존재할 때 사용하기 좋다.

구현

음수 가중치가 있는 그래프 문제인 #11657. 타임머신을 봐보자.

$N$개의 도시와 $M$개의 버스가 있으며, 버스를 타고 이동하는 시간이 0이면 순간이동, 0보다 작으면 타임머신을 이용해 시간을 되돌아가는 상황이다. (음수 가중치)

앞서 설명한 벨만-포드 알고리즘을 적용하여 구현해보자.

def bellman_ford(n: int, edges: list) -> list:
    dist = [float("inf")] * (n + 1)
    dist[1] = 0
    for i in range(1, n + 1):
        for s, e, cost in edges:
            if dist[s] != float("inf") and dist[e] > dist[s] + cost:
                dist[e] = dist[s] + cost
                if i == n: return [-1]    # n번째 반복에서도 갱신된다면 음수 사이클 존재
    # INF의 경우 도달 불가능한 도시이므로 -1
    for i in range(2, len(dist)):
        if dist[i] == float("inf"): dist[i] = -1
    return dist[2:]

시작 노드는 1번으로 설정하여 거리를 0으로 초기화하고, 도시 수($N$)만큼 반복하며 최단 거리를 갱신한다.

모든 간선에 대해 현재 노드에서 다음 노드로 가는 비용이 더 적으면 갱신하고, 이 과정을 반복한다.

만약 마지막($N$번째) 반복에서도 거리 갱신이 발생하면, 이는 음수 사이클이 존재하는 것이므로 -1을 반환한다.

최종적으로 각 도시별 최단 거리를 계산하고, 도달할 수 없는 도시는 -1로 표시한다.

#3344. N-Queen

$N$이 주어졌을 때, $N \times N$ 보드에 $N$개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 한 가지 경우를 출력하는 프로그램을 작성하시오.

첫째 줄에 $N$이 주어진다. $N$은 $8,26,213,2012,99991,99999$ 중 하나이다.

접근 방식

먼저, 또 다른 N-Queen 문제(#9663)에서는 백트래킹을 이용해 $N$일 때 나올 수 있는 해의 모든 경우의 수를 출력하였다. 해당 코드에서 첫 해를 구한 직후 바로 탈출하면 되지 않을까?

def solution(n: int, check: dict, row: int = 0) -> int:
    if n == row: return True
    for col in range(n):
        # 놓을 수 있는 공간에 말 놓기
        if check["c"][col] and check["u"][row+col] and check["d"][row-col+n-1]:
            check["c"][col] = check["u"][row+col] = check["d"][row-col+n-1] = False
            if solution(n, check, row + 1):
                print(col + 1)
                return True
            check["c"][col] = check["u"][row+col] = check["d"][row-col+n-1] = True
    return False

if __name__ == "__main__":
    N = 8
    check = {
        "c": [True]*N,
        "u": [True]*(N*2),
        "d": [True]*(N*2),
    }
    solution(N, check)

작은 숫자의 경우 빠르게 출력되는 반면, $216$과 같은 큰 숫자는 출력되는데 오랜 시간이 소요된다.

따라서 해당 접근 방식은 잘못되었다.

규칙 찾기

퀸을 어떤식으로 두어야 서로 공격할 수 없을까? $N=4$인 경우부터 확인해보자.

1. N이 4일 때 (짝수일 때)

$N=4$일 때 둘 수 있는 배치는 총 두 가지이다.

여기서 두 번째 배치를 보면, 첫 번째 행부터 $2,4$, 즉 짝수 칸에 배치하고, 그 이후부터는 $1$부터 홀수 칸에 배치한다.

아래 검증 코드를 통해 확인해보자.

# 검증 코드
def check_queen(board: list):
    N = len(board)
    check = {
        "c": [True]*N,
        "u": [True]*(N*2),
        "d": [True]*(N*2),
    }
    for row in range(len(board)):
        if check["c"][board[row]-1] and check["u"][row+board[row]-1] and check["d"][row-board[row]+N-2]:
            check["c"][board[row]-1] = check["u"][row+board[row]-1] = check["d"][row-board[row]+N-2] = False
        else:
            return False
    return True

def solution(n: int) -> int:
    board = []
    # 위쪽부터 짝수로 채우기
    for i in range(2, n + 1, 2):
        board.append(i)
    # 그 이후 홀수로 채우기
    for i in range(1, n + 1, 2):
        board.append(i)
    return board

for n in [4, 5, 6, 7, 8, 9, 10]:
    print(f"{n}의 경우:", solution(n), "✅" if check_queen(solution(n)) else "❌")

Output:
4의 경우: [2, 4, 1, 3] ✅
5의 경우: [2, 4, 1, 3, 5] ✅
6의 경우: [2, 4, 6, 1, 3, 5] ✅
7의 경우: [2, 4, 6, 1, 3, 5, 7] ✅
8의 경우: [2, 4, 6, 8, 1, 3, 5, 7] ❌
9의 경우: [2, 4, 6, 8, 1, 3, 5, 7, 9] ❌
10의 경우: [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] ✅

대부분의 짝수, 홀수에서는 정상적으로 동작하지만, $8,9,14,15,26,27$ 등의 숫자에서 반례가 등장한다.

위 숫자들의 공통점은 $6k+2, 6k+3$으로 표현된다는 것이다.

해당 숫자들에 대한 규칙도 찾아보도록 하자.

2. N이 6k+2일 때

위 그림을 보면 알 수 있듯이, 체스판 절반 아래쪽 부분이 모두 위쪽 퀸에게 공격받는 모습을 볼 수 있다.

이를 해결하기 위해서, 표시된 빨간색 및 파란색 영역을 제외하고 퀸을 배치했을 때, 서로 공격하지 않도록 해야한다.

위쪽 퀸들의 공격 경로를 빨간색과 파란색 칸으로 표시해 나타내면 다음과 같다.

빨간색 네모칸은 대각선 왼쪽으로 공격하는 경로, 파란색 네모칸은 대각선 오른쪽으로 공격하는 경로, 빨간색 X 표시는 직선 경로를 뜻한다.

여기서 가장 경우의 수가 적은 7번 열부터 시작해본다.

첫 번째 퀸	두 번째 퀸	세 번째 퀸
		3열에 퀸을 놓을 수 없으므로 불가능

$(8,7)$에는 퀸을 둘 수 없다.

다음으로, $(7,7)$을 확인해보겠다.

첫 번째 퀸	두 번째 퀸	세 번째 퀸	네 번째 퀸

$(7,7)$에 퀸을 둘 경우, 위와 같이 배치가 가능하다. 이제 위 배치에서 규칙성을 찾아보자.

• $5$는 $3$
• $6$은 $1$
• $7$은 $7$
• $8$은 $5$

사실 이거 하나만 봐서는 규칙성을 볼 수가 없다. $N=14$인 경우도 봐보자.

여기서 규칙성을 찾을 수 있다. 위쪽 행을 [2, 4, 6, 8, 10, 12, 14]와 같이 짝수 칸으로 채운 후 아래쪽 행을 채울 때, [3, 1] 배열로 시작한다는 것을 알 수 있다. 이후 7부터 홀수 열을 순서대로 채우게 되고, 맨 마지막 행은 5열에 퀸이 놓이게 된다.

이를 코드로 구현하면 다음과 같다.

def solution(n: int) -> list:
    board = []
    for i in range(2, n + 1, 2):
        board.append(i)
    if n % 6 == 2:
        board.append(3)
        board.append(1)
        for i in range(7, n + 1, 2):
            board.append(i)
        board.append(5)
    else:
        for i in range(1, n + 1, 2):
            board.append(i)
    return board

for n in [8, 14, 20, 26]:
    print(f"{n:2d}의 경우:", solution(n), "✅" if check_queen(solution(n)) else "❌")

Output:
 8의 경우: [2, 4, 6, 8, 3, 1, 7, 5] ✅
14의 경우: [2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5] ✅
20의 경우: [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5] ✅
26의 경우: [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 3, 1, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 5] ✅

완벽하다.

3. N이 6k+3일 때

이제 $6k+3$일 때의 규칙을 찾아보자. 이거는 도무지 머리로 규칙이 안떠올라서 전체 경우의 수를 다 출력해두고 괜찮아 보이는 배열을 선택하였다..

위쪽 행은 짝수 열에만, 아래쪽 행은 홀수 열에만 배치한다는 점은 동일하다.

위 배치를 보면, $4$부터 시작해서 두 칸씩 건너뛰어 $2$까지, 그리고 아래쪽은 $5$부터 시작해서 두 칸씩 건너뛰어 $3$까지 순서대로 배치하는 것을 알 수 있다.

def solution(n: int) -> list:
    board = []
    if n % 6 == 3:
        for i in range(4, n + 1, 2):
            board.append(i)
        board.append(2)
        for i in range(5, n + 1, 2):
            board.append(i)
        board.append(1)
        board.append(3) 
    else:
        for i in range(2, n + 1, 2):
            board.append(i)
        if n % 6 == 2:
            board.append(3)
            board.append(1)
            for i in range(7, n + 1, 2):
                board.append(i)
            board.append(5)
        else:
            for i in range(1, n + 1, 2):
                board.append(i)
    return board

for n in [9, 15, 21, 27]:
    print(f"{n:2d}의 경우:", solution(n), "✅" if check_queen(solution(n)) else "❌")

Output:
 9의 경우: [4, 6, 8, 2, 5, 7, 9, 1, 3] ✅
15의 경우: [4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3] ✅
21의 경우: [4, 6, 8, 10, 12, 14, 16, 18, 20, 2, 5, 7, 9, 11, 13, 15, 17, 19, 21, 1, 3] ✅
27의 경우: [4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 2, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 1, 3] ✅

번외: #21133. N-Queen 2

#21133. N-Queen 2

위 문제는 #3344랑 크게 다를 것 없는 문제이다. 하지만 그대로 제출하면 시간 초과가 뜨게 된다. 나는 그랬다.

실행 시간을 줄이기 위해 input()은 sys.stdin.readline(), print()는 sys.stdout.write()로 바꿔주어야 한다.

이 문제는 규칙만 찾을 수 있다면 구현 자체는 매우 쉬운 문제이다. 하지만 그 규칙을 찾는게 쉽지 않았다.

내가 생각한 규칙보다 더 간단하고 쉬운 규칙이 존재할 수도 있다. 그래도 여러 경우의 수를 다 따져보며 규칙을 찾아 나가는 과정이 나름 재미있었다.

피보나치 수열은 다음과 같은 점화식으로 정의되는 수열이다.

$$ F_{0} = 0 \ F_{1} = 1 \ F_{n+2} = F_{n+1} + F_{n} $$

피보나치 수열을 제 15항까지 나타낸다면 다음과 같다.

피보나치 수열의 구현

피보나치 수열은 재귀 함수를 통해 구현 가능하다.

def fib(n: int) -> int:
    if n == 0 or n == 1: return n
    return fib(n - 1) + fib(n - 2)

fib(17)

위 코드를 직접 돌려보면, $n$을 $100$과 같이 큰 숫자를 넣기만 해도 굉장히 오래 걸리는 모습을 볼 수 있다. 어디서 오랜 시간이 소요되는걸까?

fib(5)를 구하기 위한 과정은 다음과 같다.

위 과정을 보면 fib(5)를 계산하기 위해 fib(3)은 두 번 호출되고, fib(2)는 세 번 호출된다.

즉, 하나의 노드 당 두 개의 자식 노드가 생성되고 있음을 나타낸다. 이를 시간 복잡도로 표현하자면, $O(2^{n})$이 된다.

다이나믹 프로그래밍

캐싱 방식 적용하기

기존의 재귀적 문제 풀이 방식에서의 가장 큰 문제는 같은 계산을 여러 번 하는 것이었다. 이러한 문제를 해결하기 위해 캐싱 방식을 사용하면 되지 않을까?

def fib(n):
    cache = {0: 0, 1: 1}
    def calc(n):
        if n in cache:
            return cache[n]
        else:
            cache[n] = calc(n-1) + calc(n-2)
            return cache[n]
    return calc(n)

fib(100)

캐싱을 하니 $n = 100$에 대한 값도 금방 나오는 것을 확인할 수 있다. 딕셔너리에 모든 값들을 캐싱하는 것이기 때문에, 나중에 값이 매우 커졌을 때 공간 복잡도에 문제가 발생하지 않을까 싶다.

시간복잡도를 보면 캐싱으로 인해 각 $n$에 대해 한 번만 계산을 수행하기 때문에 $O(n)$의 시간 복잡도를 얻을 수 있다.

그렇다면, 공간 복잡도를 줄이면서 $O(n)$의 시간 복잡도를 가질 순 없을까?

상향식으로 접근하기

위 방법 모두 $F_{n}$을 구하기 위해 $F_{n-1}$부터 $F_{0}$까지 $n$을 감소시켜가며 접근하였다. 반대로, $n$을 늘려가며 접근하는 방식은 어떨까?

def fib(n):
    if n == 0: return 0
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

fib(100)

위 방식을 보면, a와 b를 각각 $0$, $1$로 두고, $2$부터 $n+1$까지 올라가며 계산을 진행한다.

하나의 반복문으로 계산을 진행하기 때문에 $O(n)$의 시간 복잡도를 갖는다.

행렬의 거듭제곱

백준 #11444. 피보나치 수 6를 풀면서 새롭게 알게 된 개념이다. 피보나치 수열은 행렬의 거듭제곱 형태로 표현이 가능하다.

어떻게 가능할까?

먼저, 피보나치 수열은 앞서 말했듯이, 다음과 같은 점화식을 나타낸다.

$$F_{n+1} = F_{n} + F_{n-1}$$

이를 행렬 형태로 나타내본다.

$$ \begin{pmatrix} F_{n+1} \ F_{n} \end{pmatrix}

=

A \begin{pmatrix} F_{n} \ F_{n-1} \end{pmatrix} \tag{1} $$

여기서 행렬곱의 결과가 좌변과 같아지려면, $A$는 다음과 같아야 한다.

$$ \begin{pmatrix} F_{n+1} \ F_{n} \end{pmatrix}

=

\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}

\begin{pmatrix} F_{n} \ F_{n-1} \end{pmatrix} \tag{2} $$

여기서, 우변의 $\begin{pmatrix}F_n \F_{n-1}\end{pmatrix}$ 또한 다음과 같이 나타낼 수 있다.

$$ \begin{pmatrix} F_{n} \ F_{n-1} \end{pmatrix}

=

\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}

\begin{pmatrix} F_{n-1} \ F_{n-2} \end{pmatrix} \tag{3} $$

$(2)$번 수식과 $(3)$번 수식을 합치면 다음과 같이 거듭제곱으로 표현된다.

$$ \begin{pmatrix} F_{n+1} \ F_{n} \end{pmatrix}

=

\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^{2}

\begin{pmatrix} F_{n-1} \ F_{n-2} \end{pmatrix} \tag{4} $$

위 과정을 계속 진행하다 보면, 최종적으로 다음과 같은 수식이 나오게 된다.

$$ \begin{pmatrix} F_{n} \ F_{n-1} \end{pmatrix}

=

\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^{n}

\begin{pmatrix} F_{1} \ F_{0} \end{pmatrix}

=

\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^{n}

\begin{pmatrix} 1 \ 0 \end{pmatrix} \tag{5} $$

$\begin{pmatrix}1 & 1 \1 & 0\end{pmatrix}^{n}$ 행렬의 제곱을 풀어보면 다음과 같은 관계식을 갖는 것을 알 수 있다.

$$ \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^{n-1}

=

\begin{pmatrix} F_{n} & F_{n-1} \ F_{n-1} & F_{n-2} \end{pmatrix} \tag{6} $$

즉, 행렬의 첫 번째 행 첫 번째 열에 있는 값이 피보나치 수열의 $n$번째 값이 된다.

이를 코드로 구현하면 다음과 같다.

def multi(A: list, B: list) -> list:
    a11 = A[0][0]*B[0][0] + A[1][0]*B[0][1]
    a12 = A[0][0]*B[1][0] + A[1][0]*B[1][1]
    a21 = A[0][1]*B[0][0] + A[1][1]*B[0][1]
    a22 = A[0][1]*B[1][0] + A[1][1]*B[1][1]
    return [[a11, a12], [a21, a22]]

def power(F: list, n: int) -> list:
    result = F
    for _ in range(n - 2):
        result = multi(result, F)
    return result

def fib(n: int) -> int:
    F = [[1, 1], [1, 0]]
    return power(F, n)[0][0]

fib(100)

위 방식으르 활용하면 $O(n)$의 시간 복잡도를 얻을 수 있다.

여기서 지수의 특성을 활용해 분할 정복을 하게 되면 $O(\log{n})$까지 시간 복잡도를 줄여볼 수 있다.

def multi(A: list, B: list) -> list:
    a11 = A[0][0]*B[0][0] + A[1][0]*B[0][1]
    a12 = A[0][0]*B[1][0] + A[1][0]*B[1][1]
    a21 = A[0][1]*B[0][0] + A[1][1]*B[0][1]
    a22 = A[0][1]*B[1][0] + A[1][1]*B[1][1]
    return [[a11, a12], [a21, a22]]

def power(F: list, n: int):
    # 분할 정복을 활용한 거듭제곱
    if n == 0:
        return [[1, 0], [0, 1]]
    temp = power(F, n//2)
    result = multi(temp, temp)
    if n % 2 == 1:
        return multi(F, result)
    else:
        return result

def fib(n: int) -> int:
    F = [[1, 1], [1, 0]]
    return power(F, n-1)[0][0]

fib(100)

문제 풀어보기

#2747. 피보나치 수: 브론즈 문제임에도 불구하고 재귀를 이용한 단순 무식한 방법으로는 문제를 풀 수 없게 되어있다.

#11444. 피보나치 수 6: 일반적인 방식으로는 시간 초과가 뜨기 때문에, 모듈러 연산과 행렬의 거듭제곱 방식을 활용하여 문제를 해결해야 한다.

그래프 내 모든 정점 쌍 (i, j)에 대한 최단 거리를 구하는 알고리즘.

한 정점에서 출발해서 다른 모든 정점으로 가는 것 뿐만 아니라, 모든 정점 간의 최단 경로를 한 번에 구할 수 있다.

플로이드-와샬 알고리즘은 3중 for문을 사용한 DP를 통해 구현된다. ($O(n^{3})$)

전제 조건

동작 과정

플로이드 와샬 알고리즘은 다음과 같은 방식으로 진행된다.

1. 초기화 모든 정점 간의 거리를 다음과 같이 초기화한다.

   • dist[i][j] = 0 (i == j)
   • dist[i][j] = w (i에서 j로 가는 간선의 가중치 w가 존재할 때)
   • dist[i][j] = INF (그 외의 경우)

2. 중간 노드 k에 대해 모든 경로를 갱신

모든 정점 쌍 (i, j)에 대해, i -> j로 가는 경로가 i -> k -> j로 우회했을 때 더 짧은지 확인한다.

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

즉, 각 단계에서는 경로의 중간에 정점 k를 추가했을 때 더 짧은지를 확인하고 갱신한다.

음수 간선이 존재할 경우

음수 간선이 존재할 경우에도 다익스트라와 다르게, 동작 가능하다.

하지만, 음수 사이클이 존재할 경우 올바른 최단 거리를 구할 수 없다. 이 경우, dist[i][j] < 0인 정점이 생긴다.

구현

대표적인 플로이드 문제인 #11404. 플로이드를 봐보자.

각 정점간의 최단 거리를 모두 출력해야하는 문제이다. 앞서 설명한 동작 과정을 생각하면서 구현해보자.

def floyd_warshall(n: int, edges: list) -> list:
    dist = [[float("inf")] * n for _ in range(n)]
    for i in range(n): dist[i][i] = 0
    for s, e, c in edges: dist[s - 1][e - 1] = min(dist[s - 1][e - 1], c)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i - 1][j - 1] > dist[i - 1][k - 1] + dist[k - 1][j - 1]:
                    dist[i - 1][j - 1] = dist[i - 1][k - 1] + dist[k - 1][j - 1]
    return dist

간선 정보를 바탕으로 비용을 초기화하고, 3중 for문을 통해 i에서 j로 가는 경로 중 k를 경유하는 경우가 더 짧다면 갱신하는 방식으로 동작하게 된다.

#13549. 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 $N(0 \leq N \leq 100,000)$에 있고, 동생은 점 $K(0 \leq K \leq 100,000)$에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 $X$일 때 걷는다면 1초 후에 $X-1$ 또는 $X+1$로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 $2\times X$의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

접근 방식

실버 1 문제인 #1697. 숨바꼭질과의 차이점은 수빈이가 순간이동을 할 때 걸리는 시간이 1초에서 0초로 바뀌었다는 것이다. 즉, 한 번의 행동에 동일한 시간이 소요되는것이 아니다.

따라서 해당 문제는 다익스트라 알고리즘으로 접근하였다.

def solution(subin_x: int, sister_x: int) -> int:
    dist = [float("inf")] * 100_001
    dist[subin_x] = 0
    pq = [(0, subin_x)]
    while pq:
        d, x = heappop(pq)
        if x == sister_x: return dist[sister_x]
        if d > dist[x]: continue
        for nx, cost in [(x - 1, 1), (x + 1, 1), (x * 2, 0)]:
            if nx > 100_000 or nx < 0: continue
            nd = d + cost
            if nd < dist[nx]:
                dist[nx] = nd
                heappush(pq, (nd, nx))
    return dist[sister_x]

heapq를 사용하여 최소힙에 위치 및 이동 횟수 정보를 넣어주었고, 위치가 100,000을 넘어가게 되면 continue 하였다. 그 후 거리 배열(이동 횟수 배열)에서 동생의 위치에 해당하는 인덱스의 값을 리턴해주었다.

다른 방식

문제을 다 푼 다음 알고리즘 분류를 확인해보니 0-1 너비 우선 탐색이라는 항목이 보였다. 그래서 너비 우선 탐색을 활용하여 풀어보기로 했다.

0-1 너비 우선 탐색

간선 가중치가 0 또는 1인 그래프에서 최단거리를 $O(V+E)$에 구하는 알고리즘. 다익스트라보다 더 빠르고, 구현도 단순하다.

0-1 너비 우선 탐색에서 0과 1은 각각 다음과 같이 해석이 가능하다.

• 0: 우선순위 높음
• 1: 우선순위 낮음

일반적인 BFS는 큐를 하나만 쓰는데 어떻게 다익스트라처럼 동작할까?

0-1 BFS에서는 덱(deque)을 사용한다.

• 간선 가중치가 0 -> deque의 앞쪽에 넣음 (빨리 탐색)
• 간선 가중치가 1 -> deque의 뒤쪽에 넣음 (나중에 탐색)

위 아이디어를 가지고 코드를 구현해보면 다음과 같다.

def solution_with_BFS(subin_x: int, sister_x: int) -> int:
    dist = [float("inf")] * 100_001
    dist[subin_x] = 0
    queue = deque([(subin_x, 0)])
    while queue:
        x, d = queue.popleft()
        if x == sister_x: return d
        for nx, cost in [(x - 1, 1), (x + 1, 1), (x * 2, 0)]:
            if nx > 100_000 or nx < 0: continue
            if dist[x] + cost < dist[nx]:
                if cost == 0: queue.appendleft((nx, d))
                else: queue.append((nx, d + 1))
                dist[nx] = dist[x] + cost

만약 가중치(cost)가 0이라면 appendleft()를 통해 deque의 앞쪽에 넣고, 그렇지 않다면 원래 BFS 방식대로 append()를 통해 뒤쪽에 넣게 된다. 위 방식으로 우선순위를 정해줄 수 있다.

대략 60ms 차이가 나는 것을 알 수 있다.

가중치가 양수인 그래프에서, 한 정점으로부터 모든 정점까지의 최단 거리를 구하는 알고리즘.

그래프에서 경로를 탐색하면서, 비용이 최소인 경로부터 차례로 확정해나가는 방식. 우선순위 큐(힙)를 사용하면 매우 효율적으로 구현이 가능하다.

전제 조건

우선순위 큐가 아닌 배열 기반으로 코드를 구성하면 $O(V^{2})$로 매우 느리지만, 우선순위 큐를 기반으로 코드를 구성하면 $O(E\log{V})$로 빠르다.

간선에 음수 가중치가 있다면 다익스트라는 사용할 수 없다.

동작 과정

다익스트라는 다음 과정을 반복하며 최단 거리를 확정한다.

1. 시작 노드의 거리를 0으로 설정하고, 나머지는 무한대로 초기화한다.
2. 우선순위 큐에 (거리, 노드) 형태로 삽입한다.
3. 큐에서 거리가 가장 짧은 노드를 꺼낸다.
4. 해당 노드에서 인접한 노드를 탐색하며, 더 짧은 거리로 도달 가능한 경우, 거리 배열을 갱신하고 큐에 넣는다.
5. 모든 노드가 처리될 때까지 반복한다.

그림으로 보면 다음과 같다.

순서	그래프 이미지
1
2
3
4
5
6
7

음수 가중치가 있는 경우

다익스트라는 "먼저 방문한 경로가 최단 거리"라는 가정을 전제로 한다. 하지만 음수 가중치가 있는 경우, 이 가정이 깨질 수 있다.

단순히 음수 가중치가 있다고 동작하지 않는것은 아니다. 하지만, 음수 간선 자체가 더 짧은 경로가 나중에 등장하는 상황을 만들수도 있다.

-> 따라서 음수 가중치가 있는 경우엔 벨만-포드 알고리즘을 사용해야 한다.

추가로, 그래프 내에 음수 사이클이 존재한다면 거리가 무한히 작아져 다른 알고리즘도 계산이 불가능하다.

구현

위 과정을 생각하며 코드를 구현해보자. 대표적인 다익스트라 문제인 #1753. 최단경로를 봐보자.

시작점에서 다른 모든 정점으로의 최단 경로를 구하는 전형적인 다익스트라 알고리즘 문제이다. 하나씩 구현을 해보겠다.

from heapq import heappop, heappush

def dijkstra(graph: dict, start: int) -> list:
    # 1. 시작 노드의 거리를 0으로 설정하고, 나머지는 무한대로 초기화한다.
    dist = [float("inf")] * 6        # 노드 번호가 1번부터 시작하므로 0번 인덱스는 사용하지 않음
    dist[start] = 0
    # 2. 우선순위 큐에 (거리, 노드) 형태로 삽입한다.
    pq = [(dist[start], start)]
    # 5. 모든 노드가 처리될 때까지 반복한다.
    while pq:
        print("heapq (거리, 노드):", pq)
        # 3. 큐에서 거리가 가장 짧은 노드를 꺼낸다.
        d, n = heappop(pq)
        if d > dist[n]: continue    # 현재 거리가 거리 배열에 저장된 거리보다 크다면 탐색할 필요가 없음.
        # 4. 해당 노드에서 인접한 노드를 탐색하며, 더 짧은 거리로 도달 가능한 경우, 거리 배열을 갱신하고 큐에 넣는다.
        for nn, cost in graph[n]:
            nd = d + cost
            if nd < dist[nn]:
                dist[nn] = nd
                heappush(pq, (nd, nn))
    return dist

heapq 라이브러리를 사용하여 pq 리스트에 최소힙 형태로 저장한다.

이후 큐가 빌때까지 위 과정을 무한반복하게 된다.

이후 반환되는 거리 배열을 출력해보면 테스트 케이스에 나와있는대로 값이 나오는 것을 알 수 있다.

가상 호스트 파일 만들기

아파치에서는 가상 호스트를 설정해서 하나의 서버에 여러 도메인 서비스를 제공할 수 있다. 하지만 도메인을 각각 부여하기에는 무리가 있어서, 포트별로 구분을 해주었다. 일단 musicApp.conf라는 이름의 파일을 새로 만들어준다.

sudo vi /etc/apache2/site-available/musicApp.conf

그 다음 아래와 같이 내용을 작성해주었다.

<VirtualHost *:5050>
        ServerName mydomain
        ServerAlias mydomain
        DocumentRoot /var/www/html/music-app/php
        <Directory /var/www/html/music-app/php>
                Options Indexes FollowSymLinks
                AllowOverride None
                Require all granted
        </Directory>

        ErrorLog ${APACHE_LOG_DIR}/error.log
        CustomLog ${APACHE_LOG_DIR}/access.log combined

        SSLEngine On
        SSLCertificateFile /etc/letsencrypt/live/mydomain/fullchain.pem
        SSLCertificateKeyFile /etc/letsencrypt/live/mydomain/privkey.pem
</VirtualHost>
<VirtualHost *:500>
        ServerName mydomain
        ServerAlias mydomain
        DocumentRoot /var/www/html/music-app/music-app/build
        <Directory /var/www/html/music-app/music-app/build>
                Options Indexes FollowSymLinks
                AllowOverride None
                Require all granted
        </Directory>

        SSLEngine On
        SSLCertificateFile /etc/letsencrypt/live/mydomain/fullchain.pem
        SSLCertificateKeyFile /etc/letsencrypt/live/mydomain/privkey.pem
</VirtualHost>

개인 서버에 SSL 인증서가 있어서 SSL 관련 설정도 추가해주었다. 그리고 가상 호스트를 활성화해준다.

sudo a2ensite musicApp.conf

이후 아파치를 재시작해준다.

sudo service apache2 restart

이제 js코드 내에 있는 php 통신 경로에 :5050을 붙여주고, mydomain:500으로 접근하면 정상적으로 뜰 것 같지만, 아직 안된다. 아파치에서 해당 포트에 관한 리스닝이 안되어있기 때문이다. 리스닝 설정을 해주자.

ports.conf 파일 수정하기

ports.conf 파일은 아파치 가상 호스트에서 사용하는 포트를 관리하는 파일이다.

sudo vi /etc/apache2/ports.conf

# If you just change the port or add more ports here, you will likely also
# have to change the VirtualHost statement in
# /etc/apache2/sites-enabled/000-default.conf

Listen 80

<IfModule ssl_module>
        Listen 443
</IfModule>

<IfModule mod_gnutls.c>
        Listen 443
</IfModule>

기본 구성은 다음과 같다. 80번 포트와 443번 포트에 대해서 대기하도록 설정되어 있다는 뜻이고, 모듈이 ssl_module 또는 mod_gnutls.c일 경우 443 포트에서 대기한다는 뜻이다. 80번 포트는 HTTP 트래픽, 443번 포트는 HTTPS 트래픽을 위한 포트이다. 이제 Listen 80 아랫줄에 원하는 포트 번호를 추가해주면 된다.

Listen 80
Listen 500
Listen 5050

웹 호스팅용 포트 500과 php 서버용 포트 5050을 열어주었다.

포트 방화벽 열기

만약 서버에 방화벽 설정이 되어있다면, 그냥 접속할 시 오류가 발생할 것이다. 해당 포트가 막혀있기 때문인데, 해당 포트의 방화벽을 열어주면 해결된다.

sudo ufw allow 5050/tcp
sudo ufw allow 500/tcp

tcp통신에서 5050 포트와 500 포트의 접근을 허용해준다.

위 명령어를 실행하게 되면 규칙을 추가했다는 문구가 뜰 것이다. 이제 다시 웹에 접속해보면 정상적으로 호스팅되는 모습을 확인할 수 있다.

마무리

의도치않게 가상 호스트를 나눠주는 작업을 하게 되었는데, 알고 있어야 할 유용한 내용인 것 같아 따로 정리하게 되었다. 추후 개인 서버에 토이 프로젝트를 진행하게 된다면 유용하게 사용할 것 같다.

1) User의 Home 폴더에 자동으로 public_html 폴더 생성

adduser을 했을 때 자동으로 public_html이 생성되도록 해야한다. /etc/skel 디렉토리는 리눅스 운영체제에서 새로운 사용자를 생성하였을 경우, 새 사용자를 위한 기본 폴더를 참고하는 디렉토리이다.

$ mkdir /etc/skel/public_html
$ vim /etc/skel/public_html/index.html

index.html에는 아무 내용이나 적어주면 된다.

<html>
    <head><title>This is cslinux2</title></head>
    <body><p>hello world</p></body>
</html>

아마 위 작업까지 마친 후에도 안된다면 아래 명령어를 차례대로 실행해주면 된다.

그래도 안된다 하면 아래 방법을 시도해보자.

2) Symbolic Link 설정

$ cd /etc/apache2/mods-enabled
$ sudo ln -s ../mods-available/userdir.conf userdir.conf
$ sudo ln -s ../mods-available/userdir.load userdir.load
$ sudo service apache2 restart

3) home 디렉토리 접근 권한 설정

$ sudo vim /etc/apache2/apache2.conf

<Directory /home>
        Options Indexes FollowSymLinks
        AllowOverride None
        Require all granted
</Directory>

이제 http://mydomain/~id로 들어가주면 성공적으로 뜨는 모습을 확인할 수 있다.

1) Apache2 설치

아래 명령어를 입력해 apache2를 설치해준다.

$ sudo apt update
$ sudo apt upgrade
$ sudo apt install apache2

아파치 서버를 시작 및 중지, 재시작 하는 명령어는 다음과 같다.

$ sudo service apache2 start
$ sudo service apache2 stop
$ sudo service apache2 restart

Apache2를 설치하고 난 뒤 자신의 서버에 http 프로토콜을 이용해 접속을 하게 되면 브라우저아 다음과 같은 화면이 나온다.

2) MySQL 설치

아래 명령어를 입력해 mysql을 설치해준다.

sudo apt install mysql-server

MySQL 서버의 보안 스크립트는 따로 할 필요 없다.

3) PHP 설치

Apache2와 MySQL 설치가 정상적으로 끝이 났다면 php 설치를 진행해준다.

$ sudo apt install php libapache2-mod-php php-mysql

위 명령어를 통해 php 설치 및 php에서 apache2와 mysql을 사용할 수 있게 해주는 모듈을 설치할 수 있다.

php 설치가 끝이 나면 /var/www/html 경로로 이동하여 index.php 를 생성하고 다음과 같이 코딩해준다.

<?php
    phpinfo();
?>

이러한 문제를 해결하기 위해 우분투의 커널 버전을 변경해주었다.

Ubuntu 커널 변경

1) Mainline를 통해 커널 다운로드

우리가 사용하고 있는 백업용 NAS의 최신 지원 커널이 5.9.16이었다. 물론 2년 전의 일이니 현재는 더 많은 커널 버전을 지원할 수도 있지만, 전에 사용하였던 5.9.16 버전 커널을 사용하려고 한다.

먼저 터미널을 열어 ppa를 추가해준다.

$ sudo add-apt-repository ppa:cappelikan/ppa

apt를 업데이트 한 다음 mainline을 설치한다.

$ sudo apt update
$ sudo apt install mainline

이제 Mainline을 실행시킨다.

Mainline을 실행시키면 설치 가능한 Ubuntu Kernel 버전을 확인 가능하다. 여기서 설치해야 하는 버전(5.9.16)을 선택해 Install 해 준다.

2) GRUB 설정 변경

커널의 설치가 완료된 후 재부팅을 하게 되면 새로 설치한 커널이 아닌 기존의 커널로 진입이 될 것이다. 따라서 새로 설치한 커널의 버전으로 진입하게 설정을 해주어야 하는데, GRUB 부트로더의 설정을 변경해주어야 한다.

$ sudo vim /etc/default/grub

위 명령어를 입력 후 GRUB 부트로더의 설정을 다음과 같이 변경해준다.

GRUB_TIMEOUT_STYLE=menu
GRUB_TIMEOUT=3

수정이 완료되었다면 GRUB 부트로더를 업데이트 해준다.

$ sudo update-grub

이후 재부팅하면 GRUB 부트로더 화면이 3초간 뜨게 된다.

위 아래 방향키를 이용해 [Advanced options for Ubuntu] 를 선택해준 다음 엔터를 누르게 되면 현재 설치되어 있는 커널 목록이 표시된다.

우리는 5.9.16 버전을 사용할 것이기 때문에 5.9.16 버전이 위에서 몇 번째에 있는지 확인해준다. (0부터 넘버링)

위 예시이미지에서 만약 5.13.0-25-generic으로 진입하고 싶다면 ‘2’를 기억하고 있으면 된다.

다시 grub 부트로더 파일을 수정해준다.

$ sudo vim /etc/default/grub

GRUB_DEFAULT="1>해당하는번호"

위와 같이 입력해주면 된다. 예시 이미지를 예로 들면 GRUB_DEFAULT="1>2"로 수정해주면 된다.

다시 sudo update-grub 을 해준 후에 재부팅하여 해당 커널에 잘 진입하는지 확인해보면 된다.

커널 버전을 확인하는 명령어는 다음과 같다.

$ uname -r
5.9.16-050916-generic

References

[Ubuntu 20.04-LTS]Kernel 설치 및 변경하기, by 평범한 이야기 2-1. GRUB 설치, 수정, recovery mode, by markyang92

1) Open SSH Server 설치

터미널에서 Open SSH Server를 설치한다.

$ sudo apt update
$ sudo apt install openssh-server

2) SSH Server 실행

SSH를 설치하면 자동으로 실행된다. 다음 명령어로 SSH가 실행 중인지 확인할 수 있다. 로그에서 active (running)이 보이면 실행 중인 상태이다.

$ sudo systemctl status ssh
● ssh.service - OpenBSD Secure Shell server
     Loaded: loaded (/lib/systemd/system/ssh.service; enabled; vendor preset: enabled)
     Active: active (running) since Thu 2023-01-12 17:27:49 KST; 1 day 21h ago
       Docs: man:sshd(8)
             man:sshd_config(5)
   Main PID: 837 (sshd)
      Tasks: 1 (limit: 76964)
     Memory: 4.9M
     CGroup: /system.slice/ssh.service
             └─837 sshd: /usr/sbin/sshd -D [listener] 0 of 10-100 startups

실행 중이 아니라면 다음 명령어를 통해 실행시킬 수 있다.

$ sudo systemctl enable ssh
$ sudo systemctl start ssh

SSH Server Port 변경

ssh 접속 포트는 22이다. 이를 특정 포트 번호로 바꿔줄 수 있다. 해당 포스트에서는 1022로 변경해 줄 것이다.

Ubuntu에는 기본적으로 SSH Client가 설치되어 있지만, 만일 없다면 다음 명령어를 통해 설치해 볼 수 있다.

$ sudo apt-get install openssh-client

접속 포트는 sshd_config 파일을 수정해 변경해 볼 수 있다.

$ sudo vim /etc/ssh/sshd_config

참고로 vim이 없다면 파일 수정이 불가능하니 그 전에 vim을 깔아주도록 하자.

vim이 열렸다면 i를 눌러 수정 모드로 변경한다. Port 부분의 주석을 해제하고 22를 1022로 변경해주면 된다.

Include /etc/ssh/sshd_config.d/*.conf

Port 1022
#AddressFamily any
#ListenAddress 0.0.0.0
#ListenAddress ::

수정이 완료되었다면 esc를 누른 후 :wq 를 이용해 저장해주면 된다. 변경한 포트를 적용하기 위해서는 ssh 서비스를 재시작해야 한다.

$ sudo service ssh restart

서비스를 재시작하였으면 netstat 명령어를 이용해 ssh가 변경된 포트에서 돌아가고 있는지 확인해준다. netstat은 net-tools를 설치하여 사용할 수 있다.

$ sudo apt install net-tools
$ netstat -tnlp

이제 포트 1022로 ssh 접속을 하게 되면 성공적으로 접속이 되는 것을 확인할 수 있다.

$ ssh myserver@myserver.domain.com -p 1022

Ubuntu 20.04LTS 설치

1) Ubuntu 20.04LTS 설치

이 글을 작성한 현재 시점에서는 20.04보단 22.04를 주로 사용하긴 한다. 버전이 바뀐다고 설치 방법이 달라지는 것은 아니기 때문에 20.04 버전을 기준으로 작성하였다.

먼저 아래 사이트에 접속해서 Alternative downloads > Ubuntu Server 20.04LTS를 다운받는다.

https://ubuntu.com/download/server

2) Ubuntu Server 20.04 부팅 USB 생성

ISO 파일을 다운받는 동안 아래 사이트에서 balenaEtcher를 다운받는다.

https://www.balena.io/etcher/

balenaEtcher는 이미지를 USB 드라이브로 Flash하는 무료 오픈 소스 유틸리티이며 Windows, MacOS 및 Linux를 지원한다. 설치 파일이 다운로드되면 해당 파일을 클릭하여 설치 마법사를 시작한다. 설치 마법사의 단계에 따라 Etcher를 설치한다.

balenaEtcher와 ISO 파일 설치가 완료되었으면 balenaEtcher를 열어준다.

[Flash from file]을 클릭한 다음 전에 다운받았던 ISO 파일을 선택한다.

ISO를 설치할 USB를 연결한 다음 [Select target]을 클릭해 USB Device를 선택해준다.

[Flash!] 버튼을 누르고 완료되기를 기다리면 된다.

Flash가 완료되면, 서버의 USB 포트에 USB를 연결하고 바이오스에 진입해 부팅 디스크를 USB로 바꿔준다. 바이오스에 진입하는 키는 메인보드 제조사마다 다르며, 보통 F2 혹은 F12, Del이다. 부팅 디스크를 변경해 준 후에 재부팅을 하게 되면 Ubuntu를 설치할 수 있게 된다.

3) Ubuntu 20.04 설치

언어를 한국어로 변경한 후 [Ubuntu 설치]를 눌러준다.

키보드 레이아웃을 정하고 [계속하기]를 누른다.

[일반 설치]와 [그래픽과 Wi-Fi 하드웨어 그리고 추가 미디어 포맷을 위한 서드파티 소프트웨어 설치]에 체크를 해준다. [Ubuntu 설치 중 업데이트 다운로드]는 현재 이더넷 연결을 하지 않았기 때문에 체크가 불가능하다.

[디스크를 지우고 Ubuntu 설치]를 선택하고 [지금 설치]를 클릭해준다.

이름과 컴퓨터 이름, 사용자 이름 모두 원하는 사용자 명으로 변경해준다. 암호는 서버실에서 사용하는 공용 암호로 지정해주었다.

[로그인할 때 암호 입력]에 체크를 해준다.

설치에 다소 시간이 소요된다. 기다려주면 된다.

설치가 완료되면 위와 같은 팝업창이 뜬다. [지금 다시 시작]을 눌러주면 된다.

사용자 계정 클릭 후 암호를 입력하여 로그인한다.

4) Ubuntu Server 이더넷 연결

이제 인터넷을 연결해주어야 한다.

상단의 아이콘을 눌러 인터넷 설정으로 진입한다.

톱니바퀴 모양의 아이콘을 눌러 설정창으로 진입한다.

IPv4로 들어가서 IPv4 Method를 Manual로 설정해 준 다음 Address, Netmask, Gateway, DNS 주소를 입력해준다. 서버마다 고정된 IP 주소가 있으니, 그대로 입력해주기만 하면 끝이 난다.

인터넷 연결이 되었는지에 대한 확인은 Firefox를 열어 유튜브에 들어가 확인해본다.

References

[ Ubuntu ] 우분투 설치 USB 만들기 - balenaEtcher, by VirusHeo Ubuntu 20.04 Desktop / 설치하기, by MANUAL FACTORY