대학강의정리/22.1 it개론8 제6장. 자료구조 1. 중위 표기(INFIX)를 후위 표기(POSTFIX)로 변환, 트리 생성 후 전위 표기 구하기 1. 중위 표기(INFIX)를 후위 표기(POSTFIX)로 변환 중위 표기를 후위 표기로 변환하는 것을 사람 눈으로 볼 수 있게 표현할 때에는 세가지 과정을 거칩니다. 첫째, 연산자간 우선순위를 가시적으로 보이도록 괄호로 묶는다. 둘째, 왼쪽 괄호를 만나면 무시하고 다음 문자를 읽고 연산자를 만나면 연산자를 스택에 push(저장)한다. 셋째, 오른쪽 괄호를 만날때마다 스택에 저장된 연산자를 pop 및 출력한다. (1) 중위 표기 'A+B*C'를 후위 표기로 변환 첫째, (A+(B*C)) 둘째, (A+(B*C)) A stack A stack + AB stack + AB stack * + AB stack * + ABC stack * + 셋째, ABC* stack + ABC*+ stack (2) 중위 표기 '.. 2022. 5. 28. 제6장. 자료구조 트리 1. 트리 1) 트리는 계층구조를 표현할때 사용하는 자료구조이다. 2) 노드와, 노드와 노드를 연결한 링크(link)로 구성되어 있다. 3) 가장 위에 있는 노드를 root node라고 하고 가장 아래에 있는 노드를 단말노드(terminal node) 또는 leaf node라고 한다. 4) parent node 부모 노드는 어느 노드 위에 있는 노드를, child node 자식 노드는 어느 노드 아래의 노드를 말하고 '학과 노드의 부모 노드는 대학노드이다' 이런 식으로 말한다. 5) sibling node 형제 노드는 같은 부모 노드를 가진 노드들을 말한다. 6) subtree서브 트리는 트리 아래에 있는 트리를 말한다. 7) level 레벨은 루트 노드에서 임의의 노드까지 방문한 노드의 수를 말한다. .. 2022. 5. 28. 제6장. 자료구조 그래프 0. 주요 용어와 표현 node 정점 : 그래프에서 점 edge 간선 : node와 node를 연결하는 선 degree 차수 : 노드하나를 기준으로 node에 접한 edge의 수 그래프 G 표현 G = (V, E) 인접(adjacent) : G1에서 B, C, D는 A에 인접 0.1 그래프의 종류 무방향 그래프: 방향성이 없는 간선으로 이루어진 그래프 V(G1)={A, B, C, D} E(G1)={(A, B), (A, C), (A, D), (B, C)} 혹은 E(G1)={(B, A), (C, A), (D, A), (C, B)} 방향 그래프: 방향성이 있는 간선으로 이루어진 그래프 V(G2)={A, B, C, D} E(G1)={(A, C), (A, D), (B, A), (B, C), (C, A)} 방향.. 2022. 5. 27. 제6장. 자료구조 stack 과que 스택과 큐는 각각 배열과 linked list 로 구현할 수 있다. 1. 스택 1) 데이터의 삽입과 삭제가 한쪽 방향에서만 일어나는 구조를 스택이라고 한다. 2) 스택은 가장 나중에 삽입된 데이터가 가장 먼저 나오는 LIFO 후입선출의 자료구조이다. 1.1 배열로 구현한 스택 삽입) Int stack_size = 5; 스택이 가득찼을 때 top은 스택의 크기와 같다 If (top이 스택 크기와 같은가) then 스택이 가득 차서 데이터를 삽입하지 못함 else 데이터를 스택의 top 위치에 삽입 top을 1 증가 삭제) If (top이 0인가) then 스택이 비어서 데이터를 삭제하지 못함 else top을 1 감소 데이터를 담을 변수에 top 위치의 값을 복사 1.2 연결리스트로 구현한 스택 : 리스트.. 2022. 5. 25. 제6장. 자료구조 arrary list 과 linked list 이전 강의(5장. 프로그래밍 언어)에서 배운 것 프로그래밍 언어의 종류 변수란 자료형(datatype)이란 연산자의 종류 if for 등의 제어구조 함수 저번 시간에는 리스트, 튜플, 딕셔너리등 파이썬만이 가지고 있는 독특한 자료구조에 대해 배웠지만 이번 시간에는 일반적인 자료구조와 알고리즘을 간단히 소개할 것이다. 내용 01. 자료구조의 개요 02. 배열과 연결 리스트 03. 스택과 큐 04. 그래프 05. 트리 학습목표 • 자료구조의 의미를 이해하고 종류를 알아본다. • 배열과 연결 리스트의 구조를 이해하고 데이터의 삽입과 삭제 과정을 알아본다. • 스택과 큐의 구조를 이해하고 데이터의 삽입과 삭제 과정을 알아본다. • 그래프의 구조를 이해하고 깊이 우선 방법과 너비 우선 방법으로 탐색한다. • 트리.. 2022. 5. 24. 선택 정렬, 삽입 정렬, 버블 정렬 1. 선택정렬 선택정렬은 가장 왼쪽값을 min으로 저장하고 min의 다음에 있는 모든 값과 비교합니다. 왼쪽부터 정렬됩니다. --> inner loop 1 2 3 4 5 1 2 3 4 5 . . . 1과 2 비교 2와 3 비교 1과 3 비교 2와 4 비교 1과 4 비교 2와 5 비교 1과 5 비교 outer loop 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 정렬된(최종위치가 확정된) 값들은 노란색으로 표시했다. 2. 버블정렬 버블 정렬은 두 값을 비교해서 큰 숫자를 오른쪽으로 보냅니다. 오른쪽부터 정렬됩니다. inner loop 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 outer loop 1 2 3 4 5 1 2 3 4 5 1.. 2022. 5. 10. 이전 1 2 다음
