[자료구조 & 알고리즘] 11. 다익스트라
다익스트라1. 가중치 그래프 (Weighted Graph)• 그래프의 간선에 가중치가 부여된 그래프. • 각 정점을 방문할 때 모든 간선이 똑같은 비용이 드는 것이 아닌, 서로 다른 비용이 드는 것을 나타낼 때 사용. - 예를 들어, 도시들과 그들을 잇는 도로를 그래프로 표현할 때 각 도시들끼리 도로를 따라 이동할 때 걸리는 시간을 가중치로 나타낼 수 있음. • 구현 방법 - 인접 행렬 - 각 정점에서 연결되지 않은 정점에는 0, 연결된 정점에는 가중치를 표현private static int[][] adjacencyMatrix() { return new int[][] { {0, 2, 0, 1, 0, 0, 0, 0}, {0, 0, ..
[자료구조 & 알고리즘] 10. 힙, 우선순위 큐
힙, 우선순위 큐1. 힙 (Heap)• 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리 형태의 자료구조• 최대값을 빠르게 찾기 위한 최대 힙과 최소값을 빠르게 찾기 위한 최소 힙이 있음.• Max Heap (최대 힙) - 부모 노드의 값이 자식 노드의 값보다 큼. - root 노드가 가장 큼.• Min Heap (최소 힙) - 부모 노드의 값이 자식 노드의 값보다 작음. - root 노드가 가장 작음.• 값을 삽입 및 삭제할 때마다 트리를 재정렬하여 부모 자식 간의 대소관계를 올바르게 함. - 삽입 : 완전 이진 트리의 마지막에 노드 삽입 -> 부모와 대소 관계를 비교하여 서로 자리를 바꾸는 것을 반복. O(log n)의 시간 복잡도 ..
[자료구조 & 알고리즘] 9. 동적 계획법
동적 계획법1. 동적 계획법 (DP, Dynamic Programming)• 복잡한 문제를 간단한 여러 개의 문제로 나누어 해결한 뒤, 그 결과를 저장하고 다시 사용함으로써 중복 계산을 피하여 문제의 해를 효율적으로 찾아내는 방법. • 중복 하위 문제와 최적 부분 구조를 가지고 있는 문제에 사용함. - 중복 하위 문제 (Overlapping Subproblem) : 어떤 하나의 문제가 여러 개의 하위 문제(또는 부분 문제, Subproblem)로 쪼개져 그것이 반복되는 구조. - 최적 부분 구조 (Optimal Substructure) : 부분 문제에서 구한 최적의 답을 합쳐 큰 문제의 최적의 답을 구할 수 있는 구조. • 문제에 대한 정답이 될 가능성이 있는 모든 해결책을 고려해야 함. ..
그래프 순회1. 그래프 순회 (Graph Traversal)• 그래프의 각 정점을 방문하는 과정을 말함.• 그래프 탐색(Graph Search)이라고도 함. • 트리는 부모 -> 자식으로 각 노드끼리 방향이 단방향으로 정해져 있지만, 그래프는 각 정점끼리 양방향으로 이어질 수 있기 때문에(무향 그래프일 때, 또는 유향 그래프에서 각 정점이 서로를 향하는 엣지를 가질 때) A 정점에 B 정점을 방문한 후 B 정점에서 다시 A 정점으로 방문할 가능성이 존재. - 따라서, 한 번 방문한 곳은 방문한 곳이라는 표시를 해야 함. 2. 인접 리스트의 그래프 순회• 너비 우선 탐색 (BFS, Breadth First Search) - 시작 정점의 가까운 곳 우선 탐색 -> 그 다음 떨어진 곳 탐색 ->..
[자료구조 & 알고리즘] 7. 그래프, 인접 행렬, 인접 리스트, 암시적 그래프
그래프, 인접 행렬, 인접 리스트, 암시적 그래프1. 그래프 (Graph)• 그래프는 어떤 자료나 개념을 표현하는 정점(Vertex)들의 집합 V와 이들을 연결하는 간선(Edge)들의 집합 E로 구성된 자료구조.• 트리와 비슷하지만 트리가 그래프의 한 종류임. - 트리는 부모 자식 노드라는 계층이 존재하지만, 그래프는 어느 정점이라도 모두 연결 가능.• 그래프는 그림에 따라 다르게 그려질 수 있지만, 정점들과 그들을 잇는 간선들이 같다면 같은 그래프임.• 방향 그래프와 무향 그래프 - 방향 그래프 : 간선에 방향이 정해져 있어 정점 간에 이동이 정해진 방향을 따라서만 이동할 수 있는 그래프. - 무향 그래프 : 간선에 방향이 정해지지 않아 간선만 연결되어 있으면 정점 간에 자유롭게..
[자료구조 & 알고리즘] 6. 트리, 이진 트리, 트리 순회, BFS, DFS
트리, 이진 트리, 트리 순회, BFS, DFS1. 트리 (Tree)• 서로 연결된 Node의 계층형 자료구조로써, Root와 부모-자식 관계의 Subtree로 구성.• 관련 용어 정리 - 노드 (Node) : 트리를 구성하는 기본 원소 - 간선 (Edge) : 노드 간에 연결된 선 - 루프 노드 (Root) : 트리는 항상 루트에서 시작. 가장 위에 있는 노드. - 리프 노드 (Leaf) : 더 이상 뻗어나갈 수 없는 마지막 노드 - 자식 노드 (Child), 부모 노드 (Parent), 형제 노드 (Sibling) - 차수 (Degree) : 각 노드가 갖는 자식의 수. 모든 노드의 차수가 n개 이하인 트리를 n진 트리라고 함. - 조상 (Ancest..
재귀 (Recursion)1. 재귀 함수• 자신을 정의할 때 자기 자신을 재참조하는 함수를 재귀 함수라고 함.public int factorial(int i) { if(i == 1) return 1; return i * factorial(i-1);}public int fibonacci(int i) { if(i == 1 || i == 2) return 1; return fibonacci(i-1) + fibonacci(i-2);}• 재귀의 구성 요소 - 점화식(Recurrence Relation) : f(n)을 f(n-1), f(n-2), ..., f(2), f(1)의 관계식으로 표현하는 것 - 탈출 조건(Base Case) - 더 이상 재귀 호출을 하지 않아도 값을 반환할 수..
자바의 Hash Table1. Hash Table• 해시 함수를 이용하여 효율적인 탐색(빠른 탐색)이 가능한 자료구조• key-value 쌍의 데이터를 저장하여, 데이터를 꺼낼 때 key를 통해 value를 가져올 수 있음.• 데이터를 저장하기 위해 배열을 내부적으로 사용.• 배열 형태로 저장한 데이터에 접근하는 인덱스를 만들기 위해 key 값을 해싱. - 해시(hash) : 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수. 입력이 같으면 출력도 같음. - Hash Table 내부에는 key값을 최적의 배열 인덱스 값으로 바꿔주는 해시 함수가 존재. - 이 해시 함수는 어떤 key값을 입력 받아아도 내부적으로 사용하는 배열의 크기보다 작은 정수를 결과로 출력해줌.• 즉..