알고리즘 (11) 썸네일형 리스트형 [C++] stack의 top과 pop의 차이 프로그래머스에서 알고리즘을 풀던중...스택을 사용해서 dfs를 구현했다. 아래 코드에서 요 부분이 오류가 발생했다.// 오류가 발생한 부분tuple tp = st.pop();tie(index, sum) = tp;// 변경해서 해결한 부분tuple tp = st.top();tie(index, sum) = tp;st.pop(); pop()을 사용해 빼낸 튜플로는 초기화가 안 되더라...근데 top()은 된다...파이썬을 쓸 때는 pop()을 사용해서 스택에서 제거함과 동시에 그 element를 반환받았다. https://cplusplus.com/reference/stack/stack/pop/ ⬅︎ 이 사이트를 보면 c++에서는 top은 알고 있던 것처럼 스택의 맨 위의 값을 반환하는 것이지만pop은 스택에.. [C언어] RB 트리 구현(2) - 삭제, 탐색 RB 트리는 삭제가 좀 더 복잡한데요...아무튼 보시죠 레드 블랙 트리 삭제 삭제의 경우의 수는 3가지입니다~ 코드와 함께 확인해보겠습니다. int rbtree_erase(rbtree *t, node_t *p) { node_t *y = p; node_t *x = NULL; color_t y_ori_color = y->color; if (p->left == t->nil) { x = p->right; rbtree_transplant(t, p, p->right); } else if (p->right == t->nil) { x = p->left; rbtree_transplant(t, p, p->left); } else // 자식이 2명인 경우 { y = subtree_min(t, p->right); y_ori_.. [C언어] RB 트리 구현(1) - 삽입 저번에 RB트리 개념에 대해 허접하게 정리했었는데요. 오늘은 C언어로 구현하는 방법에 대해 적어보겠습니다~ 코드는 [Introduction to Algorithms] 의 13장 레드 블랙 트리 내용을 기반으로 작성했습니다! 먼저 사용할 구조체 등을 선언해줍니다. 레드, 블랙 속성을 표현하기 위해 enum color_t를 정의합니다. key 값의 표현을 위해 typedef로 int형 key_t를 정의합니다. typedef enum { RBTREE_RED, RBTREE_BLACK } color_t; typedef int key_t; typedef struct node_t { color_t color; key_t key; struct node_t *parent, *left, *right; } node_t; t.. Red Black Tree(레드-블랙 트리) Red Black Tree란? 이진 탐색 트리의 한 종류로 스스로 균형을 잡는 밸런스 트리입니다. BST(이진탐색트리)의 worst case의 단점을 개선 - 이진 탐색 트리는 최악일 경우 O(N)의 시간복잡도를 가짐 RB Tree의 속성 모든 노드는 red 혹은 black이다. 루트 노드는 black이다. 모든 nil 노드는 black 컬러를 가진다. ( RB 트리에서 리프 노드는 nil 노드) red의 자녀들은 반드시 black. 즉, red가 연속적으로 존재할 수 없다. black은 가능! 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외함) 노드 x의 black height = 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black.. C언어) LinkedList, 연결리스트에 대해서 Linked List 연결리스트는 일반 배열과 다르게 동적으로 크기가 변할 수 있고, 삭제나 삽입 시에 데이터를 이동시킬 필요가 없는 자료구조입니다. 배열의 경우 중앙에 값을 추가/삭제할 때 그 뒤의 요소들을 전부 움직여야 하는데, 이때 깊은 복사가 일어나게 된다. 깊은 복사는 무거운 연산이기 때문에 시간이 오래 걸린다. 하지만 연결리스트에서 포인터값을 복사하며 이동하는 경우는 얕은 복사이기 때문에 이 차이점으로 인해 연결리스트의 추가, 삭제 연산은 배열보다 효율적이게 된다. 연결리스트 구현 구현 과정은 파이썬에서 구현하는 것과 크게 다르지 않습니다. typedef struct Node{ int data; struct Node* next; }node; 먼저 노드 구조체를 선언합니다. 노드의 Node*는 .. LCS (Longest Common Subsequence) LCS란 Longest Common Subsequence의 줄임말로 최장 공통 부분수열을 뜻합니다. 최장 공통 부분수열은 공통 부분 문자열 중 가장 길이가 긴 문자열을 말합니다. 앞으로 알아볼 LCS 알고리즘은 LCS에 부합하는 문자열을 찾기 위한 알고리즘입니다. LCS는 최장 공통 부분수열만이 아니라 최장 공통 문자열(Longest Common Substring)을 말하기도 하는데, 두 알고리즘의 차이점을 알아보겠습니다. 아래 그림으로 알아보자면 ABCDEF 와 GBCDFE 두 문자열을 비교해보겠습니다. 왼쪽의 최장 공통 부분수열은 BCDF, BCDE 두 개의 결과를 얻을 수 있고, 오른쪽의 최장 공통 문자열은 BCD의 결과만 얻었습니다. 최장 공통 부분수열은 부분수열이기 때문에 문자와 문자를 건너뛰어.. 최소 신장 트리란? 신장 트리(Spanning Tree) 먼저 신장 트리에 대해 설명하자면, 그래프 내의 모든 정점을 포함하는 트리 그래프의 최소 연결 부분 그래프 -> 최소 연결 = 간선의 수가 가장 적다. -> n개의 정점을 갖는 그래프의 최소 간선의 수는 n-1개이고, n-1개의 간선을 갖는 그래프 = 트리 형태 특징 하나의 그래프에 여러 개의 신장 트리가 존재할 수 있다. 모든 정점들이 연결되어 있어야 하고, 사이클을 포함해서는 안 된다. 최소 신장 트리란? (MST : 미니멈 스패닝 트리) : 각 간선의 가중치가 동일하지 않을 때, 간선의 가중치를 고려하여 최소 비용의 신장 트리를 선택하는 방법이다. 최소 신장 트리의 특징 n개의 정점에 대해 반드시 n-1개의 간선만을 이용해야 한다. 사이클을 포함하면 안 된다. .. 이진 탐색 알고리즘 이진 탐색(binary search)이란? 이진 탐색은 데이터가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘이다. 그렇기 때문에 이진 탐색 알고리즘을 사용하려면 배열의 데이터가 정렬되어 있어야 한다. 이진 탐색 알고리즘은 탐색을 반복할 때마다 검색 범위가 거의 절반으로 줄어들기 때문에 검색에 필요한 비교 횟수는 평균 O(log N)이다. 먼저, 배열의 인덱스를 가리키는 포인터를 왼쪽, 오른쪽, 중간값 세 개를 정의해줍니다. lenght = len(array) pl = 0 pc = (lenght - 1) // 2 pr = lenght - 1 pl - 왼쪽 포인터는 0 인덱스부터 pr - 오른쪽 포인터는 가장 뒤 인덱스부터 (lenght - 1) pc - 중간 포인터는.. 이전 1 2 다음 목록 더보기
