0%

Posted on In , Disqus:
Symbols count in article: 7.5k Reading time ≈ 7 mins.

Graph(그래프)

그래프는 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조로 vertex(정점)와 edge(간선)의 집합으로 이루어진다.

그래프 용어

  • 수학적으로는 G = (V,E)로 표시한다.
  • V(G)는 그래프 G의 vertex들의 집합
  • E(G)는 그래프 G의 edge들의 집합
  • Vertex는 Node라고 불린다.
  • Edge는 link라고 불린다.
  • Vertex의 종류에 따라 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 구분된다.
    • 무방향 그래프 : ‘S—-E’ 화살표가 없는 선으로 이루어진 형태이다.
      • 무방향 그래프는 간선이 방향성이 없는 그래프로 양방향으로 갈 수 있다.
      • 정점의 차수(Degree)는 그 정점에 인접한 정점의 수를 말한다.
    • 방향 그래프 : ‘S—->E’ 화살표가 있는 선으로 이루어진 형태다.
      • 방향 그래프는 간선이 방향성이 있는 그래프로 한쪽방향으로만 갈 수 있다.
  • 간선에 비용이나 가중치가 할당된 그래프는 가중치 그래프(Weighted graph) 또는 네트워크(network)라고 한다.
  • 인접정점(adjacent vertex) : 간선에 의해 직접 연결된 정점을 뜻한다.
  • 경로 중에서 반복되는 간선이 없는 경우 단순경로(Simple Path)라고 한다
  • 시작정점과 종료정점이 동일하다면 이러한 경로를 사이클(cycle)이라고 한다.
  • 완전 그래프(Complete Graph) : 그래프 속에 있는 모든 정점이 서로 연결되어 있는 그래프
    • 무방향 완전 그래프의 정점의 수를 n이라고 하면 하나의 정점은 n-1개의 다른 정점으로 연결되므로 간선의 수는 n*(n-1)/2가 된다.

그래프의 표현방법

1. 인접행렬 (adjacency matrix) O(n^2): 2차원 배열인 인접행렬 M의 각 원소는 다음 규칙에 의해 할당한다.

  • if(edge(i,j)가 그래프에 존재) M[i][j] = 1
  • otherwise M[i][j] = 0
  • 그래프에서는 자체 간선을 허용하지 않으므로 인접행렬의 대각선 성분은 모두 0으로 표시한다.
  • 무방향 그래프의 인접행렬을 대칭행렬이 된다.
  • 방향 그래프의 인접행렬은 일반적으로 대칭이 아니다.
  • n개의 정점을 가지는 그래프를 인접행렬로 표현하기 위해서는 간선의 수에 무관하게 항상 n^2개의 메모리 공간이 필요하다.

인접행렬 ADT

AdjacencyMatrix.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#ifndef ADJACENCYMATRIX_H
#define ADJACENCYMATRIX_H


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define MAX_VERTICES 10
typedef struct _GraphType {
	int n; //정점의 개수
	int adj_matrix[MAX_VERTICES][MAX_VERTICES];


}GraphType;


void graph_init(GraphType* graph);
void insertvertex(GraphType *g, int v);
void insert_edge(GraphType* g, int start, int end);
#endif //ADJACENCYMATRIX_H

AdjacencyMatrix.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//
// Created by Paik Seung Cheol on 2017. 9. 20..
//


#include "AdjacencyMatrix.h"


void graph_init(GraphType* graph) {
	int r, c;
	graph->n = 0;
	for(r = 0; r<MAX_VERTICES; r++) {
		for(c = 0; c<MAX_VERTICES; c++) {
			graph->adj_matrix[r][c] = 0;
		}
	}
}


void insertvertex(GraphType *g, int v) {
	if ((g->n+1) > MAX_VERTICES) {
		fprintf(stderr, "graph Error vertex overflow\n");
		return;
	}
	g->n++;


}
void insert_edge(GraphType* g, int start, int end) {
	g->adj_matrix[start][end] = 1;
	g->adj_matrix[end][start] = 1;
}

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "AdjacencyMatrix.h"


