Algorithm

[자료구조] 그래프란? 개념과 표현 방법

그래프란? 그래프란 노드와 간선의 집합으로 정의되며, 알고리즘에서 노드(Node)와 노드를 연결하는 간선(Edge)로 구성된 자료구조를 말한다. 이때 간선은 노드 쌍을 연결하며, 경우에 따라 가중치(Weight) 정보가 포함될 수 있다. 특히, 그래프는 선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이하다. 어디에서 많이 쓰일까? 그래프는 네트워크 모델링에 아주 유용하게 사용된다. 예를 들어, 소셜 네트워크 분석, 지하쳘 통행 분석, 최단 경로 문제와 같은 것을 해결하는 데 사용될 수 있다. 그래프의 용어 정점 (Vertex) → 그래프의 구성요소로 하나의 연결점을 가리킨다. (노드 = 정점) 간선 (Edge) → 두 정점을 연결하는 선을 말한다 차수 (D..

[알고리즘] 백트래킹 해결 방법과 예시 문제

백트래킹 이란? 백트래킹은 완전탐색을 하는 과정에서 가지치기를 통해 유망하지 않은 곳은 더 이상 탐색하지 않는 알고리즘 기법을 말한다. 백트래킹 용어 유망(Promising) 하다. 어떤 노드를 방문했을 때 그 노드를 포함한 경로가 해답이 될 수 있다면 유망하다고 한다. 가지치기 (Pruning) 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않는다. 백트래킹 문제의 일반적인 해결 방법 상태 공간 트리를 구한다. 깊이 우선 탐색(DFS)을 이용하여 상태 공간 트리를 탐색한다. 각 노드가 유망한지를 점검한다. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 다음 자식 노드로 간다. 어떤 노드가 해당 문제의 해가 되면 탐색을 중지하고, 해를 구한다. 백트래킹 문제의 예시 1. N-..

[알고리즘] 그리디 알고리즘의 특징과 그리디 구분법

그리디 알고리즘 특징 그리디 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법이다. 최적화 문제(optimization)란 가능한 해들 중에서 가장 좋은(최대 또는 최소) 해를 찾는 문제이다. 일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다. 여러 경우 중 하나를 선택 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다. 일단, 한번 선택된 것은 번복하지 않는다. 이런 특성 때문에 대부분의 탐욕 알고리즘들은 단순하며, 또한 제한적인 문제들에 적용된다. 그리..