Struggling Journey

자료구조는 데이터를 효율적으로 사용할 수 있도록 데이터를 저장하고 구성하는 방법. 1. 선형구조 선형 리스트 (Array) 배열은 연속해있는 데이터의 집합 각 데이터는 index를 가지며, n개를 원소로 가지는 배열일 때 순서대로 0 ~ n-1 배열은 고정된 크기를 가지는 자료 구조 Array의 시간복잡도 Access : O(1) Search : O(n) Insertion : O(n) Deletion : O(n) 연결 리스트 (Linked List) 연결 리스트는 요소가 연속적인 메모리 위치에 저장되지 않는 자료 구조. LinkedList는 각 원소가 다음 index 위치에 해당하는 물리적 주소를 가지고 있음. 삽입/삭제시에는 데이터를 Shift할 필요 없이, 해당되는 원소의 물리적 주소만 변경해주면 됨..

다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘. 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산함. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작. 다익스트라 알고리즘 동작 과정 출발 노드를 설정함. 최단 거리 테이블을 초기화함. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택함. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신함. 위 과정에서 3번과 4번을 반복함. 알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있음. 처리 과정에서 더 짧은 경로를 찾으면 갱신함. 다익스트라 알고리즘을 수행한 뒤에 테이블에 ..

신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 함. 최소 신장 트리 최소한의 비용으로 구성되는 신장 트리 크루스칼 알고리즘 최소 비용 신장 트리를 찾는 알고리즘 Edge의 개수를 E, Vertex의 개수를 V라고 하면 이 알고리즘은 O(ElogV)의 시간복잡도를 갖는다. 구체적인 동작 과정 간선 데이터를 비용에 따라 오름차순으로 정렬 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인 사이클이 발생하지 않는 경우 최소 신장 트리에 포함 사이클이 발생하는 경우 최소 신장 트리에 포함 X 모든 간선에 대하여 2번의 과정을 반복 [참고] ko.wikipedia.org..

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법. - 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구. - 그리디 해법은 정당성 분석이 중요. => 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토. - 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음. - 하지만 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제. - 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유 => 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문. -..

- 사이클이 없는 연결 그래프 - 정점의 개수 : V - 간선의 개수 : V-1 - 모든 정점이 연결되어 있어야 함 - 이진 트리 - 포화 이진 트리 - 리프 노드를 제외한 노드의 자식의 수 : 2 - 리프 노드의 자식의 수 : 0 - 모든 리프 노드의 깊이가 같아야 함. - 높이가 h인 토리의 노드 개수 = 2^h - 1 - 완전 이진 트리 - 마지막 레벨을 제외한 모든 노드들이 채워져있음. 마지막 레벨 노드들은 가능한 한 왼쪽부터 채워져있는 구조. - 트리는 그래프이기 때문에 그래프의 표현과 같은 방식으로 저장할 수 있음. - 루트가 있는 트리인 경우, 트리의 모든 노드는 부모를 하나 또는 0개 가지므로 부모만 저장하는 방식으로 저장할 수 있음. - 트리를 표현하는 방식 1. 배열에 트리의 부모만 저..

- 그래프는 정점과 간선으로 이루어진 자료구조의 일종 - 정점 (Node, Vertex) - 간선 (Edge) : 정점 간의 관계를 나타냄. - 경로 : 정점 A에서 B로 가는 경로 - e.g) A -> C -> D -> E -> B - 사이클 : 정점 A에서 다시 A로 돌아오는 경로 - e.g) A -> C -> B -> A - 방향 있는 그래프 - 방향 없는 그래프 (양방향 그래프) - 차수 : 정점과 연결되어 있는 간선의 개수 - 그래프 문제를 풀기 위해서는 문제에 나와있는 상황을 그래프로 모델링 후 여러가지 알고리즘을 수행해야함. - 그래프를 저장한다는 것은 간선을 저장하는 것. - 그래프를 저장하는 방법에는 2가지 방법이 있음. 인접행렬 인접리스트 - 이렇게 저장하므로써 한 정점 X와 연결된 간..

- 다이나믹 프로그래밍 -> 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 - 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있음. Overlapping Subproblem : 겹치는 부분문제 Optimal Substructure : 최적 부분구조 - 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 함. - Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같음. - 정답을 한 번 구했으면 그 값을 배열에 저장해둔다. (Memoization) - 다이나믹 프로그래밍의 구현 방식에는 두 가지 방법이 있다. Top-down : 큰 문제부터 쪼개가면서 작은 문제를 만들고 합쳐가면서 원래 문제를 푸는 방식 Bottom-up : 작은 문제들을 모아서 큰 문제..