void adjMatrix() {
	GraphType* graph = (GraphType*)malloc(sizeof(GraphType));
	grapth_init(graph);
	insertvertex(graph, 5);
	insertvertex(graph, 5);
	insertvertex(graph, 5);
	insertvertex(graph, 5);
	insert_edge(graph,4,5);
	insert_edge(graph,2,3);
	insert_edge(graph,3,1);
	insert_edge(graph,2,5);
	insert_edge(graph,7,3);


	int r, c;
	graph->n = 0;
	for(r = 0; r<MAX_VERTICES; r++) {
		for(c = 0; c<MAX_VERTICES; c++) {
			printf("%d ",graph->adj_matrix[r][c]);
		}
		printf("\n");
	}
}
int main() {
	adjMatrix();
	return 0;
}

2. 인접 리스트(adjacency list) O(n+e) : 각각의 정점에 인접한 정점들을 연결리스트로 표시한 것으로 각 연결리스트이 노드들은 인접 정점을 저장한다.

  • 연결리스트들은 헤드 포인터를 가지고 있고 이 헤드 포인터들은 하나의 배열로 구성되어 있어서 정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 연결리스트에 쉽게 접근이 가능하다.

인접리스트 ADT

AdjacencyList.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//
// Created by Paik Seung Cheol on 2017. 9. 20..
//


#ifndef ADJACENCYLIST_H
#define ADJACENCYLIST_H


#include <stdio.h>
#include <stdlib.h>


enum VisitMode { Visited, NotVisited};
typedef int Element;


typedef struct tagVertex {
	Element Data;
	int visited;
	int index;
	struct tagVertex* next;
	struct tagEdge* AdjacencyList;
}Vertex;


typedef struct tagEdge {
	int weight;
	struct tagEdge* next;
	Vertex* from;
	Vertex* target;
}Edge;


typedef struct tagGraph {
	Vertex* vertices;
	int vertexCount;
}Graph;


Graph* createGraph();
void destoryGraph(Graph* g);


Vertex* createVertex(Element data);
void destoryVertex(Vertex* v);


Edge* createEdge(Vertex* from, Vertex* target, int weight);
void destoryEdge(Edge* e);


void addVertex(Graph* g, Vertex* v);
void addEdge(Vertex* v, Edge* e);
void printGraph(Graph* g);


#endif //ADJACENCYLIST_H

AdjacencyList.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//
// Created by Paik Seung Cheol on 2017. 9. 20..
//


#include "AdjacencyList.h"


Graph* createGraph() {
	Graph* graph = (Graph*)malloc(sizeof(Graph));
	graph->vertices = NULL;
	graph->vertexCount = 0;
	return graph;
}
void destoryGraph(Graph* g) {
	while(g->vertices != NULL) {
		Vertex* verteices = g->vertices->next;
		destoryVertex(g->vertices);
		g->vertices = verteices;
	}
	free(g);
}


Vertex* createVertex(Element data) {
	Vertex* vertex = (Vertex*)malloc(sizeof(Vertex));


	vertex->Data = data;
	vertex->next = NULL;
	vertex->AdjacencyList = NULL;
	vertex->visited = NotVisited;
	vertex->index = -1;
	return vertex;
}
void destoryVertex(Vertex* v) {
	while(v->AdjacencyList != NULL) {
		Edge* edge = v->AdjacencyList->next;
		destoryEdge(v->AdjacencyList);
		v->AdjacencyList = edge;
	}
	free(v);
}


Edge* createEdge(Vertex* from, Vertex* target, int weight) {
	Edge* e = (Edge*)malloc(sizeof(Edge));
	e->from = from;
	e->target = target;
	e->weight = weight;
	e->next = NULL;
	return e;
}
void destoryEdge(Edge* e) {
	free(e);
}


