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..

대사/대사창이름태그 변경name 캐릭터이름 대사text 대사 대사창 위치wdpos 위치Y 대사창 이미지 변경wdimg 이미지넘버 캐릭터캐릭터 등장chin 캐릭터이름 위치X 캐릭터 퇴장chout 캐릭터이름 캐릭터 앞으로chfront 캐릭터이름 캐릭터 뒤로chback 캐릭터이름 캐릭터 이동chmove 캐릭터이름 위치X 캐릭터 상태chstate 캐릭터이름 상태 라벨라벨 정의label 라벨이름라벨 점프jump 라벨이름 기타대기delay 대기시간(초, 실수형태)주석//주석 차후 구현해야할 것조건문컷신그림사운드