목록전공 공부/알고리즘 (11)
Adaid's Workroom
그리디 알고리즘(greedy algorithm)- 순간마다 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘- 최종적으로는 답이 아닐 수도 있음 거스름돈 문제- 최소의 동전과 지폐를 사용하여 N원을 거슬러주는 문제(ex) 1, 5, 10, 100, ... 으로 7570원-> 그리디(ex) 1, 4, 5 으로 12원-> 그리디 X, DP 동전0Ai는 Ai-1의 배수 -> 그리디 알고리즘 성립
트리(Tree)- 사이클이 없는 그래프- 정점의 개수: V- 간선의 개수: V-1루트 있는 트리(Rooted Tree)- 루트가 있는 트리- 루트부터 아래로 방향을 정할 수 있음용어- 부모(Parent)- 자식(Child)- 단말 정점(Leaf/Terminal Node)- 형제(Sibling)- 깊이(Depth): 루트에서의 거리- 높이(Height): 깊이 중 가장 큰 값- 조상(Ancester), 자손(Descendent): p->q로 갈 수 있을 때 p가 q보다 루트에 가까우면 p는 q의 조상, q는 p의 자손- 이진트리(Binary Tree) 트리의 표현- 그래프 표현과 같은 방식으로 저장 가능- 트리의 모든 노드는 0/1개의 부모를 가지기 때문에 부모만 저장하는 방식으로 저장할 수도 있음- 이진..
그래프(Graph)- 자료구조 일종- 정점(Node, Vertex)- 간선(Edge): 정점간의 관계- G = (V,E)로 나타냄경로(Path)- 정점 A -> B로 가는 경로사이클(Cycle)- 정점 A에서 다시 B로 돌아오는 경로단순 경로와 단순 사이클- 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클- 일반적으로 지칭하는 경로/사이클유향 그래프(Directed Graph)- 간선에 방향이 있음무향/양방향 그래프(Undirected / Bidirection Graph)- 간선에 방향이 없음루프(Loop)- 간선의 양 끝점이 같은 것가중치(Weight)- 간선에 가중치가 있는 경우: A->B로 이동하는 거리, 시간, 비용 등- 가중치가 없으면 1이라고 생각하면 됨차수(Degree)-..
정렬- 선택, 버블, 삽입, 퀵, 힙, 병합, ...- 직접 구현하는 것보다는 STL sort 사용하는 것이 좋음- 좌표 정렬: STL pair 사용하면 편함 Stable Sorting- 같은 것이 있는 경우 정렬하기 전의 순서가 유지되는 정렬 알고리즘- O(N lgN)인 정렬 알고리즘 중에는 병합 정렬 있음- STL stable_sort 함수 사용
나머지 연산(Modular Arithmetic)- 데이터 저장 범위 때문에, 답을 M으로 나눈 나머지를 출력하라는 문제 등장- (A+B) mod M = ( (A mod M) + (B mod M) ) mod M- (AxB) mod M = ( (A mod M) x (B mod M) ) mod M- 나눗셈은 성립X (Modular inverse 구해야 함)- (A-B) mod M = ( (A mod M) - (B mod M) + M ) mod M* mod 연산한 결과가 음수가 나올 수도 있으므로 최대공약수(Greatest Common Divisor, GCD)- 유클리드 호제법(Euclidean algorithm)을 이용- a를, b로 나눈 나머지를 r이라 하면 GCD(a, b) = GCD(b, r)- r이 0..
다이나믹 프로그래밍(DynamicProgramming)- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘- 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있음1. Overlapping Subproblem2. Optimal Substructure- DP를 푸는 두 가지 방법1. Top-down2. Bottom-upOverlapping Subproblem- 큰 문제와 작은 문제는 상대적- 큰 문제와 작은 문제를 같은 방법으로 풀 수 있음- 문제를 작은 문제로 쪼갤 수 있음(ex) 피보나치 수Fn = Fn-1 + Fn-2 (n>=2)문제: N번째 피보나치 수를 구하는 문제작은 문제: N-1, N-2 번째 피보나치 수를 구하는 문제Optimal Substructure- 문제의 정답을 작은 문제의 정..
스택(Stack)- 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조- 마지막으로 넣은 것이 가장 먼저 나오기 때문에 Last In First Out (LIFO) 라고도 함- push: 스택에 자료를 넣는 연산- pop: 스택에서 자료를 빼는 연산- top: 스택의 가장 위에 있는 자료를 보는 연산- empty: 스택이 비어있는지 아닌지를 알아보는 연산- size: 스택에 저장되어 있는 자료의 개수를 알아보는 연산- C++ STL stack을 사용하는 것이 좋음 큐(Queue)- 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조- 먼저 것이 가장 먼저 나오기 때문에 First In First Out (FIFO) 라고도 함- push: 큐에 자료를 넣는 연산- pop: 큐에서 자료를 빼는 ..
참고자료: https://www.geeksforgeeks.org/c-qsort-vs-c-sort/http://gshscs.tistory.com/11 알고리즘을 공부하면서 qsort와 sort 함수의 성능 차이가 궁금해져서 찾아보았다.그래서 위 링크의 글 정리해봄1. qsort와 sort 함수?(1) qsortqsort는 본래 C언어의 함수이다.C에서는 에 정의되어 있으며, C++에서는 헤더를 포함하여 사용할 수 있다.(2) sortsort는 C++함수로 헤더를 포함하여 사용할 수 있다.2. 구현(1) qsort퀵소트(QuickSort) 알고리즘을 통해 구현되었다.(2) sortsort함수는 구현마다 사용된 알고리즘이 각각 다르다. 3. 복잡성(Complexity)(1) qsortC 표준 라이브러리는 qs..
프로그래밍 언어- C 보단 C++- C++ 사용시 C++11, STL, printf/scanf 사용 입출력 예시테스트 케이스로 주어지는 경우- 각각을 독립적인 문제로 보기- 전체 케이스를 입력받고 풀 필요 없음입력값 개수가 주어지지 않는 경우- EOF 까지 받으면 됨C: while( scanf("%d %d", &a, &b) == 2 )C++: while( cin >> a >> b )* scanf의 리턴값은 성공적으로 입력받은 변수 개수한줄 입력 받기- 다음은 한줄 입력 받기 안됨scanf("%s", s);cin >> s;- 다음은 한줄 전체를 입력받을 수 있음fgets(s, 100, stdin); * 줄바꿈까지 입력받기 때문에 조심해야 함scanf("[^\n]\n", s); * 각 줄 앞 뒤 공백 무시g..