void addVertex(Graph* g, Vertex* v) {
	Vertex* vertexList = g->vertices;
	if (vertexList == NULL) {
		g->vertices = v;
	}
	else {
		while(vertexList->next != NULL) {
			vertexList = vertexList->next;
		}
		vertexList->next = v;
	}
	v->index = g->vertexCount++;
}
void addEdge(Vertex* v, Edge* e) {
	if (v->AdjacencyList == NULL) {
		v->AdjacencyList = e;
	}
	else {
		Edge* adjList = v->AdjacencyList;
		while(adjList->next != NULL) {
			adjList = adjList->next;
		}
		adjList->next = e;
	}
}
void printGraph(Graph* g) {
	Vertex* v = NULL;
	Edge* e = NULL;
	if ((v = g->vertices) == NULL) {
		return;
	}


	while(v!= NULL) {
		printf("%c : ", v->Data);
		if ((e = v->AdjacencyList) == NULL) {
			v = v->next;
			printf("\n");
			continue;
		}


		while(e != NULL) {
			printf("%c[%d] ", e->target->Data, e->weight);
			e = e->next;
		}
		printf("\n");
		v = v->next;
	}
	printf("\n");
}

그래프 탐색 방법

1. 깊이 우선 탐색 (Depth First Search : DFS)

  • 더 나아갈 길이 보이지 않을 때까지 깊이 들어간다.
  • 한 방향으로 계속 가다가 더 이상 갈수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 탐색을 진행
  • 길이 나오지 않을 때까지 그래프의 정점을 타고 깊이 들어가다 더 이상 방문해왔던 정점말고는 다른 이웃을 갖고 있지 않은 정점을 만나면 뒤로 돌아와 다른 경로로 뻗어 있는 정점을 타고 방문을 재개하는 방식

DFS 알고리즘

  1. 시작 정점을 밟은 후 이 정점을 ‘방문했음’으로 표시
  2. 이 정점과 이웃하고 있는 정점(인접정점)중에서 아직 방문하지 않은 곳을 선택하고 이를 시작 정점으로 삼아 다시 깊이 우선탐색을 시작(1단계를 다시하는 것)
  3. 정점에 더 이상 방문하지 않은 인접 정점이 없으면 이전 정점으로 돌아가서 2단계를 수행
  4. 이전 정점으로 돌아가도 더 이상 방문할 이웃이 없으면 그래프의 모든 정점을 방문했으므로 탐색을 종료
1
2
3
4
5
6
//u 아직방문하지 않은 정점
depth_first_search(v)
	v를 방문했다고 표시
	for v에 인접한 정점 탐색 do
		if (탐색하지 못한 정점이 있다면)
			then depth_first_search(u)

DFS 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void DFS(Vertex* v) {
	//1. 이미 방문햇음을 표시
	Edge* e = NULL;
	printf("%d ", v->data);
	v->visited = visited; //이미 방문했다는 것을 표시
	e = v->adjacencyList; //인접한 정점 리스트
	while(e != NULL) { // 현재 정점의 모든 인접정점에 대해 DFS를 재귀적으로 호출
		if (e->target != NULL && e->target->Visited == NotVisited) {
			//인접데이터가 방문하지 않았으면 재귀호출
				DFS(e->target);
		}
		e = e->next;
	}
}

2. 너비 우선 탐색 (Breadth First Search : BFS)

  • 시작 정점부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법
  • 너비 우선 탐색을 하기 위해서 방문한 정점들을 차례로 저장하고 꺼낼 수 있는 Queue가 필요
  • 정점이 방문될 때마다 큐에 방문한 정점을 삽입하고 더이상 방문할 인접 정점이 없는 경우 큐 앞에서 정점을 꺼내어 그 정점과 인접한 정점들을 차례대로 방문

BFS 알고리즘

  1. 시작 정점을 ‘방문했음’으로 표시 하고 큐에 삽입
  2. 큐로부터 정점을 제거(dequeue)하고 제거한 정점이 이웃하고 있는 인접 정점 중 아직 방문하지 않은 곳들을 ‘방문했음’으로 표시하고 큐에 삽입
  3. 큐가 비게 되면 탐색이 끝난 것이고 큐가 빌때까지 2를 반복
