전체 글

BFS를 구현할 때 visited를 큐에 넣기 전에 바꾸는 코드를 자주 본다. 아직 정점을 꺼내서 처리하지도 않았는데 왜 방문했다고 표시할까? 같은 정점으로 가는 경로가 둘 이상인 그래프를 따라가면 이유가 보인다.여기서는 가중치가 없는 그래프에서 최단 간선 수를 구하는 단일 시작점 BFS를 다룬다. 예제는 Python 3의 인접리스트와 FIFO 큐를 사용한다.1. 방문 표시는 ‘발견했다’는 뜻이다BFS의 정점은 아직 발견하지 않은 상태, 발견해서 큐에서 기다리는 상태, 이웃 검사를 마친 상태로 나눌 수 있다. 단순한 구현에서는 뒤의 두 상태를 모두 방문한 것으로 취급한다. 따라서 방문 표시는 처리가 끝났다는 뜻보다 이미 처리할 대상으로 등록했다는 뜻에 가깝다.Boost.Graph 공식 BFS 문서도 처음..

서버가 요청을 처리했는데 응답이 도착하기 전에 연결이 끊겼다면, 클라이언트는 성공 여부를 확신하기 어렵다. 같은 요청을 다시 보내도 될까? 이 질문을 판단할 때 필요한 성질이 멱등성(idempotency)이다.1. 같은 응답이 아니라 같은 의도된 효과HTTP에서 멱등은 동일한 요청을 여러 번 보냈을 때 서버에 미치는 의도된 효과가 한 번 보냈을 때와 같은 성질이다. 응답 본문과 상태 코드까지 같아야 하는 것은 아니다. 요청마다 접근 로그가 쌓이는 것도 이 정의와 모순되지 않는다. RFC 9110은 PUT, DELETE와 안전한 메서드를 멱등으로 분류한다. RFC 9110 §9.2.2안전성(safe)은 클라이언트가 서버 상태 변경을 요청하지 않는다는 의미다. GET은 안전하고 멱등이지만, DELETE는 상..

WHERE 조건도 같고 인덱스도 같은데, SELECT에 컬럼 하나를 추가하면 조회 경로가 달라질 수 있다. 인덱스가 조건에 맞는 행을 찾는 데 쓰이는지와, 결과를 만드는 데 필요한 값까지 제공하는지는 다른 질문이기 때문이다.이 글은 MySQL 8.4의 InnoDB를 기준으로 커버링 인덱스를 정리한다. 아래 SQL은 설명용 독립 예제이며 실제 실행계획·실행 시간은 측정하지 않았다. 출력 예측을 실행 결과처럼 제시하지 않고 직접 확인할 항목을 함께 적었다.1. 커버링은 인덱스와 쿼리의 관계다커버링 인덱스는 특정 쿼리에 필요한 컬럼 값을 인덱스에서 모두 얻을 수 있는 인덱스다. 별도의 CREATE COVERING INDEX 문법으로 만드는 종류가 아니다. 같은 인덱스가 어떤 쿼리는 커버하고 다른 쿼리는 커버하..

클라우드 환경 정리 1. 클라우드 환경 개요정의클라우드 환경은 인터넷을 통해 서버, 스토리지, 네트워크, 데이터베이스, 소프트웨어 등의 자원을 필요할 때 즉시 사용할 수 있도록 제공하는 환경이다.사용 이유초기 장비 구매 비용 없이 빠른 서비스 운영 가능글로벌 확장 및 빠른 배포유지보수 부담 감소장점 & 단점장점사용량 기반 과금 (Pay-as-you-go)빠른 확장성 (Auto Scaling)고가용성 (HA 보장, 여러 리전 활용)다양한 연계 서비스 제공단점보안/개인정보 유출 위험대규모 서비스 운영 시 비용 증가 가능특정 벤더 종속성(Vendor Lock-in) 발생실무 필요 역량AWS, GCP, Azure 등 클라우드 콘솔/CLI 활용 능력Docker/Kubernetes와 같은 컨테이너 운영 능력CI/C..

vector의 push_back의 시간복잡도가 평균적으로 O(1)인 이유vector의 내부 동작 구조std::vector는 동적 배열 기반 자료구조로, 메모리 공간을 일정량 미리 할당해 두고, 새로운 원소가 추가될 때 공간이 남아 있으면 단순히 뒤에 덧붙이기(push_back)만 합니다.이 경우 추가 연산은 단순한 인덱스 접근이므로 O(1)입니다.리사이징(Reallocation)의 영향만약 현재 할당된 공간이 모두 찼다면, vector는 다음과 같은 작업을 수행합니다:더 큰 새 배열(보통 기존 크기의 2배)을 생성기존 데이터를 모두 복사이전 메모리 해제새 공간에 데이터 삽입이 과정은 O(n)이 걸리지만, 자주 발생하지 않고 지수적으로 증가하기 때문에 amortized(평균) 시간복잡도는 O(1)입니다.시..

맵(Map)맵(Map)의 정의와 자료구조 구조맵(Map)은 Key-Value 쌍의 데이터를 저장하고, Key를 통해 Value를 빠르게 검색할 수 있는 자료구조입니다. 언어별로 std::map(C++), TreeMap(Java) 등으로 제공되며, **이진 탐색 트리(Balanced BST)**를 기반으로 동작합니다.맵에서의 연산 별 시간복잡도연산시간복잡도설명검색 (find)O(log n)균형 이진 트리 기반삽입 (insert)O(log n)트리 균형 유지 포함삭제 (erase)O(log n)노드 위치 탐색 후 삭제순회 (traverse)O(n)정렬된 순서로 모든 요소 탐색 가능대부분의 표준 map 구현은 Red-Black Tree 또는 AVL Tree 기반이므로 log n 시간 보장셋(Set)셋(Set)..