나만의 깍두기판

1. 그래프 개념과 ADT1) 기본 개념(1) 정의와 용어- Graph 자료 구조: 상하위 개념이 없는 노드와 노드들을 잇는 엣지로 구성되어 있는 자료구조이다.- Graph에서는 모든 노드들이 관계를 가지고 있을 필요가 없어 비교적 자유로운 구조이다. (2) 특징- Graph는 비선형(non-linear)적이며, network model이라고도 불린다.- 노드는 방향성이 있기도 하고 없기도 해서 각각을 '무방향성 그래프', '방향성 그래프'라고 나뉘어 부른다.- 실생활에서는 지도나 지하철 노선도, 페이스북 친구 추천이나 e-commerce 추천 알고리즘이 있다.   2) 그래프 추상 데이터 타입(1) 그래프의 정의 (2) 무방향 그래프: 간선을 표현하는 두 정점의 쌍에 순서가 없는 그래프(3) 방향 그래..

1. 이진 탐색 트리1) Binary Search by Array(1) ConceptQ. 서로 다른 n개의 정렬된 수가 list에 저장되어 있을 때, 특정한 값을 찾아라A. Description of the binary search problem   2) Binary Search Trees(1) 정의: Binary Search Tree는 탐색에 목적을 둔 binary tree이다. 본 tree는 empty일 수 있고, empty가 아닌 경우는 다음의 성질을 만족한다.1️⃣모든 element는 서로 다른 key를 갖는다.2️⃣Non-empty left subtree에 있는 key들은 root의 key보다 작은 값을 갖는다.3️⃣Non-empty right subtree에 있는 key들은 root의 key보..

1. 트리 항해1) Binary Tree Traversal(1) 정의- Tree의 각 node를 한 번씩 방문하는 알고리즘- 각 node와 그 node의 subtree들을 동등하게 취급하면 6개의 traversal 조합이 있다.(L: Left로 움직임, V: 노드를 visiting, R: Right로 움직임)1️⃣LVR 2️⃣LRV 3️⃣VLR 4️⃣VRL 5️⃣RVL 6️⃣RLV - Traverse left before right를 도입하면, 3개의 조합이 남는다.  (2) In-order Traversals(중위 순회)- 방법: 왼쪽 branch를 모두 방문한 후, node를 방문하고, 오른쪽 branch를 방문함  (3) Pre-order Traversals(전위 순회)- 방법: node를 방문하고..

1. 트리 개념1) 정의: 다음의 성질을 가진 하나 이상의 node로 이루어진 finite set이다.Root라고 불리우는 특정 node가 있다.나머지 node들은 n개(n >= 0)의 disjoint set인 T1, T2, ... Tn으로 분할된다. 이때 각 set는 Tree이다.T1, T2, ... Tn를 root의 subtree라고 부른다.2) 트리는 root를 가진 acyclic graph(비순환 그래프)이고, 계층적 구조를 가진다.    3) Sample Tree로 알아보는 개념 (1) Node의 degree(자식 수) : node의 subtree 수를 말한다.A, D는 3B, E는 2C, H는 1K, L, F, G, M, I, J는 0(2) Tree의 degree: tree에 있는 node의 ..

1. 큐의 연결 표현1) Queue의 연결 표현(1) 연결된 큐(linked queue): 연결 리스트로 구현된 큐- front 포인터는 삭제와 관련되며 rear 포인터는 삽입과 관련됨- front는 연결 리스트의 맨 앞에 있는 요소를 가리키며, rear 포인터는 맨 뒤에 있는 요소를 가리킴- 큐에 요소(Element)가 없는 경우(Empty)에는 front와 rear는 NULL (2) 연결된 큐에서의 삽입과 삭제   2) 리스트를 이용한 Queue의 구현 3) 큐를 1연결 리스트로 구현한 C 프로그램   2. 우선 순위 큐와 덱1) 우선순위 Queue(1) 정의원소에 부여된 우선순위(priority)에 따라 우선순위가 가장 높은 원소부터 삭제하는 자료 구조Stack과 Queue도 우선순위 큐의 일종- ..

1. 큐의 개념과 ADT1) Queue Concept 정의: 한쪽 끝, rear에서는 삽입(enqueue)만, 또 다른 끝, front에서는 삭제(dequeue)만 하도록 제한되어 있는 유한 순서 리스트(finite ordered list)선입 선출(First In, First Out : FIFO) 리스트- 제일 먼저 삽입된 원소가 제일 먼저 삭제될(=서비스를 받을) 원소가 됨선착순 서버(First Come, First Serve : FCFS) 시스템- 서비스를 받기 위한 대기행렬로 볼 수 있음 Queue의 응용 사례- 운영 체제: 작업 큐를 통한 제출 순서에 따른 작업 스케줄(job schedule)- 서비스를 기다리는 작업들의 대기 상태를 나타내는 상황에 적합- 많은 알고리즘에서 Queue 개념을 사..

1. 단순 연결 리스트의 구체적 구현(C Implementation)1) 리스트 생성 알고리즘// 점 표기식만으로 리스트를 작성한 경우L   2) 원소를 첫 번째 노드로 삽입// 리스트 L의 첫 번째 노드로 data 값이 x인 노드를 삽입addFirstNode(L, x) // 리스트 L의 첫 번째 노드로 원소 x를 삽입 newNode    3) 원소 값이 x인 노드를 p가 가리키는 노드 다음에 삽입insertNode(L, p, x) // 리스트 L에서, p 노드 다음에 원소 x를 삽입 // p가 null인 경우는, 현재 pointing하는 노드가 없는 경우임 !!!!!!! newNode   4) 리스트 L의 마지막에 노드 x를 삽입하는 경우 (개념)(1) while(p.lin..

[ 2차시 ]정답: 구현    정답: 4번 설계해설: 설계 단계의 핵심 단어는 '알고리즘'이다.   정답: 2번 구현 레벨해설: Abstract(추상화)는 구현과 거리가 멀다   정담: 2번 ADL 변환기  정답: 3번해설: 특정 Programming 언어로 작성되어 있지 않다. 이건 목적이다.   정답: 2번해설: x...*3*2*1*1은 팩토리얼 정의에 맞지 않기 때문에 x  정답: 4번 수행 속도해설: 시스템 스택에 activation record가 쌓임 = 오버 헤드  정답: 3해설: 순환함수는 계속 시스템 스택에 activation record가 쌓인다. (오버 헤드)  정답: 4번해설: 프로그램의 모든 문장에 항상 step count 카운팅 문장을 넣는 것은 번거롭고 어렵다.  정답: 1번해설..