1
2
3
4
5
6
7
8
9
10
//u 방문하지 않은 정점
breadth_first_search(v)
	v를 방문되었다고 표시;
	queue <- v; //큐에 정점 v 삽입
	while (not is empty(queue)) do
		queue에서 정점 w를 삭제
		for 인접정점 탐색 do
		 if (아직 방문되지 않은 정점이 있다면)
		 	then u를 큐에 삽입
		 	 		 방문되었다고 표시

BFS 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void BFS(Vertex* v, LinkedQueue* queue) {
	Edge* e = NULL;
	printf("%d ",v->Data);
	v->Visited = Visited; //방문했음을 표시
	LQ_Enqueue(&queue, LQ_CreateNode(v)); //시작정점에 큐 삽입

	while(!LQ_isEmpty(queue)) {
		Node* popped = LQ_Dequeue(&queue); //큐 제거
		v = popped->Data;
		e = v->adjacencyList;
		while(e != NULL) { //인접한 정점 조사
			v = E->target;
			if (v != NULL && v->Visited == NotVisited) { //미방문 정점만 방문
				printf("%d ", v->data);
				v->Visited = Visited;
				LQ_Enqueue(&queue, LQ_CreateNode(v));
			}
			e = e->next;
		}
	}
}

Posted on Edited on In , Disqus:
Symbols count in article: 2.1k Reading time ≈ 2 mins.

ExpressionTree(수식트리)

하나의 연산자가 두 개의 피 연산자를 취한다는 가정아래 두 가지 규칙을 가짐

  1. 피연산자는 Left Node

  2. 연산자는 root Node or Branch Node

ex) 1 * 2 + (7-8)은 위와 같이 수식트리로 만들 수 있음(후위표기)

알고리즘

  1. 수식을 뒤에서부터 앞쪽으로 읽어옴
  2. 수식에서 제일 마지막에 있는 토큰은 루트노드가 된다.
  3. 후위표기식에서 가장 마지막에 있는 토큰은 항상 연산자이다.
  4. 수식에서 읽어낸 토큰이 연산자인 경우 가지노드가 되고, 이 토큰 다음에 따라오는 두 개의 토큰은 각각 오른쪽과 왼쪽 자식노드가 된다.
  5. 다음 토큰에도 연속해서 연산자인 경우 토큰으로부터 만들어지는 하위 트리가 완성된 이후에 읽어낸 토큰이 왼쪽 자식노드가 된다.
  6. 수식에서 읽어낸 토큰이 숫자이면 Left노드이다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package algorithm;

import java.math.BigDecimal;

public class ExpTree {
	class Node {
		private Object data;
		private Node left;
		private Node right;

		public Node() {
			data = null;
			left = null;
			right = null;
		}

		public Node(Object data) {
			this.data = data;
			left = null;
			right = null;
		}
	}

	public void expressionTree(StringBuilder postFixExp, Node node) {
		int len = postFixExp.length();
		char token = postFixExp.charAt(len - 1);
		postFixExp = postFixExp.deleteCharAt(len - 1);

		switch (token) {
		case '+':
		case '-':
		case '*':
		case '/':
			node = new Node(token);
			// Operator
			expressionTree(postFixExp, node.right);
			expressionTree(postFixExp, node.left);
			break;
		default:
			// Operand
			node = new Node(token);
			break;
		}
	}

	public double evaluate(Node tree) {
		double left = 0;
		double right = 0;
		double result = 0;
		if (tree == null) {
			return 0;
		}
		char data = (char) tree.data;
		System.out.println("char data : " + data);
		switch (data) {
		case '+':
		case '-':
		case '*':
		case '/':
			left = evaluate(tree.left);
			right = evaluate(tree.right);
			if (data == '+') {
				result = left + right;
			} else if (data == '-') {
				result = left - right;
			} else if (data == '*') {
				result = left * right;
			} else if (data == '/') {
				result = new BigDecimal(left).divide(new BigDecimal(right)).doubleValue();
			}
			break;
		default:
			result = new BigDecimal((char) tree.data).doubleValue();
			break;
		}
		return result;
	}

