본문 바로가기

분류 전체보기112

[C] Prim Alogrithm 1. 신장트리 (Spanning Tree): n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 이루어진 트리 : 사이클 발생하면 안됨 사이클 없이 모든 정점 포함하는 트리 1-1. 최소 비용 신장 트리 (MST, Minimum cost Spanning Tree): 무방향 가중치 그래프에서 신장 트리 구성하는 간선들의 가중치 합이 최소인 신장트리 ex) Kruskal Algorithm, Prim Algorithm 2. Prim Algorithm: 우선순위 큐를 이용하는 알고리즘 : 간선을 정렬하지않고 하나의 정점에서 트리를 확장해나가는 방법 2-1. 동작방식그래프 G에서 시작 정점 선택 ( 대부분의 경우 1로 설정)선택한 정점에 부속된 모든 간선 중 가장 낮은 간선 연결.. 2023. 10. 6.
[Python]최단 경로 알고리즘 : Dijkstra Algorithm, Floyd Washall 1. 다익스트라 알고리즘 1-1. 순차탐색을 이용한 다익스트라 INF = int(1e9) def get_min_distance(res, visited): min_val = INF idx=0 for i in range(1,len(res)): if(visited[i]==0 and min_val>res[i]): min_val = res[i] idx = i return idx def dijkstra(graph, E,V, start, res): visited = [0]*(V+1) #초기화 res[start]=0 for j in range(1,V+1): for i in range(1,V+1): now= get_min_distance(res,visited) visited[now]=1 for now_to, distan.. 2023. 9. 26.
[C]수식 트리 - Evaluate Tree 1. 수식트리 : 산술식을 트리형태로 표현 : 컴파일러가 수식을 처리하는 방식 : 단말노드 => 피연산자, 비단말노드 => 연산자 2. 수식 트리 계산 중위 표기법 수식 -> 후위 표기법 수식 -> 수식 트리 -> 수식 트리 계산 중위 표기법 수식 -> 후위 표기법 수식 : 스택 이용 후위 표기법 수식 -> 수식 트리 : 스택 이용 수식 트리 -> 수식 트리 계산 : 후위순회 이용 2-1. 후위 표기법 수식 : 스택 이용 https://growingupis.tistory.com/32?category=1186559 스택 응용(수식 계산) 1. 수식표기법 (1) 중위표기법(infix notation) : 연산자를 피연산자의 가운데 표기하는 방법 => 우리가 사용하는 방식 ex) A+B (2) 후위표기법(po.. 2023. 9. 22.
[C]트리 레벨 순회 - Level Order Traverse : 각 노드를 레벨 순으로 탐색하는 방법으로 큐 (너비우선탐색, BFS) 이용하여 구현 #define _CRT_SEUCRE_NO_WARNINGS #include #include #include #include #define SIZE 128 typedef struct _TREENODE_ { char data; struct _TREENODE_* left; struct _TREENODE_* right; }TREENODE; void deleteTree(TREENODE* node) { if (node == NULL) { return; } else { deleteTree(node->left); deleteTree(node->right); free(node); node = NULL; } } TREENODE* make.. 2023. 9. 22.
[CH3] 명령어 3-1. 소스코드와 명령어 : 모든 소스 코드는 컴퓨터 내부에서 명령어로 변환 (1) 고급언어와 저급언어 고급 언어 : 우리가 이해할 수 있는 언어 저급 언어 : 컴퓨터가 이해할 수 있는 언어 => 우리가 프로그래밍 언어(고급언어)로 작성한 코드가 실행되려면 반드시 명령어(저급언어)로 변환 1) 저급언어 기계어 : 명령어 어셈블리어 : 0과 1로 이루어진 명령어를 읽기 편한 형태로 변환 ex) 기계어(명령어) ----------------> 어셈블리어 0101 0101 -----------------> push rbp 0101 1101 -----------------> pop rbp 1100 0011 -----------------> ret 2) 컴파일 언어와 인터프리터 언어 : 고급언어(컴파일/인터프리.. 2023. 9. 20.
[CH2] 데이터 2-1. 0과 1로 숫자 표현하는 방법 (1) 단위 : 1bit -> 1byte -> 1KB (1000byte) -> 1MB(1000KB) -> 1GB(1000MB) -> 1TB(1000GB) -> 1PB(1000TB) cf> word : CPU가 한 번에 처리할 수 있는 데이터 크기 => 만약 CPU가 한 번에 16bit 처리 : 1word = 16bit 2-2. 0과 1로 문자 표현하는 방법 문자 집합 인코딩 디코딩 (1) 문자 집합 : 컴퓨터가 인식하고 표현할 수 있는 문자의 모음 ( 문자 집합에 속한 문자만 컴퓨터가 이해할 수 있음) => 이때 문자집합에 속해있는 문자라고 컴퓨터가 그대로 이해할 수 있지않음 => 문자를 0과 1로 변환하는 인코딩 과정 필요 => 이때 0과 1로 이루어진 문자 코드.. 2023. 9. 20.

티스토리툴바