동작이 되지 않던 코드를 수정 insertElementBST : 수정 전의 형태를 하게 되면 p->pLeftChild, p->pRightChild 가 가르키는 곳이 무엇인지 정해지지 않은 상태에서 element 로 할당이 되었기 때문에, 이후 삽입과정에서 element 를 찾을 수 없어서 오류가 발생하게 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 if (pBinSearchTree->pRootNode == NULL) { pBinSearchTree->pRootNode = element; return TRUE; } while(TRUE) { if (p == NULL) { p = element; return TRUE; } if (p->key > elem..

BST 이진트리 중에서 탐색을 위해 고안된 것으로 노드 위치를 키 값 기준으로 결정된다. 이진 탐색트리의 효율 편향 이진트리, 모습에 따라 탐색 효율이 달라지기에 최악의 경우에는 N이기에 염두를 해야 한다. 이진 탐색트리의 조건 노드 N에 대하여 왼쪽 하위트리에 있는 노드는 N보다 작다. 노드 N에 대하여 오른쪽 하위트리에 있는 노드는 N보다 크다. 노드 N의 왼쪽 하위트리와 오른쪽 하위트리도 이진 탐색트리이다. 키값은 유일 구현해야 하는 사항 이진 탐색트리의 탐색 이진 탐색트리의 삽입 탐색을 전제로 삽입 트리의 루트로부터 시작해서 삽입할 키와 하위 트리의 키과 비교 (반복) 이진 탐색트리의 삭제 삭제할 노드가 리프노드 삭제할 노드가 자식노드 하나만 있는 경우 삭제할 노드가 자식노드 두 개 있는 경우 이..

Heap 우선순위 큐를 구현하기 위한 자료구조, 완전 이진 트리의 형태로 구성 최대값 및 최솟값을 찾아내는 연산을 빠르기 하기 위한 용도로 사용 큐는 여기 글에서 설명이 되어있고, 우선순위 큐는 먼저 들어온 데이터가 아닌 우선순위가 높은 데이터가 먼저 나가는 형태 특징 완전이진트리의 형태 부모노드와 자식노드 간에만 대소 관계가 성립(형제 사이에는 정해지지 않는다) 중복된 값 허용 복잡도 Max Heap (최대 힙) 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙 루트노드의 값은 최대값 Min Heap (최소 힙) 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙 루트노드의 값은 최솟값 연산 createHeap() : 히프 생성 deleteHeap() : 히프 삭제 insert() : 자료 추가 트리의..

계층적인 관계를 나타내는 데 편리한 것이 트리로써, 트리의 구성 요소에 해당 하는 것을 노드라 칭한다 트리의 개념 Root Node : 부모가 없는 노드 (원조격인 노드) leaf or Terminal Node (단일 노드) : 자식이 없는 노드 Internal Node : 리프 노드를 제외한 모든 노드 부모 노드 : B, G 노드의 부모 노드는 F이다. 자식 노드 : F 노드의 자식 노드는 B, G이다. 선조 노드 : 주어진 노드의 상위에 있는 노드들, B, F는 D의 선조 노드이다. 후손 노드 : 역으로 어떤 노드의 하위에 있는 노드들, F의 후손은 그 아래 모든 노드들이다. 형제 노드 : 같은 부모를 두고 있는 노드들, B, G 노드는 형제 노드이다. 트리의 차수 : 자식 노드의 개수 트리의 레벨 ..

FIFO(First-In First-Out), 선입선출의 특성 구현해야 하는 필수 요소 인큐 연산 데이터 삽입하는 연산 ⚠️ 큐의 크기를 초과해 새로운 자료를 추가하지 못하는 현상을 오버플로 디큐 연산 데이터 삭제하는 연산 ⚠️ 아무 자료가 없는 빈 큐에 연산을 하게 되면 언더플로 현상 발생 피크 연산 프론트에 있는 데이터 제거 🚫 기다리는 줄, 공유된 프린터 하나에서 일쇄될 차례를 기다리는 것 등에 사용 #include #include #include # define TRUE 1 # define FALSE 0 typedef struct DequeNodeType { int data; struct DequeNodeType *pLLink; struct DequeNodeType *pRLink; } DequeN..

FILO(Last-In-First-Out), 후입선출의 특성 구현해야 하는 필수 요소 푸시 연산 ⚠️ 스택의 크기를 초과해 새로운 자료를 추가하지 못하는 현상을 오버플로 스택에 새로운 자료를 추가 팝 연산 ⚠️ 아무 자료가 없는 빈 스택에 연산을 하게 되면 언더플로 현상 발생 스택에서 자료를 제거 피크 연산자료를 제거 🚫 스택의 맨 위 자료를 반환 특정 정보 기억 후 재이용 할 때 주로 사용 컴퓨터 알고리즘에서 자주 쓰이는 데이터구조 수행 중의 프로그램 함수나 서브프로그램들의 복귀주소와 관련된 여러 정보들을 저장 🐬배열리스트를 이용한 구현 더보기 #include "array_list.h" intft_push(t_array_list *list, int *top, int new_data) { t_array_..

배열 (Array) 동일한 데이터 타입의 변수 여러 개를 하나로 묶어서 관리하기 위한 것이다. 배열요소가 메모리 내에 서로 붙어 있기 때문에 인덱스를 사용하여 필요한 요소가 있는 곳으로 단번에 찾을 수 있다(직접 접근) int Number[2][3] = {{11, 22, 33}, {44, 55, 66}}; C언어에서는 행 우선 순위로 사용되는데, 첫 행의 요소를 모두 나열한 다음에 둘째 행을 모두 나열하는 것으로 여전히 1차원으로 진행된다. &Number[i - 1] = A + (i - 1) x sizeof(Element Type); 배열 Number의 첫 요소가 시작되는 주소는 &Number[0]으로 Number = &Number[0]; 임을 의미한다. 배열의 크기는 선언 시에 고정된다. char Na..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 공통적인 문제풀이는 동적계획법으로 구현을 하면 되며, 구조를 제대로 보고 규칙이 어떤 것인지 확인하면 된다. 여기 문제에서의 규칙은 arr[N] = arr[N - 1] + arr[N - 5] 의 값인 구조인데, 배열로 값을 저장하지 않고, 아래와 같이 구현하였다. long long 으로 한 이유는 arr[N] 값이 int 의 값을 넘어 가기에 이렇게 적게되었다. 사실 저번의 코드를 보게되니 이번 문제는..