	public void postOrderPrint(Node tree) {
		if (tree == null) {
			return;
		}
		postOrderPrint(tree.left);
		postOrderPrint(tree.right);
		System.out.print(tree.data);

	}

	public void inOrderPrint(Node tree) {
		if (tree == null) {
			return;
		}
		System.out.print("(");
		inOrderPrint(tree.left);
		System.out.print(tree.data);
		inOrderPrint(tree.right);
    System.out.print(")");
	}
}

Posted on In , Disqus:
Symbols count in article: 2.7k Reading time ≈ 2 mins.

Binary Tree(이진트리)

  • 모든 노드가 최대 2개의 자식노드를 가질 수 있는 트리로 루트 노드를 중심으로 둘로 나뉘는 두 개의 서브 트리도 이진트리어야 하고 하위 트리도 이진트리로 구성되어 있다.

  • 최대 노드의 차수는 2이므로 자식 노드가 아예 없거나 하나 또는 둘 뿐이다.

이진트리의 종류

  • 포화 이진 트리(Full Binary Tree) : 모든 레벨별로 노드가 꽉 찬 이진 트리를 말한다.

  • 완전 이진 트리(Complete Binart Tree) : 포화 이진 트리를 이루기 전 단계의 트리로, 잎 노드들이 왼쪽부터 차곡차곡 채워진 이진 트리이며, 모든 노드에 자식 노드가 하나도 없거나 아니면 2개의 자식 노드를 갖는 이진 트리이다.

  • 높이 균형 트리(Height Balanced Tree) : 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 1 이상 차이나지 않는 트리

  • 완전 높이 균형 트리(Completely Height Balanced Tree) : 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같은 트리

이진트리의 순회

  • 트리 내 노드들 사이를 돌아다니는 것

종류

  • 전위순회 (Preorder Traversal)

    1. 방문순서 : root->left->right

    2. root node 부터 시작하여 아래로 내려오며, 왼쪽 하위 트리의 방문이 끝나면, 오른쪽 하위트리를 방문 하는 방식

    3. 순서 : 1->2->4->8->5->3->6->7

    4. ( 1( 2(4(8),5), 3( 6, 4) ))

  • 중위순회 (Inorder Traversal)

    1. 방문순서 : left->root->right

    2. 왼쪽 하위 트리부터 시작해서, 루트를 거쳐, 오른쪽 하위 트리를 방문

    3. 순서 : 8->4->2->5->1->6->3->7

  • 후위순회 (Postorder Traversal)

    1. 방문순서 : left->right->root

    2. 왼쪽 하위 트리부터 시작해서, 오른쪽 하위트리를 거쳐서, 루트를 방문

    3. 순서 : 8->4->5->2->6->7->3->1

이진트리 구현

BinaryTree.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <stdlib.h>

#ifndef BINARYTREE_H
#define BINARYTREE_H

typedef char Element;
typedef struct _Node {
    struct _Node* left;
    struct _Node* right;
    Element data;
}TreeNode;

TreeNode* createNode(Element element);
void inOrderTree(TreeNode* node);
void preOrderTree(TreeNode* node);
void postOrderTree(TreeNode* node);

#endif //BINARYTREE_H

BinaryTree.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//
// Created by Paik Seung Cheol on 2017. 9. 11..
//

#include "BinaryTree.h"


TreeNode* createNode(Element element) {
    TreeNode* newNode = (TreeNode*)malloc((sizeof(TreeNode)));
    newNode->data = element;
    newNode->left = NULL;
    newNode->right = NULL;
}
/**
 * left->root->right;
 * @param node
 */
void inOrderTree(TreeNode* node) {
    if (node == NULL)
        return;
    inOrderTree(node->left);
    printf("%c ");
    inOrderTree(node->right);
}
/**
 * root->left->right;
 * @param node
 */
void preOrderTree(TreeNode* node) {
    if (node == NULL)
        return;
    printf("%c ");
    preOrderTree(node->left);
    preOrderTree(node->right);
}
/**
 * left->right->root;
 * @param node
 */
