최대 힙, 최소 힙 (배열로 구현)

힙 기본 설명 자료구조 중 최대 힙, 최소 힙이 있다. 힙은 완전 이진 트리의 구조를 갖고 있고 수의 집합에서 특정한 수를 꺼내올때 유용하다. 예를 들어 배열 {1, 2, 3, 4, 5}중에서 가장 작거나 큰 수를 꺼내올때 단순하게 생각하면 for loop을 이용하면 시간복잡도가 O(N)이 될테지만, 힙을 사용하면 시간복잡도를 O(logN)까지 줄일 수 있다. 연결리스트로 구현할 수도 있겠지만, 배열로 구현하는 것이 편하기 때문에 배열로 구현한다. 완전 이진 트리이기 때문에, 메모리 누수도 걱정할 필요 없다. 최소 힙은 부모 노드가 자식 노드보다 항상 작거나 같은 구조다. 최대 힙은 부모 노드가 자식 노드보다 항상 크거나 같은 구조다. 최소 힙 구현 백준 1927번을 기준으로 구현한 코드다. #inclu..

트리

트리는 지금까지 배운 자료구조(스택, 큐, 덱)과는 달리 비선형 구조다. 이러한 개념을 설명한 적이 없지만 스택, 큐, 덱 등은 선형 구조다. 사실 이미 비선형 구조를 가진 문제를 푼 적이 몇 번 있는데, 그것은 그래프 문제들이었다. 그래프 설명도 따로 했어야 했는데... 까먹었다. 사실 트리도 설명하기 귀찮아서.... 정말 간단하게 소개만 하자면 트리는 부모 노드와 자식 노드로 이루어져있다. 더 자세한 개념과 용어는 대부분 부모 노드와 자식 노드의 관계에서 파생된다. 간단한 트리 구현 코드는 '1991번: 트리 순회'에서 썼다. 연결리스트로 구현을 했다. 트리를 배열로 구현하면 힙(Heap)을 구현할 수도 있다.

DFS, BFS (인접 행렬로 구현)

DFS 기본 설명 DFS (Depth First Search, 깊이 우선 탐색) DFS의 특징을 설명하자면 탐색을 한 방향으로 시작하면 갈 수 있는 최대한 깊게 간다. 그래서 위의 그래프를 예시로 하면 우선은 정점 1->2->4 들을 먼저 탐색할 것이다. 이다음으로는, 4에서 길이 막혔으므로 정점 2, 1로 되돌아가면서 다른 방향으로 탐색할 수 있는지 확인을 한다. 2에서는 다른 곳으로 갈 수 없고, 1에서 3 쪽으로 갈 수 있으므로 1->3->5 순으로 탐색을 할 것이다. 그리고 또 정점 3으로 돌아오면 6으로 갈 수 있으므로 6까지 탐색을 한다. 그러면 길이 또 막혔으므로 정점 3, 1 순으로 되돌아오면 더 이상 탐색할 수 있는 곳이 없으므로 탐색이 끝나는 것이다. 결과를 종합해보면 1->2->4->..

덱 (연결리스트로 구현)

덱의 기본 설명은 '덱 (구조체로 구현)'에서 설명을 했으므로 생략하겠다. 백준 10866번 문제를 베이스로 구현한 코드다. 코드 자체는 이중 연결리스트와 유사하다. 또한, 연결리스트로 구현했으므로 full() 함수는 없다. 덱 직접 입력 코드 구현 #include #include typedef struct Node { int data; struct Node *left; struct Node *right; }Node; typedef struct Deque { Node *front; Node *rear; int size; }Deque; void init_deque(Deque *deque) { deque->front = NULL; deque->rear = NULL; deque->size = 0; } int ..

덱 (구조체로 구현)

덱 기본 설명 덱은 간단하게 생각해서 원형 큐를 조금 확장시킨 개념이라 생각할 수 있다. 원형 큐는 rear에서 enqueue를 하고 front에서 dequeue를 했지만, 덱은 여기서 확장해서 front과 rear 모두에서 enqueue와 dequeue를 한다고 생각하면 된다. 코드의 구현에 있어서 생각해야 할 것은, 원형 큐에서의 enqueue를 push_front와 push_back로 나누고, dequeue를 pop_front와 pop_back으로 나누고 코드를 잘 짜야한다는 것이다. 밑에서 설명할 함수들에 있는 full()함수와 empty()함수는 완성된 코드에 있다. void enqueue(Queue* q, int data) { if (full(q)) { printf("큐가 포화상태입니다. 데이..

큐 (연결리스트로 구현)

연결리스트로 큐를 구현하므로 크기에 제약이 없어 큐가 꽉 찼는지 검사할 필요가 없으므로 full() 함수가 필요가 없다. 큐의 기본적인 설명은 '선형 큐 (구조체로 구현)'에서 설명했으므로 생략하겠다. 원형 큐는 선형 큐를 보완한 형태지만, 여전히 배열 때문에 크기에 제약을 받는 단점을 보인다. 연결리스트로 구현한 큐는 이러한 단점을 없애서 큐를 구현할 수 있는 가장 효율적인 방법이라고 볼 수 있다. 구현 #include #include #include typedef struct Node //노드 정의 { int data; struct Node *next; }Node; typedef struct Queue //Queue 구조체 정의 { Node *front; //맨 앞(꺼낼 위치) Node *rear; ..

원형 큐 (구조체로 구현)

원형 큐의 기본 설명은 '원형 큐 (배열로 구현)'에서 이미 했으므로 생략하겠다. 바로 구조체로 구현한 원형 큐의 동작 상태를 볼 수 있는 코드로 넘어가겠다. 원형 큐 구현 #include #include #include #define MAX 5 typedef struct Queue { int queue[MAX]; int front, rear; }Queue; void init_queue(Queue* q) { q->front = q->rear = 0; //front, rear 0으로 초기화 } int empty(Queue* q) { return (q->front == q->rear); } int full(Queue* q) { return (q->front == ((q->rear+1)%MAX)); } voi..

원형 큐 (배열로 구현)

원형 큐 기본 설명 선형 큐의 단점을 되새겨 보면 dequeue() 함수를 실행함으로서 발생하는 사용할 수 없는 공간들이 생겼었다. 즉 그 공간들을 재활용할 수 있는 코드를 구현하지 않는 이상 메모리 누수가 생긴 것이다. 그래서 이런 단점을 보완한 것이 원형 큐이다. 이를 구현한 방법은 예시로 enqueue() 함수를 보이겠다. void enqueue(int data){ if(full()) { printf("큐가 포화상태입니다. 데이터 삽입을 취소합니다.\n"); return; } else { rear = (rear+1)%MAX; queue[rear]=data; } } 위의 함수를 보면 큐가 포화상태가 아닐 시, rear은 rear+1의 MAX로 나눈 나머지 값이 대입된다. dequeue() 함수도 이와..