데이터 처리중입니다. 잠시만 기다려 주세요... AI_Developer

01. 인접행렬 adj_mat[][]에서 어떤 정점 v의 진출 차수를 알고 싶으면 어떻게 하면 되는가?→ (1) 인접 행렬의 v번째 행의 값들을 전부 더한다. 02. 인접행렬 {0,1,0,0}, {1,0,1,1}, {0,1,0,0}, {0,1,0,0} 이라면 여기에 대응되는 입접 리스트를 그려라→ 0->11->0->2->32->13->1 03. 정점의 개수를 n, 간선의 개수를e라고 할때, 인접 행렬에서 특정 정점의 차수를 계산하는 연산의 시간 복잡도는?→ (2) O(n) 04. 정점의 개수를 n, 간선의 개수가 e인 그래프를 인접 리스트로 표현하였을 경우, 인접 리슽트 상의 총 노드의  개수는?→ 방향 그래프라면 (1) e개     무방향 그래프라면 (4) 2e개 05. 다음 중 큐를 사용하는 알고리즘..

10.5 깊이 우선탐색그래프의 시작 정점에서 출발하여 시작 정점 v를 방문 하였다고 표시한다. → 이어서 v에 인접한 정점들 중에서 아직 방문하지 않은 정점 u를 선택한다. 만약, 그런 정점이 없다면 탐색은 종료만약 아직 방문하지 않은 정점 u가 있다면 u를 시작 정점으로 하여 깊이 우선 탐색을 다시 시작이 탐색이 끝나게 되면 다시 v에 인접한 정점들 중에서 아직 방문이 안된 정점을 찾는다. → 만약, 없다면 종료 / 있다면 다시 그 정점을 시작 정점으로 하여 깊이 우선탐색을 다시 시작깊이 우선 탐색도 자기 자신을 다시 호출하는 순환 알고리즘 형태를 가지고 있음깊이 우선탐색을 구현하는데는 2가지 방법이 있다. 1. 순환호출을 이용2. 명시적인 스텍을 사용하여 인접한 정점들을 스택에 저장하였다가 다시 꺼내..