void postOrderTree(TreeNode* node) {
    if (node == NULL)
        return;
    postOrderTree(node->left);
    inOrderTree(node->right);
    printf("%c ");

}

int main() {
    TreeNode* rootNode = createNode('A');
    TreeNode* BNode = createNode('B');
    TreeNode* CNode = createNode('C');
    TreeNode* DNode = createNode('D');
    TreeNode* ENode = createNode('E');
    TreeNode* FNode = createNode('F');
    TreeNode* GNode = createNode('G');

    rootNode->left = BNode;
    rootNode->right = CNode;
    BNode->left = DNode;
    BNode->right = ENode;
    CNode->left = FNode;
    CNode->right = GNode;

    printf("InOrder : ");
    inOrderTree(rootNode);
    printf("\n");
    printf("PreOrder : ");
    preOrderTree(rootNode);
    printf("\n");
    printf("PostOrder : ");
    postOrderTree(rootNode);
    printf("\n");

}

Posted on In , Disqus:
Symbols count in article: 1.6k Reading time ≈ 1 mins.

Tree(트리)

  • 나무와 유사하게 비선형(데이터가 계층적 구조로 이루어짐) 구조로 이루어져 있는 자료구조

  • 트리는 다른 자료구조보다 자료를 저장하거나 검색하는 방법이 간단하고 메모리를 효율적으로 사용할 수 있다.

구성

  • 트리는 크게 Root(뿌리), Branch(가지),leaf(잎) 세 가지 요소로 이루어짐

  • Root : 트리 구조에서 최상위에 존재하는 노드이다.

  • Branch : Root Node or Sub Tree 와 leaf 사이에 있는 노드를 말한다(자식).

  • Leaf(Terminal Node) : Branch Node의 맨 끝에 달려있는 노드로, 밑으로 또 다른 노드가 연결되어 있지 않은 노드를 말한다(Terminal(단말)노드).

  • Node : 트리의 구성요소에 해당하는 요소를 말한다.

  • Edge : 노드와 노드를 연결하는 연결선이다.

  • Sub-Tree : 큰 트리(전체)에 속하는 작은 트리

  • Level(Depth) : 루트노드에서 해당 노드까지 경로의 길이로 트리에서 각 층별로 숫자를 매김

  • Height : 트리의 최고 레벨 (3)

  • Length : 출발 노드에서 목적 노드까지 거쳐야하는 노드의 개수

  • Degree(차수) : 해당 노드의 자식노드 개수를 말한다.

트리의 표현

  1. 중첩된 괄호(Nested Parenthesis) : 같은 레벨의 노드를 괄호로 묶어 표현

  2. 중첩된 집합(Nested Set) : 트리를 집합관계로 표현

  3. 들여쓰기(Indentation) : 들여쓰기로 표현된 트리

노드 표현

부모와 자식, 형제노드를 서로 연결짓는 방법

  1. N-Link(N-링크 표현법) : 노드의 차수가 N개라면 노드가 N개의 링크를 가지고 있어서 이 링크들이 각각 자식 노드를 가리키도록 노드를 구성하는 방법(단점, 차수가 노드마다 달라지는 트리에서는 적용하기 어렵고 복잡한 트리를 만들게됨)

  2. Left Child-Right Sibling(왼쪽 자식, 오른쪽 형제 표현법) : N개의 차수를 가진 노드의 표현이 2개의 포인터(링크), 왼쪽-오른쪽 형제만 가진다.

구현

  • 노드의 선언
1
2
3
4
5
typedef struct _Node {
    int data;
    struct _Node *left;
    struct _Node *right;
}TreeNode;
  • 노드의 생성
1
2
3
4
5
6
7
TreeNode* createNode(int data) {
  TreeNode newNode = (TreeNode*)malloc(sizeof(TreeNode));
  newNode->left = NULL;
  newNode->right = NULL;
  newNode->data = data;
  return newNode;
}
  • 트리 연결
