Records rather than Memories

class를 통해 여러 변수가 존재하는 상황에서 ''특정한 변수'를 기준으로 정렬하는 방법을 적용해봤다. 그런데 class를 이용하는 것은 앞서 말한 것처럼 실무에 적용하는 것이고, 만약 프로그래밍 대회 같이 빠르게 적용하고 싶다면 어떻게 해야할까? - 일반적으로 빠른 개발이 필요할 때는 페어(pair) 알고리즘이 적용된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include #include using namespace std; int main(void) { //vector형에 담긴 페어 int, string 한 쌍의 데이터 vector v; v.push_back(pair(7, "용 갑옷")); v.push..

특정한 데이터를 정렬하기 위해 선택정렬, 삽입정렬, 퀵정렬, 합병정렬 등 여러가지 알고리즘을 만들어 정렬할 수 있는데 사실 실제로 정렬을 수행한다고 하면 이미 구현된 정렬 라이브러리를 사용하면 된다. 하지만 이러한 정렬에 대한 명확한 이해 없이 무작정 라이브러리를 가져다 쓰는 것은 좋지 않으므로 앞서 정렬 알고리즘에 대한 이해가 필요한 것이다. - sort() 함수의 기본 사용법 1 2 3 4 5 6 7 8 9 10 11 12 13 #include #include using namespace std; int main(void) { int a[10] = {2, 7, 11, 8, 3, 10, 1, 9, 6}; sort(a, a + 10); for(int i = 0; i

Union-Find 알고리즘 : '합집합 찾기' 의미를 가진 그래프 알고리즘이다. 이것은 서로소(Disjoint-Set)이라고 도 불리는데 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 다음과 같이 노드들이 연결되지 않고 존재한다고 하자. 이 때 각각의 노드들은 자기 자신만을 집합의 원소로 가지고 있다고 표현할 수 있다. 즉, 모든 값이 자기 자신을 가리키는 것이다. 1 2 3 4 5 6 7 1 2 3 4 5 6 7 다음과 같이 표로 나타냈을 때, 첫 번째 행은 '노드 번호' 두 번째 행은 '부모 노드 번호'를 의미한다. 여기서 부모 노드 번호란 해당 노드가 어떤 부모 노드에 포함되어 있는지를 의미한다 .자 그럼 다음과 같이 1번 노드와 2번 노드가 연결되었다고 하자. 이러한 연결을 컴퓨..

크루스칼 알고리즘 : 최소 비용으로 모든 노드를 연결하기 위한 알고리즘, 간선을 최소비용 순으로 정렬한 후 하나씩 확장해 나가는 방식이다. 보통 도시 혹은 마을을 도로로 연결하고자 할 때 비용을 최소화 하기 위해 적용되는 알고리즘이다. - 노드 = 도시, 마을 = 정점 - 간선에 적용된 가중치가 거리이자 비용이 된다. 다음과 같은 그래프가 있을 때 크루스칼 알고리즘을 이용해 MST를 만들어 보자. 크루스칼 알고리즘의 핵심개념을 다시 생각해보자. "거리가 짧은 간선을 순서대로 그래프에 포함시키자" 1. 모든 간선 정보를 오름차순으로 정렬. * 여기서 노드1과 노드7, 노드7과 노드1간에 연결된 간선은 같은 것이므로 한번만 포함한다. 노드 1 : 10, 26, 33 노드 2 : 72, 3, 13 노드 3 :..

최소 비용 신장 트리를 알아보기 전 신장트리(Spanning Tree)란 무엇인지 먼저 알아보자. Spaanning Tree란 그래프 내의 모든 정점을 포함하는 트리를 말한다. 단, 트리를 연결하는 간선의 수가 최소로 이루어져야한다. - 그래프에서 일부 간선을 선택해서 만든 트리 - n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1) DFS와 BFS를 이용해 그래프에서 신장 트리를 찾을 수 있다. 다음 그림처럼 하나의 그래프에는 여러개의 신장트리가 존재할 수 있다. 모든 정점이 연결되있어야 하고 사이클이 포함되면 안된다. 최소 비용 신장 트리(MST, Minimum Spanning Tree) 위에서 알아본 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리를 말한다. 즉, 간..

그리디(Greedy) 알고리즘은 이름에 나타나는 것과 같이 바로 앞에 보이는 최적의 상황만을 쫓아 결과를 도출하는 알고리즘이다. 따라서 단순한 형태의 알고리즘이자 항상 최적의 결과를 도출하진 않아도 어느 정도 최적에 근사한 값을 구할 수 있다. 가장 대표적인 그리디 알고리즘의 예는 '거스름 돈'문제이다. 이 문제에서 가장 최적의 답이란 가장 적은 양의 동전을 주는 것이다. 다시 말해 660원을 거슬러 준다고 할 때 100원 6개 10원 6개 보다는 500원 1개 100원 1개 50원 1개 10원 1개로 주는 것이 효율적이다. 따라서 무조건 큰 단위부터 거슬러 준다는 원칙으로 진행되는 방식이 그리디 알고리즘이다. 이러한 그리디 알고리즘은 크거나 작은 기준, 길거나 짧은 기준으로 하나씩 접근하기 때문에 정렬..

#includ // 기본 라이브러리 추가, printf, scanf 사용가능 int main(void){ // main 함수가 가장 먼저 실행 printf("Hello!!"); return 0; // 반환값 지정 } #includ int main(void){ int x; // 변수 선언 x=5; printf("%d", x); printf("변수 x의 메모리 크기는 %d입니다.", sizeof(x)); // sizeof() c언어에서 제공하는 함수 괄호안 메모리 값 제공 return 0; } - float y = 123456789.123456789; * float는 실수 변수(4byte까지) - printf("y = %.2f\n, y); * %.2f 실수를 출력할 때 소수점 두 자리 까지 출력 - doub..