그래프의 용어와 개념그래프 : 객체 사이의 연결관계를 표현할 수 있는 자료구조 (정점과 간선들의 유한 집합)정점 (Vertex,노드): 각 노드간선 (Edge, 링크): 정점들 간의 관계인접정점: 간선에 의해 직접 연결된 정점차수: 무방향 그래프에서 정점에 인접한 정점의 수경로: 정점의 나열 (정점 간에는 반드시 간선이 존재해야 함)단순경로: 반복되는 간선이 없는 경로싸이클: 단순 경로에서 시작정점과 종료정점이 같은 경로그래프의 종류무방향 그래프: 양방향으로 갈 수 있음 (A,B)방향 그래프: 간선에 방향성이 존재 네트워크 (가중치 그래프): 간선에 가중치가 할당된 그래프부분 그래프: 정점의 일부와 간선의 일부로 이루어진 그래프연결 그래프: 모든 정점 쌍에 대하여 항상 경로가 존재하는 뱡향 그래프 ( 트..

8.1 트리의 개념노드(node) : 트리의 구성요소루트(root) : 부모가 없는 노드 서브트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리단말노드(terminal node) : 자식이 없는 노드비단말노드 : 적어도 하나의 자식을 가지는 노드레벨(level) : 트리의 각층의 번호높이(height) : 트리의 최대 레벨차수(degree) : 노드가 가지고 있는 자식 노드의 개수8.2 이진 트리 소개이진트리의 정의모든 노드가 2개의 서브 트리를 가지고 있는 트리서브트리는 공집합 일 수 있따.이진트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수가 2이하이진트리의 성질n개의 노드를 가진 이진트리 n-1의 간선을 가짐높이가 h인 이진트리의 경우 최소 h개의..

01. 히프 트리에서 노드가 삭제되는 위치는 어디 인가?→ (1) 루트 02. 히프를 배열로 표현할 수 있는 이유는 무엇인가?→ (1) 완전 이진 트리이기 때문에 03. 히프 연산 중에서 하나의 노드가 삽입되거나 삭제되는 시간은 무엇에 비례하는가?→ (2) 트리의 높이  04. 다음 중 히프 정렬이 특히 유용하게 사용될 수 있는 경우는?→ (1) 데이터 100개 중에서 오름차순으로 20개만 뽑고자 할때 05. 최소 히프에서 가장 작은 데이터가 있는 노드는?→ (2) 첫 번째 노드(루트 노드)  06. 최소 히프에서 2번쨰로 작은 데이터가 있는 노드는?→ 2번 노드와 3번 노드 중 더 작은 값을 가지고 있는 노드 07. 10개의 데이터를 저장하고 있는 히프트리의 높이는?→ log2 10 = 4 08.참고 ..

9.1 우선순위 큐 추상 데이터 타입자료구조삭제되는 요소스택가장 최근에 들어온 데이터큐 가장 먼저 들어온 데이터우선순위 큐가장 우선순위가 높은 데이터 우선순위 큐는 배열, 연결 리스트 등의 여러가지 방법으로 구현이 가능한데, 가장 효율적인 구조는 히프 heap 9.2 우선순위 큐의 구현 방법배열을 사용하는 방법*정렬이 되어 있지 않는 경우- 삽입: 배열의 맨 끝에 새로운 요소 추가 ( 시간 복잡도 : O(1) ) - 삭제: 가장 우선 순위가 높은 요소 찾기 (정렬이 안 되어 있으므로 처음부터 끝까지 모든 요소들을 스캔해야함) ( 시간 복잡도 : O(n) )             → 요소가 삭제된 다음, 뒤에 있는 요소들을 앞으로 이동   *정렬이 되어 있는 경우- 삽입: 다른 요소와 값을 비교하여 적절한..

01. 다음 중 NULL pointer가 존재 하지 않는 구조는?→ (2) 원형 연결 리스트    원형 연결리스트에서는 마지막 노드가 첫번째 노드를 가리키므ㄹ, null포인트가 존재하지 않는다. 02. 리스트의 n번째 요소를 가장 빠르게 찾을 수 있는 구현 방법은 무엇인가?→ (1) 배열    배열에서는 인덱스 n번째에 바로 접근 가능하므로, 시간복잡도 O(1)로 가장 빠르다. 03. 단순 연결 리스트에서 포인터 last가 마지막 노드를 가리킨다고 할 떄 다음 수식 중, 참인 것은?→ (3) last->link == NULL    04. 단순 연결 리스트의 노드들을 포인터 p로 방문하고자 한다. 현재 p가 가리키는 노드에서 다음노드로 가려면 어떤 코드를 사용해야하는가?→ (c) p=p->link;    ..

리스트 객체 : n개의 element형으로 구성된 순서 있는 모임연산 : insert(list, pos, item) : pos 위치에 요소를 추가insert_last(list, item) : 맨 끝에 요소를 추가insert_first(list, item) : 맨 처음에 요소를 추가delete(list, pos) : pos 위치의 요소를 제거clear(list) : list의 모든 요소를 제거get_entry(list, pos) : pos위치의 요소를 반환get_length(list) : list의 길이를 구함is_empty(list) : list가 비었는지 검사is_full(list) : list가 꽉찼는지를 검사print_list : list의 모든 요소를 표시 리스트의 구현배열구현이 간단하고 속도가 ..

1. 스택에서 삽입 작업이 발생하면 top의 값은 어떻게 변경되는가?→ (4) top = top+1 2. 문자 A,B,C,D,E를 스택에 넣었다가 다시 꺼내어 출력하면 어떻게 되는가?→ (2) E, D, C, B, A3. 10,20,30,40,50을 스택에 넣었다가 3개의 항목을 삭제하였다. 남아있는 항목은?→ 10, 204. 배열로 구현된 스택에서 top가 3이면 현재 스택에 저장된 요소들의 개수는?→ (4) 4: 배열[0]부터 배열[3]까지 요소가 저장되어 있으므로 4개이다.5. 다음 중 배열로 구현된 스택에서 공백 상태에 해당하는 조건은?→ 공백: (1) top == -1, 포화 : (3) top == (MAX_STACK_SIZE-1)6. 스택에 항목들을 삽입하고 사ㅏㄱ제하는 연산은 시간 복잡도가 ..

1. Stack?스택은 컴퓨터 과학에서 사용되는 중요한 자료 구조 중 하나.스택은 데이터를 저장하고 검색하는데 사용되며, 주로 "Last In First Out" (LIFO) 원칙을 따름→ 가장 최근에 추가된 항목이 가장 먼저 제거 2. Stack 구성 요소데이터 요소: 스택에 저장되는 각 항목 또는 데이터 요소맥위(TOP): 스택의 맨 위에 위치한 데이터 요소를 가리키는 포인터 3. Stack 기본 동작Push : 스택에 데이터를 추가하는 작업. 새로운 항목은 스택의 맨 위에 쌓이게 됨Pop : 스택에서 가장 위에 있는 데이터를 제거하는 작업. 스택의 맨 위 항목이 제거 됨Peek ( or Top) : 스택의 맨위에 있는 데이터를 확인하지만 제거는 하지 않음isEmpty : 스택이 비어있는지 여부를 ..