Engineering Note

Breadth-First Search 넓이 우선 탐색 트리, 그래프 탐색의 대표적인 알고리즘으로 레벨탐색이라고도 불린다. 부모노드의 연결된 자식노드를 모두 탐색한 후 다시 자식노드의 연결된 다음 레벨의 자식노드를 탐색하는 방식이다. DFS(깊이우선탐색)과 반대로 넓이를 먼저 탐색하고 다음 레벨을 탐색하는 완전탐색방법이다. DFS에서는 스택 자료구조를 사용하지만 BFS는 큐를 사용한다. 사용한 자료구조 큐 First In First Out(선입선출 방식의 데이터 구조로 먼저 들어간 데이터를 먼저 삭제하는 자료구조) 위와 같이 이진트리가 주어졌을 때 BFS 그래프 탐색을 구현해 보았다. 우선 이진트리는 C++의 vector 자료구조를 활용해 인접리스트 방식으로 구현한 후 1번 노드 부터 탐색을 진행하도록 코..

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

순열 알고리즘 순열 알고리즘을 직접 구현하기 위해서는 어릴적 수형도를 그릴때를 생각하면 조금 쉽다. {'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..