Engineering Note

백트래킹 여러 후보해 중에서 특정 조건을 충족시키는 모든 해를 찾는 알고리즘 백트래킹이 다루는 문제들은 해가 하나 이상 존재합니다. 해가 둘일 수도, 셋일 수도, 수백, 수천 개일 수도 있습니다. 후보해가 많은 문제에서 해가 될 조건을 만족시키는 '진짜 해'를 효율적으로 찾는 것이 백트랙킹의 목적인것입니다. 트리에서 깊이 우선 처럼 탐색을 해나가면서 중간에 조건을 만족하지 않으면 다시 부모 노드로 돌아가 다른 길을 찾아 가는 것입니다.

순열 알고리즘 순열 알고리즘을 직접 구현하기 위해서는 어릴적 수형도를 그릴때를 생각하면 조금 쉽다. {'A','B','C'} 이렇게 A , B, C라는 3개의 데이터가 있을때 가장 첫 번째 올 수 있는 경우는 'A'가 첫 번째 오는 경우 'B'가 첫 번째 오는 경우 ' 'C'가 첫번째 오는 경우' 세가지 시작값을 정하는 초기 경우를 for문으로 구현하고 나머지 배열은 이렇게 세가지 경우로 부터 각각 재귀적으로 다음 단계를 수행하면 된다. 코드 #include char copy[] = {'A','B','C'}; void permutaion(char arr[], int start, int end); void printArray(char arr[], int size); void swap(char arr[], ..

www.zerocho.com/category/Algorithm/post/584b979a580277001862f182

병합정렬 분할정복 알고리즘의 대표적인 알고리즘 정렬할 데이터의 집합을 더이상 쪼갤 수 없을 때 까지 반으로 쪼개고 다시 정렬하면서 병합하면 된다. 알고리즘 동작 과정 정렬된 두 집합을 다시 병합하면서 정렬하는 알고리즘이다. 전체 데이터 집합을 정렬된 두 데이터 집합상태로 나누기 위해 데이터집합을 계속 반으로 나눈다. 계속 반으로 나누면서 2개의 데이터 집합이 각각 하나가 되면 분할은 종료하면 되는데 이유는 하나의 집합은 더이상 쪼갤 수 없을 뿐아니라 정렬된 상태로 볼 수 있기 때문이다. 정렬할 데이터 집합을 반으로 나눕니다. 나누어진 하위 데이터 집합의 크기가 2이상이면 이 하위 데이터 집합에 대해 1을 반복합니다. 원래 같은 집합에서 나뉘어져 나온 하위 데이터 집ㅎ바 둘을 병합하여 하나의 데이터 집합으..

#include int main() { freopen("input.txt", "rt", stdin); int n, m; int fArray[100] = { 0, }; int sArray[100] = { 0, }; int Array[200] = { 0, }; scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &fArray[i]); } scanf("%d", &m); for (int i = 0; i < m; ++i) { scanf("%d", &sArray[i]); } int i, j, k = 0; i = j = k = 0; while (i < n && j < m) { if (fArray[i] < sArray[j]) Array[k++] = fArray[i+..

Dijkstra Algorithm 대표적인 최단경로 알고리즘 음의 간선 정보가 없는 가중치그래프의 최단 경로 알고리즘이다. Dijkstra Algorithm 동작 방식 개요는 시작점으로부터 정점 v의 최단 거리를 거리 테이블에 갱신하면서 동작한다. 시작점을 설정한다. 시작점으로 부터 최소거리 정보를 거리 테이블에 저장한다. 시작점과 직접 연결된 간선 정보가 없는 정점은 무한대 또는 -1로 저장한다. 현재부터 가장 가까운 거리의 정보를 거리 테이블에 저장한다. 방문처리되지 않은 방금 저장한 정점으로 부터 특정한 노드로 가는 거리 정보를 갱신한다. 방금 위치에 있는 정점을 방문처리 한다. 3,4의 과정을 반복한다. #include int num = 6; int INF = 10000000; //전체 그래프를 ..

최단 경로 알고리즘의 변형들 비가중치 그래프(Unweighted Graph) (BFS) 비가중치 그래프에서 BFS알고리즘을 이용하면 시작점으로 부터 해당 노드까지의 최단경로를 구할 수 있다. BFS는 부모노드와 연결된 자식노드를 모두 탐색하고 다음 레벨로 진행하는 알고리즘이기 때문에 비가중치 그래프에서 연결된 곳들을 거쳐서 현재 노드로 오는 '간선 수'를 세는것 만으로도 최소경로를 구할 수 있다. 이유는 직접연결된 노드가 아니라 다른경로를 거쳐서 현재노드까지 올 수 있다면 이미 최소 간선을 통한 이동 경로가 아니기 때문이다. 비가중치에서는 연결된 노드간 이동거리를 모두 1로 볼 수 있기 때문에 출발점으로 부터 현재 노드까지 '최소간선 수'를 세는 것만으로도 최단경로이다. 가중치 그래프(Weighted G..

Graph 정의 '정점의 모음'과 이 정점을 잇는 '간선의 모음'과의 결합입니다. 즉 연결의 집합을 모형화 한것. 수학적인 표현으로는 "정접의 집합을 V, 간선의 집합을 E, 그리고 그래프를 G라고 했을 때 G = (V,E)이다." 정점 몇 개 자체로는 아무것도 아니지만 이들이 간선으로 인해 서로 연결될 때는 '관계'가 형성되고 이로 인해 그래프가 형성됩니다. Graph의 중요성 위대한 수학자 오일러가 17세기에 개발한 이래, 그래프는 수많은 분야에서 도구로 사용되어 왔습니다. 서울 시청에서 버스노선을 정리할 때, 건축회사에서 시공 일정 계획을 할 때, 네이베기션이 경로를 탐색할 때 등 그래프의 응용 분야는 굉장히 다양합니다. 게다가 거의 모든 분야가 컴퓨터에 의존하고 있는 상황에서 프로그래머는 그래프를..