List(연결리스트)
연결리스트는 랜덤 접근이 가능한 배열과는 다른 순차적인(sequential) 자료구조입니다.
연결리스트는 노드들로 구성되어 있습니다. 노드는 저장할 값과 다음 노드를 가리키는 포인터로 이루어져 있습니다. 연결리스트의 첫 노드인 헤드(Head)로 부터 노드에 다음 노드를 가리키는 포인터를 사용해 리스트를 순회할 수 있게 됩니다.
<List(연결리스트)>
위와 같은 연결리스트를 Singly Linked List라고 합니다.
Singly Linked List의 각 노드에 이전 노드를 가리키는 포인터를 추가하게 되면 양방향으로 순회가 가능한 Doubly Linked List가 되고, 환형 큐(Circular Queue)와 같이 연결리스트의 마지막 노드인 테일(Tail)과 헤드를 이으면 Circular Linked List가 됩니다.
이는 문제의 상황에 따라 구현하여 사용하시면 됩니다.
<Doubly Linked List>
각 노드는 저장할 값과 자신의 앞, 뒤 노드를 가리키는 포인터를 가짐
<Circular Linked List>
테일의 포인터는 헤드를 가리킴
두 자료구조의 장단점을 나열해보자면, 배열은 인덱스로 인한 무작위 접근이 가능하고, 리스트에 비해 저장공간을 적게 필요로 하지만, 리스트에 비해 자료의 삽입, 삭제가 비효율 적인 부분이 있습니다. 순서를 유지하면서 자료를 삽입 / 삭제하기 위해서는 최악의 경우 모든 데이터를 옮겨주어야 하기 때문입니다.
리스트는 무작위 접근이 불가능하므로 무조건 순차적으로 탐색해야 하며, 노드에 저장할 값과 포인터를 포함하고 있기 때문에 똑같은 크기의 배열에 비해 저장공간을 많이 차지하게 되지만, 자료의 삽입과 삭제가 새로운 노드를 만들어 포인터로 이어주기만 하면 되기 때문에 간편하고 유연하게 동작합니다.
리스트와 배열의 시간복잡도 비교,https://en.wikipedia.org/wiki/Linked_list
상황에 따라 유리한 자료구조가 있기 때문에 유연하게 사용할 수 있어야 합니다.
아래 코드는 리스트를 구현한 코드입니다.
JAVA
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
String command = scanner.next();
// push, get, size, count, clear
if (command.charAt(0) == 'p') {
int value = scanner.nextInt();
list.add(value);
}
else if (command.charAt(0) == 'g') {
int idx = scanner.nextInt();
System.out.println(list.get(idx));
}
else if (command.charAt(0) == 's') {
System.out.println(list.size());
}
else if (command.charAt(1) == 'o') {
int target = scanner.nextInt(), count = 0;
for (int j = 0; j < list.size(); j++) {
if (list.get(j) == target) {
count++;
}
}
System.out.println(count);
}
else {
list.clear();
}
}
}
}C++
#include <stdio.h>
#include <list>
using namespace std;
int main() {
int n;
scanf("%d", &n);
list<int> mylist;
while(n--) {
char command[10];
scanf("%s", command);
// push, get, size, count, clear
if(command[0] == 'p') {
int value;
scanf("%d", &value);
mylist.push_back(value);
} else if(command[0] == 'g') {
int idx;
scanf("%d", &idx);
list<int>::iterator it = mylist.begin();
while(idx--) {
it++;
}
printf("%d\n", *it);
} else if(command[0] == 's') {
printf("%d\n", mylist.size());
} else if(command[1] == 'o') {
int target, cnt = 0;
scanf("%d", &target);
for(list<int>::iterator it = mylist.begin(); it != mylist.end(); it++) {
if(*it == target) {
cnt++;
}
}
printf("%d\n", cnt);
} else {
mylist.clear();
}
}
return 0;
} C
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
struct node* next;
int value;
} node;
typedef struct list {
node* head;
node* last;
int size;
} list;
void init_list(list* mylist);
void push_back(list* mylist, int value);
int get_idx(list* mylist, int idx);
int count_target(list* mylist, int target);
void clear_list(list* mylist);
void free_node(node* current_node);
int main() {
int n;
scanf("%d", &n);
list mylist;
init_list(&mylist);
while(n--) {
char command[10];
scanf("%s", command);
// push, get, size, count, clear
if(command[0] == 'p') {
int value;
scanf("%d", &value);
push_back(&mylist, value);
} else if(command[0] == 'g') {
int idx;
scanf("%d", &idx);
printf("%d\n", get_idx(&mylist, idx));
} else if(command[0] == 's') {
printf("%d\n", mylist.size);
} else if(command[1] == 'o') {
int target;
scanf("%d", &target);
printf("%d\n", count_target(&mylist, target));
} else {
clear_list(&mylist);
}
}
return 0;
}
void init_list(list* mylist) {
mylist->head = (node*)malloc(sizeof(node));
mylist->head->next = NULL;
mylist->last = mylist->head;
mylist->size = 0;
}
void push_back(list* mylist, int value) {
node* new_node = (node*)malloc(sizeof(node));
new_node->value = value;
new_node->next = NULL;
mylist->last->next = new_node;
mylist->last = new_node;
mylist->size++;
}
int get_idx(list* mylist, int idx) {
node* pre_node = mylist->head;
while(idx--) {
pre_node = pre_node->next;
}
return pre_node->next->value;
}
int count_target(list* mylist, int target) {
int count = 0;
for(node* pre_node = mylist->head; pre_node->next != NULL; pre_node = pre_node->next) {
if(pre_node->next->value == target) {
count++;
}
}
return count;
}
void clear_list(list* mylist) {
free_node(mylist->head);
init_list(mylist);
}
void free_node(node* current_node) {
if(current_node->next != NULL) {
free_node(current_node->next);
}
free(current_node);
}
Queue (큐)
큐는 선형 구조이며, 삽입된 순서대로 값이 나오는 FIFO(First in First Out)로 되어 있습니다. 이때 삽입하는 과정을 enqueue라고 하며 값을 빼내는 과정을 dequeue라고 합니다.
예를 들면 a, b, c 순서로 enqueue하고 큐에 있는 값들을 모두 dequeue하면 a, b, c 순서로 나오게 됩니다.
또한 큐에는 size, front, empty라는 함수가 있으며 size는 큐에 들어있는 값들의 수를 반환하는 함수이고, front은 큐에서 가장 먼저 삽입된 값을 반환하는 함수, empty는 큐가 비어 있는지 여부를 반환하는 함수입니다.
<그림 1> enqueue
<그림 2> dequeue
그리고 이러한 큐를 만드는 방법에는 2가지 방법이 있습니다. 하나는 배열을 이용한 방법이고, 다른 하나는 링크드 리스트를 이용한 방법입니다.
1) 배열을 이용한 방법에서는 삽입될 위치인 큐의 마지막 부분을 저장하는 변수 rear와 큐의 처음 부분을 저장하는 변수 front가 필요합니다. 또한 큐의 데이터 개수를 저장하는 변수 size를 이용하여 큐의 크기(큐에 들어있는 요소의 수)를 빠르게 알 수 있습니다. 또한 큐의 크기가 0일 경우 큐가 비어 있는 것이므로 비어 있는지 여부도 쉽게 알 수 있습니다. 따라서 배열로 구현하기 위해서는 값들을 담을 배열과 큐의 처음 위치와 마지막 위치(삽입될 위치)를 저장하는 변수가 필요합니다. 또한 enqueue과정과 dequeue과정에서 각각 rear index, front index가 점점 뒤로 밀려나기 때문에 이를 효율적으로 구성하려면 환형 배열로 구현해주어야 합니다.
<그림 3> 환형 배열로 구현한 큐의 dequeue
<그림 4> 환형 배열로 구현한 큐의 enqueue
2) 링크드 리스트를 이용한 방법에서는 값과 다음 노드의 위치를 저장하는 큐 노드들을 이용할 것이며 마지막으로 삽입된 노드의 위치를 저장하는 노드형 포인터 rear와 큐의 가장 앞 노드의 위치를 저장하는 노드형 포인터 front, 노드들의 수를 저장하는 변수 size가 필요합니다. front와 rear는 초기화시 처음에 널 값을 넣어주고, enqueue할 경우 이전에 rear의 next는 새로 삽입하는 노드가 되고, 새로 삽입되는 노드가 rear가 됩니다. dequeue할 경우 이전의 Head의 next가 Head가 되고, 이전의 head는 메모리 할당 해제 시킵니다.
<그림 5> 링크드 리스트로 구현한 queue
앞서 소개한 array 와 linked list를 이용해 큐를 구현한 c/c++ 언어로 구현한 코드를 제공합니다.
C++과 JAVA에서는 Queue를 기본 라이브러리로 제공하고 있습니다. 다음은 C++/JAVA에서 큐 라이브러리를 이용한 코드를 제공합니다.
JAVA(Library)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < N; i++) {
String cmd = scanner.next();
if (cmd.charAt(0) == 's') {
System.out.println(q.size());
}
else if (cmd.charAt(0) == 'e') {
int val = scanner.nextInt();
q.add(val);
}
else if (cmd.charAt(0) == 'd') {
q.remove();
}
else if (cmd.charAt(0) == 'f') {
System.out.println(q.peek());
}
}
}
}
C++(Library)
#include <queue>
#include <iostream>
#include <string>
using namespace std;
int main() {
int val,N;
queue<int> q;
string cmd;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> cmd;
if (cmd[0] == 's') {
cout << q.size() << endl;
} else if (cmd[0] == 'e') {
cin >> val;
q.push(val);
} else if (cmd[0] == 'd') {
q.pop();
} else if (cmd[0] == 'f') {
cout << q.front() << endl;
}
}
return 0;
}
C++(Linked list)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct queue_node {
int data;
queue_node* next;
};
struct queue {
queue_node* front;
queue_node* rear;
int sz;
queue() {
front=rear = NULL;
sz = 0;
}
};
int queue_size(queue &q) {
return q.sz;
}
bool queue_empty(queue &q) {
return queue_size(q) == 0;
}
void queue_enqueue(queue& q, int val) {
queue_node *newNode = (queue_node*)malloc(sizeof(queue_node));
newNode->data = val;
newNode->next = 0;
q.sz++;
if (q.rear==NULL && q.front==NULL) {
q.rear=q.front = newNode;
return;
}
q.rear->next = newNode;
q.rear = newNode;
}
void queue_dequeue(queue& q) {
assert(!queue_empty(q));
queue_node *nextHead = q.front->next;
free(q.front);
if (q.front == q.rear) q.front = q.rear = 0;
q.front = nextHead;
q.sz--;
}
int queue_front(queue& q) {
assert(!queue_empty(q));
return q.front->data;
}
int main() {
int val;
queue q;
for (int i = 0; i < 5; i++) {
queue_enqueue(q, i); // input : 0 1 2 3 4
}
printf("output : ");
while(!queue_empty(q)) {
printf("%d ", queue_front(q));
queue_dequeue(q);
}
return 0;
}C++(Array)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct queue {
int *data;
int front,rear;
int maxsize;
int size;
queue(int sz = 16) {
maxsize = sz;
front = 0;
rear = 0;
size = 0;
data = (int*)malloc(maxsize*sizeof(int));
}
};
int queue_size(queue& q) {
return q.size;
}
bool queue_empty(queue& q) {
return queue_size(q) == 0;
}
bool queue_full(queue& q) {
return q.size == q.maxsize;
}
void queue_push(queue& q, int val) {
assert(!queue_full(q));
q.data[q.rear] = val;
q.rear = (q.rear + 1) % q.maxsize;
q.size++;
}
void queue_pop(queue& q) {
assert(!queue_empty(q));
q.front = (q.front + 1) % q.maxsize;
q.size--;
}
int queue_front(queue& q) {
assert(!queue_empty(q));
return q.data[q.front];
}
int main() {
int val;
queue q;
for (int i = 0; i < 5; i++) {
queue_push(q,i); // input : 0 1 2 3 4
}
printf("output : ");
while(!queue_empty(q)) {
printf("%d ", queue_front(q));
queue_pop(q);
}
return 0;
}
C(Linked list)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
struct queue_node {
int data;
struct queue_node* next;
};
struct queue {
struct queue_node* front;
struct queue_node* rear;
int sz;
};
void queue_init(struct queue *q) {
q->front = q->rear = NULL;
q->sz = 0;
}
int queue_size(struct queue *q) {
return q->sz;
}
bool queue_empty(struct queue *q) {
return queue_size(q) == 0;
}
void queue_enqueue(struct queue *q, int val) {
struct queue_node *newNode = (struct queue_node*)malloc(sizeof(struct queue_node));
newNode->data = val;
newNode->next = 0;
q->sz++;
if (q->rear==NULL && q->front==NULL) {
q->rear=q->front = newNode;
return;
}
q->rear->next = newNode;
q->rear = newNode;
}
void queue_dequeue(struct queue *q) {
assert(!queue_empty(q));
struct queue_node *nextHead = q->front->next;
free(q->front);
if (q->front == q->rear) q->front = q->rear = 0;
q->front = nextHead;
q->sz--;
}
int queue_front(struct queue *q) {
assert(!queue_empty(q));
return q->front->data;
}
int val, N;
char cmd[16];
int main() {
struct queue q;
scanf("%d", &N);
queue_init(&q);
for (int i = 0; i < N; i++) {
scanf(" %s", cmd);
if (cmd[0] == 's') {
printf("%d\n", queue_size(&q));
} else if (cmd[0] == 'e') {
scanf("%d", &val);
queue_enqueue(&q, val);
} else if (cmd[0] == 'd') {
queue_dequeue(&q);
} else if (cmd[0] == 'f') {
printf("%d\n", queue_front(&q));
}
}
return 0;
}C(Array)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
struct queue {
int *data;
int front,rear;
int maxsize;
int size;
};
void queue_init(struct queue* q,int sz) {
q->maxsize = sz;
q->front = 0;
q->rear = 0;
q->size = 0;
q->data = (int*)malloc(q->maxsize * sizeof(int));
}
int queue_size(struct queue* q) {
return q->size;
}
bool queue_empty(struct queue* q) {
return queue_size(q) == 0;
}
bool queue_full(struct queue* q) {
return q->size == q->maxsize;
}
void queue_enqueue(struct queue* q, int val) {
assert(!queue_full(q));
q->data[q->rear] = val;
q->rear = (q->rear + 1) % q->maxsize;
q->size++;
}
void queue_dequeue(struct queue* q) {
assert(!queue_empty(q));
q->front = (q->front + 1) % q->maxsize;
q->size--;
}
int queue_front(struct queue* q) {
assert(!queue_empty(q));
return q->data[q->front];
}
int val, N;
char cmd[16];
int main() {
struct queue q;
scanf("%d", &N);
queue_init(&q, N);
for (int i = 0; i < N; i++) {
scanf(" %s", cmd);
if (cmd[0] == 's') {
printf("%d\n", queue_size(&q));
} else if (cmd[0] == 'e') {
scanf("%d", &val);
queue_enqueue(&q, val);
} else if (cmd[0] == 'd') {
queue_dequeue(&q);
} else if (cmd[0] == 'f') {
printf("%d\n", queue_front(&q));
}
}
return 0;
}Stack(스택)
스택은 선형 구조이며, 마지막으로 삽입된 값이 가장 먼저 나오는 LIFO(Last in First Out)으로 되어 있습니다. 이 때 삽입하는 과정을 push라고 하며 값을 빼내는 과정을 pop이라고 합니다. 예를 들면 a, b, c 순서로 push하고 스택에 있는 값들을 모두 pop하면 c, b, a 순서로 나오게 되는 것입니다. 또한 스택에는 size, top, empty라는 함수가 있으며 size는 스택에 들어있는 값들의 수를 반환하는 함수이고, top은 마지막으로 삽입된 값을 반환하는 함수, empty는 스택이 비어 있는지 여부를 반환하는 함수입니다.
JAVA (Library)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
Stack<Integer> st = new Stack<>();
for (int i = 0; i < N; i++) {
String cmd = scanner.next();
if (cmd.charAt(0) == 's') {
System.out.println(st.size());
}
else if (cmd.charAt(0) == 'p') {
if (cmd.charAt(1) == 'u') {
int val = scanner.nextInt();
st.add(val);
}
else if (cmd.charAt(1) == 'o') {
st.pop();
}
}
else if (cmd.charAt(0) == 't') {
System.out.println(st.peek());
}
}
}
}C++(Library)
#include <stack>
#include <iostream>
#include <string>
using namespace std;
int N, val;
string cmd;
int main() {
stack<int> st;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> cmd;
if (cmd[0] == 's') {
cout << st.size() << endl;
} else if (cmd[0] == 'p') {
if (cmd[1] == 'u') {
cin >> val;
st.push(val);
} else if (cmd[1] == 'o') {
st.pop();
}
} else if (cmd[0] == 't') {
cout << st.top() << endl;
}
}
return 0;
}Graph (그래프)
그래프란 어떤 상태 혹은 객체 간의 관계를 나타내는 자료구조입니다. 그래프는 정점(Vertex)과 간선(Edge)으로 구성됩니다.
정점이란 어떠한 상태 혹은 객체를 나타냅니다. 간선은 그러한 정점 간의 관계, 그중에서도 연결성을 표현하는 요소입니다.
C++
#include <iostream>
#include <vector>
#include <list>
#define MAX 55
using namespace std;
int main() {
int adj_matrix[MAX][MAX], n;
cin >> n;
vector < list < int > > head(n + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
cin >> adj_matrix[i][j];
if (adj_matrix[i][j])
head[i].push_front(j);
}
for (int i = 1; i <= n; i++) {
cout << i << " : ";
if (!head[i].empty())
for (auto x : head[i])
cout << x << " ";
cout << endl;
}
return 0;
}JAVA
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] adj_matrix = new int[n + 1][n + 1];
ArrayList<Integer>[] adj_list = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
adj_list[i] = new ArrayList<>();
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
adj_matrix[i][j] = scanner.nextInt();
if (adj_matrix[i][j] == 1) {
adj_list[i].add(j);
}
}
}
for (int i = 1; i <= n; i++) {
System.out.print(i + " : ");
for (int j = 0; j < adj_list[i].size(); j++) {
System.out.print(adj_list[i].get(j) + " ");
}
System.out.println();
}
} }
Tree (트리)
트리는 자식과 부모의 관계로 이루어진 계층적인 구조입니다. 필요에 따라 다양한 종류로 나뉘게 되는데 이번 문서에서는 제일 간단한 트리인 이진 트리에 대해서 설명하려고 합니다. 먼저 이진 트리에서 사용하는 용어들을 정리해보면 다음과 같습니다.
Root : 트리에서 가장 최상위에 존재하는 노드
Child : 어떠한 노드의 자식 노드
Parent : 어떠한 노드의 부모 노드
Siblings : 같은 부모를 갖는 형제 노드
Leaf/Terminal : 자식 노드를 갖지 않는 노드
Branch/Internal : 자식 노드를 적어도 1개 이상 갖는 노드
Degree : 노드가 가지고 있는 자식 노드의 개수
Height : 해당 노드부터 Leaf 노드까지의 가장 긴 거리
Level : 트리 각 층의 단계 (루트 노드의 경우 1)
JAVA(in/out)
import java.util.*;
public class Main {
static final int EMPTY = -1;
static final int TREE_MAX_SIZE = 10000;
static int child[][];
static int root = 0, N, P;
static void insert(int parent_idx, int child_idx) {
if (parent_idx == -1) root = child_idx;
else if (child[parent_idx][0] == EMPTY) {
child[parent_idx][0] = child_idx;
}
else if (child[parent_idx][1] == EMPTY) {
child[parent_idx][1] = child_idx;
}
else {
// tree_node has left, right
}
}
static void pre_order(int cur) {
int left = child[cur][0];
int right = child[cur][1];
System.out.print(String.valueOf(cur) + ' ');
if (left != EMPTY) {
pre_order(left);
}
if (right != EMPTY) {
pre_order(right);
}
}
static void in_order(int cur) {
int left = child[cur][0];
int right = child[cur][1];
if (left != EMPTY) {
pre_order(left);
}
System.out.print(String.valueOf(cur) + ' ');
if (right != EMPTY) {
pre_order(right);
}
}
static void post_order(int cur) {
int left = child[cur][0];
int right = child[cur][1];
if (left != EMPTY) {
post_order(left);
}
if (right != EMPTY) {
post_order(right);
}
System.out.print(String.valueOf(cur) + ' ');
}
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
child = new int[TREE_MAX_SIZE][2];
for (int i = 0; i < TREE_MAX_SIZE; i++)
for (int j = 0; j < 2; j++)
child[i][j] = EMPTY;
N = scanner.nextInt();
for (int i = 0; i < N; i++) {
P = scanner.nextInt();
if (P == -1) {
root = i;
}
else {
insert(P, i);
}
}
pre_order(root);
System.out.println("");
in_order(root);
System.out.println("");
post_order(root);
System.out.println("");
}
}C++(in/out)
#include <iostream>
#include <cstring>
using namespace std;
int N, root, P;
const int EMPTY = -1;
const int TREE_MAX_SIZE = 10000;
int child[TREE_MAX_SIZE][2];
void insert(int parent_idx, int child_idx) {
if (parent_idx == -1) root = child_idx;
else if (child[parent_idx][0] == EMPTY) {
child[parent_idx][0] = child_idx;
} else if (child[parent_idx][1] == EMPTY) {
child[parent_idx][1] = child_idx;
} else {
// tree_node has left, right
}
}
void pre_order(int cur) {
int left = child[cur][0];
int right = child[cur][1];
cout << cur << ' ';
if (left != EMPTY) {
pre_order(left);
}
if (right != EMPTY) {
pre_order(right);
}
}
void in_order(int cur) {
int left = child[cur][0];
int right = child[cur][1];
if (left != EMPTY) {
pre_order(left);
}
cout << cur << ' ';
if (right != EMPTY) {
pre_order(right);
}
}
void post_order(int cur) {
int left = child[cur][0];
int right = child[cur][1];
if (left != EMPTY) {
post_order(left);
}
if (right != EMPTY) {
post_order(right);
}
cout << cur << ' ';
}
int main() {
memset(child, -1, sizeof(child));
cin >> N;
for (int i = 0; i < N; i++) {
cin >> P;
if (P == -1) {
root = i;
} else {
insert(P, i);
}
}
pre_order(root);
puts("");
in_order(root);
puts("");
post_order(root);
puts("");
}C++(Vector)
#include <iostream>
#include <vector>
using namespace std;
const int TREE_MAX_SIZE = 10000;
vector <int> child[TREE_MAX_SIZE];
void insert(int p,int c) {
if (p == -1) {
return;
}
child[p].push_back(c);
}
void pre_order(int cur) {
cout << cur << ' ';
for (int i = 0; i < child[cur].size(); i++) {
pre_order(child[cur][i]);
}
}
void post_order(int cur) {
for (int i = 0; i < child[cur].size(); i++) {
post_order(child[cur][i]);
}
cout << cur << ' ';
}
int main() {
insert(-1,0);
insert(0, 1);
insert(0, 2);
insert(1, 3);
insert(1, 4);
pre_order(0);
puts("");
post_order(0);
}C(in/out)
#include <stdio.h>
#include <string.h>
const int EMPTY = -1;
int child[10000][2];
int N, root, P;
void insert(int parent_idx, int child_idx) {
if (parent_idx == -1) root = child_idx;
else if (child[parent_idx][0] == EMPTY) {
child[parent_idx][0] = child_idx;
} else if (child[parent_idx][1] == EMPTY) {
child[parent_idx][1] = child_idx;
} else {
// tree_node has left, right
}
}
void pre_order(int cur) {
int left = child[cur][0];
int right = child[cur][1];
printf("%d ", cur);
if (left != EMPTY) {
pre_order(left);
}
if (right != EMPTY) {
pre_order(right);
}
}
void in_order(int cur) {
int left = child[cur][0];
int right = child[cur][1];
if (left != EMPTY) {
pre_order(left);
}
printf("%d ", cur);
if (right != EMPTY) {
pre_order(right);
}
}
void post_order(int cur) {
int left = child[cur][0];
int right = child[cur][1];
if (left != EMPTY) {
post_order(left);
}
if (right != EMPTY) {
post_order(right);
}
printf("%d ", cur);
}
int main() {
memset(child, -1, sizeof(child));
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &P);
if (P == -1) {
root = i;
} else {
insert(P, i);
}
}
pre_order(root);
puts("");
in_order(root);
puts("");
post_order(root);
puts("");
}Heap (힙)
힙(heap) 은 최댓값 또는 최솟값을 빠르게 찾아낼 수 있는 트리형 자료구조입니다.
힙은 완전이진트리 형식을 따르며 모든 부모 노드의 값이 자식 노드들의 값과 일정한 대소 관계를 가지게 되는 규칙을 가지고 있습니다.
또한 자식노드 사이의 상관관계는 없으므로 유의하여야 합니다.
부모 노드의 값이 자식 노드의 값보다 크다면 최대 힙(Max Heap), 부모 노드의 값이 자식 노드의 값보다 작다면 최소 힙(Min Heap) 으로 부릅니다.
힙의 규칙에 따라 트리의 가장 상단에는 최댓값 또는 최솟값이 있는 것이 자명하기 때문에, O(1) 만에 최댓값과 최솟값을 찾을 수 있습니다.
JAVA
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
ArrayList<Integer> heap = new ArrayList<>();
ArrayList<Integer> ans = new ArrayList<>();
heap.add(0); // for 1-based tree
for (int i = 1; i <= n; i++) {
heap.add(scanner.nextInt());
for (int j = i; j > 1; j /= 2) {
if (heap.get(j) < heap.get(j / 2)) {
int temp = heap.get(j);
heap.set(j, heap.get(j / 2));
heap.set(j / 2, temp);
}
}
}
for (int i = 1; i <= n; i++) {
ans.add(heap.get(1));
heap.set(1, heap.get(n - i + 1));
for (int j = 1; ; ) {
int k = j * 2;
if (k > n - i) break;
if (k + 1 <= n - i && heap.get(k) > heap.get(k + 1)) k++;
if (heap.get(j) > heap.get(k)) {
int temp = heap.get(j);
heap.set(j, heap.get(k));
heap.set(k, temp);
j = k;
}
else break;
}
}
for (int i = 0; i < n; i++)
System.out.print(ans.get(i) + " ");
}
}C++
#include <iostream>
#include <algorithm>
#define MAX 5005
using namespace std;
int heap[MAX];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int m;
cin >> m;
heap[i] = m;
for (int j = i; j > 1; j /= 2) {
if (heap[j] > heap[j / 2]) {
swap(heap[j], heap[j / 2]);
}
}
}
for (int i = 1; i <= n; i++) {
swap(heap[1], heap[n - i + 1]);
for (int j = 1; ; ) {
int k = j * 2;
if (k > n - i) break;
if (k + 1 <= n - i && heap[k] < heap[k + 1]) k++;
if (heap[j] < heap[k]) {
swap(heap[j], heap[k]);
j = k;
}
else break;
}
}
for (int i = 1; i <= n; i++)
cout << heap[i] << " ";
return 0;
}C
#include <stdio.h>
#define MAX 5005
int heap[MAX];
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int m;
scanf("%d", &m);
heap[i] = m;
for (int j = i; j > 1; j /= 2) {
if (heap[j] > heap[j / 2]) {
swap(&heap[j], &heap[j / 2]);
}
}
}
for (int i = 1; i <= n; i++) {
swap(&heap[1], &heap[n - i + 1]);
for (int j = 1; ; ) {
int k = j * 2;
if (k > n - i) break;
if (k + 1 <= n - i && heap[k] < heap[k + 1]) k++;
if (heap[j] < heap[k]) {
swap(&heap[j], &heap[k]);
j = k;
}
else break;
}
}
for (int i = 1; i <= n; i++)
printf("%d ", heap[i]);
return 0;
}Hashing (해싱)
해싱은 임의의 길이의 데이터(키, Key)를 고정된 길이의 데이터(해시값, Hash value)로 변환해 작은 크기의 해시 테이블로 대응(Mapping)시켜 식별하는 하나의 기법입니다. 해시 테이블은 M개의 버킷으로 이루어져 있으며, 이 글에서 다루는 해시값은 해당 키가 저장될 버킷의 번호(해시 테이블의 인덱스)를 나타냅니다.
키에서 해시값을 추출하는 일련의 과정을 해시 함수(Hash function)라고 합니다. 해시 함수는 같은 키에 대해서는 동일한 해시값을, 다른 키에 대해서는 다른 해시값을 추출해야 합니다. 하지만 일반적으로 해싱에서 해시값의 범위(M)는 키의 범위보다 작기 때문에 어떤 이상적인 해시 함수라도 비둘기집의 원리에 의해 서로 다른 두 키가 같은 해시값을 가질 수 있습니다. 이런 경우를 충돌(Collision)이라고 합니다.
해싱이 사용되는 예로 문자열(Key)을 정숫값(Hash value)으로 치환하여 문제를 해결하는 방법이 있습니다. 이에 사용되는 가장 대표적인 해시 함수는 진법을
이용하는 것입니다. "SCPC"이라는 단어가 있다고 하면, 아래와 같이 진법을 이용한 해시 함수를 만들 수 있습니다.
f(key) = ((((key[0]) * 26 + key[1]) * 26 + key[2])) * 26 … key[l – 1])
f("SCPC") = 19 * 26^3 + 3 * 26^2 + 16 * 26^1 + 3 * 26^0 = 336391
해시 함수의 시간 복잡도를 O(H)라고 할 때 해시값의 중복이 없는 이상적인 해싱에서 키의 검색, 삽입, 삭제에는 모두 O(H)의 시간이 걸립니다.
하지만 앞서 말했듯 해시값의 범위가 키의 범위보다 작을 때에는 충돌이 발생할 수밖에 없습니다.
예를 들어 위와 같은 진법 변환을 해시 함수로 사용할 때에는 문자열이 길어지면 해시값이 너무 커지므로 적당히 큰 수로 나머지 연산한 값, 이 글에서는 해시 테이블의 크기 M으로 나머지 연산한 값을 해시값으로 쓸 수 있습니다.이때 해시값의 M에 대한 나머지가 같은 키끼리는 충돌이 발생합니다.
해시 함수와 마찬가지로 충돌을 제어하는 방법도 다양합니다. 여기에서는 대표적인 충돌 제어 방법 중 하나인 체이닝(Chaining)에 대해서 설명하겠습니다.
체이닝은 충돌한 키들을 보존하기 위해 각 버킷을 리스트 형태로 구현합니다. 최초의 버킷은 모두 원소가 0개인 리스트의 헤더이며, 해당 버킷에 데이터가 추가될 때마다 노드를 추가합니다.
이때 어떤 키가 해시 테이블에 존재하는지 검사하기 위해서는 해당 키의 해시값에 해당하는 버킷이 가진 노드를 모두 순회해야 합니다.
이는 리스트에서 원소를 찾는 연산과 동일하며 이에 기반한 삭제 연산도 같은 선형 시간이 걸립니다.
이때 몇 개의 버킷에만 데이터가 편중되는 최악의 경우 각 연산의 시간 복잡도는 O(H + N)이 됩니다.
이런 상황을 최소한으로 하기 위해서는 해시값의 추출 과정, 즉 해시 함수를 어떻게 구성할 것인지가 핵심이 됩니다.
좋은 해시 함수란 해시값을 추출하는 연산이 빠르되 충돌이 적고 해시 테이블의 영역을 고르게 사용할 수 있어야 합니다.
예를 들어 위에서 다룬 A * pow(B) mod M 형태의 진법 변환을 사용할 때 A의 값을 0이 아닌 1부터 시작하는 것이 좋습니다.
0을 사용하게 되면 "A"와 "AAA"의 해시값이 같아지기 때문입니다. 또한 B와 M이 서로소인 것이 충돌 확률이 낮아 더 좋은 해시 함수가 될 수 있습니다.
해시 함수의 구현과 충돌 제어 방법, 좋은 해시 함수의 조건에 관해서는 굉장히 많은 자료가 있으므로 보다 깊은 이해를 위해 직접 찾아보시기 바랍니다.
글의 첫 부분에서 말했듯 해싱의 핵심은 값의 식별입니다. 그렇기에 원소의 중복을 허용하지 않는 Set이나 Key:Value쌍에서 중복된 Key가 존재하면 안 되는 Map과 같은 자료구조를 구현하는 데에 사용되기도 합니다.
아래는 해싱을 사용해 set을 구현한 코드입니다.
JAVA
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
HashSet<String> hash = new HashSet<String>();
for (int i = 0; i < n; i++) {
int command = sc.nextInt();
String key = sc.next();
if (command == 1) {
hash.add(key);
}
else if (command == 2) {
hash.remove(key);
}
else {
if (hash.contains(key)) {
System.out.println("1");
}
else {
System.out.println("0");
}
}
}
}
}C++
#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
unordered_set<string> hash;
for(int i = 0; i < n; i++) {
int command;
string key;
cin >> command >> key;
if(command == 1) {
hash.insert(key);
} else if(command == 2) {
hash.erase(key);
} else {
if(hash.count(key) == 1) {
printf("1\n");
} else {
printf("0\n");
}
}
}
return 0;
}C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUCKET_COUNT 10007
#define MAX_STRING_LENGTH 100
typedef struct node {
struct node* next;
int hash_value;
} node;
int get_hash_value(char* key) {
int value = 0, len = strlen(key);
for(int i = 0; i < len; i++)
value = (value * 27 + key[i] - 'A' + 1) % MAX_STRING_LENGTH;
return value;
}
void insert(node** head, char* key) {
int hash_value = get_hash_value(key);
for(node* current_node = (*head)->next;
current_node->next != NULL;
current_node = current_node->next) {
if(current_node->hash_value == hash_value) {
return ;
}
}
node* new_node = (node *)malloc(sizeof(node));
new_node->hash_value = hash_value;
if (!(*head)) {
new_node->next = NULL;
(*head) = new_node;
} else {
new_node->next = (*head);
(*head) = new_node;
}
return;
}
void erase(node** head, char* key) {
int hash_value = get_hash_value(key);
for(node* precedent_node = *head;
precedent_node->next != NULL;
precedent_node = precedent_node->next) {
if(precedent_node->next->hash_value == hash_value) {
precedent_node->next = precedent_node->next->next;
}
}
return;
}
int count(node** head, char* key) {
int counter = 0;
int hash_value = get_hash_value(key);
for(node* current_node = (*head)->next;
current_node->next != NULL;
current_node = current_node->next) {
if(current_node->hash_value == hash_value) {
counter++;
}
}
return counter;
}
int main() {
int n;
scanf("%d", &n);
node* hash[BUCKET_COUNT];
for(int i = 0; i < n; i++) {
int command;
char key[MAX_STRING_LENGTH + 1];
scanf("%d %s", &command, key);
if(command == 1) {
insert(hash, key);
} else if(command == 2) {
erase(hash, key);
} else {
if(0 < count(hash, key)) {
printf("1\n");
} else {
printf("0\n");
}
}
}
return 0;
}