1
2
3
4
5
6
7
8
9
10
11
void addChildNode(TreeNode* parent, TreeNode* child) {
  if (parent->left == NULL) {
    parent->left = child;
  } else {
    TreeNode* tmpNode = parent->left;
    while(tmpNode->right != null) {
      tmpNode = tmpNode->right;
    }
    tmpNode->right = child;
  }
}
  • 트리 출력
1
2
3
4
5
6
7
8
9
10
11
12
13
void printTree(TreeNode* node, int depth) {
  int i = 0;
  for (int i =0; i<depth; i++) {
    printf(" ");
  }
  printf("%d\n", node->data);
  if (node->left != NULL) {
    printTree(node->left, depth+1);
  }
  if (node->right != NULL) {
    printTree(node->right, depth+1);
  }
}

Posted on Edited on In , Disqus:
Symbols count in article: 1k Reading time ≈ 1 mins.

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 “백설 공주와 일곱 난쟁이”의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

예제 입력

1
2
3
4
5
6
7
8
9
20
7
23
19
10
15
25
8
13

예제 출력

1
2
3
4
5
6
7
7
8
10
13
19
20
23

풀이

7 난쟁이 키의 합이 100이므로

9명의 난쟁이 합을 구하여 2명의 키 값을 뺀 값이 100이면 두 난쟁이를 -1로 처리

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int[] a = new int[9];
        int sum = 0;
        for (int i = 0; i < 9; i++) {
            a[i] = scan.nextInt();
            sum += a[i];
        }
        int[] result = dwarfOf7(a, sum);
        if (result == null) {
            return;
        }
        Arrays.sort(result);
        for (int i = 2 ;i <result.length; i++) {
            System.out.println(result[i]);

        }
    }

    public static int[] dwarfOf7(int a[], int sum) {
        for (int i =0 ; i < 9; i++) {
            for (int j = i + 1; j < 9; j++) {
                if (sum - (a[i] + a[j]) == 100) {
                    a[i] = a[j] = -1;
                    return a;
                }
            }
        }
        return null;
    }
}

Posted on Edited on In , Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins.

연속합

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

1
2
10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1

1
33

예제 입력 2

1
2
10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2

1
14

예제 입력 3

1
2
5
-1 -2 -3 -4 -5

예제 출력 3

1
-1

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(in.readLine());
        
        String[] split = in.readLine().split(" ");
        int[] a = new int[t];
        for (int i = 0; i < split.length; i++) {
            a[i] = Integer.parseInt(split[i]);
        }
        out.write("" + continuitySum(a));
        out.flush();
        in.close();
        out.close();
    }

    public static long continuitySum(int[] a) {
        long[] dp = new long[a.length];
        long result = dp[0] = a[0];
        for (int i = 1; i < a.length; i++) {
            dp[i] = Math.max(dp[i-1] + a[i], a[i]);
            if (result < dp[i]) {
                result = dp[i];
            }
        }
        return result;
    }
}

Posted on In , Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

1,2,3 더하기 5

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

  • 1+2+1
  • 1+3
  • 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

예제 입력 1

1
2
3
4
3
4
7
10

예제 출력 1

1
2
3
3
9
27

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    private static final long MOD = 1000000009L;
    private static final int LENGTH = 100000;
    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(in.readLine());
        long[][] dp = plus123_5();
        while (t-- != 0) {
            int n = Integer.parseInt(in.readLine());
            out.write("" + (dp[n][1] + dp[n][2] + dp[n][3]) % MOD);
            out.write("\n");
            out.flush();
        }
        in.close();
        out.close();
    }

    public static long[][] plus123_5() {
        long[][] dp = new long[LENGTH + 1][4];
        for (int i = 1; i <= LENGTH; i++) {
            dp[i][1] = (i == 1) ? 1 : (dp[i-1][2] + dp[i-1][3]) % MOD;

            if (i - 2 >= 0) {
                dp[i][2] = (i == 2) ? 1 : (dp[i-2][1] + dp[i-2][3]) % MOD;
            }
            if (i - 3 >= 0) {
                dp[i][3] = (i == 3) ? 1 : (dp[i-3][1] + dp[i-3][2]) % MOD;
            }
        }
        return dp;
    }
}

