개발 및 기술 블로그

#include #include struct NODE { struct NODE *next; //다음 노드의 주소를 저장할 포인터 int data; }; void addFirst(struct NODE *target, int data) { struct NODE *newNode = malloc(sizeof(struct NODE)); newNode->next = target->next; newNode->data = data; target->next = newNode; } void removeFirst(struct NODE *target) { struct NODE *removeNode = target->next; target->next = removeNode->next; free(removeNode); } int..

트리란? 트리는 어떤 노드들의 집합인데 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 폴더 디렉토리의 구조가 트리구조의 대표적인 예다. 관련 용어 Root Node : 트리 구조에서 최상위에 존재하는 A와 같은 노드 Node : 트리의 구성요소에 해당하는 A,B,C,D,E,F,G,H,I,J와 같은 요소 Edge : 노드와 노드를 연결하는 연결설 Terminal Node(Leaf Node) : 밑으로 또 다른 노드가 연결되어 있지 않은 H,I,J,F,G와 같은 노드 Sub-Tree : 큰 트리(전체)에 속하는 작은 트리 Level : 트리에서 각 층별로 숫자를 매김 Height : 트리의 최고 레벨 (3) 참고 자료:velog.io/@adam2/TREE

그래프란? 노드(Vertex)가 있고 그 노드를 연결하는 간선(edge)을 하나로 모아놓은 비선형 자료구조 그래프의 종류 무방향 그래프(undirected graph): 간선을 통해 양방향으로 이동하며, 정점A와 정점B를 연결하는 간선은 (A, B)와 같이 쌍으로 표현한다. 방향 그래프(directed graph): 간선에 방향성이 존재한다. A →B 로만 갈 수 있는 간선은 로 표시한다. 와 는 다르다. 가중치 그래프(weighted graph): 간선에 비용이나 가중치가 할당된 그래프로 ‘네트워크(Network)’라고도 한다. 그래프의 구현 방식 1. 인접 행렬 2. 인접 리스트 그래프 메서드 .addNode() : 새로운 node를 생성하여 그래프에 추가한다. .contains() : node.va..

해쉬테이블이란? 해쉬테이블은 키와 값을 한 쌍으로 저장하는 자료구조이다. 키를 입력받으면 숫자를 반환하는 Hash함수가 있다. 이 숫자는 인덱스 번호가 된다. 해쉬테이블 시간 복잡도 값을 가져올 때 : O(1) 값을 추가할 때 : O(1) 값을 삭제할 때 : O(1) 해쉬 충돌 해결방법 종류 Chaining 장점: 1)한정된 저장소를 효율적으로 쓸 수 있다. 2)해시 함수를 선택하는 중요성이 상대적으로 적다. 3)상대적으로 적은 메모리를 쓴다. 단점: 1)쏠림현상이 생긴다. 2)외부 저장 공간을 사용한다. Open Addressing(개방주소법) 개방주소법은 데이터의 해시(hash)가 변경되지 않았던 chaining과는 달리 비어있는 해시(hash)를 찾아 데이터를 저장하는 기법이다. 따라서 개방주소법에..

연결리스트란? 크기가 동적인 자료구조이다. 노드로 구성되어있으며, 내가 구현한 단일 연결리스트의 구성은 그림과 같다. 단일 연결리스트 메서드 addToTail: 꼬리에 노드 추가 remove: 주어진 값을 찾아서 연결 해제 getNodeAt: 주어진 인덱스의 노드를 찾아서 반환 Contains: 리스트에 주어진 값이 존재하는지 여부 확인 indexOf: 주어진 값의 인덱스를 반환 구현방법 1. 배열을 이용하는 방법 2. 구조체와 포인터를 이용하는 방법

큐 란? 큐는 스택과 다르게 선입 선출의 구조이다. 줄을 세우는것과 비슷하다. 큐 메서드 Enqueue: 큐 맨 뒤에 데이터 추가 Dequeue: 큐 맨 앞쪽 요소 삭제 구현 방법 1. 배열 2. 연결리스트

스택이란? 한 쪽 끝에서만 데이터를 넣고 뺼 수 있는 자료구조 흡사 접시를 쌓는것과 비슷하다. 스택 메서드 종류 pop():스택에서 가장 위 항목을 제거 push();스택 가장 위에 데이터 추가 peek():스택 가장 위 항목을 반환 구현 방법 1. 배열 사용 2. 연결리스트