복습노트 복습노트

heap 자료구조는 크게 두 가지로 나뉘어 집니다. max heap 과 min heap 이 있습니다. Max heap 루트 노드가 자식 노드보다 큰 경우 입니다. 이러한 heap의 자료구조는 우선 순위 큐(Priority Queue) 에서 사용됩니다. 우선 순위 큐는 일반적인 큐와 달리 우선순위에 해당하는 값이 큐의 맨 앞에 위치하고 삭제할때도 가장 먼저 삭제 됩니다. 우선순위는 사용자에 따라 설정할 수 있는데 (max, min) 등 다양하게 설정 가능합니다. 따라서 뒤에 설명할 예시는 max 우선순위 큐를 heap 자료구조로 구현한 예시 입니다. #define MAX_ELEMENTS 200 #define HEAP_FULL(n) (n==MAX_ELEMENTS-1) #define HEAP_EMPTY(n) ..

순회 알고리즘이란 tree의 각 node를 한번씩 방문하는 알고리즘입니다. typedef struct node* treepointer; //노드를 가리키는 포인터 typedef struct node { //노드생성 int data; treepointer left, right; //노드의 오른쪽,왼쪽을 가리키는 포인터 }node; Inorder 중위 순회 왼쪽 branch(가지)를 모두 방문한 후 node를 방문하고 오른쪽 branch를 방문합니다. 다음 그림에서 보면 중위순회를 하게 되면 output은 A / B * C * D + E가 됩니다. void inorder(treepointer ptr) { //중위 순회 if (ptr) { inorder(ptr->left); //왼쪽 자식 먼저 printf("..

Doubly Linked List는 이중연결리스트 입니다. Singly Linked List가 일방적인 방향으로 연결되었다면 반대로 Doubly Linke List는 양방향으로 연결되어 node의 연결을 용이하게 합니다. Doubly Linked List는 Circular로 구현할 수 있고 아닐 수 도 있습니다. typedef struct node* node_pointer; typedef struct node { node_pointer llink; //왼쪽 포인터 int item; //data node_pointer rlink; //오른쪽 포인터 }; 위의 그림은 Doubly Linked List의 header node입니다. 특징은 왼쪽 부분은 포인터 가운데 부분은 data 오른쪽 부분도 포인터 입니다..

Chain 형태 typedef struct list_node *list_pointer; typedef struct list_node{ char data; list_pointer link; }; Invert (연결 리스트 거꾸로) list_pointer invert(list_pointer lead) { list_pointer middle, trail; middle = NULL; while (lead) { trail = middle; middle = lead; lead = lead->link; middle->link = trail; } return middle; } middle이 맨 앞으로 가고 lead가 NULL이 되면 함수가 종료됩니다. Comcatenate (연결 리스트 연결) list_pointer ..

예전에 배운 다항식 연산을 연결리스트로 구현하는 것입니다. typedef struct poly_node* poly_pointer; typedef struct poly_node { int coef; int expon; poly_pointer link; }poly_node; 다항식을 계산하기 위한 리스트의 원형입니다. coef 부분은 계수 expon 부분은 차수 link 부분은 다음 리스트를 가리킵니다. 리스트의 덧셈 부분입니다. a = 3x^14 + 2x^8 + 1 b = 8x^14 + 4x^10 - 2x^8 이라고 가정하면 오른쪽 그림과 같은 모습이 됩니다. poly_pointer padd(poly_pointer a, poly_pointer b) { poly_pointer front, rear, temp..

문제 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 숫자를 입력받아 k 개의 숫자를 빼서 가장 큰 수를 출력하는 문제입니다. 문제는 간단하지만 구현하는게 생각이 많았습니다. int n, k; cin >> n >> k; string st; cin >> st; 먼저 숫자의 갯수 n 과 몇개를 빼는지 k를 입력받습니다. 숫자는 string으로 입력받는데 n의 범위가 500000까지 이기 때문입니다. vectorv; dequeq; q.push_back(st[0] - '0'); 벡터 v는 완성된 숫자를 넣어줄 공간입니다. 덱 q는 string으로 부터 숫자를 받아 저장할 임시 공간입니다. 먼저..

문제 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 친구들의 이름을 성적 순대로 입력 받고 성적 순위가 k이하로 되고 이름의 길이가 같은 친구의 수를 세는 문제입니다. 단순히 naive하게 이중 for문을 사용하면 시간복잡도가 O(n^2) 이 발생하기 때문에 다른방법을 생각해주어야 합니다. 따라서 입력받은 이름을 문자열의 길이로 변환해 QUEUE에 넣어줍니다. QUEUE는 가장 먼저 들어온게 맨 앞으로 가고 늦게 들어오면 뒤로 들어가므로 각각의 문자열의 길이에 맞는 QUEUE 배열 인덱스..

문제 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 예시의 그림처럼 각 기둥의 천장을 이어서 만든 넓이를 구하는 문제입니다. 스택을 이용하여 풀 수 도 있지만 다른 방법을 사용하여 풀어 보았습니다. 간단히 말하면 먼저 기둥 중에서 가장 높은 기둥을 구하고 그 기둥을 기준으로 양쪽으로 나누어 넓이를 따로 구해주었습니다. int n; cin >> n; vectorv(n); pair top = { 0,0 }; for (int i = 0; i > v[i].first >..