Posted on In , Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

쉬운 계단 수

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

1
1

예제 출력 1

1
9

예제 입력 2

1
2

예제 출력 2

1
17

풀이

  • 인접 한 자리의 차이 1 이 나는 걸 계단 수라고 함
  • 45656
  • 길이가 N인 계단 수를 개수를 구하는 문제

Dp[N][L]의 길이가 N인 계단 수

마지막 수 L 는 L + 1 or L - 1

즉 DP[i][j] 는 길이가 i이인 마지막 수가 j인 계단수의 개수

  • Dp[i][j] = Dp[i-1][j-1] + Dp[i-1][j+1]

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        out.write("" + easyStair(n));
        out.write("\n");
        out.flush();
        out.close();
        in.close();
    }

    public static long easyStair(int n) {
        long mod = 1000000000L;
        long[][] dp = new long[n + 1][10];
        for (int i = 1; i <= 9; i++) {
            dp[1][i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
                dp[i][j] = 0;
                if (j - 1 >= 0) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
                if (j + 1 <= 9) {
                    dp[i][j] += dp[i - 1][j + 1];
                }
                dp[i][j] %= mod;
            }
        }
        long solv = 0;
        for (int i = 0; i <=9; i++) {
            solv += dp[n][i];
        }
        return solv %= mod;
    }
}

Posted on In , Disqus:
Symbols count in article: 2.1k Reading time ≈ 2 mins.

카드 구매하기

문제

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

전설카드
레드카드
오렌지카드
퍼플카드
블루카드
청록카드
그린카드
그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, … 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

예제 입력 1

1
2
4
1 5 6 7

예제 출력 1

1
10

예제 입력 2

1
2
5
10 9 8 7 6

예제 출력 2

1
50

예제 입력 3

1
2
10
1 1 2 3 5 8 13 21 34 55

예제 출력 3

1
55

예제 입력 4

1
2
10
5 10 11 12 13 30 35 40 45 47

예제 출력 4

1
50

예제 입력 5

1
2
4
5 2 8 10

예제 출력 5

1
20

예제 입력 6

1
2
4
3 5 15 16

예제 출력 6

1
18

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        String[] ar = in.readLine().split(" ");
        int[] p = new int[n+1];
        for (int i = 1; i<=n; i++) {
            p[i] = Integer.parseInt(ar[i-1]);
        }
        out.write("" + cardBuy(p, n));
        out.write("\n");
        out.flush();
        out.close();
        in.close();
    }

    public static int cardBuy(int[] p, int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] = Math.max(dp[i], dp[i - j] + p[j]);
            }
        }
        return dp[n];
    }
    // 카드구매하기 2
    //https://www.acmicpc.net/problem/16194
    public static int cardBuy2(int[] p, int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = -1;
            for (int j = 1; j <= i; j++) {
                if (dp[i] == -1 || dp[i] > dp[i-j] + p[j]) {
                    dp[i] = dp[i-j] + p[j];
                }
            }
        }
        return dp[n];
    }
}

Posted on Edited on In , Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

1,2,3 더하기

문제

정수 4를 1,2,3의 조합으로 나타내는 방법은 총 7가지가 있다.

  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1

정수 N이 주어졌을 때, N을, 1,2,3합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫쨰 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1,2,3의 합으로 나타내는 방법의 수를 출력한다.

예제입력

1
2
3
4
3  
4  
7  
10

예제출력

1
2
3
7  
44  
274

점화식

1의 조합일 때

N-1 + 1 = N

2의 조합일 때

N-2 + 2 = N

3의 조합일 때

N-3 + 3 = N

D[N] = D[n-1] + D[n-2] + D[n-3]

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(in.readLine());
        while(t-- != 0) {
            int n = Integer.parseInt(in.readLine());
            out.write("" + plus123(n));
            out.write("\n");
        }
        out.flush();
        out.close();
        in.close();
    }
    public static int plus123(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= 3 && i - j >= 0; j++) {
                    dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
}