알고리즘 자료구조 공부일지

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)..

그래프 표현 방식으로서 인접행렬과 인접리스트의 근본적 개념 차이인접행렬의 정의정점 수가 V인 그래프에 대해 V × V 크기의 2차원 배열을 사용하여 정점 간의 연결 상태를 저장합니다.G[i][j]의 값은 정점 i에서 정점 j로의 간선 유무 또는 가중치를 나타냅니다.인접리스트의 정의정점마다 별도의 리스트를 만들어 각 정점에 연결된 이웃 정점들의 정보를 저장합니다.총 V개의 리스트가 존재하며, 리스트 내부에 연결된 간선만 저장합니다.메모리 사용 측면에서의 공간 복잡도 차이인접행렬의 공간 복잡도O(V²)→ 정점 쌍마다 하나의 값이 필요하므로, 간선의 수(E)와 무관하게 항상 정점 수 제곱 크기의 메모리가 필요합니다.희소 그래프에서 비효율적→ 대부분의 값이 0이지만, 그럼에도 불구하고 메모리를 차지함인접리스트의..

그래프 이론에서 인접리스트(Adjacency List)의 개념과 정의인접리스트(Adjacency List)란, 그래프의 정점 간 연결 관계를 표현하기 위한 자료구조로, 각 정점이 연결된 다른 정점들의 리스트를 개별적으로 유지하는 방식입니다.이는 희소 그래프(Sparse Graph) 즉, 간선의 수가 적은 그래프에서 특히 유리한 표현 방식으로, 메모리 공간의 효율성과 탐색 효율성을 동시에 고려한 구조입니다.인접리스트의 기본 구조 정의그래프에 정점이 V개 존재할 때, **크기가 V인 배열(또는 리스트)**을 생성합니다.각 인덱스 i는 정점 i를 의미하며, 그 위치에는 정점 i와 연결된 정점들의 리스트가 저장됩니다.예: 정점 0과 연결된 정점이 1, 3이면 → adj[0] = [1, 3]리스트의 구현 방식은 ..

그래프 이론에서 인접행렬(Adjacency Matrix)의 개념과 정의인접행렬은 그래프(Graph)의 정점(Vertex) 간 연결 관계를 2차원 배열 형태로 표현하는 방식입니다.그래프를 컴퓨터에 저장하거나 알고리즘을 적용하기 위해서는 정점 간의 간선(Edge) 정보를 구조화해야 하며, 그 대표적인 방식 중 하나가 인접행렬입니다.인접행렬의 기본 정의V개의 정점을 가진 그래프에 대해, **V x V 크기의 2차원 배열(matrix)**을 생성합니다.행과 열은 각각 그래프의 정점을 의미하며, 행 i, 열 j에 저장된 값은 정점 i에서 정점 j로의 간선 존재 여부나 가중치를 나타냅니다.G[i][j] = 1 → 정점 i와 정점 j가 연결되어 있음 (무가중치 그래프 기준)G[i][j] = w → 연결..

이진 탐색 트리의 정의 및 구조적 원리 설명이진 탐색 트리(Binary Search Tree, BST)는 이진 트리의 특수한 형태로, 각 노드가 정렬된 방식으로 데이터를 저장하는 구조입니다. BST는 다음과 같은 조건을 만족합니다:각 노드는 최대 두 개의 자식 노드를 가짐 (이진 트리 조건)왼쪽 서브트리의 모든 노드 값 오른쪽 서브트리의 모든 노드 값 > 현재 노드의 값이 속성은 모든 서브트리에 재귀적으로 적용됨이러한 구조적 원리를 통해 BST는 효율적인 검색, 삽입, 삭제 연산을 지원합니다.이진 탐색 트리의 삽입, 탐색, 삭제 알고리즘 설명삽입(Insert) 연산의 작동 방식루트 노드부터 시작하여 삽입할 값을 비교합니다.삽입할 값이 현재 노드보다 작으면 왼쪽 자식으로 이동합니다.크면 오른쪽 자식으로 이..