Engineering Note

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세기에 개발한 이래, 그래프는 수많은 분야에서 도구로 사용되어 왔습니다. 서울 시청에서 버스노선을 정리할 때, 건축회사에서 시공 일정 계획을 할 때, 네이베기션이 경로를 탐색할 때 등 그래프의 응용 분야는 굉장히 다양합니다. 게다가 거의 모든 분야가 컴퓨터에 의존하고 있는 상황에서 프로그래머는 그래프를..

it 취업을위한알고리즘문제풀이 문제 코드1 //50. 영지(territory) 선택 : (small) #include int main() { //freopen("input.txt", "rt", stdin); int map[51][51]; int H, W, HH, HW, count = 0, maxCount = 0; //입력 scanf("%d %d", &H, &W); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { scanf("%d", &map[i][j]); } } scanf("%d %d", &HH, &HW); //알고리즘 //i,j는 누적해서 더해 갈 시작위치 값을 의미 for (int i = 0; i

it 취업을위한알고리즘문제풀이 문제 알고리즘 개선 전 소스코드 //50. 영지(territory) 선택 : (small) #include int main() { //freopen("input.txt", "rt", stdin); int map[51][51]; int H, W, HH, HW, count = 0, maxCount = 0; //입력 scanf("%d %d", &H, &W); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { scanf("%d", &map[i][j]); } } scanf("%d %d", &HH, &HW); //알고리즘 //i,j는 누적해서 더해 갈 시작위치 값을 의미 for (int i = 0; i