Yeong Jin

노드의 차수: 어떤 노드가 가지고 있는 자식노드의 개수트리의 차수: 트리가 가지고 있는 노드의 차수 중 가장 큰 값루트의 레벨 : 1트리의 높이: 트리가 가진 최대 레벨 쓰레드트리 스레드라는 포인터를 갖는 이진트리 스레드 : 정해진 순회 방법에 따른 방문 순서를 유지하는 포인터오른쪽스레드 : 정해진 순회 순서에 따른 그 노드의 후속노드를 가리킴왼쪽스레드 : 그 노드의 선행 노드를 가리킴  합병정렬: 차례로 정렬한 데이터 리스트 k개를 완전한 순서를 유지하는 하나의 리스트로 만드는 과정선택트리 : 합병정렬에 사용하는 특수한트리  히프(Heap) 조건 - 부모노드가 자식노드보다 크거나(최대힙)  작다(최소힙)   -  (같아도 된다고 한다)- 완전이진트리이다.  즉 왼쪽부터 노드가 차례대로 채워져야함 히프의..

G(V,E)V:정점(vertex)E :간선(edge)  무방향그래프의 정점쌍 {v1,v2}     - 순서가 상관이 없음. 방향그래프의 간선 순서쌍 (v1,v2)  - 순서가 있음 v1 ->v2    경로 길이 : 경로에 있는 간선의 수단순 경로 : 경로상에 있는 모든 정점이 서로 다른 경로기본 경로: 경로상에 있는 모든 간선이 서로 다른 경로 ( 자기자신으로 되돌아오는것도 경로로 봄) 사이클: 출발점과 도착점이 동일한 단순경로 무방향그래프 차수: 정점에 연결된간선들의 개수방향그래프 차수: 진출차수와 진입차수의 합 루프: 간선의 시작점과 끝점이 같은 정점의 길이가 1인 경로 - 사이클에 포함이 됨DAG: 방향이있는 무사이클그 래프  그래프 탐색  깊이우선탐색DFS-스택을 사용하여 가장 최근에 선택의 지점..

m원 탐색트리    - 자식노드를 m개 까지 가질 수 있는 트리  - 같은 수의 노드를 갖는 이진탐색트리보다 낮은 높이의  m원 트리  - 하나의 노드에 여러개의 키값을 가져서 자식노드를 여러개 갖음 (3원탐색트리는 키값 2개 필요)왼쪽 서브트리는 86보다 작은 애들중간에는 86보다크고 90보다 작은애들오른쪽서브트리는 90보다 큰 애들로 만든 서브트리m원 트리는 서븥트리의 균형은 고려하지않음  B 트리m원탐색트리를 개선한 B트리는 인덱스 구조를 구현하는데 가장 일반적으로 활용함  . 전체적으로 균형을 유지-루트와 잎노드를 제외한 트리의 각 노드는 최소 [m/2] 개의 서브트리를 갖는다.- 트리의 루트는 최소한 2개의 서브트리를 갖는다- 트리의 모든 잎 노드는 같은 레벨에 있다.B* 트리 - 노드의 2/3..

선택트리 승자트리  - 각 노드가 두 자식노드의 작은값을 갖는 완전이진트리- 작은 값이 승자가 되어 올라가는 토너먼트와 유사- 루트값이 트리에서 가장 작은 값이 됨 11이 삭제가되면 24가 22랑 겨뤄서 작은값이 올라오면 된다.   패자트리-루트노드위에 최상위 0번 노드를 놓음 - 최종승자를 저장함-잎 노드들이 각 리스트의 head를 가리킴-트리의 각 내부노드에는 승자가 아닌 패자를 저장함-패자를 부모노드에 저장(큰값) 승자는 부모의 부모노드로 올라가서 다시 경쟁)-루트에는 마지막 패자(두번째 작은 값)를 저장하고 최종승자(가장 작은값)를 0번 노드에 저장 두개 비교해서 작은애가 승자니까 큰값은 적고 작은애를 올려보냄 즉  한번 더올라감(부모의 부모로) 0번 노드에 최소값이 있으므로 이 값을 제거하여 전..

스레드: 순회 방법에 따른 방문순서를 유지하는 포인터 스레드 트리 구현방법(1) :포인터 필드의 추가 스레드를 저장하는 포인터를 추가하는것. 오른쪽 스레드: 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킴왼쪽스레드 : 그 노드의 선행노드를 가리킴                                                                                처음에 어떤 순서로 시작하는지 기억한다.처음 3번의 순회중 부모노드가 언제 순회되는지를 보면된다.  스레드의 구현방법(2) : 빈 포인터 활용 기존의 이진트리의 노드 구조를 그대로 활용하면서 노드에 있는 사용하지않는 포인터(빈포인터) 를 활용하는 방법어떤 노드 X에 대해 오른쪽 포인터가 NULL이면 이 포인터를 노드..

서브트리: 부모노드를 삭제하면 생기는 트리들잎 노드: 트리의 맨 바닥에 있으면서 자신의 서브트리,자식을 갖지 않는 노드 진입차수: 나한테 들어온 길루트노드는 진입차수 0루트를 제외한 모든 노드의 진입차수는 1진출차수: 나가는 길잎노드는 진출차수가 0 노드의 레벨: 루트로부터 그 노드까지 이어진 경로의 길루트노드는 레벨0 깊이는 레벨+1깊이: 트리의 레벨에서 가장 큰 값에 1을 더한 것이진트리 : 모든 노드의 차수가 2이하인 트리(진출 차수가2 이하) Q.모든노드의 진입차수는 1이다 ?  => x  루트노드는 0   가득찬 이진트리(포화이진트리) : 이진트리의 각 레벨에서 허용되는 최대 개수 노드를 가지는 트리  완전이진트리 :높이가 k인 이진트리가 0 레벨부터 k-2 까지 다 채우고 마지막 k-1레벨에서..

리스트와 배열의 차이리스트 : 일정한 순서의 나열 . 어떤 정의에 의해서 결정된 논리적인 순서의 나열 배열: 원소의 메모리 공간의 물리적인 위치를 순서적으로 결정하는 특징 . 배열의 순서는 메모리 공간에서 저장되는 원소값의 물리적 순서 다음 중 포인터로 구현된 리스트에 대한 설명으로 틀린 것은?1 ‘일정한 순서’의 나열2어떤 정의에 의해서 결정된 ‘논리적인 순서’의 나열3리스트를 포인터로 구현할 경우에는 배열에 비해서 추가적인 메모리 공간이 필요하다. 4메모리 공간(주기억 장치, DDR)에서의 물리적인 위치가 논리적 위치와 일치한다.  typedef struct ListNode {   // 단순 연결 리스트의 노드 구조 정의     int data; struct ListNode* link;  // [가]..

중위표기법 A+B전위 표기법 +AB후위표기법 AB+ Q2스택의 응용 분야가 아닌 것은 ?1시스템 스택2서브루틴 호출3작업 스케쥴링4후위 수식의 계산 스택의 응용 변수에 대한 메모리할당과 수집을 위한 시스템스택서브루틴호출관리를 위한 스택연산자들간의 우선순위에 의해 계산 순서가 결정되는 수식계산인터럽트의 처리와 되돌아갈 명령 수행 지점을 저장하기 위한 스택컴파일러, 순환호출  스택의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있습니다.  중위표기법을 후위표기법으로 바꿀때 스택의 상태ex)A+B*C  => ABC*+ 왼쪽부터 읽어가는데, 알파벳의 경우에는 그냥 출력.  연산자의경우에는 아래 규칙에 따라 ..

추상화 : 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것  정보 : 어떤 상황에서 적절한 의사결정을 할수 있게 하는 지식으로서 자료의 유효한 해설이나 자료 상호간의 관계를 표현하는 내용. 자료의 2차처리 결과물 자료의 추상화: 다양한 대상을 컴퓨터에서 저장하고 처리하기 위해 그 대상들의 의미와 구조에 대해서 공통의 특징을 뽑아 정의한 것 자료구조 : 추상화를 통해 알고리즘에서 사용할 자료의 논리적 관계를 구조화한것 Q2 ‘정보’는 현실 세계에서 관찰이나 측정을 통해서 수집된 값(value)이나 사실(fact)이다. X 자료이다. Q3.자료의 추상화란 컴퓨터에 의해 수행되기 위해 필요한 명령어들의 유한 집합이 사람의 머릿속에 추상화되어 존재하는 것이다. X 알고리즘이다. Q4알고리즘을 실..